A simple distributed algorithm for small idempotent information (opens in new tab)

While the wiki article seems to do a decent job of explaining mathematics behind idempotency it sheds no light on why it's so important in distributed systems. antirez talks about idempotency in sort of mathematical sense, though I could be wrong as I've just skimmed through the article.

Since failures are a norm in distributed systems one would want clients to retry a request without worrying about double updations (placing the order twice in the example above, debiting the money twice etc.,).

Just elaborate this further. Let's say the "place order" request didn't even reach the server. In this case client can just retry the request. However, if the request did reach the server but the response didn't reach the client then client can't safely retry without creating duplicate order. The problem here for the client is that there's no way for it to distinguish between a lost request vs lost response.

In such cases idempotency is achieved by requiring clients to send a unique identifier with each request. Server can now ensure that for a given request identifier the operation is performed just once.

In the very first part of the post: "The algorithm is mostly borrowed from Raft, however because of the premises it uses only a subset of Raft that is trivial to implement."

Maybe you only scanned the article.

Check the "retry" part, basically when there is a split-brain during an election, a new process will try again and eventually will succeed. This is copied from Raft.

It works because when some instance retries, it increments again the currentEpoch, so ti is a new voting process from the point of view of the voters.

Btw it is not needed that to retry is the instance that did it the previous time, because even if the voting failed, the currentEpoch of the process that tried to get elected, will be propagated across the system, so every process will get the new epoch, and can try with an updated epoch to get voted.

Right. For the same reason, the Paxos protocol allows multiple prepare votes from each acceptor. It makes this safe by requiring that each acceptor tell the proposer of the value for the highest ballot number it has accepted, and requires the proposer to switch proposal values when receiving such a message. This is, at first glance, one of the strange edges of the Paxos (synod) protocol, but it makes a lot of sense once you see an example where it is needed.

Raft has somewhat similar constructs, but explained slightly differently.

Hmm -- if a process bumps its `currentEpoch` for every proposal, and the delays are randomized, it looks like this would fail only probabilistically and may eventually succeed. I'll have to take a closer look later today...