Distributed Computing, COMP 4001 1
Leader Election in the Ring
(Part 2)
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 2
Outline
• Non-Comparison Based Algorithms – Time Slice
– Variable Speeds
• Lower Bounds
• Randomized
– identity selection – Leader election
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 3
Comparison of Leader Election Algorithms
• Resulting Tradeo↵s
Algorithm
Rounds
Time
# Messages
TimeSlice
O(uminn)
O(uminn)
O(n) O(n)
VariableSpeed
O(2umin n)
O(2umin n)
Randomized
O(log n)
O(n)
O(n log n)
where ui denotes the i-th node’s identifier and umin the minimum identifier among the node identifiers.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 4
Non-Comparison Based
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 5
Time Slice Algorithm
• Uses the strong assumption that
– the ring size n is known to all the processes (non-uniform).
• It assumes unidirectional communication.
• It elects the process with the minimum user ID.
• Assumes processor IDs are natural numbers.
– Each process i has the ID ui (unknown to the rest of the
processors).
• Employs synchrony in a deeper way in that – it uses a token to convey information.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 6
Time Slice Algorithm: Searhing for IDs!
• Employs a circulating token, carrying an ID around the ring. Token
• Let v denote the phase: Starting from v = 1 and each phase incrementing by 1, it attempts to elect v as leader.
• For v = 1,2,…: in phase v only a token carrying ID v is permitted to circulate.
• Processor IDs are unknown to other processors (and can be large numbers).
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 7
Time Slice Algorithm
1. Computation proceeds in phases 1, 2, . . . and each phase consists of n consecutive rounds (we use n is known).
2. Each phase devoted to the possible circulation, all the way around the ring, of a token carrying a particular value. @Nodes check if their ID is equal to the value of the token.
3. In phase v, which consists of rounds (v 1)n+1,…,vn, only a token carrying value v is permitted to circulate.
4. If a process i with ID equal to v exists, and round
(v 1)n + 1 is reached then process i elects itself the leader and sends a token carrying its ID around the ring.
5. As this token travels, all the other processes note that they have received it, which prevents them from electing themselves as leader or initiating the sending of a token at any later phase.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
1.e., you assume the nodes have
MAC
addresses
:
in the NetworkCard
Distributed Computing, COMP 4001 8
Example of Time Slice Algorithm
• A token carrying a certain value circulates around the ring.
Token
Value is v
1. Phase v = 1: Token carrying ID equal to 1 circulating around the ring; nodes check if their ID is equal to 1;
2. Phase v = 2: Token carrying ID equal to 1 circulating around the ring; nodes check if their ID is equal to 1;
3. etc.
• Note that in each phase, it takes n steps for the token to go around the ring.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 9
Correctness of Time Slice Algorithm
• The minimum ID umin eventually getscall the way around, which causes its originating process to become elected.
– No messages are sent before round (umin 1)n + 1, and – no messages are sent after round uminn.
• The total number of messages sent is just n.
– These are the non-null messages of the node with minimum
ID umin claiming to be the leader.
• If we prefer to elect the process with the maximum ID rather than the process with the minimum, we can simply let the minimum send a special message around after it is discovered in order to determine the maximum.
• The communication complexity is still O(n).
ume
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
E *l
‘
–
P
e
o
–
e
7 •
→; toffee
–
it •←
or
‘
Distributed Computing, COMP 4001 10
Correctness of Time Slice Algorithm
• The good property of the TimeSlice algorithm is that the total number of messages is n.
• Unfortunately, the time complexity is about numin, which is an unbounded number, even in a fixed-size ring.
• This time complexity limits the practicality of the algorithm.
• It is only useful in practice for small ring networks in which IDs are assigned from among the small positive integers.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 11
Variable Speed Algorithm
• Employs circulating tokens (as many tokens as nodes) carrying certain IDs.
Token
• Each process i has the ID ui (unknown to the rest of the processors).
• Process i initiates a token, which travels around the ring, carrying the ID ui of the originating process i.
• Di↵erent tokens travel at di↵erent speeds.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 12
Variable Speed Algorithm
1. Each process i initiates a token, which travels around the ring, carrying the value ui of the ID originating process i.
2. Di↵erent tokens travel at di↵erent speeds.
• A token with value v travels at the speed of one message transmission per 2v rounds, that is, each process along its path waits 2v rounds after receiving the token before sending it out. /* a token with value v takes time n2v to circulate around the ring (if it does) */
3. Each process keeps track of the smallest value it has seen so far and simply discards any token carrying an identifier that is larger than this smallest one.
4. If a token returns to its originator the originator is elected leader.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 13
Correctness of Variable Speed Algorithm
• Algorithm guarantees that
– by the time the token carrying the smallest identifier umin
gets all the way around the ring,
– the second smallest identifier could only get at most halfway around, the third smallest could only get at most a quarter of the way around, and in general,
– the kth smallest could only get at most 1/2k 1 of the way around.
• Therefore, up to the time of election, the token carrying umin uses more messages than all the others combined.
• Since umin uses exactly n messages, the total number of messages sent, up to the time of election, is less than 2n.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 14
Correctness of Variable Speed Algorithm
• By the time umin gets all the way around the ring, all nodes know about this value, and so will refuse to send out any other tokens.
• It follows that 2n is an upper bound on the total number of messages that are ever sent by the algorithm (including the time after the leader output).
• The time complexity, as mentioned above, is n2umin , since each node delays the token carrying ID umin for 2umin time units.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 15
Leader Election Lower Bound
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 16
Comparison Based Algorithms
• An algorithm is comparison based if it behaves the same on rings that have the same order pattern of the identifiers.
– in two rings with corresponding processors p1, p2, . . . , pn and q1, q2, . . . , qn the actions of the algorithm depend only on the order of the identifiers ID(p1), ID(p2), . . . , ID(pn) and ID(q1), ID(q2), . . . , ID(qn), respectively.
• We have seen that the best comparison based algorithm achieves the following bounds:
– communication complexity of O(n log n) messages, and
– time of O(n).
Growth
Radius
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 17
Non-Comparison Based Algorithms
• Non-comparison based algorithms, on the other hand, use O(n) messages, but (can) have a huge running time.
• A lower bound of ⌦(n log n) messages can be shown for
1. comparison based algorithms; lower bound holds even if we assume that communication is bidirectional and the ring size n is known to the processes
2. non-comparison based algorithms: with bounded time complexity (i.e., bounded number of rounds).a
• In the sequel we discuss only the first bound for comparison based algorithms.b
aThis can be proved using Ramsey Theory.
bGreg N. Frederickson and Nancy A. Lynch. Electing a leader in a syn- chronous ring. Journal of the ACM, 34(1):98-115, January 1987.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 18
The Plan: What Are We Going to Do?
• Assume we are given a uniform (n is unknown) algorithm A that solves the above comparison based variant of the leader election problem.
• We will show that there exists an admissible execution (i.e., an execution that conforms to the model being considered) of A in which ⌦(n log n) messages are being sent.
– So not all executions will satisfy this ⌦(n log n) lower bound condition!
• Theorem 1 For any comparison based leader election algorithm on a ring of size n there is an execution of the algorithm in which ⌦(n log n) messages are being sent.
Ok
.
IE
.
log
n
)
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 19 How Do You Prove a ⌦(nlogn) Lower Bound?
• The quantity being considered is the following: M(n) = “the number of messages required to elect a leader in an n-node ring”.
• This means that we m1ust find a constant c > 0 independent of n such that
M (n) cn log n,
about
• But how do we accomplish this task? c independentof n
-we – Using a recurrence!
do
not really care
ago
for all n.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
1. Split LE(n) into two subproblems LE(n/2). :;
Distributed Computing, COMP 4001
20
• We will show that I• What does this mean?
A Simple Recurrence
M(n) 2M(n/2) + n/4 • Lets denote our problem LE(n):
(1)
– Leader Election in a ring of size n.
• One way to interpret Inequality (1) is the following:
2. Show that the number of messages required to solve LE(n) is at least the number of messages required to solve two LE(n/2) problems plus n/4.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 21
What Does it Mean to Split?
• From our definition M(n/2) = “the number of messages required to elect a leader in an n/2-node ring”.
• So we need to split the ring of size n into two subrings each of size n/2:
mittimus , E
– The term 2M(n/2) in Inequality (1) should come from this two subrings in tohis splitting!
• How about the term n/4 in Inequality (1)?
– The term n/4 in Inequality (1) should come from messages which are in transit from one subring to the other and needed to elect a leaser! (Discussed later.)
⇒
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
O of.
Do
Distributed Computing, COMP 4001 22
Glueing!
• How do you glue two subrings into a bigger ring? ←
→
• You must find two respective schedules in the subrings of size n/2 which send at least M(n/2) messages in each subring and also leave at least one edge unused!
– You need this so that you can do the glueing!
• We will call such schedules which leave an edge of the ring
unused open
– open because they leave an edge unused.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 23
Inequality (1) Implies M (n) n (log n + 1) 4
¥
Ei fE9z
• For simplicity, assume n is a power of 2.
• Assume that M (n) 2M (n/2) + n/4 has been proveda
• By induction: we will prove
– Base case: 2 ‘ ‘
M(2) 4(log2+1) = 1 Assuming the inductive assumption
– Inductive Case:
M (n/2) n (log n + 1)
82
we’ll prove
M(n) n(logn+1) 4
aWe have not proved this yet! This is our goal in this lecture!
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
You
do not
know ‘ Scn )
Cn) E 2 SCI)t
S’
SCn)= #of
formula for Example Radius
satisfies ?
this
what is Scn)
7
inequality
F
steps
what th e explicit is
Growth
h
n 12 M 2
Ine n e n e T
– stiffly
ICnE S(Ma
S) 2 )tNg
E 2 (2 SCH
i%
) t 44
:÷÷:÷÷÷÷÷÷n÷
n – SG) tlogn
.
F
¥ SC2I2.sGltIQ.SGlE2.scz1-et@GscqE2.S
G
S’
Ul
!
(4) t !
E 9
Distributed Computing, COMP 4001 24
Base Case
• Here we must show that
M(2) 2(log2+1)=1
4
• Somehow this seems like a simple statement about rings of just 2 nodes.
– Lets postpone it for a moment!
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 25
• Assumie the inductive assumption
M (n/2) n (log n + 1)
• Therefore
M (n)
2 ⇣ n ⇣log n + 1⌘⌘ + n (Inductive Assumption) 824
Inductive Step
82
2M (n/2) + n/✓4 (By Inequality (1))
= nlogn+n 44
= n(logn+1) 4
login
-1
• Lets move now to the details! We are missing the proofs of – the base case, and
– Inequality (1).
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 26
Basic Concepts/Assumptions
• We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring;
– in addition, all the processors must know the identifier of
Mcmenamin
the elected leader.a
• We only accept uniform algorithms where the node with the
maximum identifier can be the leader.
• Additionally, every node that is not the leader must know the identity of the leader.
• Ring is asynchronous: nodes may wake up at arbitrary times (but at the latest when receiving the first message).
aUnless this is done, no leader has been elected.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 27
Rules of the Game
• Recall execution model
• Nodes wake up at the latest when receiving first message
• Algorithms must be uniform
• We assume we have an algorithm and show it cannot complete faster than O(n log n) time
• Algorithm needs to do this regardless of how messages are scheduled
– And when nodes wake up
– Otherwise it is not a solution
• But communication links must be FIFO
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 28
Schedules
• An execution of a distributed algorithm is a list of events, sorted by time.
– An event is a record (time, node, type, message) where type is “send” or “receive”.
• A schedule of A for a particular ring is open if there exists an edge e of the ring such that in no message is delivered over the edge e in either direction;
– Edge is open if no message which is traversing the edge has been received so far.
– Schedule is open if there is an open edge in the ring.
We two
need to “cut” the subring s
ring
into
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
to ¥e÷÷÷÷. Open m e a n s
unused
.
execution will take place that will transmit
” enough” messages and still leave an edgeused.
We
need
to
ensure
that a n
42
attach
i.
÷:
Vs
Distributed Computing, COMP 4001 29
Scheduler
• We assume no two events happen at exactly the same time.
• During the proof we can “play god” and specify which message
in transmission arrives next in the execution.
• If more than one message is in transit, the scheduler can choose which one arrives first.
• If two messages are transmitted over the same directed edge, then it is sometimes required that the message transmitted first will also be received first.
– We respect the FIFO conditions for links.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 30
Open Schedules
• Schedule: Execution chosen by the scheduler • Open schedule:
– Schedule with an open edge / communication link
• Open edge:
– Edge along which no message has yet been scheduled
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 31
Main Idea: Ring of n nodes
• We want to count how many messages we need to send to elect a leader and at the same time maintain an open schedule, i.e. there is an edge for which no message has been received so far.
– We prove it by induction on n – Will assume n is a power of 2.
• The proof is by induction on n:
– Thebasecaseisforn=21;
– The inductive step is for n = 2i, where i > 1.
MIE)
> TteTalEltf
M- l n ) w
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 32
Base Case: Starting the recursion in a 2-node Ring • Lemma 1 Given a ring R with two nodes, we can construct
an open schedule in which at least one message is received.
– The nodes cannot distinguish this schedule from one on a larger ring with all other nodes being where the open edge is.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 33
2-node Ring
• Two processors p0, p1 have identifiers u an’d v s.t. u > v.
Y →
u
p0
↳
p1
v
• Processor p1 must learn the identity of node v, thus receive at least one message.
• We stop the execution of the algorithm as soon as the first message is received.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 34
Induction Step
• Assume two rings of size n/2 with open schedules r:
in L.
” :
(L
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001
35
Induction Step
• Assume two rings of size n/2 with open schedules
•
Def –
of
leaderink e.ee.
,
:÷a
in
We can construct an open schedule on a ring of size n
• If M(n/2) is number of messages can construct schedule with
2M(n/2) without scheduling either of the two open edges
• Remember: We decide when edges are scheduled and when
nodes wake up
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
r
Distributed Computing, COMP 4001 36
Induction Step
• Each node in, say R1, must learn of at least one node in R2
• At least n/2 messages must be passed from R1 to R2a
• But some messages use e1 and others use e2 is not good enough as an argument!
• Closing one of the edges will cause at least n/4 messages to be passed (not necessarily over the closed edge though)
• Schedule this edge and leave the other open
aThis is crucial to the leader election process!
: ÷:÷÷÷÷
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
.
Distributed Computing, COMP 4001 37
• We can show that
Gluing Together
Lemma 2 Gluing together R1 and R2, at least 2M(n/2) + n/4 messages must be exchanged to solve leader election on the ring of size n. Moreover, at least one edge of the ring will be left open.a
O>
aThis is crucial to the validity of the induction step.
E
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 38
Recursive Step: Stitching
• Take two size n/2 subrings R1 and R2 with open schedules.
– Take the open edges in each sub-schedule and use these edges to glue the subrings into a ring of size n.
• Electing a leader in the resulting “glued” ring involves messages that
1. stay within each subring, plus
2. move from one ring to the other.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 39
Stitching
• Glue two rings of size n/2:
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 40
n-node Ring: Idea of Inductive Hypothesis
• Lemma 3 By glueing together two rings of size n/2 for which we have open schedules, we can construct a new open schedule on a ring of size n.
– If M(n/2) denotes the number of messages already received in each of these schedules, at least n/4 additional messages have to be exchanged in order to solve leader election.
• Divide the ring into two subrings R1 and R2 of size n/2.
• These subrings cannot be distinguished from rings with n/2 nodes if no messages are received from “outsiders”.
• Can ensure this by not scheduling such messages until we want.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 41
n-node Ring: Idea of Inductive Hypothesis
• Executing both given open schedules on R1 and R2 “in parallel” is possible because we control not only the scheduling of the messages, but also when nodes wake up.
• This ensures that 2M(n/2) messages are sent before the nodes in R1 and R2 learn anything of each other!
Without loss of generality, R1 contains the maximum identifier.
• Each node in R2 must learn the identity of the max identifier, thus at least n/2 additional messages must be received.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 42
Close One and Open the Other
• The only problem is that we cannot connect the two subrings with both edges since the new ring needs to remain open.
• Thus, only messages over one of the edges can be received.
• We look into the future: we check what happens when we close only one of these connecting edges.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 43
Count Messages
• Since we know that n/2 nodes have to be informed in R2, there must be at least n/2 messages that must be received by R2.
• Closing both edges must inform n/2 nodes, thus for one of the two edges there must be a node in distance n/4 which will be informed upon creating that edge.
• This results in n/4 additional messages. Thus, we pick this edge and leave the other one open which yields the claim.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
We know that % messages must
pass
why
,
overhead
R2
8either via e through ,
on via e Yz
isn’t the
In the new ” glued” from the,
area we need open ! many
leave a n gonna track -1
:O ring
to
edge
C-
g-
Distributed Computing, COMP 4001 44
⌦(nlogn) messages • So we have proved.
• Theorem 2 Any comparison based leader election algorithm on a ring of size n needs at least ⌦(n log n) messages.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 45
Randomized Leader Election
{Deform .
Iet
.
lead El
..
with random labels
CE
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 46
A Simple Way to Break Symmetry
• Assume that each node is equipped with a generator of random bits.
• EachnodeicanflipafaircoinXi,fori=0,1,…,n 1.
– Warning: we are not using i as an identity!
– Xi is a “fair coin” means we assume that Pr[Xi =0]=Pr[Xi =1]= 1.
• The coins are independent of each other. • Observe that for i 6= j,
Pr[Xi = Xj] = 1
2XEXj ’14
2
—
X i Xj – o o r
£4
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 47
Randomized Identity Selection (1/2)
• For simplicity assume the ring is unidirectional.
1. Each node “flips a coin” and chooses a random bit 0 or 1;
the selection of each node is independent of the others.
2. For c log n rounds each node sends and receives bits from
its neighbour.a /* We must specify how the hidden constant
c
c in c log n is selected */
>
4
3. Each node uses as identity the number whose binary representation is the sequence of c log n bits it has collected, in the order received.
• NB: The input collection phase is c log n rounds. ac > 0 is a constant that will be determined later.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 48
Randomized Identity Selection: Example
O
v ofO5
1
61 7
0
01 48
13 90
i a
2 10 11
11
0
• Each node collects the k bits it receives and converts the result to decimal.
1
1 12
0
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 49
Randomized Identity Selection: Example for 4 Steps
Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 Node 9 Node 10 Node 11 Node 12
1100 12 1001 9 0011 3 0111 7 1110 14 1101 13 1010 10 0100 4 1001 9 0011 6 0111 7 1110 14
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 50
Correctness of Randomized Identity Selection
• Theorem 3 For c 3, w.h.p. (i.e., with probability 1 1/n) Algorithm Randomized ID Selection ensures that the identities selected are pairwise distinct. Moreover, the algorithm
1. uses a total of n random bits,
2. terminates in c log n rounds,
3. the total number of bits transmitted is cn log n.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 51
Correctness of Randomized Identity Selection
• Consider the i-th node. Lets use the notation k = c log n.
• After c log n rounds node i will have received the following
sequence of bits
Xi, X(i+1) mod n, X(i+2) mod n, . . . X(i+k) mod n and form its identity
IDi := XiX(i+1) mod nX(i+2) mod n · · · X(i+k) mod n
– –
Xg Xgti
.
• We now ask the question.
How likely is it that two di↵erent nodes i 6= j of the ring will obtain the same identity?
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 52
Correctness of Randomized Identity Selection
• Assume i 6= j. • Observ-e that
IDi = IDj i↵ XiX(i+1) mod n ···X(i+k) mod n
= XjX(j+1) mod n ···X(j+k) mod n
i↵Xi+l =Xj+l, forall1lk. Pr[IDi = IDj] = Pr[8l k(Xi+l = Xj+l)]
• Therefore
inY
k
= Pr[Xi+l = Xj+l]
l=1
= 2 k = 1 (sincek=clogn)
ITalk nc
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 53
Correctness of Randomized Identity Selection
• However since there are at most
n X –
2 pairs i 6= j we get
Pr[IDi = IDj] Boole’s i6=j Rule
Union Rule
• Hence,
Pr[9i 6= j(IDi = IDj)]
n2 nc
1
nc 2 – -÷
Pr[8i6=j(IDi 6=IDj)] 1 1 .
nc 2
i
–
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 54
Randomized Leader Election (2/2)
• A leader election algorithm in a ring of size n has to run for n rounds so as to ensure that every node is informed of the leader.
•
Algorithm Randomized Leader Election
1. Each node chooses a random bit 0 or 1 independently of each other.
2. For n rounds each node sends and receives bits from its neighbour.
3. Each node computes its identity as the sequence of n bits it receives /* in the order received */
4. A node becomes a leader if its identity is the largest among everybody else’s identities.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 55
Randomized Identity Selection: Example
• Lets run the algorithm for
Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 Node 9
… …
4 steps:
• Which one of the 12 nodes receives the largest identifier?
1100 12 1001 9 0011 3 0111 7 1110 14 1101 13 1010 10 0100 4 1001 9
…
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 56
Correctness of Randomized Leader Election
• Theorem 4 With probability at least 1 n2/2n Algorithm Randomized Leader Election ensures that a unique leader is elected. The algorithm uses a total of n random bits, terminates in n rounds and the total number of bits transmitted is n2.a
• The algorithm terminates in n rounds, because Step 2 of the algorithm runs for n rounds (not c log n as in identity selection).
• In Step 4, how does each node compute the identity of every other node without additional communication?
aNotice that the IDs constructed by this algorithm can be as large as 2n.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 57
Correctness of Randomized Leader Election
• For the sake of simplicity, assume addition below is modn
• If
is i’s identity as computed by the algorithm then i can
IDi = XiXi+1 · · · Xi+n 1
compute IDi+k mod n by simply rotating it k positions.
• Indeed
IDi = I Di+1 = I Di+2 =
Xi Xi+1 Xi+2 Xi+3 · · · Xi+n 2 Xi+n 1 Xi+1 Xi+2 Xi+3 · · · Xi+n 2 Xi+n 1 Xi Xi+2 Xi+3 · · · Xi+n 2 Xi+n 1 Xi Xi+1
. = • No additional
. communication round is needed.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 58
Correctness of Randomized Identity Selection
• Finally, the claim on the probability.
• Just repeating the previous argument with k = n we see that
Pr[IDi = IDj] = PYr[8l k(Xi+l = Xj+l)] k
= Pr[Xi+l = Xj+l] l=1
= 2 n
• Therefore since there are at most 2 pairs i 6= j we get
n X
Pr[9i 6= j(IDi = IDj)] Pr[IDi = IDj]
i6=j
Çn2å/2n
n2/2n.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 59
Sources
• H. Attiya, J. Welch, Distributed Computing, John Wiley and Sons, 2E, 2004.
• R. Wattenhofer, Lecture Notes on Principles of Distributed Computing, ETH Spring 2012.
• N. Lynch, Distributed Algorithms, Morgan-Kaufmann, 1996.
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 60
Exercisesa
1. Can paiwise distinct identifiers be selected if the nodes have
independent random generators?
2. Why are we allowed to interpret an event E that is valid “with probability at least 1 n2/2n” as “it is valid with high probability”?
3. Justify the validity of the approximation e 1 ⇡ 1 x, for |x| su ciently small. (Use the Taylor series expansion of the function eu, where u is a real number.)
4. Consider the following variant of randomized ID selection:
Each node selects k random bits b1, b2, . . . , bk and makes the
sequence b1b2 · · · bk its identifier. Show that by choosing k
appropriately with high probability the identifiers chosen by
the nodes are pairwise distinct. NB. This algorithm di↵ers
aDo not submit!
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)
Distributed Computing, COMP 4001 61
from the one discussed in class in that it does not require any message exchanges.
5. How do “TimeSlice” and “VariableSpeed” di↵er from the traditional “C;lock-wise” and “RadiusGrowth” algorithms?
Evangelos Kranakis, Carleton University, SCS (October 3, 2020)