FloodSet Algorithm: Distributed Consensus Under Process Crash Failures

Reaching consensus is one of the most fundamental challenges in distributed computing. In real-world systems—such as replicated databases, coordination services, or distributed transaction managers—independent nodes must repeatedly agree on shared state (e.g., whether a transaction should commit or abort, or determining the correct value of a replicated variable).

The complexity of consensus depends heavily on the failure model of the underlying network and nodes. The FloodSet algorithm is an elegant, foundational consensus algorithm designed to achieve fault-tolerant agreement in synchronous distributed systems where processes can fail by crashing (the crash-stop model).

---

The Spectrum of Failures in Distributed Consensus

Consensus difficulty scales with the unpredictability of the environment:

1. Zero Failures (Ideal World): When processes never crash and the network never drops, delays, or reorders messages, consensus is trivial. Nodes simply exchange messages, compare values, and decide.
2. Unreliable Networks (Arbitrary Message Loss): If messages can be dropped without bounds, achieving deterministic consensus is mathematically impossible. This is famously illustrated by the Two Generals’ Problem, where two parties cannot reach common knowledge over an unreliable communication channel.
3. Crash-Stop Failures in a Synchronous Network: If the network is synchronous (message delays are bounded) but individual nodes can arbitrarily crash mid-execution, consensus becomes solvable. This is the exact domain of the FloodSet algorithm.

+-------------------------------------------------------------------------+
|                        Distributed System Models                        |
+-------------------------------------------------------------------------+
|  Zero Failures       -> Trivial consensus via direct message exchange   |
|  Crash-Stop Failures -> Solvable in synchronous systems via FloodSet/Pax|
|  Unreliable Network  -> Impossible deterministic consensus (Two Generals) |
+-------------------------------------------------------------------------+

---

Formal System Model and Consensus Properties

System Assumptions

• Network Topology: A complete graph of $n$ processes ($P_1, P_2, \dots, P_n$), meaning every node knows about and can communicate directly with every other node.
• Synchronous System: Execution proceeds in synchronized, lock-step communication rounds. A message sent in round $r$ is guaranteed to be delivered before round $r+1$ begins, unless the sender crashes during round $r$.
• Failure Model: Crash-stop (fail-silent). A node behaves correctly until it crashes, after which it ceases all communication permanently. At most $f$ processes can crash during the algorithm’s execution ($f < n$).
• Values: Every process $i$ begins with an initial proposal $v_i \in V$. There is also a globally known default value $v_0$ (typically representing ABORT or a null value).

Formal Guarantees Required

To be considered a correct consensus protocol, the algorithm must satisfy three invariant properties:

1. Agreement: No two non-faulty processes decide on different values.
2. Validity: If all processes start with the same initial value $v$, every non-faulty process must decide $v$. Furthermore, any decided value must have been proposed by at least one process, or be the predefined default fallback $v_0$.
3. Termination: Every non-faulty process must eventually decide on a value.

---

The FloodSet Mechanism

The Core Intuition

The fundamental premise of the FloodSet algorithm is that nodes keep track of all values observed so far by flooding the network, then apply a deterministic, deterministic decision rule once enough rounds have passed.

Each node maintains a local set $W \subseteq V$:

• Initially, a node puts only its own proposed value into $W$.
• Over consecutive rounds, nodes broadcast $W$ to all peers and incorporate received sets using a set union ($W \leftarrow W \cup W_{\text{received}}$).

Node 1: Starts with {1000} ---\                       /---> Round 1: W = {1000, 2000}
                               Broadcast & Set Union
Node 2: Starts with {2000} ---/                       \---> Round 1: W = {1000, 2000}

Why Exactly $f + 1$ Rounds?

If at most $f$ processes can fail, why does the algorithm need to execute for precisely $f + 1$ rounds?

• Suppose a process crashes during round $r$ while in the middle of broadcasting its set. It might successfully transmit its value to process $A$, but crash before sending it to process $B$. At the end of round $r$, $A$ and $B$ have divergent views of $W$.
• Because at most $f$ processes can fail across the entire execution, running for $f + 1$ rounds guarantees by the Pigeonhole Principle that at least one round contains zero process crashes (a “clean” round).
• During this clean round, every surviving node successfully broadcasts its current set $W$ to every other surviving node.
• Once a clean round occurs, every surviving node receives the exact same set of values. As a result, their local sets $W$ become identical and remain identical for all subsequent rounds.

Round 1: Node crashes mid-broadcast (partial delivery)
Round 2: Another node crashes (partial delivery)
...
Round k (k <= f+1): CLEAN ROUND -> No nodes crash during broadcast
                   -> All surviving nodes achieve identical W sets

---

Algorithmic Walkthrough & Pseudocode

FloodSet Algorithm Specification

Algorithm FloodSet(initial_value v_i, max_failures f):
    W = { v_i }                     // Initialize local set with own proposal
    
    // Communication Phase: Execute exactly f + 1 rounds
    for round = 1 to f + 1:
        broadcast W to all processes
        
        for each message W_j received from process P_j in this round:
            W = W ∪ W_j             // Accumulate all observed values
            
    // Decision Phase
    if |W| == 1:
        decide the unique element in W
    else:
        decide default value v_0    // Conflicting inputs -> fallback / abort

Trace Scenario: Conflicting Proposals

1. Consider three nodes: $P_1$ proposes 1000, $P_2$ proposes 2000, and $P_3$ proposes 2000. Let $f = 1$ (at most 1 crash), meaning the algorithm runs for $1 + 1 = 2$ rounds.
2. Round 1:
   • $P_1$ broadcasts {1000}.
   • $P_2$ broadcasts {2000}.
   • $P_3$ crashes before sending anything.
   • Surviving nodes $P_1$ and $P_2$ receive each other’s messages.
   • $P_1$ updates: $W_1 = \{1000\} \cup \{2000\} = \{1000, 2000\}$.
   • $P_2$ updates: $W_2 = \{2000\} \cup \{1000\} = \{1000, 2000\}$.
3. Round 2 (Clean Round):
   • $P_1$ and $P_2$ broadcast $\{1000, 2000\}$. Both receive the same set.
   • $W_1 = \{1000, 2000\}$, $W_2 = \{1000, 2000\}$.
4. Decision:
   • Both $P_1$ and $P_2$ observe that $|W| = 2 > 1$.
   • Both deterministically decide on $v_0$ (e.g., ABORT). Agreement is preserved.

---

Alternative Decision Strategies: Beyond Fallbacks

The standard FloodSet rule decides $v_0$ when $|W| > 1$. However, because the communication phase guarantees that all non-faulty nodes end up with the identical set $W$, any deterministic function applied to $W$ will yield consensus without discarding proposed values.

Total Ordering Rules

If the application requires picking a concrete value rather than aborting, nodes can agree on an arbitrary deterministic selection function, provided there is a total order over values:

1. Minimum / Maximum Value: $\text{decide } \min(W) \quad \text{or} \quad \max(W)$
2. Timestamp / Version-Based Ordering: If proposals carry metadata (such as logical timestamps or client IDs), nodes can select the value with the latest timestamp or lowest node ID.

Because $W$ is identical across all non-faulty nodes after $f + 1$ rounds, applying any deterministic function $f(W)$ guarantees identical decisions everywhere.

---

Complexity Analysis

Dimension	Complexity	Explanation
Time Complexity (Rounds)	$\mathcal{O}(f + 1)$	Nodes must run for $f + 1$ rounds to guarantee at least one failure-free round.
Message Complexity	$\mathcal{O}((f + 1) \cdot n^2)$	In every round, up to $n$ nodes send messages to $n$ peers, generating $\approx n^2$ messages per round.
Space Complexity per Node	$\mathcal{O}(\|V\|)$	The local set $W$ grows at most to the cardinality of all proposed values $\|V\| \le n$.

Scalability Constraints

While conceptually simple and robust, the communication overhead of FloodSet makes it impractical for large-scale distributed systems:

• With $n = 100$ and $f = 10$, the protocol requires 11 rounds and up to $11 \times 10,000 = 110,000$ messages.
• FloodSet assumes a strictly synchronous model with known upper-bound latency, which does not hold across the public internet or large asynchronous clusters.
• Consequently, FloodSet is predominantly used as a pedagogical foundation and within small, tightly coupled synchronous hardware architectures or mission-critical embedded systems.

---

Summary of Key Takeaways

• Crash Tolerance in Synchronous Systems: The FloodSet algorithm proves that distributed consensus is deterministic and solvable despite node crashes, provided the network is synchronous.
• The $f + 1$ Principle: Running for $f + 1$ rounds guarantees that at least one communication round is free of process crashes, ensuring all non-faulty processes converge on identical sets of observed values.
• Decoupled Flooding and Decision: FloodSet divides consensus into two distinct phases: an information dissemination phase (flooding union sets) and a deterministic decision phase (evaluating cardinality or applying total ordering rules).