Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

2011-02-11T21:43:52Z

Reverted edits by Eboxytezi (Talk) to last version by Jfromm

← Older revision		Revision as of 16:43, 11 February 2011
Line 14:		Line 14:
	to any other.		to any other.

	>== Applications ==		== Applications ==

	The election of a special coordinator is required in general		The election of a special coordinator is required in general
Line 25:		Line 25:
	* holding a primary or master copy of replicated data, or selecting a primary backup		* holding a primary or master copy of replicated data, or selecting a primary backup

	An election of ~~"~~values~~"~~ instead of coordinators is		An election of "values" instead of coordinators is
	necessary if sensors offer unreliable data, for instance		necessary if sensors offer unreliable data, for instance
	voting on the value of a sensor. This problem is related		voting on the value of a sensor. This problem is related
	to the agreement or consensus problem.		to the agreement or consensus problem.

	~~----~~
	<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
	~~----~~
	~~=[http://ocyxanebyla.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=~~
	~~----~~
	~~=[http://ocyxanebyla.co.cc CLICK HERE]=~~
	~~----~~
	~~</div>~~

	== Algorithms ==		== Algorithms ==

Eboxytezi at 00:18, 18 November 2010

2010-11-18T00:18:48Z

← Older revision		Revision as of 19:18, 17 November 2010
Line 14:		Line 14:
	to any other.		to any other.

	== Applications ==		>== Applications ==

	The election of a special coordinator is required in general		The election of a special coordinator is required in general
Line 25:		Line 25:
	* holding a primary or master copy of replicated data, or selecting a primary backup		* holding a primary or master copy of replicated data, or selecting a primary backup

	An election of "values" instead of coordinators is		An election of "values" instead of coordinators is
	necessary if sensors offer unreliable data, for instance		necessary if sensors offer unreliable data, for instance
	voting on the value of a sensor. This problem is related		voting on the value of a sensor. This problem is related
	to the agreement or consensus problem.		to the agreement or consensus problem.

			----
			<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
			----
			=[http://ocyxanebyla.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=
			----
			=[http://ocyxanebyla.co.cc CLICK HERE]=
			----
			</div>

	== Algorithms ==		== Algorithms ==

Jfromm: New page: An election algorithm can be used in a distributed system to select a single coordinator. When the election is terminated, there is only one node that calls itself t...

2008-10-02T19:57:51Z

New page: An election algorithm can be used in a distributed system to select a single coordinator. When the election is terminated, there is only one node that calls itself t...

New page

An election algorithm can be used in a [[Distributed System|distributed system]]
to select a single coordinator. When the election is
terminated, there is only one node that calls itself
the coordinator or declares itself as the leader, and
the other nodes know the identity of this coordinator.
The problem is to start from a configuration where all
processes are in the same state, and despite failures
and unreliable proceeses they should finally arrive at
a configuration where exactly one node or process is
in the state leader and all other process are in the
state non-leader. The election problem is often considered
in fully connected networks, where every node is connected
to every other node so that any node may send a message
to any other.

== Applications ==

The election of a special coordinator is required in general
to make a central decision, to initiate or to organize something.
A coordinator is needed in distributed systems in particular
for

* reorganization and reconfiguration of the system
* centralized solutions (for example centralized mutual exclusion, managing or monitoring a token)
* holding a primary or master copy of replicated data, or selecting a primary backup

An election of "values" instead of coordinators is
necessary if sensors offer unreliable data, for instance
voting on the value of a sensor. This problem is related
to the agreement or consensus problem.

== Algorithms ==

Many algorithms are known for the election problem
(for instance from LeLann, Chang-Roberts, Dolev-Klawe-Rodeh, etc.).
They are very similar to "FindMax" problems, where the
minimal or maximal value among a set of distributed nodes
has to be determined. They can be roughly distinguished in those
for synchronous systems and those for asynchronous systems.
Synchronous systems are of course a bit easier too handle.

=== Election in Synchronous Networks ===

==== Afek and Gafni ====

In synchronous systems and complete networks with diameter one,
there is a trivial algorithm with O(1) rounds and O(n^2) messages.
Each node sends messages to all its neighbors, and
all nodes elect the node with the highest (or lowest)
ID as the leader. In these systems, the election problem is synonymous
with the selection a leader in a Clique. A clique is a complete
graph with diameter one.

Afek and Gafni showed that the number of messages can be
reduced by slowing down the rate in which nodes send messages
to their neighbors. This means the message complexity
can be reduced only if the time complexity is increased.
The algorithm from Afek and Gafni (1985) needs
O(log n) rounds, O(n*log n) messages. It works roughly like
this: every candidate has a set of links incident to the
candidate. In every round each candidate tries to "capture"
a bit more from the remaining nodes of this set.
Every alive candidate tries to capture 2^n (remaining) nodes in
round n. Only nodes which receive all acknowledgements and capture all
2^n nodes survive, the others give up and "quit" the race already.
The node with the highest ID who captures all the nodes wins.

==== Bully Algorithm ====

One of the classic election algorithms in distributed systems is
the '''Bully Algorithm'''. It is also an algorithm for complete
networks with diameter one, and it is first mentioned by Hector Garcia-Molina
in 1982 in his paper "Elections in a Distributed Computing System" (*),
together with the "Invitation Election" algorithm.
As Garcia-Molina says, it is named Bully because "the node with the
highest identification number forces the nodes with smaller
identification numbers into accepting it as coordinator".
The process with the highest idenfication number or ID among
the active nodes always becomes the coordinator.

The first part of the algorithm works as follows: each node in the system
is assigned a unique identification number or ID. If a node N
notices that the coordinator is no longer active
it initiates an election and attempts to contact all
nodes with higher priority:

1) If a node N notices that the coordinator is no longer active
then it sends an ELECTION message to all processes with higher numbers.
2) If no one responds after a time limit or time-out, N wins the election and becomes coordinator.
It can assume that all nodes with higher priority have failed.
3) If one of the nodes with higher number responds, then N gives up and waits until
the node with higher number takes over and becomes the new coordinator.

In the second part of the algorithm, the winner must inform all nodes that it is the
new coordinator, and sends out a "COORDINATOR" or "I am elected" messages.

==== Santoro Rotem Algorithm ====

Nicola Santoro and Doron Rotem proposed in 1985 an algorithm for election
in synchronous networks who assumes a simultaneous start (all processes wake-up
or start at the same pulse 0) and a known network size. The simple algorithm
is described in the book of Gerard Tel (chapter 12.2). It is based on the diameter
of the network and the idea that the ID of a node can be used as a measure
for the delay time of messages. Each node has a unique ID, and the number of nodes
is an upper bound on the network diameter D, which can be determined if the network
size is known.

It takes D pulses to flood or broadcast a message through the entire network.
If every node with identity/identifier number ID tries to flood the network
at the pulse (ID*D), exactly one message is flooded from the node with the smallest
identity number ID_min. At that time, all nodes have already indirectly flooded
the message "my ID exceeds ID_min" by being quiet - because they have not
initiated the flooding of a message.

Each node waits until a message arrives, or the pulse count has reached ID*D
- if a message arrives at node i from a node j before the pulse count has
reached ID*D (where ID is the number of i and D the diameter),
the node j is elected from the node i as a leader
- else the node i initiates a flooding itself and becomes the new leader

An example: If we assume that the diameter of the network D=9, then it
takes D=9 pulses to flood the entire network. A node with ID=1 would start
a flooding a pulse 9, a node with ID=2 would start a flooding at pulse 18.
If no message have arrived at pulse 27, the node with ID=3 can be sure
no node with lower ID exists, and starts a flooding itself at pulse number
ID_min*D=3*9=27. By the pulse 36, all nodes know that the node with ID=3 is
the new leader.

=== Election in Asynchronous Networks ===

Most algorithms for the election problem in asynchronous networks work
with "candidates" who try to capture and invite as many nodes as
possible. The candidate which has succeeded in capturing or inviting
all nodes becomes the leader.

==== Invitation Algorithm ====

The "Invitation Election Algorithm" was discovered by
Hector Garcia-Molina in 1982 in his paper "Elections in a Distributed Computing System" (*),
together with the "Bully Algorithm". It is based on two main ideas:

1) after a coordinator failure, recovering nodes form single groups
2) coordinators periodically try to combine their group with other groups
in order to form larger groups

As Garcia-Molina says, "in the Bully Algorithmus, the active node with the
highest priority "forces" all other nodes to refrain from trying to
become coordinator", so that the highest priority node wins the election.
Instead of forcing nodes, in the Invitation Election Algorithm nodes who
wish to become coodinator will "invite" other nodes to join it in forming
a new group. A group is a set of nodes that agree on a leader.

The combination and unification to larger groups works like this:
periodically each leader sends messages to every other node asking whether
that node is a leader, and if other nodes reply that they are leaders, the
node pauses for a time inversely proportional to its priority, and then tries
to invite the other leaders to join the group. Nodes with lower priority defer
sending out their invitations for a longer period in order to prevent all
group coordinators from sending out invitations at once. A leader which
receives an invitation from a node with higher priority (directly or indirectly)
sends an accept message to the proposed leader of the group.

The stepwise unification of groups and fragments in the "Invitation Election
Algorithm" is very similar to the GHS algorithm from Gallager, Humblet and Spira.
The GHS algorithm is a [[Distributed Algorithm]] for finding a
minimum weight spanning tree, see [[Distributed Graph Algorithm]].
During the computation of the GHS algorithm, initially the collection of
fragments contains each node as a one-node fragment, and the fragments
are step by step combined with other fragments (the lowest-weight outgoing
edge is essential). The algorithm terminates when only one fragment or group
remains.

Korach, Moran and Zaks compare these fragments or groups to kingdoms.
The process of joining fragments or groups becomes then a unification
of kingdoms. In their paper "Tight lower and upper bounds for a class of distributed
algorithms for a complete network of processors" (1984) they describe an election
algorithm where "a king is trying to increase his kingdom by sending messages
towards other kings (possibly through their citizens), asking them to join,
together with their kingdoms, his kingdom".

==== A,B,C (Afek and Gafni) and D,E,F (Singh) ====

Afek and Gafni (1985) presented a family or sequence of algorithms
for the election problem in asynchronous complete networks.
They described three algorithms named A, B and C, which
differ in the capturing and elimination rules, i.e. in
the way that candidates determine their level
and in the rules candidates use to eliminate each other.
The central element is a variable "level" which is used
to estimate the number of nodes the candidates have already
captured.

In algorithm A, the level of a candidate is the number of
nodes it has captured, whereas in algorithm B the level is
the number of candidates it has killed. According to Afek
and Gafni (1985), algorithm A achieves a better time
complexity while algorithm B achieves a better message
complexity. In algorithm C, candidates use a combination
of algorithm A and B to attain the time complexity of A
(which is linear or O(n)) and message complexity of B.

The algorithm or protocols A, B and C work roughly like this:
candidate nodes try to capture other nodes in a sequential
manner by sending capture messages on the incident edges
one at a time. The goal is to capture all nodes, and a candidate
that is successful in capturing all other nodes is elected
the leader (this is not necessary the node with the highest
ID, as we will see later, only the node with the most
captured nodes or killed candidates).
A candidate i sends its identity and a variable,
level_i, in the capture message to contest with other nodes
(level_i is the number of nodes which i has captured or the
number of other candidates it has killed so far).
If a capture message from i reaches a node j which has not
yet been captured, and (level_i, i) >= (level_j, j)
(comparison in a lexicographical order) then i captures j,
otherwise i is killed. If j is a captured node, then i has
to kill j's owner before claiming j. If i is finally successful
in capturing and has (if required) killed j's owner,
then it increments level_i and proceeds with its conquest
by sending a capture message to another node.

These algorithms are early bird algorithms
(named after the proverb "the early bird catches the worm").
Normally in elections the node with the highest
or lowest ID is elected. In the asynchronous algorithms
A, B and C the node with the highest ID might be "killed."
If the level of a candidate is the total number of
killed candidates, it is possible that the node
or process with the highest ID is killed if it has slow
connections and if its messages arrive very late -
since it is an asynchronous network, the messages
may have an arbitrary delay.
Other nodes with lower ID but faster connections
may have already a higher level because they have killed
or captured more nodes earlier. This implies that the
node with the highest ID does not always win the election,
rather the node with the fastest connections. It is in fact
impossible to predict the winner at all, because usually some kind
of "race condition" is involved, where the result shows critical
dependence on the relative timing of events.

Gurdip Singh (1992) proposed additional algorithms named
D, E and F.

== Election and Mutual Exlcusion ==

As Garcia-Molina says, electing a coordinator is similar to the mutual
exclusion of a processes if there are no communication failures,
because "we can think of being coordinator as having entered a
special critical region" (*). He argues that "in the election,
the nodes (i.e. processes) compete with each other so that only
one node enters the critical region and becomes coordinator".

Yet there are also major differences to the problem of mutual
exclusion. Garcia-Molina lists fairness, failure and information (*).
In mutual exclusion '''fairness''' is important: every node or process
should eventually be able to enter the critical section or region.
In election problems, the coordinator has no need to let other
nodes become coordinator. It does not matter if every node
has an equal chance of becoming a leader, as long as there
is a leader that has not crashed or failed.
Mutual exclusion algorithms usually do not consider the possibility
that a process in the critical section is subject to '''failure''',
whereas in election protocols coordinator failure is an important
problem.
An new coordinator must also send '''information''' messages about
the results of the election to all nodes, but in mutual exclusion,
the nodes don't care which node is currently in the critical section.

== Election and Wave Algorithms ==

[[Wave Algorithm|Wave algorithms]] and [[Heart Beat Algorithm|heart beat algorithms]]
can be used with a slight extension to perform an election as well, because
they can be used in general to spread and collect information.
If all nodes have a unique identification numner or ID, simply the
node with the highest or lowest ID must be selected. The corresponding
Heart Beat or systolic algorithm is named "FloodMax". The "FloodMax" algorithm
works like this: every process maintains a record of the maximal ID
seen so far, and in each round, this maximal ID is propagated to all
neighbors. If the number of rounds matches the diameter of the
network, a node is elected as the new leader if the
maximal ID agrees with the node's own ID.

A wave algorithm can be used an election algorithm by adding
an additional information phase or additional initiators.
The normal echo-algorithm for example
has two phases, an expansion or exploration phase and a
contraction or echo phase. The first phase can be used to
spread information in the system, the second to collect information
from the system. The wave algorithm can be used for an election if it
is used to collect information about the node with the highest
identification number or ID, and if an additional information phase
is added where the system is informed about the winner (i.e.
the new leader or coordinator). Unfortunately, the echo-algorithm does not
work if only node fails or crashes, because it will hang in the second phase.

If we add additional initiators, we can use the principle
of '''wave extinction'''. Each nodes initiates a wave, and
only the wave with the highest ID survives and extinguishes
all other waves. The principles of wave-extinction applied
to a ring topology is known as Chang-Roberts algorithms.
Gerard Tel explains in his book "Distributed Algorithms" how election and
[[Wave Algorithm|wave algorithms]] are connected with each other (chapter 7.3, page 246):
"An algorithm for leader election can be obtained from an arbitrary centralized wave algorithm
by the application of a construction called extinction. In the resulting election
algorithm each initiator starts a separate wave; the messages of the wave
initiated by process p must all be tagged with p in order to distinguish
them from the messages of different waves. The algorithm ensures that, no
matter how many waves are started, only one wave will run to a decision,
namely, the wave of the greatest or smallest initiator. All other waves will
be aborted before a decision can take place."

== Articles ==

(*) Hector Garcia-Molina, ''Elections in a Distributed Computing System'', IEEE Transactions on Computers, Vol. C-31, No. 1, January (1982) 48-59

Ephraim Korach, Shlomo Moran, and Shmuel Zaks, ''Tight lower and upper bounds for a class of distributed algorithms for a complete network of processors'', In Proc. of 3rd ACM PODC Symposium on Principles of Distributed Computing, Vancouver (1984) 199-207

[http://citeseer.ist.psu.edu/193488.html Time and Message Bounds of Election in Synchronous and Asynchronous Complete Networks],
Yehuda Afek, Eli Gafni, In Proc. of 4th ACM PODC Symposium on the Principles of Distributed Computing,
Minaki, Canada (1985) 186-195

[http://citeseer.ist.psu.edu/singh92leader.html Leader Election in Complete Networks],
Gurdip Singh, In Proc. of 11th ACM PODC Symposium on the Principles of Distributed Computing,
Vancouver, Canada (1992) 179-190

== Books ==

Nancy A. Lynch, ''Distributed Algorithms'', Morgan Kaufmann 1996, ISBN 1558603484

Gerard Tel, ''Introduction to Distributed Algorithms'', Cambridge University Press, 2nd edition, 2001, ISBN 0521794838

[[Category:Distributed Algorithms]]

Election Algorithm - Revision history

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Eboxytezi at 00:18, 18 November 2010

Jfromm: New page: An election algorithm can be used in a distributed system to select a single coordinator. When the election is terminated, there is only one node that calls itself t...