<div dir="ltr"><div dir="auto" style="border-color:rgb(32,33,36)">I think Aliaksei put it well. The simpler election algorithms like bully and ring election are not partition-tolerant, they can elect multiple leaders at the same time if the network is bad. Raft uses a fancier algorithm based on majority vote which solves that weakness (and more).</div><div dir="auto" style="border-color:rgb(32,33,36)"><br></div><div dir="auto" style="border-color:rgb(32,33,36)">Dominic</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">2022年1月8日(土) 15:09 Aliaksei Artamonau <<a href="mailto:aliaksiej.artamonau@gmail.com">aliaksiej.artamonau@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">When you talk about implementing consensus on top of leader election, how exactly do you envision it? Getting a bit more details could help answer your question.<br></div><div dir="ltr"><br></div><div>You could use the bully algorithm to implement leader election for a consensus protocol like (Multi-)Paxos. Raft is slightly different because it uses leader election to avoid the need for the new leader to synchronize with the other nodes to get all updates that may have been committed by previous leaders. At the same time, the leader election algorithm that Raft uses is not that different from the bully algorithm: substitute process IDs for log positions and require at least a majority of responses.</div><div><br></div><div>Some reasons for why majority voting schemes are typically used to implement consensus protocols (to my understanding).</div><div><br></div><div>1. In order for the consensus protocol to make progress a majority of nodes is required anyway. So it does not achieve much to choose a leader when there's no majority.</div><div>2. In Raft specifically, leaders use integer term/epoch numbers. And no term/epoch should have more than one leader, which requires for at least a majority of nodes to agree on a leader.</div><div>3. Competing leaders impede progress. So checking with a majority of nodes lowers the probability of having concurrent leaders.</div><div><br></div><div>Roughly speaking what a consensus protocol like Raft gives you:</div><div><br></div><div>1. A total order on leader terms.</div><div>2. A way to ensure that a stale leader can't commit anything once a new term has commenced.</div><div>3. A way for a new leader to be sure that it has got all updates that may have previously been committed.</div><div>4. A total order on all updates.</div><div>5. A way to change the set of nodes in your cluster while preserving safety.<br></div><div>5. Availability as long as a majority of nodes are alive.</div><div><br></div><div>Here's a paper that I found useful <a href="https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/deconstr_paxos.pdf" target="_blank">https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/deconstr_paxos.pdf</a>.</div><div><br></div><div><br></div><div>Aliaksei<br></div></div>
</blockquote></div>