The number of times that a node can improve the maintained path to the
root is at most the difference between the shortest path from that node to the
root and the longest path from that node to the root.
Each node sends updates to all neighbors (except the sender) when it receives an update with a shorter path than it has ever received. The paths may be received in decreasing order of lengths, and therefore the total number of messages is no more than:
The number of times that a node can improve the maintained path to the
root is at most the number of different paths from that node to the root. This
is because the link weights may be unique, and so can be the path weights.
Each node sends updates to all neighbors (except the sender) when it receives an update with a lesser weight path than it has ever received. The paths may be received in decreasing order of weights, and therefore the total number of messages is no more than:
If the processors do not know n, then for the input X0(2t+1)||X1(2t+1) (where t is greater than the locality of computing f(X0) and f(X1) ), there is a node to which the ring looks locally the same as X0, and there is a node to which the ring looks locally the same as X1. Therefore, f(X0) must equal f(X1).
We will prove for a synchronous ring, and the result for an asynchronous ring will follow.
Assume by way of contradiction that f is non-constant. That is, there are two inputs, X0 and X1, of lengths n0 and n1, for which f(X0)=0, f(X1)=1, respectively. Let the time (number of rounds) after which all processors halt on any of the two inputs be at most t. Then the locality of computing f(X0) is at most t, and so is the locality of computing f(X1). This means (since f is cyclic) the output of each processor depends on the input of itself and of processors at most t hops away. Let Y be some input of length m and let X2 be the input X0^(2t+1)||Y||X1^(2t+1). Then the output of processor 1 when computing f(X0) is identical to the output of processor tn0+1 when computing f(X2), since the inputs of the processor under discussion and processors t hops away from it in the computation of f(X0) are the same as in the computation of f(X2). The same argument applies to the output of processor 1 when computing f(X1) and the output of processor 2tn0+m+tn1+2 when computing f(X2). It follows that two processors that compute f(X2) output different values – a contradiction.
A deterministic algorithm cannot break symmetry in an initial
configuration in which half of the processors have one of their incident links
leading towards the successor processor and their other incident link leading
towards the predecessor processor and the other half of the processors in the
reverse direction, and achieve an asymmetric markings as output.
We will prove for a synchronous ring, and the result for an asynchronous ring will follow.
Assume, by way of contradiction, that such algorithm exists for an even
n. Let 
such that 
if processor i has one
of its incident links leading to processor (i+1)(mod n) and the other leading
to processor (i-1)(mod n), and 
otherwise (1<=i<=n).
We first prove, by induction on k, that if there are i, j, k (1<=i,j<=n, k>=0), such that the following 2k+1 equations hold:
…
Then at round k, processor i enters the same state as processor j:
For k=1, processors i and j receive no messages at round 1. Since all processors are identical, processors i and j start in the same initial state. Therefore, at round 1 they will enter the same state. Assume that if there are i, j, k such that the 2k+1 equation hold then at round k, processor i enters the same state as processor j. If there are i, j, k+1 such that 2k+3 equation hold, it follows that at round k, processor (i-1)(mod n) enters the same state as (j-1)(mod n), processor i enters the same state as processor j, and processor (i+1)(mod n) enters the same state as processor (j+1)(mod n). This means that at round k processor (i-1)(mod n) and processor (j-1)(mod n) send the same messages, and so do processor (i+1)(mod n) and processor (i+1)(mod n). As results, at round k processors i and j receive the same messages from the same directions (from their respective points of view), and therefore processors i and j enter the same state at round k+1.
If X=1^(n/2)||0^(n/2), then the condition holds for i=1,j=n,k=n/2, which means that it holds for any k, including k>t – where t is the locality of the algorithm. Therefore, processors 1 and n will both output the same markings, although their links are opposite.
Such algorithm exists. The algorithm creates segments of nodes with the same orientation. When two nodes that belong to segments with opposite orientation discover that they are neighbors, the node that belongs to the shorter segment switches its orientation and joins the longer segment. The algorithm solves ties using the symmetry breaking markings.
UPON RECEIVING WAKE
if state != awake
then mark my incident links arbitrarily
state <-- awake
left_segment <-- -1
my_segment <-- 1
send WAKE on the link marked L
send RIGHT(my_segment) on the link
marked R
UPON RECEIVING RIGHT(length) ON
l
if state = awake
then if l is marked R
then
if (length > my_segment) OR
(
(length = my_segment) AND
l's head is not
towards me
)
then if (my_segment = 1) AND
(
(left_segment > length) OR
(
(left_segment =
length) AND
l's head is
towards
me
)
)
then my_segment <-- left_segment
send
RIGHT(my_segment) on the link
marked
R
else switch L and R markings
my_segment
<-- length + 1
send
RIGHT(my_segment) on the link
marked R
else
left_segment <-- length + 1
else mark l as L and the other link as R
my_segment <- length + 1
send RIGHT(my_segment) on the link
marked R
When a node invites its right neighbor to join its segment, the node tosses a fair coin and sends the result with the invitation. If the neighbor needs to break symmetry, it tosses its own coin and compares the two results. If they are equal, another round of the coin tossing is performed, until exactly one of the nodes gets "1" and captures the other.
UPON RECEIVING WAKE
if state != awake
then mark my incident links arbitrarily
state <-- awake
left_segment <-- -1
my_segment <-- 1
send WAKE on the link marked L
send RIGHT(my_segment, coin_toss()) on
the link marked R
UPON RECEIVING RIGHT(length,
other_coin) ON l
my_coin <-- coin_toss()
if state = awake
then if l is marked R
then
if (length > my_segment) OR
(
(length =
my_segment) AND
(my_coin <
other_coin)
)
then if (my_segment = 1) AND
(
(left_segment >
length) OR
(
(left_segment =
length) AND
(my_coin >
other_coin)
)
)
then my_segment <-- left_segment
send RIGHT(my_segment, 2)
on the
link marked R
else switch L and R markings
my_segment
<-- length + 1
send
RIGHT(my_segment, coin_toss())
on the
link marked R
else if (my_length = length) AND
(my_coin =
other_coin)
then send TRY_AGAIN on the link marked R
else
left_segment <-- length + 1
else mark l as L and the other link as R
my_segment <- length + 1
send RIGHT(my_segment, coin_toss()) on
the link marked R
UPON RECEIVING TRY_AGAIN
send RIGHT(my_segment, coin_toss())
on the link marked R
Each node sends a token on a non-traversed link. When the node receives the token over that link, the sub-graph that is reachable from that link has been traversed, and the node sends the token on the next non-traversed link, or (if none exists) on the link on which it first received the token. In order to visit all the nodes the token must traverse all the links of the network, since there might have been a node on the center of any non-traversed link, causing the algorithm to fail.
|
|
|
|
|
|
Each node sends exactly one token on each incident link, since tokens are only sent on the following kinds of links:
1. The parent link: Each node has at most one such link, and if it has one:
1.1. This link is marked.
1.2. The node eventually sends a token on that link.
1.3. The node sends no more tokens afterwards.
2. Non-marked links: Initially, all the links are not marked. Each node
eventually sends a token over each such link, and when it does, that link is
marked before the next token is sent.
There is always exactly one token in transit.
Each node first sends the Token on all forward links simultaneously. This prevents neighbors from spending time on traversing links that are not part of the tree.
|
|
|
|
|
|
If a node that has an active link receives the token from a neighbor other than its parent, then the path of active links leads to the sender. The token backtracks on that path, and the nodes it passes through mark this path as a candidate path towards a node that has an active link. If a node that has no active links receives the token, then there is a path of marked links from it to a node that does have an active link.
I have provided a solution assuming that nodes have no unique ids.
Initially
state <-- unvisited
parent <-- nil
initiator <-- false
relay <-- false
FirstTime <-- true
root
if there is a non-traversed link l
then state <-- active
Participated_in_backtracking <-- false
activelink <-- l
Token.direction <-- forward
send Token on activelink
else finished global
all nodes
UPON RECEIVING TOKEN ON l
if state != active
then Participated_in_backtracking <--
false
parent <-- l
pick a non-traversed link r
activelink <-- r
send Token on activelink
else If Token.direction = forward
then Token.direction <-- backtrack
initiator <-- true
Token.ParityBitRelayWinner = (0|0|false|false)
if activelink != nil
then send Token on activelink
else send Token on markedlink
else if activelink != nil
then if not Participated_in_backtracking
AND
(l = parent)
then Token.New_candidate <-- true
Participated_in_backtracking <-- true
if Token.New_candidate
then markedlink <-- activelink
if initiator
then if not Token.Relay AND not
FirstTime
then Token.ParityBitRelayWinner
= (0|0|false|true)
initiator <-- false
relay <-- false
FirstTime <-- false
else
Token.ParityBitRelayWinner =
(Token.Bit|0|false|false)
else if relay
then if Token.winner
then initiator <-- false
relay <-- false
FirstTime <-- false
else if Token.winner
then initiator <-- false
relay <-- false
FirstTime <-- false
Token.New_candidate
<-- false
if there is a non-traversed link r
then activelink <-- r
Token.direction = forward
else
activelink <-- nil
if parent = nil
then finished global
else initiator <-- true
Token.ParityBitRelayWinner =
(0|0|false|false)
else if not FirstTime AND
(parity !=
Token.parity)
then relay <-- true
Token.Relay = true
else FirstTime <--
false
Token.Bit = !Token.Bit
parity <--
Token.Bit
if activelink != nil
then send Token on activelink
else send Token on markedlink
The initiators are like cores in Gallager's algorithm: each one starts at level zero and sends a traverse token that marks lower level nodes with the initiator's id and level.
A token that encounters a node with a higher level mark vanishes.
A token that encounters a node with the same level mark either waits until the token that marked that node backtracks or proceeds towards that token, depending on the ids. Eventually the two tokens meet and vanish, and the node in which they met becomes an initiator in a higher level.
Exactly one initiator completes a full traversal and issues another traversal to announce its election.
UPON RECEIVING WAKE
if owner = nil
then if there is a non-traversed
link l
then level <-- 0
owner <-- my_id
Token.level <-- level
Token.id <-- owner
active_link <-- l
send Token on l
UPON RECEIVING TOKEN ON l
mark l traversed
if (level = Token.level) and
(owner = Token.id) and
waiting
then Token.level++
Token.id = my_id
parent <-- nil
else if (level < Token.level)
then parent <-- l
if (level < Token.level)
then level <-- Token.level
owner <-- Token.id
waiting <-- false
clear link markings
if level = Token.level
then if owner = Token.id
then if l != active_link
then mark l traversed
send Token on l
else mark l traversed
if there is a non-traversed link
r
then active_link <-- r
send Token on r
else if parent != nil
then send Token on parent
if Token.leader then
finished - The
leader is owner
else clear link markings
if Token.leader or
there are no incident links
then finished - I am
the leader
else Token.leader
<-- true
choose a
non-traversed link s
active_link
<-- s
send Token on s
else if (owner > Token.id) OR chased
then waiting <-- true
else Token.chased_id <-- owner
send Token on active_link