HS algorithm

HS algorithm

The HS Algorithm is named after Dan Hirschberg and J. B. Sinclair. It is a distributed algorithm designed for the Leader Election problem in a Synchronous Ring.

The algorithm requires the use of unique IDs (UID) for each process. The algorithm works in phases and sends its UID out in both directions. The message goes out a distance of 2Phase Number hops and then the message heads back to the originating process. While the messages are heading "out" each receiving process will compare the incoming UID to its own. If the UID is greater than its own UID then it will continue the message on. Otherwise if the UID is less than its own UID, it will not pass the information on. At the end of a phase, a process can determine if it will send out messages in the next round by if it received both of its incoming messages. Phases continue until a process receives both of its out messages, from both of its neighbors. At this time the process knows it is the largest UID in the ring and declares itself the leader.

References

* Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers, Inc. (1996) pp. 31-35.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Algorithm design — is a specific method to create a mathematical process in solving problems. Applied algorithm design is algorithm engineering.Algorithm design is identified and incorporated into many solution theories of operation research, such as dynamic… …   Wikipedia

  • Algorithm engineering — is a combination of theoretical algorithm design with real world data. By taking an algorithm and combining it with a hardware device connected to the real world, you are able to more accurately verify and validate the algorithm results and… …   Wikipedia

  • algorithm — UK US /ˈælgərɪðəm/ noun [C] IT ► a set of mathematical instructions that must be followed in a fixed order, and that, especially if given to a computer, will help to calculate an answer to a mathematical problem: a computer/mathematical/search… …   Financial and business terms

  • algorithm — n. a precise rule (or set of rules) specifying how to solve some problem; a set of procedures guaranteed to find the solution to a problem. Syn: algorithmic rule, algorithmic program [WordNet 1.5 +PJC] …   The Collaborative International Dictionary of English

  • algorithm — [al′gə rith΄əm] n. [altered (after ARITHMETIC) < ALGORISM] 1. Math. a) any systematic method of solving a certain kind of problem b) the repetitive calculations used in finding the greatest common divisor of two numbers: called in full… …   English World dictionary

  • Algorithm Builder — ist eine Entwicklungsumgebung für AVR Mikrocontroller, basierend auf einer graphischen Makro Assembler Sprache. Der gesamte Programmablauf wird in graphischer Form als Flussdiagramm eingegeben. Es lässt sich mit einzelnen Anweisungen direkt auf… …   Deutsch Wikipedia

  • Algorithm —   [engl.], Algorithmus.   …   Universal-Lexikon

  • algorithm — (n.) 1690s, from Fr. algorithme, refashioned (under mistaken connection with Gk. arithmos number ) from O.Fr. algorisme the Arabic numeral system (13c.), from M.L. algorismus, a mangled transliteration of Arabic al Khwarizmi native of Khwarazm,… …   Etymology dictionary

  • algorithm — ► NOUN ▪ a process or set of rules used in calculations or other problem solving operations. DERIVATIVES algorithmic adjective. ORIGIN Latin algorismus, from an Arabic word meaning the man of Kw rizm , referring to a 9th century mathematician …   English terms dictionary

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

Share the article and excerpts

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