Today I learned - consensus algorithms

Paxos #

1. Paxos is notorious for being difficult to understand. However, the vanilla version seems somewhat straightforward albeit with one limitation: it only allows you to reach consensus on one value. For practical purposes, you want to reach consensus for multiple values in sequence, similar to a replicated log, and you need multi-Paxos for that. And that is hard.
2. Think of basic Paxos as: “do we know already where we’ll go for dinner” and, if not, “let’s go for burgers”.
3. Three roles: proposers, acceptors and learners.
4. Odd number of acceptors.
5. While both proposers and acceptors use numbers in the algorithm, those are just mechanisms to reach consensus on one value. Once consensus is reached, they can continue using more numbers but that value will never change.
   1. So, one run of the algorithm gets you one consensus value. If you want more, use multi-Paxos.

The algorithm, the way I understand it, is as follows:

1. Proposer sends a prepare(id = x) to all acceptors.
2. If acceptor has seen an id lower than or equal to x, it ignores the message (or, as an optimization, return an error). Otherwise, it responds with promise(id = x).
3. If proposer receives acceptances from a quorum, it sends accept(id = x, value = y) to all the acceptors.
   1. It could so happen that one or more acceptors had accepted. In that case, the acceptor must have sent the value which the acceptor had accepted, so the proposer should use that (corresponding to the acceptor with the highest id) instead of the one it wants.
4. If acceptor has seen an id lower than x, it ignores the message. Otherwise, it responds with accepted(id = x, value = y) to the proposer and any learners who may call them in future.
   1. If at least one acceptor received the accept message, that’s the point where the sytem reached consensus on what value to accept. Failures could still happen and another proposer could try to start a new round with another id and value (say, y’). However, in that case, that one acceptor that got the accept message will respond with the new id but old value it had accepted. In other words, the new proposer will finish the work of the older one.

Resources:

1. https://people.cs.rutgers.edu/~pxk/417/notes/paxos.html
2. There are some good vides on YouTube as well.

Bitcoin’s blockchain #

1. Bitcoin’s use case is different from Paxos’ in that nodes are free to come and go at any time but the overall system should still make progress. Also, nodes aren’t all trustworthy.
2. In blockchain data structure, each node contains a pointer to the previous node. So, it’s sort of like an inverted linked list.
3. How to think about the algorithm, in sequence:
   1. Any node can add new nodes on the chain. When they do, they’ll replicate the new chain to all other nodes in the system.
   2. However, discrepancies will occur if a lot of nodes do this in parallel or when network partitions occur and nodes continue doing this on both sides of the partition. So, each node starts a random timer whenever it adds a new node itself or learns of another node who did that.
   3. Now, we can’t trust nodes to honor the timer rule. The solution for that is “proof of work” which essentially uses real world constraints to add delays between new node additions.
4. The math problem in proof of work could be as simple as “create a block such that its hash value starts with X zeros”. Bitcoin varies X at runtime in such a way that it only adds one block every 10 minute.