Leader Election Notes | EduRev

: Leader Election Notes | EduRev

 Page 1


Dept. of CSE, IIT KGP
Leader Election
Leader Election
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Page 2


Dept. of CSE, IIT KGP
Leader Election
Leader Election
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Leader Election in Rings
Leader Election in Rings
• • Models Models
– – Synchronous or Asynchronous Synchronous or Asynchronous
– – Anonymous (no unique id) or Non Anonymous (no unique id) or Non- -anonymous (unique anonymous (unique 
ids) ids)
– – Uniform (no knowledge of Uniform (no knowledge of N N, the number of processes) or , the number of processes) or 
non non- -uniform (knows uniform (knows N N) ) 
• • Known Impossibility Result: Known Impossibility Result:
– – There is no synchronous, non There is no synchronous, non- -uniform leader election uniform leader election 
protocol for anonymous rings protocol for anonymous rings
Page 3


Dept. of CSE, IIT KGP
Leader Election
Leader Election
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Leader Election in Rings
Leader Election in Rings
• • Models Models
– – Synchronous or Asynchronous Synchronous or Asynchronous
– – Anonymous (no unique id) or Non Anonymous (no unique id) or Non- -anonymous (unique anonymous (unique 
ids) ids)
– – Uniform (no knowledge of Uniform (no knowledge of N N, the number of processes) or , the number of processes) or 
non non- -uniform (knows uniform (knows N N) ) 
• • Known Impossibility Result: Known Impossibility Result:
– – There is no synchronous, non There is no synchronous, non- -uniform leader election uniform leader election 
protocol for anonymous rings protocol for anonymous rings
Dept. of CSE, IIT KGP
Election in Asynchronous Rings
Election in Asynchronous Rings
• • LeLann’s LeLann’s and Chang and Chang- -Robert’s Algorithms Robert’s Algorithms
– – send own id to node on left send own id to node on left
– – if an id received from right, forward id to left node if an id received from right, forward id to left node 
only if received id greater than own id, else ignore only if received id greater than own id, else ignore
– – if own id received, declares itself “leader” if own id received, declares itself “leader”
• • Works on unidirectional rings Works on unidirectional rings
• • Message complexity = O(n Message complexity = O(n
2 2
) )
Page 4


Dept. of CSE, IIT KGP
Leader Election
Leader Election
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Leader Election in Rings
Leader Election in Rings
• • Models Models
– – Synchronous or Asynchronous Synchronous or Asynchronous
– – Anonymous (no unique id) or Non Anonymous (no unique id) or Non- -anonymous (unique anonymous (unique 
ids) ids)
– – Uniform (no knowledge of Uniform (no knowledge of N N, the number of processes) or , the number of processes) or 
non non- -uniform (knows uniform (knows N N) ) 
• • Known Impossibility Result: Known Impossibility Result:
– – There is no synchronous, non There is no synchronous, non- -uniform leader election uniform leader election 
protocol for anonymous rings protocol for anonymous rings
Dept. of CSE, IIT KGP
Election in Asynchronous Rings
Election in Asynchronous Rings
• • LeLann’s LeLann’s and Chang and Chang- -Robert’s Algorithms Robert’s Algorithms
– – send own id to node on left send own id to node on left
– – if an id received from right, forward id to left node if an id received from right, forward id to left node 
only if received id greater than own id, else ignore only if received id greater than own id, else ignore
– – if own id received, declares itself “leader” if own id received, declares itself “leader”
• • Works on unidirectional rings Works on unidirectional rings
• • Message complexity = O(n Message complexity = O(n
2 2
) )
Dept. of CSE, IIT KGP
Hirschberg
Hirschberg
-
-
Sinclair Algorithm
Sinclair Algorithm
• • Operates in phases, requires bidirectional ring Operates in phases, requires bidirectional ring
• • In the In the k k
th th
phase, send own id to 2 phase, send own id to 2
k k
processes on both sides of processes on both sides of 
yourself (directly send only to next processes with id and yourself (directly send only to next processes with id and k k in it) in it)
• • If id received, forward if received id greater than own id, else If id received, forward if received id greater than own id, else ignore ignore
• • Last process in the chain sends a reply to originator if its id Last process in the chain sends a reply to originator if its id less less 
than received id than received id
• • Replies are always forwarded Replies are always forwarded
• • A process goes to (k+1) A process goes to (k+1)
th th
phase only if it receives a reply from both phase only if it receives a reply from both 
sides in sides in k k
th th
phase phase
• • Process receiving its own id Process receiving its own id – – declare itself “leader”. At most declare itself “leader”. At most lg lgn n
rounds rounds
Page 5


Dept. of CSE, IIT KGP
Leader Election
Leader Election
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Leader Election in Rings
Leader Election in Rings
• • Models Models
– – Synchronous or Asynchronous Synchronous or Asynchronous
– – Anonymous (no unique id) or Non Anonymous (no unique id) or Non- -anonymous (unique anonymous (unique 
ids) ids)
– – Uniform (no knowledge of Uniform (no knowledge of N N, the number of processes) or , the number of processes) or 
non non- -uniform (knows uniform (knows N N) ) 
• • Known Impossibility Result: Known Impossibility Result:
– – There is no synchronous, non There is no synchronous, non- -uniform leader election uniform leader election 
protocol for anonymous rings protocol for anonymous rings
Dept. of CSE, IIT KGP
Election in Asynchronous Rings
Election in Asynchronous Rings
• • LeLann’s LeLann’s and Chang and Chang- -Robert’s Algorithms Robert’s Algorithms
– – send own id to node on left send own id to node on left
– – if an id received from right, forward id to left node if an id received from right, forward id to left node 
only if received id greater than own id, else ignore only if received id greater than own id, else ignore
– – if own id received, declares itself “leader” if own id received, declares itself “leader”
• • Works on unidirectional rings Works on unidirectional rings
• • Message complexity = O(n Message complexity = O(n
2 2
) )
Dept. of CSE, IIT KGP
Hirschberg
Hirschberg
-
-
Sinclair Algorithm
Sinclair Algorithm
• • Operates in phases, requires bidirectional ring Operates in phases, requires bidirectional ring
• • In the In the k k
th th
phase, send own id to 2 phase, send own id to 2
k k
processes on both sides of processes on both sides of 
yourself (directly send only to next processes with id and yourself (directly send only to next processes with id and k k in it) in it)
• • If id received, forward if received id greater than own id, else If id received, forward if received id greater than own id, else ignore ignore
• • Last process in the chain sends a reply to originator if its id Last process in the chain sends a reply to originator if its id less less 
than received id than received id
• • Replies are always forwarded Replies are always forwarded
• • A process goes to (k+1) A process goes to (k+1)
th th
phase only if it receives a reply from both phase only if it receives a reply from both 
sides in sides in k k
th th
phase phase
• • Process receiving its own id Process receiving its own id – – declare itself “leader”. At most declare itself “leader”. At most lg lgn n
rounds rounds
Dept. of CSE, IIT KGP
Features: Hirschberg
Features: Hirschberg
-
-
Sinclair 
Sinclair 
• • Message Complexity: O( Message Complexity: O(n n lg lgn n) )
• • Lots of other algorithms exist for rings Lots of other algorithms exist for rings
• • Lower Bound Result: Lower Bound Result:
– – Any Any comparison comparison- -based based leader election algorithm in a leader election algorithm in a 
ring requires ring requires ? ?( (n n lg lgn n) messages ) messages
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!