Editing Distributed computing (section)

===[[Leader election|Election]]===
''Coordinator election'' (or ''leader election'') is the process of designating a single [[Process (computing)|process]] as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are either unaware which node will serve as the "coordinator" (or leader) of the task, or unable to communicate with the current coordinator. After a coordinator election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task coordinator.<ref name="HaloiApache15">{{cite book |url=https://books.google.com/books?id=Ym9uBgAAQBAJ&pg=PA100 |title=Apache ZooKeeper Essentials |author=Haloi, S. |publisher=Packt Publishing Ltd |pages=100–101 |year=2015 |isbn=9781784398323 |access-date=2018-07-20 |archive-date=2023-01-20 |archive-url=https://web.archive.org/web/20230120182456/https://books.google.com/books?id=Ym9uBgAAQBAJ&pg=PA100 |url-status=live }}</ref>

The network nodes communicate among themselves in order to decide which of them will get into the "coordinator" state. For that, they need some method in order to break the symmetry among them. For example, if each node has unique and comparable identities, then the nodes can compare their identities, and decide that the node with the highest identity is the coordinator.<ref name="HaloiApache15" />

The definition of this problem is often attributed to [[Gérard Le Lann|LeLann]], who formalized it as a method to create a new token in a token [[ring network]] in which the token has been lost.<ref>{{Cite journal|last=LeLann|first=G.|year=1977|title=Distributed systems - toward a formal approach|journal=Information Processing|volume=77|pages=155·160|via=Elsevier}}</ref>

Coordinator election algorithms are designed to be economical in terms of total [[byte]]s transmitted, and time. The algorithm suggested by Gallager, Humblet, and Spira<ref>{{cite journal|date=January 1983|title=A Distributed Algorithm for Minimum-Weight Spanning Trees|url=http://www.apposite-tech.com/blog/wp-content/uploads/2017/09/p66-gallager.pdf |archive-url=https://web.archive.org/web/20170926040957/http://www.apposite-tech.com/blog/wp-content/uploads/2017/09/p66-gallager.pdf |archive-date=2017-09-26 |url-status=live|journal=ACM Transactions on Programming Languages and Systems|volume=5|issue=1|pages=66–77|doi=10.1145/357195.357200|author=[[Robert G. Gallager|R. G. Gallager]], P. A. Humblet, and P. M. Spira|s2cid=2758285}}</ref> for general undirected graphs has had a strong impact on the design of distributed algorithms in general, and won the [[Dijkstra Prize]] for an influential paper in distributed computing.

Many other algorithms were suggested for different kinds of network [[Graph (discrete mathematics)|graph]]s, such as undirected rings, unidirectional rings, complete graphs, grids, directed Euler graphs, and others. A general method that decouples the issue of the graph family from the design of the coordinator election algorithm was suggested by Korach, Kutten, and Moran.<ref>{{cite journal|year=1990|title=A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms|journal=ACM Transactions on Programming Languages and Systems|volume=12|issue=1|pages=84–101|doi=10.1145/77606.77610|first1=Ephraim|last1=Korach|first2=Shay|last2=Kutten|first3=Shlomo|last3=Moran|author-link2=Shay Kutten|author-link3=Shlomo Moran|url=https://www.cs.technion.ac.il/~moran/r/PS/kkm.pdf |archive-url=https://web.archive.org/web/20070418150944/http://www.cs.technion.ac.il/~moran/r/PS/kkm.pdf |archive-date=2007-04-18 |url-status=live|citeseerx=10.1.1.139.7342|s2cid=9175968}}</ref>

In order to perform coordination, distributed systems employ the concept of coordinators. The coordinator election problem is to choose a process from among a group of processes on different processors in a distributed system to act as the central coordinator. Several central coordinator election algorithms exist.<ref>{{cite web|url=http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html|title=Distributed Algorithms|last=Hamilton|first=Howard|access-date=2013-03-03|archive-date=2012-11-24|archive-url=https://web.archive.org/web/20121124002402/http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html|url-status=live}}</ref>