Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 64
Текст из файла (страница 64)
Similar forms of counter ushing can be used toimplement Data Links (AfekB89]) and token passing DolevIM91:unbound]) between a pairof nodes. Counter ushing is, however, not limited to rings or pair of nodes. Katz and Perry311KatzP90] extend the use of counter ushing to arbitrary networks in an ingenious way.The stabilizing end-to-end protocol (APV-91]) is obtained by rst applying local correctionto the Slide protocol AGR92:slide] and then applying a variant of counter ushing to theMajority protocol of AGR92:slide].23.4 Message Passing ModelHaving understood the techniques of counter ushing and local checking and correction in ashared memory model, we move to a more realistic message passing model. The work in thenext three sections is based on V92], which formalizes the ideas introduced in APV-91].
Tomodel a network protocol, we will model the network topology, the links between nodes, andthe nodes themselves. Our model is essentially the standard asynchronous message passingmodel except for two major dierences: The major dierence is that links are restricted to store at most one packet at a time. We assume that for every pair of neighbors, there is some a priori way of assigning oneof the two nodes as the \leader" of the pair.We will argue that even with these dierences our model can be implemented in realnetworks.23.4.1 Modeling the TopologyWe will call a directed graph (V E ) symmetric if for every edge (u v) 2 E there is an edge(v u) 2 E .Denition 3 A topology graph G = (V E l) is a symmetric, directed graph (V E ) togetherwith a leader function l such that for every edge (u v) 2 E , l(u v ) = l(v u) and eitherl(u v) = u or l(u v) = v.We use E (G) and V (G) to denote the set of edges and nodes in G.
If it is clear whatgraph we mean we sometimes simply say E and V . As usual, if (u v) 2 E we will call v aneighbor of u.23.4.2 Modeling LinksTraditional models of a data link have used what we call Unbounded Storage Data Links thatcan store an unbounded number of packets.
Now, real physical links do have bounds on the312Each p belongs to the packet alphabet P dened above.The state of the automaton consists of a single variable Q 2 P nil.u vSend (p) (*input action*)u vEect:If Q = nil then Q := pu vu vFree (*output action*)u vPrecondition: Q = nilEect: Noneu vReceive (p) (*output action*)Precondition: p = Q =6 nilu vEect: Q := nilu vu vThe Free and Receive actions are in separate classesFigure 23.7: Unit Storage Data Link automatonnumber of stored packets.
However, the unbounded storage model is a useful abstraction ina non-stabilizing context.Unfortunately, this is no longer true in a stabilizing setting. If the link can store anunbounded number of packets, it can have an unbounded number of \bad" packets in theinitial state.
It has been shown DolevIM91:unbound] that almost any non-trivial task isimpossible in such a setting. Thus in a stabilizing setting it is necessary to dene Data Linksthat have bounded storage.A network automaton for topology graph G consists of a node automaton for every vertexin G and one channel automaton for every edge in G. We will restrict ourselves to a specialtype of channel automaton, a unit storage data link or UDL for short.
Intuitively, a UDLcan only store at most one packet at any instant. Node automata communicate by sendingpackets to the UDLs that connect them. In the next section, we will argue that a UDL canbe implemented over real physical channels.We x a packet alphabet P . We assume that P = Pdata Pcontrol consists of two disjointpacket alphabets.
These correspond to what we call data packets and control packets. Thespecication for a UDL will allow both data and control packets to be sent on a UDL.Denition 4 We say that Cu v is the UDL corresponding to ordered pair (u v) if Cu v is theIOA dened in Figure 23.7.Cu v is a UIOA since we have not dened any start states for Cu v . The external interface313to Cu v includes an action to send a packet at node u (Sendu v (p)), an action to receive apacket at node v (Receiveu v (p)), and an action Freeu v to tell the sender that the link isready to accept a new packet. The state of Cu v is simply a single variable Qu v that storesa packet or has the default value of nil.Notice two points about the specication of a UDL.
The rst is that if the UDL has apacket stored, then any new packet sent will be dropped. Second, the Free action is enabledcontinuously whenever the UDL does not contain a packet.23.4.3 Modeling Network Nodes and NetworksNext we specify node automata. We do so using a set that contains a node automaton forevery node in the topology graph. For every edge incident to a node u, a node automatonNu must have interfaces to send and receive packets on the channels corresponding to thatedge. However, we will go further and require that nodes obey a certain stylized conventionin order to receive feedback from and send packets on links.In the specication for a UDL if a packet p is sent when the UDL already has a packetstored, then the new packet p is dropped.
We will prevent packets from being dropped byrequiring that the sending node keep a corresponding free variable for the link that recordswhether or not the link is free to accept new packets. The sender sets the free variable totrue whenever it receives a Free action from the link. We require that the sender onlysend packets on the link when the free variable is true. Finally, whenever the sender sendsa packet on the link, the sender sets its free variable to false.We wish the interface to a UDL to stabilize to \good behavior" even when the senderand link begin in arbitrary states. Suppose the sender and the link begin in arbitrary states.Then we can have two possible problems.
First, if free = true but the UDL contains a packet,then the rst packet sent by the sender can be dropped. However, it is easy to see that allsubsequent packets will be accepted and delivered by the link. This is because after the rstpacket is sent, the sender will never set free to true unless it receives a Free noticationfrom the link. But a Free notication is delivered to the sender only when the link is empty.The second possible problem is deadlock.
Suppose that initially free = false but the channeldoes not contain a packet. To avoid deadlock, the UDL specication ensures that the Freeaction is enabled continuously whenever the link does not contain a packet.A formal description of node automata can be found in V92]. We omit it here. Finallya network automaton is the composition of a set of node and channel automata.314SEND (p)Physical ChannelRECEIVE (p)queueFREEData Link SenderData Link ReceiverFigure 23.8: Implementing a UDL over a physical channel23.4.4 Implementing the Model in Real NetworksIn a real network implementation, the physical channel connecting any two neighboring nodeswould typically not be a UDL.
For example, a telephone line connecting two nodes can oftenstore more than one packet. The physical channel may also not deliver a free signal. Instead,an implementation can construct a Data Link protocol on top of the physical channel suchthat the resulting Data Link protocol stabilizes to the behaviors of a UDL (e.g. AfekB89],S-89]).Figure 23.8 shows the structure of such a Data Link protocol over a physical link. Thesender end of the Data Link protocol has a queue that can contain a single packet. Whenthe queue is empty, the Free signal is enabled. When a Send(p) arrives and the queue isempty, p is placed on the queue if the queue is full, p is dropped. If there is a packet on thequeue, the sender end constantly attempts to send the packet.
When the receiving end ofthe Data Link receives a packet, the receiver sends an ack to the sender. When the senderreceives an ack for the packet currently in the queue, the sender removes the packet fromthe queue.If the physical channel is initially empty and the physical channel is FIFO (i.e., doesnot permute the order of packets), then a standard stop and wait or alternating bit protocolBSW-69] will implement a UDL. However, if the physical channel can initially store packets,then the alternating bit protocol is not stabilizing S-89]. There are two approaches tocreating a stabilizing stop and wait protocol.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
