Huang's Algorithm
Encyclopedia
Huang's algorithm is an algorithm
for detecting termination
in a distributed system. The algorithm was proposed by Shing-Tsaan Huang in 1989 in the Journal of Computers.
Termination occurs when all processes in the distributed system become idle and there are no computational messages in transit.
Some weaknesses to Huang's algorithm are that it is unable to detect termination if a message is lost in transit or if a process fails while in an active state.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for detecting termination
Termination analysis
In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate. Because the halting problem is undecidable, termination analysis cannot work correctly in all cases. The aim is to find the answer...
in a distributed system. The algorithm was proposed by Shing-Tsaan Huang in 1989 in the Journal of Computers.
Termination detection
The basis of termination detection is in the concept of a distributed system process' state. At any time, a process in a distributed system is either in an active state or in an idle state. An active process may become idle at any time but an idle process may only become active again upon receiving a computational message.Termination occurs when all processes in the distributed system become idle and there are no computational messages in transit.
Algorithm
Huang's algorithm can be described by the following:- Initially all processes are idle.
- A distributed task is started by a process sending a computational message to another process. This initial process to send the message is the "controlling agent".
- The initial weight of the controlling agent is
(usually 1).
- The initial weight of the controlling agent is
- The following rules are applied throughout the computation:
- A process sending a message splits its current weight between itself and the message.
- A process receiving a message adds the weight of the message to itself.
- Upon becoming idle, a process sends a message containing its entire weight back to the controlling agent.
- Termination occurs when the controlling agent has a weight of
and is in the idle state.
Some weaknesses to Huang's algorithm are that it is unable to detect termination if a message is lost in transit or if a process fails while in an active state.