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

Such universal channels exist.)So it remains to manufacture this bad situation.We need one further denition:De nition 2 T <kT 0 if T T 0 (This inclusion is among multisets of packets.) 9 packet p s.t. mult(p T ) < mult(p T 0) k )(mult(p T ) denotes the multiplicity of p within the multiset T ).Lemma 2 If is valid, and T is a multiset of packets in transit after, then either4001. there exists a k -extension such that themultiset of packetsreceived by Ar in is a submultiset of T , or2.

there exists a valid execution 0 = such that(a) all packets received in are sent in , and(b) 9 a new multiset T 0 of packets in transitafter 0 such thatT <kT 0.Suppose that this lemma is true.We then show that there is some valid 1, and a multisetT1 of packets in transit after1 such that case 1 holds.As we already argued, the existence of such 1 andT1 leads to the desired contradiction.For this we dene two sequences i and Ti with equal to the empty sequence and T empty.If condition 1 does not hold for and T (i.e.,for i = 0)we are in the situation of case 2.We then set = 0 and T = T 0.In general, assuming that case 1 does not hold for i andTi, we are then in case 2 and derive a valid extensioni of i and a multiset Ti of packets intransit after i(Ti <k Ti ).But, by denition of the< relation,kthe sequence T <kT <k : : : <kTi<k : : :can have at most kjP j terms.Its last term is the T1 we are looking for.(jP j is the number of dierent possible packets, which is nitebecause we assumed that the packet alphabet and the size of theheaders are bounded.)000101+1+1+1+101401Proof: (of Lemma 2)Pick any m, and get a k-extension for m, bythe k-boundedness condition.If the multiset of packets received by Ar is included in T weare in case (a).Otherwise there is some packet p for which the multiplicityof rec-pkt(p) actions in is bigger thenmult(p T ).We then set T 0 = T fpg.Since the extension is k-bounded, the number ofof these rec-pkt(p) is at most k so thatmult(p T 0) k.We now want to get a valid extension 0 of leaving the packets from T 0 in transit.We know that there is a send-pkt(p) action in (since all packets received in were sent in ).Consider then a prex of ending with therst such send-pkt(p).

(See Figure B.1.)send(p)ααrec(p)βγFigure B.1: An extension of with a send ; pkt(p) actionAfter all packets from T 0 are still in transit.We want to extend to a valid execution withoutdelivering any packet from T 0.There are three cases.First, suppose that both the send-message and receive-message eventsfrom appear in then itself suces.402Second, suppose that only the send-message, but not thereceive-message event appears in .To get validity we need to deliver m, which is the onlyundelivered message, without delivering a packet from T 0.We can achieve this because of a basic property of live executions inthis architecture: for any nite execution, there is a liveextension that contains no new send-message events and that does notdeliver any old packets.Because of the correctness condition, this must eventually deliverm.The needed sequence stops just after the receive-message event.Third and nally, suppose that neither the send-message nor thereceive-message event appears in .Then add a new send-message event just after , andextend this just as in the previous case to get the needed valid extension.B.1.2 Tolerating Node CrashesThe results above settle pretty much all the cases for reliable nodes.Now we add consideration of faulty nodes.This time, we consider node crashes that lose information.We give two impossibility results, then show a practical algorithmused in the internet.Impossibility ResultsConsider the case where each node has an input action crash,and a corresponding output recover .When a crash occurs, a special crash ag just gets set, and nolocally controlled actions other than recover can be enabled.At some later time, a corresponding recover action is supposedto occur when this happens, the state of the node goes back to anarbitrary initial state.Thus, the crash causes all information to be lost.403In such a model, it is not hard to see that we can't solve thereliable communication problem, even if the underlying channels arecompletely reliable (FIFO, no loss or duplication).Proof:Consider any live execution in which a singlesend (m) event occurs but no crashes.Then correctness implies that there is a later receive (m).Let 0 be the prex ending just before this receive (m).Now consider 0 followed by the events crash r recover r .By basic properties of the model,this can be extended to a live execution , in which nofurther send-message events or crashes occur.Since must also satisfy the correctness conditions, it mustbe that contains a receive (m) event correspondingto the given send (m) event, sometime after the given crash.Now take the portion of after the crash-recover,and splice it at the end of the nite execution0receive (m)crash r recoverr .Claim that the result is another live execution.But this execution has two receive (m) events, a contradiction to thecorrectness conditions.1111Thus, the key idea is that the system cannot tell whether a receiver crashoccurred before or after the delivery of a message.Note that a key fact that makes this result work is the separationbetween the receive (m) event and any other eect such assending an acknowledgement.We could argue that the problem statement is too strong for the caseof crashes.Now we weaken the problem statement quite a lot, but still obtain animpossibility result (though it's harder to prove).We continue to forbid duplication.We allow reordering, however.And, most importantly, we now allow loss of messages sent before thelast recover action.Messages sent after the last recover must be delivered, however.404We describe the underlying channels in as strong a way as possible.Thus, we insist that they are FIFO and don't duplicate.All they can do is lose messages.The only constraint on losing messages is the liveness constraint:innitely many sends lead to innitely many receives.(or a port version of this).Now it makes sense to talk about a sequence of packets being\in transit" on a channel.By this we mean that the sequence is a subsequence of all the packetsin the channel (sent after the sending of the last packet delivered).Notation:If is an execution, x 2 fs rg, 0 k jj,then dene:in ( x k) to be the sequence of packets received by Axduring the rst k steps of ,out ( x k) to be the sequence of packets sent by Axduring the rst k steps of ,state ( x k ) to be the state of Ax after exactly ksteps of , andext ( x k ) to be the sequence of external actions of Axoccurring during the rst k steps of .Dene x$ to be the opposite node to x.Lemma 3 Let be any crash-free nite execution, of length n.

Let x be either node, and let0 k n. Suppose that either k = 0 or else the kth action in is an action of Ax. Thenthere is a nite execution 0(possibly containing crashes) that ends in a state in which:1. the state of x is state ( x k),2. the state of x$ is state ( x$ k), and3. the sequence out ( x k ) is in transit from x.Proof: Proceed by induction on k.k = 0 is immediate { use the initial conguration only.Inductive step:405Suppose true for all values smaller than k > 0 and prove for k.Case 1: The rst k steps in are all steps of Ax.Then the rst k steps of suce.Case 2: The rst k steps in include at least one step ofAx.Then let j be the greatest integer k such that the kthstep is a step of Ax.Note that in fact j < k since we have assumed the kth step is astep of Ax.Then in ( x k) is a subsequence ofout ( x$ j ), andstate ( x$ k) = state ( x$ j ).By inductive hypothesis, we get an execution that leads thetwo nodes to state ( x j ) andstate ( x$ j ), respectively, and that hasout ( x$ j ) in transit from x$ to x.This already has x$ in the needed state.Now run Ax alone { let it rst crash and recover, going back toits initial state in .Now let it run on its own, using the messages inin ( x k ), which are available in the incoming channel sincethey are a subsequence of out ( x$ j ).This brings x to the needed state and puts the needed messages inthe outgoing channel.1Now we nish the proof.Choose (length n) to be a crash-free execution containing onesend (m) and its corresponding receive (m) (must exist).Now use to construct an execution whose nal node states arethose of ,and that has a send as the last external action.How to do this:Let k be the last step of occurring at the receiver (mustexist one, since there is a receive event in .406Then Lemma yields an execution 0 ending in the node statesafter k steps, and with out ( r k) in transit.Note that state ( r k) = state ( r n).Now crash and recover the sender, and then have it run again fromthe beginning, using the inputs in in ( s n), which are asubsequence of the available sequence out ( r k).This lets it reach state ( s n).Also, there is a send step, but no other external step, inthis sux.This is as needed.Now we get a contradiction.Let be the execution obtained above, whose nal nodestates are those of ,and that has a send as the last external action.Now lose all the messages in transit in both channels, then extend to a live execution containing no further send or crashevents.By the correctness, this extension must eventually deliver the lastmessage.Now claim we can attach this sux at the end of , and itwill again deliver the message.But alread had an equal number of sends and receives (one ofeach), so this extra receive violates correctness.QED11This says that we can't even solve a weak version of the problem, whenwe have to contend with crashes that lose all state information.B.2 5-packet Handshake Internet ProtocolBut note that it is important in practice to have a message deliveryprotocol that can tolerate node crashes.Here we give one important example, the 5-packet handshake protocol ofBelsnes (used in the Internet).This does tolerates node crashes.407It uses a small amount of stable storage in the form of unique ID's {think of this as stable storage because even after a crash, the system\remembers" not to reuse any ID.Underlying channels can reorder, duplicate (but only nitely manytimes), and lose.Yields no reordering, no duplication (ever), and always deliversmessages sent after the last recovery.The ve-packet handshake protocol of Belsnes is one of a batchhe designed, getting successively more reliability out of successivelymore messages.