FloodMax Algorithm for Leader Election in Distributed Systems

Leader election is a fundamental building block in distributed systems. When a coordinator or leader node fails, the cluster must recover autonomously without human intervention to maintain high availability and prevent split-brain states. While many classical election algorithms assume a specific network topology (such as rings or trees), real-world distributed architectures often exhibit arbitrary, interconnected topologies.

FloodMax is a simple, robust leader election algorithm that operates on arbitrary network topologies, electing the node with the highest unique identifier (UID) by flooding the network over a bounded number of synchronous rounds.

---

1. Network Assumptions and Prerequisites

To understand FloodMax, several foundational assumptions and definitions must be clarified:

Arbitrary Network Topology

FloodMax makes no assumptions about the structure of the network. It does not require a logical ring, star, tree, or fully connected mesh. As long as the network graph is connected (meaning every node has at least one path to every other node), FloodMax functions correctly.

Comparable Unique Identifiers (UIDs)

Every node $v$ in the network is assigned a distinct, comparable UID (e.g., node $1, 7, 18$). The objective is to elect the node with $\max(\text{UID})$ as the leader.

The Diameter of a Network ($D$)

The network diameter ($D$) is defined as the maximum shortest-path distance between any pair of nodes in the graph:

$D = \max_{u, v \in V} \text{dist}(u, v)$

• If two nodes are directly adjacent, the shortest path between them is $1$ edge.
• If two nodes require traversing multiple hops, the distance is the minimum number of hops between them.
• The diameter represents the worst-case propagation delay (in hops) required for a message sent by any node to reach every other node in the network.

Core Assumption: For the standard FloodMax algorithm to terminate correctly, every node must know the network diameter ($D$) beforehand. This value determines the exact number of rounds each node must execute before finalizing the election.

---

2. How the FloodMax Algorithm Works

The intuition behind FloodMax is direct: flood the network with the maximum identifier observed so far.

Round 1: Every node broadcasts its own UID to immediate neighbors.
Round 2 to D: Every node updates its known max UID and broadcasts it.
After Round D: If max_seen == self.UID, the node declares itself Leader.

Step-by-Step Execution

1. Initialization:

   • Each node initializes a local variable max_uid to its own identifier: max_uid = self.uid.
   • Each node initializes a round counter: round = 1.

2. Rounds $1$ through $D$:

   • In each round, every node broadcasts its current max_uid to all of its immediate neighbors.
   • Every node collects incoming UID messages from its neighbors.
   • Each node updates its max_uid: $\text{max\_uid} = \max(\text{max\_uid}, \text{incoming\_uids})$

3. Termination (After Round $D$):

   • Because the algorithm runs for $D$ synchronous rounds, the message originating from the node with the true maximum UID is guaranteed to traverse across the longest possible shortest path and reach every single node in the network.
   • Each node inspects its local max_uid:
     • If $\text{max\_uid} == \text{self.uid}$, the node marks its state as LEADER.
     • If $\text{max\_uid} \neq \text{self.uid}$, the node marks its state as NON-LEADER (follower), knowing that the node matching max_uid is the leader.

sequenceDiagram
    autonumber
    participant NodeA as Node 3
    participant NodeB as Node 7
    participant NodeC as Node 18 (Max)

    Note over NodeA,NodeC: Round 1: Local state broadcasted
    NodeA->>NodeB: UID: 3
    NodeB->>NodeA: UID: 7
    NodeB->>NodeC: UID: 7
    NodeC->>NodeB: UID: 18

    Note over NodeA,NodeC: Round 2: Propagate highest observed
    NodeB->>NodeA: UID: 18
    NodeB->>NodeC: UID: 18

    Note over NodeA,NodeC: After Round D (D=2): Halting Condition
    Note over NodeA: max_seen (18) != self (3) -> FOLLOWER
    Note over NodeB: max_seen (18) != self (7) -> FOLLOWER
    Note over NodeC: max_seen (18) == self (18) -> LEADER

---

3. Algorithm Pseudocode

def run_floodmax(node_id: int, neighbors: list, network_diameter: int):
    max_seen = node_id
    
    for round_num in range(1, network_diameter + 1):
        # Send current max_seen to all immediate neighbors
        for neighbor in neighbors:
            send_message(to=neighbor, payload=max_seen)
            
        # Receive messages from all neighbors for this round
        received_uids = receive_messages_from_neighbors()
        
        # Update the maximum UID observed
        for uid in received_uids:
            if uid > max_seen:
                max_seen = uid
                
    # Decision phase after D rounds
    if max_seen == node_id:
        role = "LEADER"
    else:
        role = "NON_LEADER"
        
    return role, max_seen

---

4. Complexity Analysis

Time Complexity

• The algorithm executes in lock-step synchronous rounds.
• The total number of rounds is strictly dictated by the diameter of the network, $D$.
• Time Complexity: $O(D)$ rounds.

Communication (Message) Complexity

• In the naive implementation, every node broadcasts a message across every outgoing directed edge in every round.
• Let $|E|$ be the total number of directed edges in the network.
• In each of the $D$ rounds, $|E|$ messages are sent.
• Message Complexity: $O(D \cdot |E|)$ messages.

For dense graphs where $|E| \approx O(V^2)$, the unoptimized FloodMax algorithm generates significant network bandwidth overhead.

---

5. Optimizations to Reduce Message Complexity

While the time complexity $O(D)$ is optimal for flooding across arbitrary graphs, exchanging messages on every edge in every round is wasteful. Two key optimizations substantially reduce the total messages exchanged:

Optimization 1: Broadcast Only on State Change

In the naive version, nodes send their max_seen value in every round, regardless of whether it has changed.

• Refinement: A node only sends a broadcast to its neighbors if its max_seen value actually increases during the current round.
• If a node receives incoming values that are all smaller than or equal to its current max_seen, it remains silent in the next round.
• Nodes with smaller initial UIDs quickly cease transmission once higher UIDs reach them, saving network traffic.

Optimization 2: Suppress Echoing Back to the Sender

When a node updates its max_seen due to a message from a particular neighbor, transmitting that same value back to that neighbor is redundant.

• Refinement: If Node $B$ receives a new maximum UID $X$ from Node $C$, Node $B$ does not forward $X$ back to Node $C$.
• Node $C$ already knows $X$ (and likely sourced it or received it earlier). Suppressing this return edge eliminates useless traversals and immediate message discards.

---

6. Summary Comparison & Trade-offs

Attribute	FloodMax (Naive)	FloodMax (Optimized)
Topology Requirements	Arbitrary connected graph	Arbitrary connected graph
Prerequisite Knowledge	Network Diameter ($D$)	Network Diameter ($D$)
Round / Time Complexity	$O(D)$	$O(D)$
Worst-Case Messages	$O(D \cdot	E
Average-Case Messages	High (transmits on every edge)	Significantly lower via selective broadcast
Halting Condition	Synchronous round count reaches $D$	Synchronous round count reaches $D$

Key Takeaways

1. Topology Agnostic: Unlike ring-based leader election algorithms (such as Chang-Roberts or HS), FloodMax does not require maintaining a virtual ring overlay.
2. Diameter Dependency: The correctness and termination of the algorithm hinge entirely on knowing the network diameter $D$. Underestimating $D$ can cause split-brain states where multiple nodes consider themselves leaders; overestimating $D$ adds unnecessary round latency.
3. Flooding Efficiency: With simple message suppression checks (broadcasting only on state change and avoiding echoes), FloodMax becomes a practical baseline for leader election in synchronous, fixed-topology networks.