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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

We describe the algorithm in Figure 14.9 below in a sort of pseudocode, roughlysimilar to the original Lamport algorithm, rather than precondition-eects notation.The invocations of label and scan are written as single statements, but they denote pairsof invocation and response actions to the CTS object, e.g., beginlabel i and endlabel i.Let us go over the dierences from the original bakery algorithm. First, instead ofexplicitly reading all the variables and taking the maximum, we just do a label operationto establish the order (everything is hidden within the CTS object). Second, the structureof the checks is changed a little.

Instead of looping through the processes one at a time,the modied algorithm rst checks that no one is choosing, and then checks the priorities.Note that the algorithm is not sensitive to this dierence. Third, in the loop where we checkthe priorities, instead of reading the numbers, the modied algorithm at process i does scanto obtain the order, and then looks for i to be ahead of everyone else. Note that in thisvariant, we only check for i to be ahead of those that are currently competing in the prioralgorithm, the number was explicitly set back to 0 when a process left, but now we no longerhave sucient explicit control to assign those numbers.

So instead, we leave the order as itis, but explicitly discount those that aren't competing.To understand the above algorithm, consider it rst when the unbounded CTS algorithmis employed. We claim that in this case, similar arguments to those used in the correctnessproof for the original bakery algorithm show the same properties, i.e., mutual exclusion,deadlock-freedom, lockout-freedom, and FIFO after a wait-free doorway (now the doorwayis the portion of the code from entry to the trying region until the process sets its ag to2). The unbounded variant is more complicated, has worse time complexity, and so far, doesnot seem to be better than the original algorithm.

But now note that we can replace theunbounded CTS object within this algorithm by the bounded CTS object. Since every wellformed behavior of the bounded algorithm is also a well-formed behavior of the unboundedalgorithm, we obtained an algorithm that uses bounded-size registers, and still works correctly! Recall that the bounded algorithm is based on snapshot, based on single-writerregisters. And the only values that need to be written in the registers are the timestamps,176chosen from the bounded domain.

Note that this application did not use the value part ofthe CTS only the ordering part is used.177Shared variables:ag : an array indexed by 1..n] of integers from f0,1g, initially all 0, where ag i]is written by pi and read by allCTS : a concurrent timestamp objectCode for pitry iL1:ag i] 1label iag i] 2L2:for j 2 f1 : : : ng doif ag j ] = 1 then goto L2end ifend forL3:scan i ()for j 2 f1 : : : ng doif j i and ag j ] = 1 then goto L3end ifend forcrit i**Critical region**exit iag i] 0rem i**Remainder region**Figure 14.9: the bakery algorithm with concurrent timestamps1786.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchNovember 3, 1992Lecture 1515.1 Multi-Writer Register Implementation Using CTSIn this section we show another simple and interesting application of CTS, namely implementing multi-writer multi-reader registers from single-writer multi-reader registers.

In thisapplication, we use the value part of the CTS as well as the ordering part.15.1.1 The AlgorithmThe code is very simple:read i process: scan i (o v%), and return vj , where j is the maximum index in o.write i (v ) process: label i (v).The algorithm is straightforward: a write simply inserts the new value as part of a labelaction, while read returns the latest value, as determined by the order returned by an embedded scan. In fact, the algorithm is easier to understand by considering the high level code andthe CTS level code together (but keeping the snapshot abstraction instantaneous).

In thismore elaborate description, the low-level memory consists of a vector of (value timestamp )pairs. The write action snaps all of memory instantaneously, chooses a timestamp biggerthan the biggest timestamp already existing in the memory (with the exception that if italready is the biggest, it keeps its value), and (in a separate step) writes back the new valuewith that new timestamp.

The read process snaps all of memory instantaneously, and returnsthe value that is associated with the biggest timestamp.Note that if the algorithm works correctly using the unbounded CTS algorithm, thenit will also work using the bounded algorithm, which can be implemented using boundedspace.

Thus, it is sucient to prove that the algorithm works correctly using unboundedtimestamps.It is easy to see that the algorithm has the nice properties of wait-freeness, fairness,and well-formedness. The interesting thing here is to show the existence of the neededserialization points. We do it by rst proving the following lemma.17915.1.2 A Lemma for Showing AtomicityLemma 1 Let be a well-formed sequence of invocations and responses for a read-writeregister. Let T be any subset of the incomplete operations in .

Let S be the union of thecomplete operations and T . Suppose that is a partial ordering of all the operations in S ,satisfying the following properties.1. Let i be a write operation in S , and let j be any operation in S . Then we have i jor j i. In other words, totally orders all the write operations, and orders all theread operations with respect to the write operations.2. The value returned by each complete read operation in S is the value written by the lastpreceding write operation according to (or the initial value, if none).3.

If i is a complete operation and end i precedes begin j in , then it cannot be the casethat j i.4. For any operation i, there are only nitely many operations j such that j i.Then is an atomic read-write register behavior (i.e., satises the atomicity condition).Proof: We construct serialization points for all the operations in S as follows.

We inserteach serialization point i immediately after the later of begin i and all begin j such that j i.(Note that Condition 4 ensures that the position is well dened.) For consecutive 's, orderthem in any way that is consistent with . Also, for each (incomplete) read in T , assign areturn value equal to the value of the last write operation in S that is ordered before it by (or the initial value, if none).To prove that this serialization satises the requirements, we have to show that1. the serialization points are all within the respective operation intervals, and2. each read i returns the value of the write whose serialization point is the last one beforei (or the initial value, if none).For the rst claim, consider the i serialization point.

By construction, it must be afterbegin i . If i is a complete operation, it is also before end i: if not, then end i precedes begin jfor some j having j i, contradicting Condition 3.For the second claim, consider read operation i. By Condition 2 for complete reads, andthe denition for incomplete reads, the value returned by read i is the value written by thelast write operation in S that is ordered before op i by (or the initial value, if none).Condition 1 says that orders all the writes with respect to all other writes and all reads.To show that read i returns the value of the write whose serialization point is the last one180before i (or the initial value, if none), it is sucient to show that the (total) order of theserialization points is consistent with , i.e., if i j then i precedes j .

This is true sinceby denition, i occurs after the last of begin i and all begin k , for k i, while j occurs afterthe last of begin j and all begin k where k j . Thus, if i j then for all k such that k i wehave k j , and hence j occurs after i.15.1.3 Proof of the Multi-writer AlgorithmWe now continue verifying the implementation of multi-writer registers. We dene an ordering on all the completed operations and T , where T is the set of all the incomplete writeoperations that get far enough to perform their embedded update steps.

Namely, order allthe write operations in order of the timestamps they choose, with ties broken by processindex as usual. Also, if two operations have the same timestamp and the same process index, then we order them in order of their occurrence | this can be done since one musttotally precede the other. Order each complete read operation after the write whose valueit returns, (or before all the writes, if it returns the initial value). Note that this can bedetermined by examining the execution.

To complete the proof, we need to check that thisordering satises the four conditions. It is immediate from the denitions that Conditions 1and 2 are satised. Condition 4 is left to the reader | we remark only that it follows fromthe fact that any write in T eventually performs its update, and so after that time, othernew write operations will see it and choose bigger timestamps.The interesting one is Condition 3. We must show that if i is a complete operation, andend i precedes begin j , then it is not the case that j i.First, note that for any particular process, the timestamps written in the vector locationfor that process are monotone nondecreasing.

This is because each process sees the timestamp written by the previous one, and hence chooses a larger timestamp (or the same, if it'sthe maximum). We proceed by case analysis, based on the types of the operations involved.Case 1: Two writes. First suppose that i and j are performed by dierent processes.Then in the snap step, j sees the update performed by i (or something with a timestamp atleast as big), and hence j chooses a larger timestamp than i's, and gets ordered after i by.Now suppose that i and j are performed by the same process.

Then since j sees theupdate performed by i, j chooses either the same or a larger timestamp then i. If it choosesa larger timestamp, then as before, j gets ordered after i by . On the other hand, if itchooses the same timestamp, then the explicit tie-breaking convention says that the twowrite s are ordered by in order of occurrence, i.e., with j after i.Case 2: Two reads. If read i nishes before read j starts, then by the monotonicity above,181j sees at least as large timestamps for all the processes as i does. This means that read jreturns a value associated with a (timestamp index ) pair at least as great as that of i, andso j does not get ordered before i.Case 3: read i, write j .

Характеристики

Список файлов книги