DOC PREVIEW
MIT 6 826 - Reliable Messages and Connection Establishment

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Handout 25 1Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 — Principles of Computer SystemsHandout 25 April 23, 1997________________________________________________________________________Reliable MessagesThe attached paper on reliable messages is Chapter 10 from the book Distributed Systems:Architecture and Implementation, edited by Sape Mullender, Addison-Wesley, 1993. Itcontains a careful and complete treatment of protocols for ensuring that a message isdelivered at most once, and that if there are no serious failures it is delivered exactly onceand its delivery is properly acknowledged.Handout 25 2Chapter 10Reliable Messages andConnection EstablishmentButler W. Lampson10.1 IntroductionGiven an unreliable network, we would like to reliably deliver messages from asender to a receiver. This is the function of the transport layer of the ISO seven-layer cake. It uses the network layer, which provides unreliable message delivery,as a channel for communication between the sender and the receiver.Ideally we would like to ensure that• messages are delivered in the order they are sent,• every message sent is delivered exactly once, and• an acknowledgement is returned for each delivered message.Unfortunately, it’s expensive to achieve the second and third goals in spite ofcrashes and an unreliable network. In particular, it’s not possible to achieve themwithout making some change to stable state (state that survives a crash) everytime a message is received. Why? When we receive a message after a crash, wehave to be able to tell whether it has already been delivered. But if delivering themessage doesn’t change any state that survives the crash, then we can’t tell.So if we want a cheap deliver operation which doesn’t require writing stablestate, we have to choose between delivering some messages more than once andlosing some messages entirely when the receiver crashes. If the effect of a mes-sage is idempotent, of course, then duplications are harmless and we will choosethe first alternative. But this is rare, and the latter choice is usually the lesser ofThis chapter appeared in Distributed Systems, ed. S. Mullender, Addison-Wesley, 1993, pp 251-281.It is the result of joint work with Nancy Lynch and Jørgen Søgaard-Andersen.Handout 25 3two evils. It is called ‘at-most-once’ message delivery. Usually the sender alsowants an acknowledgement that the message has been delivered, or in case thereceiver crashes, an indication that it might have been lost. At-most-once mes-sages with acknowledgements are called ‘reliable’ messages.There are various ways to implement reliable messages. An implementation iscalled a ‘protocol’, and we will look at several of them. All are based on the ideaof tagging a message with an identifier and transmitting it repeatedly to over-come the unreliability of the channel. The receiver keeps a stock of good identifiersthat it has never accepted before; when it sees a message tagged with a goodidentifier, it accepts it, delivers it, and removes that identifier from the good set.Otherwise, the receiver just discards the message, perhaps after acknowledgingit. In order for the sender to be sure that its message will be delivered rather thandiscarded, it must tag the message with a good identifer.What makes the implementations tricky is that we expect to lose some statewhen there is a crash. In particular, the receiver will be keeping track of at leastsome of its good identifiers in volatile variables, so these identifiers will becomebad at the crash. But the sender doesn’t know about the crash, so it will go onusing the bad identifiers and thus send messages that the receiver will reject. Dif-ferent protocols use different methods to keep the sender and the receiver moreor less in sync about what identifiers to use.In practice reliable messages are most often implemented in the form of ‘con-nections’. The idea is that a connection is ‘established’, any amount of informationis sent on the connection, and then the connection is ‘closed’. You can think of thisas the sending of a single large message, or as sending the first message using oneof the protocols we discuss, and then sending later messages with increasingsequence numbers. Usually connections are full-duplex, so that either end cansend independently, and it is often cheaper to establish both directions at thesame time. We ignore all these complications in order to concentrate on theessential logic of the protocols.What we mean by a crash is not simply a failure and restart of a node. In prac-tice, protocols for reliable messages have limits, called ‘timeouts’, on the length oftime for which they will wait to deliver a message or get an ack. We model theexpiration of a timeout as a crash: the protocol abandons its normal operation andreports failure, even though in general it’s possible that the message in fact hasbeen or will be delivered.We begin by writing a careful specification S for reliable messages. Then wepresent a ‘lower-level’ spec D in which the non-determinism associated with los-ing messages when there is a crash is moved to a place that is more convenientfor implementations. We explain why D implements S but don’t give a proof,since that requires techniques beyond the scope of this chapter. With this ground-work, we present a generic protocol G and a proof that it implements D. Then wedescribe two protocols that are used in practice, the handshake protocol H andthe clock-based protocol C, and show how both implement G. Finally, we explainhow to modify our protocols to work with finite sets of message identifiers, andsummarize our results.Handout 25 4The goals of this chapter are to:• Give a simple, clear, and precise specification of reliable message delivery inthe presence of crashes.• Explain the standard handshake protocol for reliable messages that is usedin TCP, ISO TP4, and many other widespread communication systems, aswell as a newer clock-based protocol.• Show that both protocols can be best understood as special cases of a sim-pler, more general protocol for using identifiers to tag messages andacknowledgements for reliable delivery.• Use the method of abstraction functions and invariants to help in under-standing these three subtle concurrent and fault-tolerant algorithms, and inthe process present all the hard parts of correctness proofs for all of them.• Take


View Full Document

MIT 6 826 - Reliable Messages and Connection Establishment

Documents in this Course
Consensus

Consensus

10 pages

Load more
Download Reliable Messages and Connection Establishment
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Reliable Messages and Connection Establishment and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Reliable Messages and Connection Establishment 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?