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

Luckily, not all the algorithms we consider will have to contend with all ofthese types of uncertainty!Distributed algorithms can be extremely complex, at least in their details, and can bequite dicult to understand. Even though the actual \code" may be short, the fact thatmany processors are executing the code in parallel, with steps interleaved in some undetermined way, implies that there can be prohibitively many dierent executions, even for thesame inputs.

This implies that it is nearly impossible to understand everything about theexecutions of distributed algorithms. This can be contrasted with other kinds of parallelalgorithms such as PRAM algorithms, for which one might hope to understand exactly whatthe (well-dened) state looks like at each given point in time.

Therefore, instead of tryingto understand all the details of the execution, one tends to assert certain properties of theexecution, and just understand and prove these properties.1.1.2 StyleThe general avor of the work to be studied is as follows.Identify problems of major signicance in (practical) distributed computing and deneabstract versions of the problems for mathematical study.Give precise problem statements.Describe algorithms precisely.14Prove rigorously that the algorithms solve the problems.Analyze the complexity of the algorithms.Prove corresponding impossibility results.Note the emphasis on rigor this is important in this area, because of the subtle complications that arise. A rigorous approach seems necessary to be sure that the problems aremeaningful, the algorithms are correct, the impossibility results are true and meaningful,and the interfaces are suciently well-dened to allow system building.However, because of the many complications, rigor is hard to achieve.

In fact, the development of good formal methods for describing and reasoning about distributed algorithmsis the subject of a good deal of recent research. Specically, there has been much seriouswork in dening appropriate formal mathematical models, both for describing the algorithmsand for describing the problems they are supposed to solve a considerable amount of workhas also been devoted to proof methods. One diculty in carrying out a rigorous approachis that, unlike in many other areas of theoretical computer science, there is no any singleaccepted formal model to cover all the settings and problems that arise in this area.

Thisphenomenon is unavoidable, because there are so many very dierent settings to be studied(consider the dierence between shared memory and message-passing), and each of them hasits own suitable formal models.So, rigor is a goal to be striven for, rather than one that we will achieve entirely in thiscourse. Due to time limitations, and (sometimes) the diculty of making formal presentations intuitively understandable, the presentation in class will be a mixture of rigorous andintuitive.1.1.3 Overview of the CourseThere are many dierent orders in which this material could be presented.

In this course, wedivide it up rst according to timing assumptions, since that seems to be the most importantmodel distinction. The timing models to be considered are the following.synchronous : This is the simplest model. We assume that components take steps simultaneously, i.e., the execution proceeds in synchronous rounds.asynchronous : Here we assume that the separate components take steps in arbitrary order.partially synchronous (timing-based): This is an \in-between" model | there are somerestrictions on relative timing of events, but execution is not completely lock-step.15The next division is by the IPC mechanism: shared memory vs. message-passing.

Thenwe subdivide by the problem studied. And nally, each model and problem can be consideredwith various failure assumptions.We now go over the bibliographical list and the tentative schedule (Handouts 2 and 3).The bibliographical list doesn't completely correspond to the order of topics to be coveredthe dierence is that the material on models will be spread throughout the course as needed.General references. These include the previous course notes, and some related books.There is not really much in the way of textbooks on this material.Introduction. The chapter on distributed computing in the handbook on TheoreticalComputer Science is a sketchy overview of some of the modeling and algorithmic ideas.Models and Proof Methods.

We shall not study this as an isolated topic in the course{ rather, it is distributed through the various units. The basic models used are automatatheoretic, starting with a basic state-machine model with little structure. These state machines need not necessarily be nite-state. Invariant assertions are often proved aboutautomaton states, by induction. Sometimes we use one automaton to represent the problembeing solved, and another to represent the solution then a correctness proof boils downto establishing a correspondence that preserves the desired external behavior. In this case,proving the correspondence is often done using a mapping or simulation method.

Speciallytailored state machine models have been designed for some special purposes, e.g., for sharedmemory models (where the structure consists of processes and shared variables). Anothermodel is the I/O automaton model for reactive systems, i.e., systems that interact with anexternal environment in an ongoing fashion. This model can model systems based on sharedvariables, but is more appropriate for message-passing systems. One of the key features ofthis model is that it has good compositionality properties, e.g., that the correctness of a compound automaton can be proved using the correctness of its components. Temporal logic isan example of a special set of methods (language, logic) mainly designed for proving livenessproperties (e.g., something eventually happens).

Timed models are mainly newer researchwork. Typically, these are specially-tailored models for talking about timing-based systems{ e.g., those whose components have access to system clocks, can use timeouts, etc. Algebraic methods are an important research subarea (but we will not have time for this). Thealgebraic methods describe concurrent processes and systems using algebraic expressions,then use equations involving these expressions to prove equivalences and implementationrelationships among the processes.16Synchronous Message-Passing. As noted, the material is organized rst by timingmodel.

The simplest model (i.e., the one with the least uncertainty) is the synchronousmodel, in which all the processes take steps in synchronous rounds. The shared-memoryversion of this model is the PRAM. Since it is studied in other courses, we shall skip thissubject, and start with synchronous networks.We spend the rst two weeks or so of the course on problems in synchronous networksthat are typical of the distributed setting. In the network setting we have the processorsat the nodes of a graph G, communicating with their neighbors via messages in the edges.We start with a simple toy example, involving ring computation.

The problem is to elect aunique leader in a simple network of processors, which are assumed to be identical except forUnique Identiers (UID's). The uncertainty is that the size of network, and the set of ID'sof processors, are unknown (although it is known that the UID's are indeed unique). Themain application for this problem is a token ring, where there is a single token circulating,and sometimes it it necessary to regenerate a lost token. We shall see some details of themodeling, and some typical complexity measures will be studied.

For example, we shallshow upper and lower bounds for the time and the amount of communication (i.e., numberof messages) required. We shall also study some other problems in this simple setting.Next, we'll go through a brief survey of some protocols in more general networks. Weshall see some protocols used in unknown synchronous networks of processes to solve somebasic problems like nding shortest paths, dening a minimum spanning tree, computing amaximal independent set, etc.Then we turn to the problem of reaching consensus.

This refers to the problem ofreaching agreement on some abstract fact, where there are initial dierences of opinion.The uncertainty here stems not only from dierent initial opinions, but also from processorfailures. We consider failures of dierent types: stopping, where a processor suddenly stopsexecuting its local protocol omission, where messages may be lost en route and Byzantine,where a faulty processor is completely unrestricted. This has been an active research areain the past few years, and there are many interesting results, so we shall spend a couple oflectures on this problem. We shall see some interesting bounds on the number of tolerablefaults, time, and communication.Asynchronous Shared Memory. After \warming up" with synchronous algorithms (inwhich there is only a little uncertainty), we move into the more characteristic (and possiblymore interesting) part of the course, on asynchronous algorithms.

Here, processors are nolonger assumed to take steps in lock-step synchrony, but rather can interleave their steps inarbitrary order, with no bound on individual process speeds. Typically, the interactions withthe external world (i.e., input/output) are ongoing, rather than just initial input and nal17output. The results in this setting have quite a dierent avor from those for synchronousnetworks.The rst problem we deal with is mutual exclusion This is one of the fundamental (andhistorically rst) problems in this area, and consequently, much work has been dedicatedto exploring it.