Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 5

The idea is that each process sends its identieraround the ring when a node receives an incoming identier, it compares that identier toits own. If the incoming identier is greater than its own, it keeps passing the identierif it's less than its own, it discards the incoming identier and if it's equal to its own, theprocess declares itself the leader.

Intuitively, it seems clear that the process with the largestID will be the one that outputs a leader message. In order to make this intuition precise, wegive a more careful description of the system.The message alphabet M consists of the UID's plus the special message leader .The state set state (i) consists of the following components.own , of type UID, initially i's UIDsend , of type UID or null , initially i's UIDstatus , with values in funknown chosen reported g, initially unknownThe start state start (i) is dened by the initializations above.The messages function msgs (i) is dened as follows.

Send message m, a UID, to clockwiseneighbor exactly if m is the current value of send . Send leader to dummy node exactly ifstatus = chosen .The transition function is dened by the following pseudo-code.Suppose new message is m.send := nullIf status = chosen then status := reportedCase:m > own thensend := mm = own thenstatus := chosensend := nullelse no-opEndcaseAlthough the description is in a fairly convenient programming-language style, note thatit has a direct translation into a state machine (e.g., each state consists of a value for eachof the variables). We do not, in general, place restrictions on the amount of computationneeded to go from one state to another.

Also note the relative scarcity of ow of control22statements. This phenomenon is pretty typical for distributed algorithms. The presence ofsuch statements would make the translation from program to state machine less transparent.How do we go about proving that the algorithm is correct? Correctness means thatexactly one process ever does leader output. Let imax denote the index (where indices arearranged consecutively around the ring) of the processor with the maximum UID. It sucesto show that (1) imax does a leader output at round n + 1, and (2) no other processor everdoes such an output.

We prove these properties, respectively, in the following two lemmas.Lemma 2 Node imax outputs leader message at round n + 1.Proof: Let vmax be the own value of imax . Note that own values never change (by thecode), that they are all distinct (by assumption), and that imax has the largest (by denitionof imax ).

By the code, it suces to show that after n rounds,status (imax ) = chosen :This can be proved (as things of this sort are typically proved) by induction on the numberof computation steps, here the number of rounds. We need to strengthen the statement tobe able to prove it by induction we make the following assertion.For 0 r n ; 1 after r rounds send (imax + r) = vmax(Addition is modulo n.) In words, the assertion is that the maximum value appears at theposition r away from imax . Now this assertion is straightforward to prove by induction.The key step is that every node other than imax admits the maximum value into its sendcomponent, since vmax is greater than all the other values.Lemma 3 No process other than imax ever sends a leader message.It suces to show that all other processes always have status = unknown .

Again, ithelps to have an invariant. Let a b) denote the set of positions fa a + 1 : : : b ; 1g, whereaddition is modulo n. The following invariant asserts that only the maximum value appearbetween the maximum and the owner in the ring.If i 6= imax and j 2 imax i) then own (i) 6= send (j ) :Again, it is straightforward to prove the assertion by induction (the key step is that a nonmaximum value does not get past the maximum). Obviously, we use the fact that vmax isgreater than all the others.Termination: As written, this algorithm never terminates, in the sense of all the processorsreaching some designated nal state. We could augment the model to include the concept23of a nal state.

For this algorithm, to have everyone terminate, we could have the electedleader start a report message around the ring, and anyone who receives it can halt.Note that nal states do not play the same role, i.e., that of accepting state for distributedalgorithms as they do for nite-state automata | normally, no notion of acceptance is usedhere.Complexity analysis: The time complexity is n + 1 rounds, for a ring of size n, until aleader is announced. The communication complexity is O(n2) messages.246.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchSeptember 15, 1992Lecture 22.1 Leader Election on a Ring (cont.)Last time we considered the LeLann/Chang-Roberts algorithm. We showed that its timecomplexity is n+1 time units (rounds), and its communication complexity is O(n2) messages.The presentation of the algorithm was made fairly formally, and the proofs were sketched.Today we shall use less formal descriptions of three other algorithms.2.1.1 Algorithm 2: Hirshberg-SinclairThe time complexity of the LCR algorithm is ne.

The number of messages, however,looks excessive. The rst algorithm to reduce the worst-case complexity to O(n log n) wasthat of Hirshberg-Sinclair. Again, we assume that the ring size is unknown, but now weuse bidirectional communication. As in LCR, this algorithm elects the process with themaximum UID.The idea is that every process, instead of sending messages all the way around the ringas in the LCR algorithm, will send messages that \turn around" and come back to theoriginating process. The algorithm proceeds as follows.Each process sends out messages (in both directions) that go distances that aresuccessively larger powers of 2 and then return to their origin (see Figure 2.1).When UID vi is sent out by process i, other processes on vi's path compare vi totheir own UID. For such a process j whose UID is vj , there are two possibilities.If vi < vj , then rather than pass along the original message, j sends back amessage to i telling i to stop initiating messages.

Otherwise, vi > vj . In thatcase, j relays vi, and since j can deduce that it cannot win, it will not initiate anynew messages. Finally, if a process receives its own message before that messagehas \turned around", then that process is the winner.25124-d-d-d124Figure 2.1: Successive message-sends in the Hirshberg-Sinclair algorithmAnalysis.

A process initiates a message along a path of length 2i only if it has not beendefeated by another process within distance 2i;1 in either direction along the ring. Thismeans that within any group of 2i;1 + 1 consecutive processes along the ring, at most onewill go on to initiate messages along paths of length 2i. This can be used to show that atmostn 2i;1 + 1in total will initiate messages along paths of length 2i.The total number of messages sent out is then bounded bynnni4 (1 n) + (2 2 ) + (4 3 ) + : : : (2 2i;1 + 1 ) + : : : :The factor of 4 in this expression is derived from the fact that each round of messagesending for a given process occurs in both directions | clockwise and counterclockwise |and that each outgoing message must turn around and return. (For example, in the rstround of messages, each process sends out two messages | one in each direction | a distanceof one each and then each outgoing message returns a distance of one, for a net total of fourmessages sent.) Each term in the large parenthesized expression is the number of messagessent out around the ring at a given pass (counting only messages sent in one direction, andalong the outgoing path).

Thus, the rst term, (1 n), indicates that all n processes sendout messages for an outgoing distance of 1.Each term in the large parenthesized expression is less than or equal to 2n, and there areat most 1 + dlog ne terms in the expression, so the total number of messages is O(n log n),with a constant factor of approximately 8.The time complexity for this algorithm is just O(n), as can be seen by considering thetime taken for the eventual winner. The winning process will send out messages that take26time 2, 4, 8, and so forth to go out and return and it will nish after sending out thedlog neth message.

If n is an exact power of 2, then the time taken by the winning processis approximately 3n, and if not the time taken is at most 5n.2.1.2 Counterexample AlgorithmsNow we consider the question of whether it is possible to elect a leader with fewer !(n log n)messages. The answer to this problem, as we shall demonstrate shortly with an impossibilityresult, is negative. That result, however, is valid only in a restricted model (comparisonbased protocols, which are dened in Denition 1 below).

For the general case, the followingcounterexample algorithms can be used to show that no such impossibility result can beproved. We use the term \counterexample algorithm" for an algorithm that isn't interestingby itself, e.g., neither practical nor particularly elegant from a mathematical viewpoint.However, it serves to show that an impossibility result cannot be proved.Algorithm 3: We now suppose that the model is simpler, with only little uncertainty.Specically, we assume the following.n is known to all processes.The communication is unidirectional.The ID's are positive integers.All processes start algorithm at the same time.In this setting, the following simple algorithm works:1In the rst n rounds, only a message marked with UID \1" can travel around.If a processor with UID \1"does exists, then this message is relayed throughoutthe ring.

Otherwise, the rst n rounds are idle. In general, the rounds in therange kn + 1 kn + 2 : : : (k + 1)n are reserved for UID k + 1. Thus, the minimalUID eventually gets all the way around, which causes its originating process toget distinguished.If it is desired to have the maximum elected instead of the minimum, simply let the minimumsend a special message around at the end to determine the maximum.1Actually, algorithm 3 isn't entirely a counterexample algorithm { it has really been used in some systems.27The nice property of the algorithm is that the total number of messages is n.

Unfortunately, the time is about n M , where M is the value of the minimum ID this value isunbounded for a xed size ring. Note how heavily this algorithm uses the synchrony, quitedierently from the rst two algorithms.Algorithm 4: Frederickson-Lynch. We now present an algorithm that achieves theO(n) message bound in the case of unknown ring size (all other assumptions as for algorithm2). The cost is time complexity which is even worse than algorithm 3 (!), specically O(n2M ),where M is the minimum UID.