Attiya, Hagit Constructing efficient election algorithms from efficient traversal algorithms. (English) Zbl 0644.68061 Distributed algorithms, Proc. 2nd Int. Workshop, Amsterdam/Neth. 1987, Lect. Notes Comput. Sci. 312, 337-344 (1988). [For the entire collection see Zbl 0638.00039.] Traversal and election are two fundamental tasks in distributed systems. A traversal algorithm enables a processor to send a message from node to node around the system. An election algorithm ends with some processor in a distinguished state (the leader). Traversal is a task which is executed locally, while an election algorithm requires global coordination among processors. In this paper, we present a general technique for using traversal algorithms to construct election algorithms. The algorithm simplifies and improves the previously known technique of Korach, Kutten and Moran. Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 68N99 Theory of software 68W99 Algorithms in computer science 68N25 Theory of operating systems Keywords:network of asynchronous processors; distributed systems; traversal algorithms; election algorithms Citations:Zbl 0638.00039 PDFBibTeX XML