Hello,
Could anybody please help me understand the idea of LCR leader election in a synchronous ring?
The idea is: Suppose a distributed system consists of a collection of
homogeneous participants
• How to pick one out of this group?
Basic assumptions
• Each participant has a unique identifier
• Goal is to choose that member with the largest identifier as leade
• Set of all identifiers unknown to all participants
Time assumptions
• Synchronous time model – all processes operate in lock-step,
bounded message transit time.
PS: i have NO IDEA what lock-step means! i couldnt understand the
--------------------------------------------------------------------------------------
above time assumptions.
--------------------------------
Assumptions
• G is a ring consisting of n nodes
• Nodes are numbered 1 to n
• Nodes do not know their indices, nor those of their neighbors
• Node can distinguish its clockwise neighbor from its
counterclockwise neighbor
Algorithm (informal)
• Each node sends its UID to its neighbor. A received UID is
compared to the own UID.
• If new UID < own UID: ignore new UID, send largest UID so far
• If new UID > largest so far occurred UID: pass this UID on
• If new UID = own UID: claim leadership
Invariant: Each node sends in every round the largest so
far occurred UID to its neighbor
PS: Could anybody tell me what a round is !?!
----------------------------------------------------------
Message complexity is o(n^2) ( WHY ?)
say we have the ring with processes numbered :
1, 2, 4, 3, and 5.
what i understood is :
time 0:
1 sends its UID 1 to 2, 2 compares it, and since 2 bigger, it discards it.
time1:
So now the token in with 2, 2 sends its UID 2 to 4, since 4 is bigger, it discards it.
time2:
So now the token in with 4, 4 sends its UID 4 to 3, since 3 is less, 3 passes UID 4 to 5.
time3:
So now the token in with 3, 3 sends its UID 4 to 5, since 5 is less, 5 passes it discards it.
and so on...5 sends uid 5 to 1...
is that true? please could anybody answer my questions above?
THANK you SO much