predecessors or merely slow predecessors.If an unprobed For each node u,we assume that it maintains a neighbors node simply assumes that it has no predecessors and that it set N.,which induces an underlying graph G with edges should pair with any successor that accepts it,the adversary (u,v)for all pairs with vE Nu.Initially N consists of those can schedule events so that every node in a long chain only nodes whose identity u knows at the start of the protocol.It learns of its unrequited predecessor after it has committed is updated by adding any node that sends u a probe message. to its successor,creating the linear-time backlog described Neighbor sets are merged when two nodes join into a single above.On the other hand,if a node chooses to wait for supernode.A neighbor that refuses a proposal is removed: a predecessor to come,it may be left stuck in this state this prevents a slow node from being pestered by arbitrarily forever. large numbers of duplicate proposals from a faster neighbor, The solution is to retain the coin-flip by which a node since the faster neighbor will only try again after the slow chooses its orientation,but let the presence of a successor node has rejoined its neighbor set (by sending out a probe who wants to pair now override the wait for a predecessor message after completing a merge). that may never arrive.In addition,the successor-pairing The algorithm is described below.It has a main thread procedure is modified slightly:instead of pairing all succes- which is responsible for the main function of the pairing. sors,possibly leaving none,a process always saves the first and four daemon threads which are triggered by messages successor for itself and pairs off only subsequent pairs.This and responsible for state transitions.The execution of the may leave an odd successor that is not paired,but there is at daemon threads should be implemented to be atomic.which most one such node left out for each node that participates is quite reasonable because there is no waiting in the daemon in the (now very implicit)randomized matching protocol.If threads and our model ignores the running time of a process. this left-out node is waiting for its predecessor,it will even- tually be picked up after the predecessor merges with its For each node u: preferred successor. What makes all of this work is that the randomization 1.Let state-ISOLATED:let chosen be picked uni- breaks up long waiting chains:it is unlikely that a long chain formly at random from ipred,suce. of nodes will all be pointed the same way by their coin-flips. 2.For each v Eneighbors,send a message (u,v,probe) At the same time,opportunistic merging by nodes with the to v and wait for all replies; first available suitor prevents deadlocks in cycles,even if all nodes are pointed in the same direction,as some node's 3.Let v,v2,...v be the nodes that reply with 'ac- proposal gets in first. cept.'For each odd i less than k,send a mes- sage (u,vi,pair,v+1)to vi and (u,vi+1,pair,vi) 3.1.1 Details of the Algorithm to vi+1.If k is odd,let succ-vk,and send a Formally,each node can be in one of four different states, message (u,succ,no_pair)to the node succ;else depending on what messages it has received.The four dif let chosen-pred; ferent states and their attitudes towards incoming pairing 4.While (state=ISOLATED or state=PROBED)wait: proposals are described as follows: 5.If state=PROPOSING then: ISOLATED:The node has not yet received any probes Send a message (u,chosen,propose)to the and has no predecessor.So once it receives a proposal node chosen; from its successor,it can accept it immediately. If reply is (chosen,u,accept)then let state←-PAIRED and obj←-chosen: PROBED:The node has been probed,but not yet been told whether it is paired off by its predecessor, else if reply is (chosen,u,reject-propose)then nor it has a pairable successor.In this case,it waits let neighbors-neighbors-ichosen to find out what its predecessor will do with it.If else if reply is (chosen,u,paired)then it receives a proposal from its successor and its coin is do nothing but proceed; also pointed to its successor,it enters the PROPOSED 6.If state=PAIRED,then merge with obj: state.If the proposal conflicts with its coin,it refuses the proposal immediately. 7.Go to line 1. PROPOSED:The node has a waiting proposal,but Upon receiving message (v,u,probe)from node v do: has not yet been told whether it is paired off by its Let neighbors-neighborsUfv; predecessor.It defers responding to the proposal until If state=ISOLATED then: its state changes due to the notice from its predecessor. Let pred-v and state-PROBED: PROPOSING:The node has a predecessor and has Send a message (u,v,accept)to node v; been told by the predecessor that it is not paired off. else: So the node should actively send out a proposal in Send a message (u,v,reject)to node v. the direction indicated by its coin and accept immedi- ately any proposal that does not conflict with its coin. Upon receiving message (v,u,propose)from node v Proposals that conflict with its coin are refused imme- do the one of the following according to the value of state: diately. ISOLATED:Let state--PAIRED and obj+v; PAIRED:The node has been paired,either by its pre- reply with (u,v,accept); decessor or due to coins.It refuses any proposals (al- PROBED:If chosen=v,then let waiting-v and though it may later be available for new proposals once state-PROPOSED: it has completed a merge operation with its partner). if otherwise,reply with (u,v,reject-propose);predecessors or merely slow predecessors. If an unprobed node simply assumes that it has no predecessors and that it should pair with any successor that accepts it, the adversary can schedule events so that every node in a long chain only learns of its unrequited predecessor after it has committed to its successor, creating the linear-time backlog described above. On the other hand, if a node chooses to wait for a predecessor to come, it may be left stuck in this state forever. The solution is to retain the coin-flip by which a node chooses its orientation, but let the presence of a successor who wants to pair now override the wait for a predecessor that may never arrive. In addition, the successor-pairing procedure is modified slightly: instead of pairing all succes￾sors, possibly leaving none, a process always saves the first successor for itself and pairs off only subsequent pairs. This may leave an odd successor that is not paired, but there is at most one such node left out for each node that participates in the (now very implicit) randomized matching protocol. If this left-out node is waiting for its predecessor, it will even￾tually be picked up after the predecessor merges with its preferred successor. What makes all of this work is that the randomization breaks up long waiting chains: it is unlikely that a long chain of nodes will all be pointed the same way by their coin-flips. At the same time, opportunistic merging by nodes with the first available suitor prevents deadlocks in cycles, even if all nodes are pointed in the same direction, as some node’s proposal gets in first. 3.1.1 Details of the Algorithm Formally, each node can be in one of four different states, depending on what messages it has received. The four dif￾ferent states and their attitudes towards incoming pairing proposals are described as follows: • ISOLATED: The node has not yet received any probes and has no predecessor. So once it receives a proposal from its successor, it can accept it immediately. • PROBED: The node has been probed, but not yet been told whether it is paired off by its predecessor, nor it has a pairable successor. In this case, it waits to find out what its predecessor will do with it. If it receives a proposal from its successor and its coin is also pointed to its successor, it enters the PROPOSED state. If the proposal conflicts with its coin, it refuses the proposal immediately. • PROPOSED: The node has a waiting proposal, but has not yet been told whether it is paired off by its predecessor. It defers responding to the proposal until its state changes due to the notice from its predecessor. • PROPOSING: The node has a predecessor and has been told by the predecessor that it is not paired off. So the node should actively send out a proposal in the direction indicated by its coin and accept immedi￾ately any proposal that does not conflict with its coin. Proposals that conflict with its coin are refused imme￾diately. • PAIRED: The node has been paired, either by its pre￾decessor or due to coins. It refuses any proposals (al￾though it may later be available for new proposals once it has completed a merge operation with its partner). For each node u, we assume that it maintains a neighbors set Nu, which induces an underlying graph G with edges (u, v) for all pairs with v ∈ Nu. Initially Nu consists of those nodes whose identity u knows at the start of the protocol. It is updated by adding any node that sends u a probe message. Neighbor sets are merged when two nodes join into a single supernode. A neighbor that refuses a proposal is removed: this prevents a slow node from being pestered by arbitrarily large numbers of duplicate proposals from a faster neighbor, since the faster neighbor will only try again after the slow node has rejoined its neighbor set (by sending out a probe message after completing a merge). The algorithm is described below. It has a main thread which is responsible for the main function of the pairing, and four daemon threads which are triggered by messages and responsible for state transitions. The execution of the daemon threads should be implemented to be atomic, which is quite reasonable because there is no waiting in the daemon threads and our model ignores the running time of a process. For each node u: 1. Let state←ISOLATED; let chosen be picked uni￾formly at random from {pred, succ}. 2. For each v ∈neighbors, send a message (u, v, probe) to v and wait for all replies; 3. Let v1, v2, . . . vk be the nodes that reply with ‘ac￾cept.’ For each odd i less than k, send a mes￾sage (u, vi, pair, vi+1) to vi and (u, vi+1, pair, vi) to vi+1. If k is odd, let succ← vk, and send a message (u, succ, no pair) to the node succ; else let chosen←pred; 4. While (state=ISOLATED or state=PROBED) wait; 5. If state=PROPOSING then: Send a message (u, chosen, propose) to the node chosen; If reply is (chosen, u, accept) then let state←PAIRED and obj←chosen; else if reply is (chosen, u, reject propose) then let neighbors←neighbors−{chosen} else if reply is (chosen, u, paired) then do nothing but proceed; 6. If state=PAIRED, then merge with obj; 7. Go to line 1. Upon receiving message (v, u, probe) from node v do: Let neighbors←neighbors∪{v}; If state=ISOLATED then: Let pred← v and state←PROBED; Send a message (u, v, accept) to node v; else: Send a message (u, v, reject) to node v. Upon receiving message (v, u, propose) from node v do the one of the following according to the value of state: ISOLATED: Let state←PAIRED and obj←v; reply with (u, v, accept); PROBED: If chosen=v, then let waiting← v and state←PROPOSED; if otherwise, reply with (u, v, reject propose);