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

Essentially, the problem involves arbitrating access to a single, indivisible,exclusive-use resource. The uncertainty here is about who is going to request access andwhen. We'll sketch some of the important algorithms, starting with the original algorithmof Dijkstra. Many important concepts for this eld will be illustrated in this context, including progress, fairness, fault-tolerance, and time analysis for asynchronous algorithms.We shall see upper bounds on the amount of shared memory, corresponding lower bounds,and impossibility results. We shall also discuss generalizations of mutual exclusion to moregeneral resource allocation problems. For example, we will consider the Dining Philosophersproblem { a prototypical resource allocation problem.Next, we shall study the concept of atomic registers : so far, we have been assuming indivisible access to shared memory. But how can one implement this on simpler architectures?We shall look at several algorithms that solve this problem in terms of weaker primitives.

Aninteresting new property that appears here is wait-freeness, which means that any operationon the register must complete regardless of the failure of other concurrent operations.An atomic snapshot is a convenient primitive for shared read-write memory. Roughlyspeaking, the objective is to take an instantaneous snapshot of all the memory locations atonce. An atomic snapshot is a useful primitive to have for building more powerful systems.We shall see how to implement it.A concurrent timestamp system is another nice primitive. This is a system that issues,upon request, timestamps that can be used by programs to establish a consistent orderamong their operations. The twist here is how to implement such systems with boundedmemory. It turns out out such bounded timestamp systems can be built in terms of atomicsnapshots.

Also, a concurrent timestamp system can be used to build more powerful formsof shared memory, such as multi-writer multi-reader memory.We shall also reconsider the consensus problem in the asynchronous shared memorymodel, and prove the interesting fact it is impossible to solve in this setting.A possible new topic this time is shared memory for multiprocessors. Much recent researchis aimed at identifying dierent types of memory abstractions that are used, or might beuseful, for real systems. Systems architects who develop such types of memory frequently donot give precise statements of what their memory guarantees (especially in the presence ofconcurrent accesses and failures).

So recently, theoreticians have started trying to do this.18Asynchronous Message-Passing Systems. This section deals with algorithms that op-erate in asynchronous networks. Again, the system is modeled as a graph with processors atnodes, and communication links are represented by the edges, but now the system does notoperate in rounds. In particular, messages can arrive at arbitrary times, and the processorscan take steps at arbitrary speeds.

One might say that we now have \looser coupling" ofthe components of the system: we have more independence and uncertainty.Computing in static graphs. The simplest type of setting here is computation in a xed(unknown) graph in which the inputs arrive at the beginning, and there is a single outputto be produced. Some examples are leader election in ring, and minimum spanning treecomputation.Network synchronization. At this point, we could plunge into a study the many specialpurpose algorithms designed expressly for asynchronous distributed networks. But instead,we shall rst try to impose some structure on such algorithms by considering \algorithmtransformations" that can be used to run algorithms designed for a simpler computationmodel on a a complex asynchronous network.The rst example here arises in the very important paper by Lamport, where he showsa simple method of assigning consistent logical times to events in a distributed network.This can be used to allow an asynchronous network to simulate one in which the nodeshave access to perfectly synchronized real-time clocks.

The second example is Awerbuch'ssynchronizer, which allows an asynchronous network to simulate the lock-step synchronousnetworks discussed in the rst part of the course (at least, those without failures), and todo so eciently. We shall contrast this simulation result with an interesting lower boundthat seems to say that any such simulation must be inecient (the apparent contradictionturns out to depend on the kind of problem being solved).

Third, we shall see that ansynchronous network can simulate a centralized (non-distributed) state machine. And fourth,an asynchronous network can be used to simulate asynchronous shared memory. Any of thesesimulations can be used to run algorithms from simpler models in the general asynchronousnetwork model.Next, we shall look at some specic problems, such as resource allocation. We shall seehow to solve mutual exclusion, dining philosophers etc.

in networks.Detection of stable properties refers to a class of problems with a similar avor and acommon solution. Suppose that there is a separate algorithm running, and we want todesign another algorithm to \monitor" the rst. To monitors here might mean, for instance,to detect when it terminates or deadlocks, or to take a \consistent snapshot" of its state.We shall also revisit the consensus problem in the context of networks.

The problem iseasy without faults, but with faults, it is mostly impossible (even for very simple types of19faults such as just stopping).Datalink protocols involve the implementation of a reliable communication link in termsof unreliable underlying channels. We shall see the basic Alternating Bit Protocol (thestandard case study for concurrent algorithm verication papers). There have been manynew algorithms and impossibility results for this problem.Special-Purpose Network Building Blocks.

Some special problems that arise in communication networks have special solutions that seem able to combine with others. Majorexamples are the protocols of broadcast-convergecast, reset, end-to-end.Self-stabilization. Informally, a protocol is said to be self-stabilizing if its specicationdoes not require a certain \initial conguration" to be imposed on the system to ensure correct behavior of the protocol. The idea is that a self-stabilizing protocol is highly resilient: itcan recover from any transient error.

We shall see some of the basic self-stabilizing protocols,and survey some of the recent results.Timing-based Systems. These systems lie between synchronous and asynchronous, sothey have somewhat less uncertainty than the latter. They are put at the end of the coursebecause they are a subject of newer research, and since they are less well understood. Inthese systems, processors have some knowledge of time, for example, access to real time, orapproximate real time, or some timeout facility. Another possible assumption is that theprocessor step time, or message delivery time is within some known bounds. Time addssome extra structure and complication to state machine models, but it can be handled in thesame general framework. In terms of the various time parameters, one can get upper andlower bounds for various interesting problems, such as mutual exclusion, resource allocation,consensus, and communication.We may have time to look at some popular clock synchronization algorithms, and perhapssome of their applications.1.2 Synchronous Network AlgorithmsWe start with the synchronous network algorithms.

Our computation model is dened asfollows. We are given a collection of nodes, organized into a directed graph G = (V E ). Weshall denote n = jV j. We assume the existence of some message alphabet M , and let nulldenote the absence of a message. Each node i 2 V hasstates (i) : a set of statesstart (i) : a subset of states (i)msgs (i) : mapping states (i) out-nbrs(i) to elements of M or null20trans (i) : mapping states (i) and a vector of messages in M fnull g,one per in-neighbor of i, to states (i)Execution begins with all the nodes in some start states, and all channels empty. Thenthe nodes, in lock step, repeatedly execute the following procedure called round.1.

Apply message generation function to generate messages for out-neighbors.2. Put them in the channels.3. Apply transition function to the incoming messages and the state to get the new state.Remarks. Note the following points. First, the inputs are assumed to be encoded in thestart states. Second, the model presented here is deterministic | the transitions and themessages are functions, i.e., single-valued.1.2.1 Problem Example: Leader Election in a RingConsider a graph that is a ring, plus (a technicality for the problem denition) an extradummy node representing the outside world.

The ring is assumed to be unidirectional (messages can be sent only clockwise). The ring is of arbitrary size, unknown to the processors(i.e., size information is not built into their states). The requirement is that eventually,exactly one process outputs a leader message on its dummy outgoing channel.A rst easy observation is that if all the nodes are identical then this problem is impossibleto solve in this model.Proposition 1 If all the nodes in the ring have identical state sets, start states, messagefunctions and transition functions, then they do not solve the leader election problem forn > 1.Proof: It is straightforward to verify, by induction on the number of rounds, that all theprocessors are in identical states, after any number of rounds. Therefore, if any processorever sends a leader message, then they all do so at the same time, violating the problemrequirement.As indicated by Proposition 1, the only way to solve the leader election problem is tobreak the symmetry somehow.

A reasonable assumption from practice is that the nodes areidentical except for a unique identier (UID), chosen from some large totally ordered set(e.g., the integers). We are guaranteed that each node's UID is dierent from each other's inthe ring, though there is no constraint on which ID's actually appear in the given ring. (E.g.,they don't have to be consecutive integers.) We exploit this assumption in the solutions wepresent.211.2.2 Algorithm 1: LeLann, Chang-RobertsWe rst describe the algorithm informally.