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

But by our assumption, turn := i is only performed once during one pass byprocess i through the trying region, a contradiction.9.2.3 Tournament AlgorithmWe now extend the basic two-process algorithm to a more general number of processes. Here,for simplicity, we assume that n is a power of 2. The basic idea is to run a tournament, usingthe 2-process strategy.In the following presentation, we take the Peterson-Fischer tournament algorithm, andrephrase it using Peterson's simpler 2-process algorithm. We remark that the originalPeterson-Fischer algorithm is quite messy (at least too messy to prove formally here).

Thecode given here seems simpler, but it still needs careful checking and proof. A disadvantageof this code as compared to the Peterson-Fischer code is that this one involves multi-writervariables, while the original protocol works with single-writer registers.Before we give the algorithm, we need some notation. For 1 i n and 1 k log nwe dene the following notions.The (i k)-competition is the number given by the high-order (log n ; k) bits of i, i.e.,icomp (i k) = k :2The (i k)-role is the (log n ; k + 1)st bit of the binary representation of i, i.e.,irole (i k ) = k mod 2 :2The (i k)-opponents is the set of numbers with the same high-order (log n ; k) bits asi, and opposite (log n ; k + 1)st bit, i.e.,opponents (i k) = fj : comp (j k ) = comp (i k) and role (j k) 6= role (i k )g :108Shared variables:level: an array indexed by 1::n] of f0 : : : log ng, initially all 0turn: a Boolean array indexed by all binary strings of length at most log n ; 1,initial state arbitraryCode for pi :** Remainder Region **try ifor k := 1 to log n dolevel (i) := kturn (comp(i k)) := role (i k )wait for 8j 2 opponents (i k) : level (j ) < k] or turn (comp (i k)) 6= role (i k)]end forcrit i** Critical Region **exit ilevel (i) := 0rem iFigure 9.3: Peterson's tournament algorithmThe code of the algorithm is given in Figure 9.3.

We only sketch the correctness argumentsfor the algorithm.Theorem 12 The tournament algorithm satises mutual exclusion.Proof Sketch: The proof follows the same ideas as for two processes. This time, we mustshow that at most one process from each subtree of a level k node reaches level k + 1 (ornishes, if k = log n). This is proven using an invariant.We think of the main loop of the algorithm unfolded. For 1 k log n, dene done k tobe the set of points in the code from right after the level k loop, until the end of C . Considerthe following invariant.8k 1 k log ni 2 done k ] =) opponents (i k) \ (wait k done k ) = or turn (comp (i k)) 6= role (i k) :109(9.3)We rst show that (9.3) implies the result: if two processes i j reach the critical sectiontogether, consider their lowest common competition (that is, minl fcomp (i l) = comp (j l)g).Suppose this competition is at level k.

Then both i and j are in done k , and so they musthave conicting settings of the role variable.The inductive proof of (9.3) is roughly as follows. Fix a process i and level number k.We need to verify the following key steps: (a) when i passes the level k test (this case iseasy), (b) an opponent setting turn , and (c) a relative setting turn (i can't, from where it is,and others can't reach there by inductive hypothesis, level k ; 1).Theorem 13 The tournament algorithm satises deadlock freedom.Proof Sketch: Deadlock freedom follows from lockout freedom, which in turn follows froma time bound.

We show a time bound. Specically, we claim that in O(s n2 + cn) time anyprocess in T enters C . We prove this bound using a recurrence as follows.Dene T (0) to be the maximum time from when a process enters T until it enters C . For1 k log n, let T (k) be the maximum time it takes a process to enter C after winning(completing the body of the loop) at level k. We wish to bound T (0).By the code, we have T (log n) s, since only one step is needed to enter C after winningat the top level. Now, in order to nd T (0), we set up a recurrence for T (k) in terms ofT (k + 1).Suppose that pi has just won at level k, and advances to level k +1. First, pi does a coupleof assignments (taking O(s) time), and then it reaches the wait loop.

Now we consider twocases:1. If pi nds the wait condition to be true the rst time it tests it, then pi immediatelywins at level k + 1. Since the number of opponents at level k is 2k , and since pi musttest the level of all its opponents, this fragment takes O(s 2k ) time. The remainingtime till it reaches the critical region is at most T (k + 1), by denition.

The total timeis, in this case, at most O(s 2k ) + T (k + 1).2. If pi nds the wait condition to be false the rst time it tests it, then there is acompetitor (say pj ) at a level k + 1. In this case, we claim that either pi or pj mustwin at level k + 1 within time O(s 2k ) of when pi reaches the wait condition. (In fact,pj might have already won before pi reached the wait condition.) This is true becausewithin time O(s), pj must reach its wait condition, and then one of the wait conditionsmust be true (because of the value of turn (comp (i k + 1))). Within an additionalO(s 2k ), someone will discover the wait condition is true, and win.

Now, if pi is thewinner, then it takes an additional T (k + 1) until it reaches the critical region if pj isthe winner, then within additional time T (k + 1), pj reaches C , and within additional110time c, it leaves C . After another O(s) time, it resets level (j ) := 0. Thereafter, weclaim that pi will soon win at level k + 1: right after pj resets its level , all the levelvalues of opponents (i k) are less than k + 1. If they remain this way for time O(s 2k ),pi will nd its condition true and win. If not, then within this time, some opponent ofi reaches level k + 1. Then within additional time s, it sets turn to be favorable to i,and within an additional O(s 2k ), pi will discover this fact and win.The total time is thus at most the maximum of the two cases above, ornomax (s 2k ) + T (k + 1) O(s 2k ) + 2T (k + 1) + c = O(s 2k ) + 2T (k + 1) + c :Thus we need to solve the following recurrence.T (k)T (log n)2T (k + 1) + O(s 2k ) + csLet a be the constant hidden by the big-O notation.

We haveT (0)2T (1) + as20 + c 22 T (2) + as(20 + 22 ) + c(20 + 21 )... 2k T (k ) + as(20 + 22 + : : : + 22k;2 ) + c(20 + 21 + : : : + 2k;1 )... 2log n T (log n) + as(20 + 22 + : : : 22(logn;1) ) + c(20 + 21 + : : : + 2log n;1 )= ns + O(s n2) + O(cn)= O(s n2 + cn)Bounded Bypass. As a last remark, we point out the fact that Peterson's algorithm doesnot have any bound on the number of bypasses. To see this, consider an execution in whichone process i arrives at its leaf, and takes its steps with intervening times equal to the upperbound s, and meanwhile, another process j arrives in the other half of the tree, going muchfaster.

Process j can reach all the way to the top and win, and in fact it can repeat thisarbitrarily many times, before i even wins at level 1. This is due to the fact that is no lowerbound was assumed on process step times. Note that there is no contradiction betweenunbounded bypass and a time upper bound, because the unbounded bypass can only occurwhen some processes take steps very fast.111Shared variables:level: an array indexed by 1::n] of f0 : : : n ; 1g, initially all 0turn: an array indexed by 1::n ; 1] of f1 : : : ng, initial state arbitraryCode for pi :** Remainder Region **try ifor k := 1 to n ; 1 dolevel (i) := kturn (k) := iwait for 8j 6= i : level (j ) < k] or turn (k) 6= i]end forcrit i** Critical Region **exit ilevel (i) := 0rem iFigure 9.4: Peterson's iterative algorithmRemark.

In the original Peterson-Fischer tournament algorithm (with single-writer variables), the turn information is not kept in a centralized variables, but is rather distributedaround variables belonging to the separate processes. This leads to a complex system ofrepeated reads of the variables, in order to obtain consistent readings.9.2.4 Iterative AlgorithmIn Peterson's newer paper, there is another variant of the algorithm presented above. Insteadof a tournament, this one conducts only one competition for each level, and rather thanallowing only one winner for each competition, it makes sure there is at least one loser.

Inthis algorithm, all n processes can compete at the beginning, but at most n ; 1 can havewon at level 1 at any particular time, and in general, at most n ; k can have won at level k.Thus, after n ; 1 levels, get only one winner. The code is given in Figure 9.4.1126.852J/18.437J Distributed AlgorithmsLecturer: Boaz Patt-ShamirOctober 15, 1992Lecture 1010.1 Atomic ObjectsIn the past couple of lectures, we have been considering the mutual exclusion problem in theasynchronous shared-memory model.