Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 33
Текст из файла (страница 33)
An external signature consisting of input actions, called invocations, and output actions, called responses. There is also a xed binary relation that relates responses(syntactically) to corresponding invocations.2. A set of sequences of external actions all sequences in the set are \well-formed", i.e.,they contain alternating invocations and (corresponding) responses on each of the lines(with invocation rst). The set is prex-closed.This is a very general notion. Basically, this is an arbitrary behavior specication at theobject boundary. The behavior specication for atomic objects is a special case.An IOA with the appropriate interface is said to satisfy, or implement, this specicationif the following conditions hold.1.
It preserves well-formedness.2. All its well-formed behaviors are in the set.3. All its fair behaviors include responses to all invocations.Compositionality of Object ImplementationsSuppose that we start with a system A in the object specication model, using a particularset of object specications for its objects.
We need to be a little more careful about what thismeans. The executions of this system are the executions of the processes that get responsesallowed by the object specications. The fair executions of the system are then dened tobe those executions that are fair to all the processes and in which all invocations to theobject specications eventually return. We also assume that each process of A preserveswell-formedness for each object specication.161Suppose that A itself satises another, \higher-level" object specication.
Consider theresult of replacing all the object specications of A with object IOA's that satisfy the corresponding specications (in the object specication model). We claim that the resultingsystem still implements the external object specication.interfacelinecombinedprocessprocesslineobjectFigure 13.1: On the left we see an object composed of smaller objects. All the shaded processesare associated with the same external interface line. On the right we see the combined process forfairness purposes.Note that fairness of the composed implementation refers to fair execution of all theprocesses, high-level and low-level, plus the object specication liveness condition for thelow level objects.Note that the resulting architecture is dierent from the model we have been using.
Itdoesn't have one process per line, but rather a distributed collection of processes. We canconvert this to a system in the usual architecture by composing some of these processes togive the processes we want, as follows (see gure 13.1). Compose the distributed processesthat operate on behalf of any particular line i | the high-level process plus, for every line ofthe intermediate-level objects that it uses, the corresponding low-level process (or processes,if one high-level process invokes several dierent operation types on a single object). Callthis composition qi. Let the composed processes qi be the processes of the composed implementation. (Notice that they have several fairness classes each: this is why we didn't wantto rule this out earlier.)Remark: We can get similar result composing a system that uses object specications withobject implementations that use instantaneous memory, getting a composed implementationthat uses instantaneous memory.1626.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchOctober 29, 1992Lecture 1414.1 Modularity (cont.)14.1.1 Wait-freedomIn this section we consider the wait-freedom property.
We dene this property only forimplementations in some special forms as follows.1. In the instantaneous shared memory model, wait-freedom deals with an intermediatenotion between ordinary IOA fairness (fairness to all processes) and no fairness: namely,fairness to particular processes. For this setting, the wait freedom condition is that ifan execution is fair to any particular process i, then any invocation of i eventually getsa response.2. In the object specication model, where in place of the objects we have object specications, the wait freedom condition is that if an execution is fair to any particular processi, and all invocations to memory objects by process i return, then any invocation of ieventually gets a response.Let us consider the compositionality of wait-free implementations. To be specic, supposethat we start with a system A in the object spec model, that by itself satises some objectspec, using a particular set of object specs for its objects.
Suppose that each process of Apreserve well-formedness for each object. Assume also that A is wait-free. Suppose we thenreplace all the object specs used by A with wait-free objects that satisfy the correspondingspecs again, these are required to be expressed in the object spec model. We already knowhow to get the composition, and we also know that the result satises the external objectspec. We now want to claim that the resulting system is also wait-free. We argue that asfollows.
Let be an execution of the composed system, in which qi does not fail, and inwhich all invocations by qi on low-level objects return. In , the high-level pi does not fail,since by assumption, qi doesn't fail. Also, any invocation by pi on the intermediate-levelobject must return, by the wait-freedom of the implementation of the intermediate objects.163Therefore, by the wait-freedom of the high-level implementation, any invocation on line ieventually returns.Remark.
We can get a similar result about composing a wait-free implementation thatuses object specs, with wait-free object implementations that use instantaneous memory,getting a wait-free composed implementation that uses instantaneous memory.14.2 Concurrent Timestamp SystemsToday we shall go through some constructions to show how we could build some powerfulobjects out of others. We shall do this hierarchically.
We have already seen (in Lecture10) how we can get a wait-free implementation of an atomic snapshot object, in terms ofinstantaneous access single-writer multi-reader read-write objects. In this section we showhow to get a wait-free implementation of another type of object, called concurrent timestampobject (CTS), in terms of instantaneous snapshot objects. By the compositionality resultsabove, we can combine these and get a wait-free implementation of a concurrent timestampobject in terms of instantaneous access single-writer multi-reader read-write variables.We shall then see how we can use a CTS object as a building block for other tasks.Specically, we give an improvement to Lamport's bakery algorithm, and an implementationof a wait-free multi-writer multi-reader register. CTS objects can also be use for other tasks,e.g., resource allocation systems.14.2.1 Denition of CTS ObjectsA concurrent timestamp system object has two operations.label i (v): always gets the response \OK".scan i : gets a response that describes a total ordering of the n processes, together withan associated value for each process.The rough idea is that each newly arrived process gets an associated label of some kind,and we require that later labels can be detected as \larger" than earlier labels.
The scanoperation is supposed to return a reasonable ordering of the processes, based on the orderof their most recent labels (i.e., the approximate order of their most recent arrivals). And,for good measure, it also returns the values associated with those labels.Note that this is not an atomic object it has a more general kind of object spec. Inthe literature (see Gawlick's thesis, and Dolev-Shavit), the precise requirements are givenby a set of axioms about the well-formed behaviors.
These look a little too complicated to164present in class, so instead we dene the correct behaviors as the well-formed behaviors of afairly simple algorithm, given in Figures 14.2 and 14.1.This \spec algorithm" uses a dierent programming notation from what we have previously used (e.g., for mutual exclusion). The notation presented here describes I/O automatamore directly: each action is specied separately, with an explicit description of the statesin which it can occur, and the changes it causes to the process state. Note also the explicitmanipulation of the program counter (pc). This notation is very similar to that used in theprevious lecture to describe a user automaton the main dierences are that here we useassignment statements rather than equations and leave the pre- and post-states implicit.The \begin" and \end" actions just move the pc and transmit the results.
The real workis done by embedded snap and update actions. In the scan , the process does a snap to getan instantaneous snapshot of everyone's latest label and value. Then it returns the orderdetermined by the labels, with the associated values. In the label , the process rst doesa snap to collect everyone's labels. Then if the process does not already have the max, itchooses some larger value (this could be the integer one greater than the max, as in Lamport'sbakery, or it could be some more general real value).
Finally, it does an instantaneous updateto write the new label and value in the shared memory.A straightforward observation is that the algorithm is wait-free. The most interestingproperty of the algorithm, however, is that it can be implemented using a bounded domain forthe labels. This property will allow us to obtain bounded versions for bakery-style mutualexclusion algorithm, and a wait-free implementation of multi-writer multi-reader atomicobjects in terms of single-writer multi-reader (which uses three levels of implementation:snapshot in terms of single-writer objects, CTS object in terms of snapshot, and multi-writerregisters in terms of CTS object).14.2.2 Bounded Label ImplementationWe start with a bounded label implementation.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
