CoreConcept & Pseudocode Entry

Bully Algorithm

Elects a coordinator in a distributed system by having any node that detects leader failure challenge all higher-ID nodes, so the live process with the highest numeric ID wins.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Systems
Difficulty: Beginner
Family: Leader Election & Coordination
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready
Aliases: Bully Leader Election, Garcia-Molina Coordinator Election

Overview

Hector Garcia-Molina's Bully Algorithm assumes each process has a unique comparable numeric ID and knows the IDs/addresses of all peers. When a process notices the coordinator is unresponsive, it sends ELECTION messages to all processes with higher IDs. If any higher-ID process replies OK, the challenger yields and waits; if no higher-ID process responds within the timeout, the process declares itself the new coordinator and broadcasts COORDINATOR to all lower-ID nodes.

Core Concepts

priority by process IDELECTION / OK / COORDINATOR messagestimeout-based failure detection

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N) messages (when second-highest ID initiates election)

Average

O(N^2) messages

Worst

O(N^2) messages (when lowest ID initiates election)

Space

O(N) peer table

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Bully Algorithm across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(N^2) messages

0.2 min

Offline Batch / Timeout Risk~5.00B ops

Est. Worst-Case TimeO(N^2) messages (when lowest ID initiates election)

0.2 min

Offline Batch / Timeout Risk~5.00B ops

Est. Working MemoryO(N) peer table

1.53 MB

Standard Heap FitN=100,000

When to Use

Use the Bully Algorithm when you need a simple coordinator election protocol in a synchronous or bounded-delay cluster where every node knows the set of peer IDs.
Use it when you want the most capable (highest-ID) live machine to deterministically become leader.

When Not to Use

Avoid in asynchronous networks with partitions where split-brain could elect two coordinators without a majority quorum (use Raft or Paxos instead), or when a flapping high-ID node causes repeated election storms.

What It Does

Elects the highest-ID non-faulty node as cluster coordinator after a leader crash
Allows a recovering highest-ID node to immediately reclaim leadership ('bully' its way back in)

Use Cases

Coordinator election in small-to-medium distributed clusters with known node IDs (e.g., Berkeley clock sync master)
Primary-backup database failover controller selection when message delivery timeouts are bounded
Simple distributed lock manager coordinator recovery

Inputs

Set of N distributed processes with unique numeric IDs 1..N and failure detection timeout T

Outputs

Elected coordinator ID = max{id of currently live processes}

Key Formulas (1)

Worst-Case Message Count

M_worst = (N − 1)(N − 2) / 2 + (N − 1) = O(N²)

M_worst = (N - 1)(N - 2) / 2 + (N - 1) = O(N^2)

Occurs when node 1 initiates an election and every intermediate node 2..N-1 cascades elections.

Pseudocode

1.When process P detects coordinator failure (or recovers):
2. Send ELECTION(P.id) to all processes Q with Q.id > P.id
3. If no OK reply arrives within timeout T:
4. Broadcast COORDINATOR(P.id) to all processes with id < P.id and become leader
5. Else (at least one higher-ID process replied OK):
6. Wait for a COORDINATOR message; if none arrives within 2*T, restart election
7.When process Q receives ELECTION(senderId) with senderId < Q.id:
8. Reply OK to senderId and start Q's own election if not already running

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

When process P detects coordinator failure (or recovers):
Send ELECTION(P.id) to all processes Q with Q.id > P.id
If no OK reply arrives within timeout T:
Broadcast COORDINATOR(P.id) to all processes with id < P.id and become leader
Else (at least one higher-ID process replied OK):
Wait for a COORDINATOR message; if none arrives within 2*T, restart election
When process Q receives ELECTION(senderId) with senderId < Q.id:
Reply OK to senderId and start Q's own election if not already running

Canonical Example

Input: Nodes {1, 2, 3, 4, 5}; Leader 5 crashes; Node 2 detects timeout first
Output: Node 2 challenges {3, 4, 5}; 3 and 4 reply OK; 4 challenges 5 (no reply); Node 4 broadcasts COORDINATOR(4)
Explanation: Higher-ID live nodes take over the election until Node 4 (highest live ID) receives no OK from crashed Node 5 and becomes leader.

Implementation Notes

Suppress duplicate concurrent elections on a node if it has already forwarded an ELECTION message in the current timeout window.

Common Pitfalls

Election thrashing when the highest-ID node repeatedly crashes and recovers ('flapping'); add quarantine backoff before a recovering node initiates an election.
Split-brain during network partitions because Bully relies on timeouts rather than majority quorum intersection.