The Paxos Algorithm

A Google TechTalk, 2/2/18, presented by Luis Quesada Torres.
ABSTRACT: This Tech Talk presents the Paxos algorithm and discusses a fictional distributed storage system (i.e. simplified Megastore) based on Paxos.

The Paxos algorithm is one of the most common consensus algorithms. Consensus algorithms are one of the mechanisms that allow satisfying consistency constraints in distributed systems with consistency constraints, whether they follow a leader-replica schema or a peer-to-peer schema.

Leader-replica systems consist of a leader node that proposes, manages, accepts, and serializes changes, and replica nodes that propose changes to the current leader node. Given that a single entity is in charge of acception and serialization, leader-replica systems do not require consensus algorithms in order to agree on what the next state is. However, if the leader node becomes unreachable, the replica nodes need to agree on which one should become the next leader node, and they usually run consensus algorithms to reach that agreement.

Peer-to-peer systems consist of nodes that can propose changes and participate in accepting changes. The nodes need to agree on what the next state is in order to establish consistency, and they usually run consensus algorithms to reach that agreement.

SREs within and outside Google work with highly scalable (and therefore distributed) systems that have consistency constraints and involve consensus algorithms.

About the Speaker: Luis Quesada Torres is a Senior Software Engineer in Google's Site Reliability Engineering team.

[pavan]

One of the best presentations on Paxos!! Great job Luis. Very easy to understand and simple examples make it clearer!

[clinthall]

Switching the metaphor from *voting and politics* to *deciding what to do together when we just want to do something together but don't so much care what* was super helpful to me. Thanks.

[Error-rpdk]

Far more useful than my thousand-euro uni course that, after 4 hours, made me go home crying and with a headache. You've saved me hours of disappointment and confusion, wish you all the best

[stevehe]

What do you mean by piggyback? It’s very confusing

[sanskaripatrick]

probably the only video on PAXOS that actually explains all the concepts clearly. Thank you so much!

[nomad]

Thank you soo much Luis!!!! It's no surprise, how these videos are better at teaching (for Free!) than my University!

[yicain]

I have watched quite a lot of videos about Paxos. The one is the most enjoyable. Thanks

[MasoudGhaffarinia]

Great presentation! Especially I like the presentations in which the algorithm is tweaked/changed as they go through examples, revealing the reasoning behind any subtle part of it. But I wish you also went through the case the proposer receives two different values accepted. That would have shed more light on it. Anyway, thank you for this video.

[brandonkarai]

This is the best explanation of Paxos I've come across, thanks

[joshuablaeser]

Well Done. The slides showing communications between nodes made for great examples. Thank you!

[croncoder]

How does the proposer know how many majority acceptors are present in the network?

[shitaoweng]

great presentation! i was confused between log pos and Prepare Id. but it all made sense when i realized they are different things.

[contactrajpal]

Excellent !! Please prepare the same type presentation for other type Paxoses.

[rgi]

Thank you. Also would be nice to get an overview of scenarios when nodes, including proposers, fail and then come back alive

[arazsharma]

Brilliant Sir!! Looking forward to more such talks from you :D

[mienislav]

I have an exam tomorrow and this video helped me a lot! Thank you very much!

[camillegoze]

Thanks a lot for the video :). I watched it a couple of times to be sure to understand every detail. You saved my exam

[flain]

This is a good simplified version of Paxos, but does lack a lot of detail.

[pseeker]

It is great, Luis. Thanks for your time explaining Paxos!

[waffleboot]

I don't understand how Paxos run is finished, because acceptor will send piggyback promise for each new promise request and proposer have to send accept request with that value instead of wanted value.