Leader Election
l Very useful because once we have the leader
l The leader makes the decision and everyone follows
l Reduce the hard distributed n2 setting back to the 1-to-n setting
Copyright By PowCoder代写 加微信 powcoder
l E.g., Raft first elects a leader for its replicated state machine consensus problem
l In centralized model
l the leader dies => the system dies
l In distributed, leader election is the problem of once a leader dies (e.g., not sending heartbeat to the others), the nodes elect a new leader that is agreed by everybody as soon as possible
Leader Election vs Mutual Exclusion
l In some sense, it is also like an ME problem because every time only ONE guy can take the lock (take the “leader role”)
l So, one might wonder we can use a distributed ME algorithm to solve LE?
l ME algorithms don’t deal with failed leader l ME hates starvation
n Vs. LE: A leader can stay as long as there is no failure
l i.e., it can stay in the CS as long as it likes (so it violates ME’s bounded waiting)
Leader Election
l There is no politics indeed
l Given me one unique process as the leader ASAP
l Each process has l a unique ID
l a variable L; the id of my leader
l V: set of IDs
l ∀i,j∈V: i,jarenonfaulty::L(i)∈V ∧ L(i)=L(j) ∧ L(i)isnonfaulty
agree on same leader
Difficulty of implementing and testing – Leader Election
l BothAandBdetectLeaderLdies
l They both publish that they want to be the leader l For C and D, who should they vote for?
n Vote for the one who asks for your vote first?
n What if A’s request arrives C first but B’s request arrives D first?
l Leader L no heartbeats to the others
l A, B, and C elect A be the new leader and while A is doing the following:
n While {for each other node i}
l Send ‘I am the new leader, yeah’ to i. //Then L wakes up and sends heartbeat
l … “enjoy” more of them in your Raft assignment part 1
What about this 1-line protocol?
l We set the one with the largest IP as the leader l Given a set of nodes with IP1, IP2, IP3, IP4, IP5 l Now, IP5 leader is dead
l Others think IP4 is the new leader
l But what if IP4 also dead?
l When shall IP3 announce it is the new leader? l Do we still have new leader quick enough?
l So, is this protocol complete in terms of safety and liveness? l Bully algorithm makes this idea complete
Bully Algorithm [Garcia-Molina82]
l Works on fully connected network
l Meaning: messages from X to {w, h, a, t, e, v, e, r} arrive roughly the same time
l Goal: Elect the one with the highest ID as the leader l Assume links are fault-free
l Assume failures can be detected by time-out (=sync)
l Once a process detects a leader has failed (e.g., by time-out) l That process will trigger Bully Algorithm to begin the election
l Eventually, the non-faulty process with the highest ID is the new leader
l 3 kinds of messages:
l Election;Reply;Leader
l Any process who detects failure,
l willattempttobecomethenewleaderby
l sendingan
n Essentially implying that “Can I be the new leader?”
n Why not send only to the process with the next highest ID?
l Because that process may also die
l If any process (with a higher ID) replies, then the requesting process gives up and
wait for a
l If I receive nobody replying my
l If someone turns down my
l If I receive an
l Irestarttheelectionprocessbysendingan
http://www.cs.colostate.edu/~cs551/CourseNotes/Synchronization/BullyExample.html
Message Complexity
l Worst-case happens when the process with the lowest-id (detects current leader fail) W0 and triggers the election
l Best-case is the process with the highest-id triggers
l W0 sends n-1
l All receiving processes turn that down and each independently triggers a new election and so
l W1: sends N-2
l Wmax: sends to myself
l O(N2)
l O(N2)
l O(N)
Other logical (becoz of physical distance) or physical network topology?
l Bully works on fully connected synchronous network
l Other types of network. E.g.,
l ring network, each node only knows two entries
n
l tree network, often used in a small data center
A Comparative Study Of Data Center Network Architectures
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com