Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 24
Текст из файла (страница 24)
For this rule,we have the following simple property.Suppose every update leaves a unique mark in its register. If two consecutiveglobal reads return identical values, then the values returned are consistent, i.e.,they constitute a true snapshot.The observation above immediately gives rise to the following simplistic algorithm: eachupdate increments the local sequence number each snap collects repeatedly all the values,until two identical consecutive sets of collected values are seen (a successful double collect).This common set is returned by the snap-respond.This algorithm always returns correct answers, but it suers from the problem that asnap may never return, if there are updates invoked concurrently.For this problem, however, we have the following observation (see Figure 10.4).If a snap sees a value being updated 3 times, then the updater executes a completeupdate operation within the interval of the snap.1st valueSnap2nd value3rd valueFigure 10.4: a complete update must be contained in the interval containing three changes of asingle value.
Notice the embedded snap in the middle update.The observation above leads us to the main idea of the algorithm, which can be informallystated as If you want to write, then read rst! Specically, we extend the algorithm suchthat before an update process writes, it must take a snap action, and save the result of thisinternal snap somewhere accessible to all others. We shall use the term embedded snap forthe snaps activated by updates.We can now describe the unbounded algorithm. The system structure is depicted inFigure 10.5.
First, we describe the state variables.For each update i we have a register which is a record with the following elds.value vi118sequence number siview (i.e., a vector of values) Gisnapjembeddedsnapsnapupdateupdate iFigure 10.5: system structure for the algorithmThe code for snap i process is as follows.Read all registers until eithersee 2 equal sj for all j (\double collect"), orsee 3 distinct values of sk for some k.In the rst case, return the repeated vector of vj s.In the second case, return the second Gk for that k (\borrowed view").The code for update i(v) process is as follows.Do snap i (embedded snap procedure).Write (atomically):incremented sequence number in si,v in vi, andthe value returned by the snap in GiCorrectness.
The well-formedness condition is clearly maintained. The more interestingparts are serializability and termination.Theorem 1 The algorithm satises the atomicity condition.119Proof: We construct explicit serialization points in the operations interval at which theread or write can said to have occurred. Clearly, update must be serialized at the point ofwrite.For the snap operation, the situation is a bit more complicated. Consider the sequenceof writes that occurs in any execution. At any point in time, there is a unique vector ofvis.
Call these \acceptable vectors". We show that only acceptable vectors are obtained bysnaps. We will construct serialization point for all snaps (\real" and embedded) as follows.First, consider snaps that terminate with successful double collects. For these, we canpick any point between the end of rst collect and the beginning of second as a serializationpoint. It is clear that the vector returned by snap-respond is exactly the acceptable vectorat this point, because there is no change in that interval, by the assumption that any changeeects the sequence numbers.Second, consider snaps that terminate with borrowed view. We pick serialization pointsfor these by induction on their order of the completion. Base case is trivial (no such snaps).For the inductive step, note that the borrowed view of the kth such snap is the result ofsome other snap which is completely contained within the snap at hand.
By induction, theformer was already assigned a point. We choose that same point for the snap at hand. Thispoint is in the bigger snap interval since it is in the smaller (see Figure 10.5).By the induction, we also have that the value returned is exactly the acceptable vectorat the serialization point.Theorem 2 In a fair execution, each snap and update terminates in O(n2) memory accesssteps.Proof: For snap, it follows from the pigeon-hole principle, that after at most 2n + 1 \collects" of all the values, there must be a process with 3 changes. Since in each collect the snapprocess reads n values, the O(n2) bound follows. For update, we have O(n2) too, because ofembedded snap (which is followed only by a single write).10.2.3 Bounded Register AlgorithmThe requirement of the previous algorithm to have unbounded registers is problematic.
Theoretically, this means that the algorithm needs unbounded space. The point is that thecorrectness only required that a change is detectable having a sequence number gives us atotal order, which is far more than we need.If we think of the algorithm a little, we can see that the purpose of the sequence numberswas that snap processes could tell when update i produced a new value. This, however, canbe communicated explicitly using handshake bits.
More specically, the main idea is asfollows. Instead of keeping sequence numbers for update i, keep n pairs of handshake bits for120communication between update i and snap j for all j (actually, 2n | for real and embeddedsnaps). The handshake protocol is similar the Peterson-Fisher 2-process mutual exclusionalgorithm: update i sets the bits to be unequal, and snap i sets them equal.We use the following notation for the handshake bits. For each (update i snap j ) pair, wehave bits pij at i, and qji at j .
with this notation, the handshake protocol is simply thefollowing.1. When update i writes: pij :qji.2. Before snap j reads: qji pijThe handshake protocol is \nearly" sucient. As we shall see, it can be the case thattwo consecutive values can be confused. To overcome this problem, each update i has anadditional toggle bit, toggle i, that it ips during each write. This ensures that each writechanges the register value.We can now give a sketch of the code of the bounded algorithm. (The complete algorithmcan be found in page 10 of Handout 15.)update i:Read the handshake bits qji for all jSnapWrite the value, borrowed view, the negated handshake bits, and negated toggle bitsnap j :RepeatRead handshake bits pij and set qji pij for all iDo two collectIf both collects are equal in all pij and toggle i, then return common vectorelse record who has movedUntil someone moved 3 timesReturn borrowed viewCorrectness.
The general idea is the same as for unbounded case. We serialize updates bythe writes. For snap: we can serialize snap that return borrowed view using the same induction. Not surprisingly, the problem now is correctness of snaps that return by double-collect.The following argument shows that the same serialization rule (i.e., any point between thetwo collects).121Claim 3 If a snap does a successful double collect, then no write occurs between the end ofthe rst and the beginning of the second.Proof: By contradiction. Suppose two reads by snap j of ri produce pij equal to qji's mostrecent values and toggle bit, and assume a write by i occurs in between the 2 reads. Considerthe last such write i | it must write the same pij and toggle i read by snapj .
Since duringupdate i , pij gets :qji, then the read must precede snap j 's most recent write of qji .Thus we must have the situation depicted in Figure 10.6.update processread(q=−b)write(q=b)write(p=b,toggle=t)read(p=b,toggle=t)read(p=b,toggle=t)snap processFigure 10.6: scenario described in the proof of Claim 3. The shaded area represent the activeinterval of the last update before the second read of snap .ijThe read i and write i are part of the same update i, so the two reads by snap j returnvalues written by the 2 successive update i writes, with identical toggle bits | contradictingthe code.Before we conclude the discussion of the atomic snapshot algorithm, we remark that ithas the additional nice property of wait-freedom. Namely, in any execution, including thosethat are not necessarily fair to all processes, but just to some subset subset P , any operationof any i 2 P is guaranteed to terminate.
Notice that processes not in P may even stop,without aecting the progress of the processes in P . We will discuss this concept extensivelyin future lectures.1226.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchOctober 20, 1992Lecture 11So far, we have been working within a model based on read-write shared memory, whilestudying the mutual exclusion and atomic snapshot problems. We have digressed slightlyby jumping from the mutual exclusion problem to the atomic snapshot problem.
Today, wewill return to the mutual exclusion problem once again. In the following lectures, we willconsider the consensus problem in read-write shared memory, and then consider atomic (andother) objects once again.11.1 Burns' Mutual Exclusion AlgorithmBoth of the algorithms we have studied so far (Dijkstra's and Peterson's) use multi-writervariables (turn ) along with a collection of single-writer variables (ag ). Due to the fact thatit might be dicult and inecient to implement (i.e., physically build) multi-writer sharedvariables in certain systems (in particular, in distributed systems), algorithms that use onlysingle-writer variables are worth investigating.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
