Huang's algorithm

Huang's algorithm

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 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 becomes 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 w (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.
** Termination occurs when the controlling agent has a weight of w 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

* Dijkstra-Scholten algorithm


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Huang Daren — (Traditional Chinese: 黃達人, Simplified Chinese: 黄达人), is a Chinese mathematician and the current president of Sun Yat sen University [ [http://www.chinavitae.org/biography/Huang Daren ChinaVitae Huang Daren] ] .IntroductionHuang was born in Apr… …   Wikipedia

  • Dijkstra–Scholten algorithm — The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and C. S. Scholten) is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980. First, let us consider the case of …   Wikipedia

  • Dijkstra-Scholten algorithm — The Dijkstra Scholten algorithm is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980.First, let us consider the case of a simple process graph which is a tree. A… …   Wikipedia

  • Xuedong Huang — (also known as XD, Simplified Chinese: 黄学东, b. October 20, 1962) is the key person behind Microsoft s speech recognition technologies. BackgroundHuang grew up in Hunan, China and became a US citizen in 1995.CareerEducationIn 1978, Huang entered… …   Wikipedia

  • Hilbert-Huang transform — The Hilbert Huang Transform (HHT) is a way to decompose a signal into so called intrinsic mode functions (IMF), and obtain instantaneous frequency data. It is designed to work well for data that are nonstationary and nonlinear. In contrast to… …   Wikipedia

  • Pitch detection algorithm — A pitch detection algorithm (PDA) is an algorithm designed to estimate the pitch or fundamental frequency of a quasiperiodic or virtually periodic signal, usually a digital recording of speech or a musical note or tone. This can be done in the… …   Wikipedia

  • Junction tree algorithm — The junction tree algorithm is a method used in machine learning for exact marginalization in general graphs. In essence, it entails performing belief propagation on a modified graph called a junction tree. The basic premise is to eliminate… …   Wikipedia

  • Cooperative optimization — is a global optimization method invented by chinese mathematician Xiao Fei Huang, that can solve real world NP hard optimization problems (up to millions of variables) with outstanding performances and unprecedented speeds. It knows whether a… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Demosaicing — A demosaicing algorithm is a digital image process used to reconstruct a full color image from the incomplete color samples output from an image sensor overlaid with a color filter array (CFA). Also known as CFA interpolation or color… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”