Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel (Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel.pdf), страница 7

Because failures are acceptable with small probability, it suffices to executea single phase of the Itai–Rodeh algorithm: each process randomly selects a name from therange [0..U ) and verifies, by circulating a token, if its name is minimal. Smaller processesremover token, so if a process receives its own token (hopcount N ) it becomes a leader. Byincreasing U the probability that the minimum is not unique (a situation that would lead tothe selection of more than one leader) is made arbitrarily small. The message complexity isat most N 2 because each token makes at most N steps.In its simplest form, this algorithm terminates only in the leader(s); Kees van Kemenadedemonstrated how the leader(s) can process-terminate the other processes, still within N 2messages (worst-case).

Each token (as long as it survives) accumulates the number of hopsfrom its initiator to the next process with the same name. When a process becomes leaderand learns that the next process with the same name is h hops away, it sends a terminationsignal for h − 1 hops. These hops do not push the message complexity over N 2 , because thetokens of the next h − 1 processes were not fully propagated.(The simpler strategy of sending a termination signal to the next leader, i.e., over h hops,generates N 2 + N messages in the case all processes draw the same name.)Exercise 9.12.

The processes execute input collection as in Theorem 9.6; process p obtainsa sequence seqp of names, consisting of an enumeration of the names on the ring, starting atp. Because the distribution of identities is non-periodic, the N sequences are different; theunique process whose string is lexicographically maximal becomes elected. (For p this is thecase if and only if seqp is maximal among the cyclic shifts of seqp .)Exercise 9.13.

Assuming such an algorithm exists, it will generate a finite computation Con the small ring on the left at the end of which one process, a say, terminates as a leader. Letthe maximal length of the trace of any message received in C be K, and the largest numberof random bits used by any process.ac a b cu au leaderb uu u PbPuPuPuJa Q cuJQ auJQleaderJuuQu leadercbThe steps taken in C can occur in processes in a larger ring, as depicted on the right, if itcontains a pattern of length K +1+3 labeled with the repeated pattern a, b, c, . .

.. Moreover,each process in this segment must have the same first L random bits as the correspondingprocess on the small ring. The first K processes execute a strict prefix of the steps taken bytheir counterpart in the small ring, but the last 3 + 1 processes simulate the entire sequenceof steps, implying that two processes labeled a terminate as a leader. The probability thatthis happens is at least 2−(K+3+1).L .A very large ring may contain sufficiently many segments as labeled above so as to makethe probability of error arbitrarily large, and have the name d at one place in the ring to make23it non-periodic.

This shows that erroneous behavior of the algorithm is extremely likely, evenin non-periodic rings.Exercise 9.14. The solution performs input collection and can therefore be used to evaluate any cyclic function; it is based on Itai and Rodeh’s algorithm to evaluate the ring size(Algorithm 9.5).In a test message of Algorithm 9.5 a process includes its input; whenever a process receivesa message with hop count h it learns the input of the process h hops back in the ring.

Whenthe algorithm terminates (with common value e of the est variables), each process knows theinputs of the e processes preceding it and evaluates g on this string.With high probability (as specified in Theorem 9.15) e equals N , and in this case theresult equals the desired value of g.Exercise 9.15. It is not possible to use Safra’s algorithm, because this algorithm pre-assumesthat a leader (the process named p0 in Algorithm 8.7) is available.Neither can any other termination detection algorithm be used; it would turn Algorithm 9.5 into a process terminating algorithm, but such an algorithm does not exist byTheorem 9.12.24Chapter 10: SnapshotsExercise 10.1.

If S ∗ is not meaningful there exist p and q and corresponding send/receiveevents s and r such that ap ≺p s and r ≺q aq , which implies ap ≺ aq , so ap 6k aq .Next assume for some p and q, ap ≺ aq ; that is, there exists a causal chain from ap toaq . As ap and aq internal but in different processes, the chain contains at least one evente in p following ap , and one event f in q preceding aq . The cut defined by the snapshotincludes f but not e, while e ≺ f ; hence the cut is not consistent, and S ∗ is not meaningfulby Theorem 10.5.Exercise 10.3.

The meaningfulness of the snapshot is not guaranteed at all, but by carefuluse of colors meaningless snapshots are recognized and rejected. The snapshot shows a terminated configuration if (upon return of the token to p0 ) mcp0 + q = 0, but this allows callingAnnounce only if in addition c = white and color p0 = white.Let m be a postshot message sent by p to q, which is received preshot.

The receipt ofthe message colors q black, thus causing q to invalidate the snapshot by coloring the tokenblack as well. Because the receipt of any message colors q black, meaningful snapshots may berejected as well; but termination implies that a terminated snapshot is eventually computedand not rejected.25Chapter 12: Synchrony in Networks√Exercise 12.1. If m denotes the contents of the message, the sender computes r = d me√and s = r2 − m; observe r ≤ m + 1 and s ≤ 2r. The sender sends a h start i message in,say, pulse i and h defr i and h defs i messages in pulses i + r and i + s, respectively.The receiver counts the number of pulses between the receipt of the h start i and theh defr i and h defs i messages, thus finding r and s, and “decodes” the message by setting mto r2 − s.Needless to say, this idea can be generalized to a protocol that transmits the message inO(m1/k ) time by sending k + 1 small messages.Exercise 12.2.

Yes, and the proof is similar. The ith process in the segment of the largering goes through the same sequence of states as the corresponding process in the small ring,but up to the ith configuration only.Exercise 12.3. Assume p receives a j-message from q during pulse i; let σ and τ be the timeof sending and receipt of the message. As the message is received during pulse i,)2iµ ≤ CLOCK (τp ≤ 2(i + 1)µ.As the message delay is strictly bounded by µ,2iµ − µ < CLOCK (σ)p ≤ 2(i + 1)µ.As the clocks of neighbors differ by less than µ,2iµ − 2µ < CLOCK (σ)q < 2(i + 1)µ + µ.By the algorithm, the message is sent when CLOCK q = 2jµ, so2iµ − 2µ < 2jµ < 2(i + 1)µ + µ,which implies i ≤ j ≤ i + 1.Exercise 12.4.

The time between sending the h start i message and sending an i-messageis exactly 2iµ. Each of the messages incurs a delay of at least 0 but less than µ, so the timebetween the receipt of these messages is between 2iµ − µ and 2iµ + µ (exclusive).Exercise 12.6. In all three cases the message is propagated through a suitably chosenspanning tree.The N -Clique: In the flooding algorithm for the clique, the initiator sends a message to itsN − 1 neighbors in the first pulse, which completes the flooding.

The message complexity isN − 1 because every process other than the initiator receives the message exactly once.The n × n-Torus: In the torus, the message is sent upwards with a hop counter for n − 1 steps,so every process in the initiator’s column (except the initiator itself) receives the messageexactly once.

Each process in this column (that is, the initiator and every process receivinga message from down) forwards the message to the right through its row, again with a hopcounter and for n − 1 steps. Here every process not in the initiator’s column receives themessages exactly once and from the left. Again, every process except the initiator receivesthe message exactly once.26The last process to receive the message is in the row below and the column left of theinitiator; in the (n − 1)th pulse the message receives this row, and only in the 2(n − 1)th pulsethe message is propagated to the end of the row.The number of pulses can be reduced to 2bn/2c by starting upwards and downwardsfrom the initiator until the messages almost meet, and serve each row also by sending in twodirections.