Huang's algorithm: Difference between revisions
Content deleted Content added
→top: Fix name of journal, from possible vandalism |
|||
| (7 intermediate revisions by 7 users not shown) | |||
| Line 1: | Line 1: | ||
{{ |
{{More citations needed|date=February 2022}} |
||
'''Huang's algorithm''' is an [[algorithm]] for detecting [[Termination analysis|termination]] in a [[distributed system]]. The algorithm was proposed by [[Shing-Tsaan Huang]] in 1989 in |
'''Huang's algorithm''' is an [[algorithm]] for detecting [[Termination analysis|termination]] in a [[distributed system]]. The algorithm was proposed by [[Shing-Tsaan Huang]] in 1989 in ''[[Information Processing Letters]]''.<ref>{{cite journal |last1=Huang |first1=Shing-Tsaan |author1-link=Shing-Tsaan Huang |title=Termination detection by using distributed snapshots |journal=Information Processing Letters |volume=32 |issue=3 |pages=113–119 |year=1989 |url=https://www.sciencedirect.com/science/article/abs/pii/0020019089900100 |doi=10.1016/0020-0190(89)90010-0 }}</ref> |
||
==Termination detection== |
==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. |
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. |
Termination occurs when all processes in the distributed system become idle and there are no computational messages in transit. |
||
| Line 15: | Line 15: | ||
** A process sending a message splits its current weight between itself and the message. |
** 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. |
** 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 and it goes idle. |
|||
** Termination occurs when the controlling agent has a weight of <math>w</math> and is in the idle state. |
** Termination occurs when the controlling agent has a weight of <math>w</math> and is in the idle state. |
||
| Line 20: | Line 21: | ||
==See also== |
==See also== |
||
* [[ |
* [[Dijkstra–Scholten algorithm]] |
||
==Notes== |
|||
{{reflist}} |
|||
{{DEFAULTSORT:Huang's Algorithm}} |
{{DEFAULTSORT:Huang's Algorithm}} |
||
Latest revision as of 03:34, 13 September 2024
 | This article needs additional citations for verification. (February 2022) |
Huang's algorithm is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Shing-Tsaan Huang in 1989 in Information Processing Letters.[1]
Termination detection
[edit]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
[edit]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 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 and it goes idle.
- 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.
See also
[edit]Notes
[edit]- ^ Huang, Shing-Tsaan (1989). "Termination detection by using distributed snapshots". Information Processing Letters. 32 (3): 113–119. doi:10.1016/0020-0190(89)90010-0.