Arpit's Newsletter read by 90000+ engineers

Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.

Reaching consensus is extremely important in any distributed network. For example, we cannot have two data nodes in a cluster where one thinks that `price`

is `$1000`

while the other thinks it is `$2000`

.

So, we need the nodes to talk to each other and reach a consensus and converge on the true value of `price`

. Reaching consensus is easy when there are no failures - no network failures, or process failures.

Reaching a consensus

- is impossible when the network is unreliable
- is simple when there are no network/process failures
- is tricky when we have to deal with process failures

The core idea of the FloodSet algorithm is to keep track of all the values seen so far and use some decision rule such that all nodes choose the same value.

Every node maintains a set `W`

to hold all the values seen so far. If we assume at max `f`

nodes would fail then the FloodSet algorithm runs for `f + 1`

rounds, giving chances for processes to fail.

Every node starts with `W = {v}`

, its own value. In each round, every node broadcasts `W`

in the network. When a node receives the `W`

from other nodes it updates its `W`

by doing a set union.

After the `f + 1`

rounds, every node will have the same `W`

that holds all possible values of the network participating in the transaction.

The decision-making is decentralized. If `W`

contains just one value then the node converges to that value. If it contains more than one value, the node defaults to the last value.

This decision-making is use-case specific, so defaulting to the old value can mean that the transaction is aborted and the node is reverting to the old value.

Depending on the usecase, we may choose another decision strategy like picking the smallest value or the largest value or the oldest value, or the newest value.

So long as we have a total ordering of the values, we can define our own decision strategy.

Here's the video ⤵

Alongside my daily work, I also teach some highly practical courses, with a no-fluff no-nonsense approach, that are designed to spark engineering curiosity and help you ace your career.

A no-fluff masterclass that helps experienced engineers form the right intuition to design and implement highly scalable, fault-tolerant, extensible, and available systems.

An in-depth and self-paced course for absolute beginners to become great at designing and implementing scalable, available, and extensible systems.

A self-paced and hands-on course covering Redis internals - data structures, algorithms, and some core features by re-implementing them in Go.

Arpit's Newsletter read by 90000+ engineers

Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.

- © Arpit Bhayani, 2024