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

But if p1fails, the others can be left waiting, either to receive the tentative 1 or the nal 1. Theymust do something at the end of the four rounds if they haven't decided yet.At this point, the literature is a little messy | elaborate protocols have been described,with many alternative versions. We give below the key ideas for the case where p1 has failed.After 4 rounds, every process p 6= p1 , even it has failed, is in one of the following states:decided 0,uncertain (hasn't decided, and hasn't received a round 2 \tentative 1" message),ready (hasn't decided, and has received a round 2 \tentative 1" message), ordecided 1.The important property of 3PC is stated in the following observation.Observation 1 Let p be any process (failed or not, including p1 ).

If p has decided 0, thenall nonfaulty processes (in fact, all processes) are either uncertain or have decided 0, and ifp has decided 1, then all nonfaulty processes are either ready or have decided 1.Using this observation, the non-failed processes try to complete the protocol. For instance, this could involve electing a new leader. One solution is to use p2 (and if this fails, touse p3 , etc.).

(This assumes that the processes know their indices.) The new leader collectsthe status info from the non-failed processes, and uses the following termination rule.1. If some process reports that it decided, the leader decides in the same way, and broadcasts the decision.2.

If all processes report that they are uncertain, then the leader decides 0 and broadcasts0.863. Otherwise (i.e., all are uncertain or ready, and at least one is ready), the leader continues the work of the original protocol from the \middle" of round 2. That is, it sendstentative 1 messages to all that reported uncertain, waits, and decides 1. (Notice thatthis cannot cause a violation of the validity requirement, since the fact that someonewas ready implies that all started with initial value 1.)Any process that receives a 0 or 1 message decides on that value.7.2.3 Lower Bound on the Number of MessagesIt is interesting to consider the number of messages that are sent in the protocol. In thissection we prove the following theorem Dwork-Skeen].Theorem 4 Any protocol that solves the commit problem, even with weak termination, sendsat least 2n ; 2 messages in the failure-free run starting with all 1's.Note that 2PC uses 2n ; 2 messages in the failure-free case, and therefore the result istight.The key idea in the lower bound is stated in the following lemma.Lemma 5 Let be the run where all processes start with 1, and there are no failures.

Thenthere must be a path of messages from every node to every other node.Before we prove Lemma 5, let us consider a special case. Consider the failure-free execution whose graph is depicted in Figure 7.5. Assume all processes start with 1 in .ρp1 11111110p4Figure 7.5: execution graphs for andfailure.ρ’0in the special case. Black square represents processIn , there is no path from p4 to p1. Consider now an alternative execution 0, in whichthe initial value of p4 is 0, and all processes stop when they rst \hear" from p4. (In otherwords, in 0, all the edges reachable from the node of p4 at time 0 are removed.) It isp1 0straightforward to show that regardless of the initial value of p4.

However, validityrequires that p1 decides 1 in , and 0 in 0, a contradiction.The general case proof uses the same argument.87Proof: By example. In , the decision of all processes must be 1, by termination andvalidity. If the lemma is false, then there is some pair of processes p q such that there is nopath of messages from p to q in . Thus in , q never learns about p. Now construct 0 byfailing every process exactly when it rst learns about p, and changing p's input to 0.

Theresulting run looks the same to q, i.e., 0, and therefore q decides 1 in 0, which violatesvalidity.The proof of Theorem 4 is completed by the following graph-theoretic lemma.Lemma 6 Let G be a communication graph for n processes. If each of i processes is connected to each of all the n processes (by a chain of messages), then there are at least n + i ; 2messages in the graph.Proof: By induction on i.Base case: i = 1.

The n ; 1 follows from the fact that there must be some message toeach of the n ; 1 processes other than the given process.Inductive step: assume the lemma holds for i. Let S be the set of i + 1 processes thatare joined to all n. Without loss of generality, we can assume that in round 1, at least oneof the processes in S sends a message. (If not, we can remove all the initial rounds in whichno process in S sends a message | what is left still joins S to all n.) Call some such processp.

Now consider the reduced graph, obtained by removing a single rst-round message fromp to anyone. The remaining graph connects everyone in S ; fpg to all n. By induction, itmust have at least n + i ; 2 edges. So the whole graph has at least n + i ; 2 + 1 edges, whichis n + (i + 1) ; 2, as needed.886.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchOctober 6, 1992Lecture 88.1 Asynchronous Shared MemoryIn this lecture we begin a new topic, which features a major switch in the avor of thealgorithms we study. Namely, we add the very important uncertainty of asynchrony | forprocesses, variable process speeds, and for messages, variable message delay.

We shall startthis part with shared memory rather than networks. These systems can be thought of as theasynchronous analog of PRAMs. At rst, as a simplifying assumption, we will not considerfailures: asynchrony is complicated enough to deal with.Before we can express any algorithm, or make any meaningful statement, we need todene a new computation model. We rst describe the model informally and consider anexample to gain some intuition only then will we come back to a more formal model.8.1.1 Informal ModelThe system is modeled as a collection of processes and shared memory cells, with externalinterface (see Figure 8.1).Each process is a kind of state machine, with a set states of states and a subset start ofstates indicating the initial states, as before.

But now it also has labeled actions describingactivities it participates in. These are classied as either input , output , or internal actions.We further distinguish between two dierent kinds of internal actions: those that involve theshared memory, and those which involve strictly local computation.There is no message generation function, since there are no messages in this model (allcommunication is via the shared memory).There is a transition relation trans , which is a set of (s s0) triples, where is the labelof an input, output, or local computation action. The triple (s s0) 2 trans says that from astate s, it is possible to go to state s0 while performing action .

(Note that trans is a relationrather than a function | this generality includes the convenience of nondeterminism.)We assume that input actions can always happen (technically, this is an input-enablingmodel). Formally, for every s and input action , there exists s0 such that (s s0) 2 trans .89Figure 8.1: shared memory system. Circles represent processes, squares represent shared memorycells, and arrows represent the external interface (i.e., the input and output actions).In contrast, output and local computation steps might be enabled only in a subset of thestates.

The intuition behind the input-enabling property is that we think of the input actionsas being controlled by an arbitrary external user, while the internal and output actions areunder the control of the system.Shared memory access transitions are formalized dierently. Specically, the transitionshave the form ((s m) (s0 m0)), where s s0 are process states, and m m0 are shared memorystates.

These describe changes to the state and the shared memory as a result of accessingthe shared memory from some state. A special condition that we impose here is that theenabling of a shared memory access action should depend on the local process state only,and not on the contents of shared memory however, the particular response, i.e., the changeto the states of the process and of the shared memory, can depend on the shared memorystate.

Formally, this property is captured by saying that if is enabled in (s m), then forall memory states m0, is enabled in (s m0). In particular cases, the accesses are furtherconstrained.The most common restriction is to allow access only one location to be involved in asingle step. Another popular restriction is that all accesses should be of type read or write.A read just involves copying the value of a shared memory location to a local variable, whilea write just involves writing a designated value to a shared memory location, overwritingwhatever was there before.An execution is modeled very dierently from before.

Now processes are allowed to takesteps one at a time, in arbitrary order (rather than taking steps in synchronized rounds).90This arbitrariness is the essence of asynchrony. More formally, an execution is an alternatingsequence s0 s1 : : :, consisting of system states (i.e., the states of all the processes and ofthe shared memory), alternated with actions (each identied with a particular process),where successive (state, action, state) triples satisfy the transition relation. An executionmay be a nite or an innite sequence.There is one important exception to the arbitrariness: we don't want to allow a processto stop when it is supposed to be taking steps.

This situation arises when the process is ina state in which any locally controlled action (i.e., non-input action) is enabled. (Recall thatinput actions are always enabled however, we will not require that they actually occur.) Apossible solution is to require that if a process takes only nitely many steps, its last steptakes it to a state in which no more locally controlled actions are enabled.

But that is notquite sucient: we would like also to rule out another case, where a process does innitelymany steps but after some point all these steps are input steps. We want to make sure thatthe process itself also gets turns. But we have to be careful in saying this: consider thescenario in which innitely many inputs occur, and no locally-controlled actions, but in factno locally controlled actions are enabled. That seems OK, since vacuously, the process had\chances" to take steps but simply had none it wanted to take. We account for all thesepossibilities in the following denition. For each process i, either1. the entire execution is nite, and in the nal state no locally controlled action of processi is enabled, or2. the execution is innite, and there are either innitely many places in the sequencewhere i does a locally controlled action, or else innitely many places where no suchaction is enabled.We call this condition the fairness condition for this system.We will normally consider the case where the execution is fair.