Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 41
Текст из файла (страница 41)
Lamport carries out a series of wait-free constructions, startingwith the simplest registers and ending up with single-reader single-writer k-ary registers.Others have completed the remaining constructions. We have already seen how to get multiwriter multi-reader registers from single-writer multi-reader registers (although there is roomfor improved eciency). Also, Singh, Anderson, and Gouda have given an implementationof single-writer multi-reader registers from single-writer single-reader registers.In this general development, some of the algorithms are logically complex and/or timeconsuming, so there is some question about their practicality.The general development we consider here can be formalized in the object spec model.So we get transitivity as discussed earlier.
Recall the architecture.reader lineRPx1writer 1 lineWP1x2writer 2 lineWP2Figure 16.8: Example: Implementing a 2-writer 1-reader register with two 1-writer 2-readerregistersIn Figure 16.8 we see a particular implementation of a 2-writer 1-reader register in termsof two 1-writer 2-reader registers. There is a process for each line of the register beingimplemented, i.e., for each of the high-level writers and the high-level reader. These processes202are connected to the low-level registers in such a way that each line of a low-level register isconnected to only one process.In general, we call the high-level registers logical registers and the low-level registersphysical registers. In all of the constructions we will consider, a logical register is constructedfrom one or more physical registers.
Each input line to the logical register is connected to aprocess. These processes in turn are connected to one or more of the physical registers usinginternal lines. Exactly one process is connected to any internal line of a physical register.This permits the processes to guarantee sequentiality on each line.
Processes connected toexternal write lines are called write processes, and processes connected to external read linesare called read processes. Note that nothing prevents a read process from being connectedto an internal write line of a physical register, and vice versa.We follow Lamport's development. We have safe vs. regular vs.
atomic single-readervs. multi-reader and binary vs. k-ary registers. We thus consider the twelve dierent kindsof registers this classication gives rise to, and see which register types can be used toimplement which other types. The implementation relationships in Figure 16.9 should beobvious, because they indicate types of registers that are special cases of other types.Safess ssn-readerk-aryJRegularss ssn-readerk-aryJAtomicss ssn-readerk-aryJJJJJ ?J ?J^ 1-reader n-reader @@^J 1-reader n-reader @@JJ^ 1-readern-reader binary J @k-arybinary J @k-arybinary Jk-aryIIJ@J@JJJJJ^ ^ J^ J1-readerbinary1-readerbinary1-readerbinaryFigure 16.9: Obvious implementation relationships between register types. An arrow fromtype A to type B means that B can be implemented using A.16.2.3 Register ConstructionsLamport presents ve constructions to show other implementation relationships.
In thefollowing constructions, actions on external lines are always specied in upper-case, whereas203actions on internal lines are specied in lower-case. For example, WRITE and READ denoteexternal operations whereas write and read denote internal operations.N -Reader Registers from Single-Reader RegistersThe following construction (Construction 1 in the paper) implements an n-reader safe registerfrom n single-reader safe registers.
The same algorithm also implements an n-reader regularregister from n single-reader regular registers. The write process is connected to the writelines of all n internal registers as in Figure 16.10.WR1R2Rn$'& %WPRP1rx1 wRP2rx2 wRPnrxn wFigure 16.10: N -Reader Registers from n 1-Reader RegistersRead process i is connected to the read line of the ith physical register. Thus, the writeprocess writes all the physical registers, while each read process only reads one physicalregister.
The code is as follows.WRITE (v): For all i in f1 : : : ng, invoke write(v) on xi . Wait for acks from all xi and thendo ACK. (The writes can be done in any order.)READ i : Invoke read on xi. Wait for return (v) and then do RETURN (v ).Claim 2 If x1 : : : xn are safe registers, then so is the logical register.Proof: Within each WRITE, exactly one write is performed on each particular register xi.Therefore, since WRITE operations occur sequentially, write operations for each particularxi are also sequential.
Likewise, read operations for a particular xi are also sequential.204Therefore, each physical register has the required sequentiality of accesses. This means thatthe physical registers return values according to their second conditions (behavior specs).Now if a READ, say by RPi , does not overlap any WRITE, then its contained read doesnot overlap any write to xi. Therefore, the correctness of xi assures that the read operationgets the value written by the last completed write to xi. This is the same value as written bythe last completed WRITE, and since RPi returns this value, this READ returns the valueof the last completed WRITE.Claim 3 If x1 : : : xn are regular registers, then so is the logical register.Proof: We can \reuse" the preceding proof to get the required sequentiality of accesses toeach physical register, and to prove that any READ that does not overlap a WRITE returnsthe correct value.
Therefore, we only need to show that if a READ process R overlaps someWRITE operations, then it returns the value written by a feasible WRITE. Since the read rfor R falls somewhere inside the interval of R, the set of feasible writes for r corresponds toa subset of the feasible WRITES for R.Therefore, regularity of the physical register xi implies that r gets one of the valueswritten by the set of feasible writes, and hence R gets one of the values written by the setof feasible WRITES.Consider two READ s done sequentially at dierent processes, bracketed within a singleWRITE.
They can obtain out-of-order results, if the rst sees the result of the WRITEbut the later one does not (since WRITE isn't done atomically). This implies that theconstruction does not make the logical register atomic even if the xi are atomic.With this construction, Figure 16.8 reduces to Figure 16.11.Wait-freedom. The previous construction guarantees that all logical operations terminatein a bounded number of steps of the given process, regardless of what the other processesdo.
Therefore, the implementation is wait-free. In fact, the property satised is stronger,since it mentions a bounded number of steps. Sometimes in the literature, wait-freedom isformulated in terms of such a bound.K -ary Safe Registers from Binary Safe Registersj kIf k = 2l , then we can implement a k-ary safe register using l binary safe registers (Construction 2 in the paper). We do this by storing the ith bit of the value in binary register xi.The logical register will allow the same number of readers as the physical registers do (seeFigure 16.12).The code for this construction is as follows.WRITE (v ): For i in f1 : : : lg (in any order), write bit i of the value to register xi .205SafeRegulark-aryk-aryssss?AtomicyXXXXXXss ssn-readerk-aryJJXXXXXJX^n-reader XXXXJbinaryJJJ^ J?binarybinary1-readerbinaryFigure 16.11: Collapsed Implementation Relationships$' & %x1WR1R2Rnx2xlWP wwwRP1rrrRP2rrrRPnrrrFigure 16.12: K -ary Safe Registers from Binary Safe Registers2061-readerk-aryREAD i: For i in f1 : : : lg (in any order), read bit i of value v from register xi .
ThenRETURN(v ).Note that unlike the Construction 1, this construction works for safe registers only, i.e., ak-ary regular register cannot be constructed from a binary regular register using this method.With this construction, Figure 16.11 reduces to Figure 16.13.SafesRegularssk-aryAtomicss ssn-readerk-aryyXXXXXkQQJXXXXXJQQJXXQQ^n-reader XXXXJQQbinary JQQJJQQ ?^ JQbinary1-readerbinaryFigure 16.13: Collapsed Implementation Relationships2071-readerk-ary6.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchNovember 10, 1992Lecture 1717.1 Register Constructions (cont.)We continue investigating the implementation relationships among the dierent register models.
In the last lecture, we saw Constructions 1 and 2, and we have consequently reducedthe relationship to the one described in Figure 17.1.SafesRegularssk-aryAtomicss ssn-readerk-aryyXXXXXkQQJXXXXXJQQJXQQX^n-reader XXXXJQQbinary JQQJQQ ?J^ JQbinary1-readerk-ary1-readerbinaryFigure 17.1: Collapsed Implementation Relationships17.1.1 Construction 3: Binary Regular Register from Binary SafeRegisterA binary regular register can easily be implemented using just one binary safe register (seeFigure 17.2).Recall that a read from a binary safe register may return any value from its domain theread overlaps a write.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
