×

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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68N99 Theory of software
68W99 Algorithms in computer science
68N25 Theory of operating systems

Citations:

Zbl 0638.00039