<div dir="ltr">Thank you Aliaksei, this is helpful.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Jan 8, 2022 at 7:09 AM Aliaksei Artamonau <<a href="mailto:aliaksiej.artamonau@gmail.com">aliaksiej.artamonau@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid 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>