Skip to content
AfluidityAlgorithm Atlas
Distributed SystemsAll categories
CoreConcept & Pseudocode Entry

Berkeley Algorithm

Synchronizes physical clocks across a cluster without an external UTC time source by polling all nodes, discarding outlier skews, and adjusting each node to the fault-tolerant average time.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Distributed Systems
Difficulty
Intermediate
Family
Physical & Logical Clock Synchronization
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
3
Code example
Not ready
Visualization
Ready
Aliases
Berkeley Clock Synchronization, Internal Average Physical Clock Sync

Overview

The Berkeley Algorithm elects a coordinator node that periodically polls all machines in a distributed cluster for their current physical clock values, compensating for RTT using Cristian's estimate. The coordinator discards clock readings that deviate beyond a maximum fault threshold, computes the average offset of the remaining healthy clocks, and sends each node a relative adjustment delta.

Core Concepts

coordinator pollingfault-tolerant averageoutlier clock rejectionrelative offset delta

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N) messages per sync round

Average

O(N)

Worst

O(N)

Space

O(N)

Interactive Runtime & Memory Budget Calculator

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

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(N)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(N)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(N)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Use the Berkeley Algorithm when a cluster of machines must keep their physical clocks mutually synchronized without access to an external UTC time server.
  • Use it when sending relative clock adjustments (deltas) avoids introducing new network transit delay on the correction message.

When Not to Use

  • Avoid when strict alignment to external real-world UTC time is required (use Cristian's algorithm or NTP/Marzullo with external stratum servers).

What It Does

  • Agrees on a consistent internal physical wall-clock time across cluster nodes without needing an external GPS/UTC receiver
  • Filters out faulty or runaway clocks before computing the cluster-wide average time offset

Use Cases

  • Internal physical clock synchronization in isolated or air-gapped server clusters
  • Maintaining tight relative wall-clock agreement across distributed database nodes
  • Fault-tolerant cluster time alignment when individual crystal oscillators drift

Inputs

  • Clock readings and RTTs from N cluster nodes, plus maximum skew tolerance tau

Outputs

  • Per-node relative time adjustment delta_i sent to each machine

Key Formulas (1)

Relative Adjustment Delta

δi = (1 / |H|) · sum_{j in H} dj − di
delta_i = (1 / |H|) * sum_{j in H} d_j - d_i

Shifts node i from its current skew d_i to the mean skew of the healthy node subset H.

Pseudocode

  1. 1.Coordinator polls all N nodes and estimates each node's clock skew d_i using RTT/2 compensation
  2. 2.Discard any reading d_i whose pairwise difference from the coordinator or median exceeds fault threshold tau
  3. 3.Compute the average skew avg_d over the remaining healthy nodes (including coordinator d_0 = 0)
  4. 4.For each node i, compute relative adjustment delta_i = avg_d - d_i
  5. 5.Send delta_i to each node i to slew its local physical clock

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

  1. Coordinator polls all N nodes and estimates each node's clock skew d_i using RTT/2 compensation
  2. Discard any reading d_i whose pairwise difference from the coordinator or median exceeds fault threshold tau
  3. Compute the average skew avg_d over the remaining healthy nodes (including coordinator d_0 = 0)
  4. For each node i, compute relative adjustment delta_i = avg_d - d_i
  5. Send delta_i to each node i to slew its local physical clock

Canonical Example

Input
Coordinator at 3:00:00; Node A at +10 ms, Node B at -20 ms, Faulty Node C at +5000 ms (tau = 100 ms)
Output
Node C rejected; average skew of {0, +10, -20} is -3.33 ms; deltas: Coord -3.33 ms, A -13.33 ms, B +16.67 ms
Explanation
Outlier Node C is excluded from the mean, and all healthy nodes receive relative offsets bringing them to 2:59:59.9967.

Implementation Notes

  • If the master coordinator fails, elect a new coordinator using a leader election protocol such as the Bully algorithm.

Common Pitfalls

  • Averaging all clocks blindly without rejecting outliers beyond threshold tau, allowing one runaway clock to skew the entire cluster.
  • Sending an absolute target timestamp instead of a relative delta_i, which would re-introduce one-way network delay error.

Interactive Mechanism Walkthrough & State Debugger

Iterative Convergence & State Trajectory
Berkeley Algorithm mechanism walkthrough step 1 of 5x₀x₁x₂x*
iteration kk = 0
state estimate x_k2.36828
residual |f(x_k)|3.92e-1
convergenceDescending gradient
Step 1 of 5: Coordinator polls all N nodes and estimates each node's clock skew d_i using RTT/2 compensation

Notes

Concept entry for Berkeley Algorithm: verified code implementation pending.

Sources (1)

What each reference supports for this entry.

Gusella & Zatti (1989) — The Accuracy of the Clock Synchronization Achieved by TEMPO in Berkeley UNIX 4.3BSD

Paper

IEEE Transactions on Software Engineering paper defining the Berkeley clock synchronization protocol.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toCristian's Algorithm

Distributed Systems · Core

Synchronizes clocks internally to a fault-tolerant cluster average rather than an external reference server.

Compare with this
Often paired withBully Algorithm

Distributed Systems · Core

Uses leader election to replace the time coordinator if the master node crashes.

Compare with this

Relationships

View full relationship page
Alternative toCristian's Algorithm

Synchronizes clocks internally to a fault-tolerant cluster average rather than an external reference server.

Often paired withBully Algorithm

Uses leader election to replace the time coordinator if the master node crashes.

Related Algorithms

Cristian's AlgorithmMarzullo's Algorithm (NTP Clock Selection)Bully AlgorithmLamport Logical Clocks

Tags

Distributed SystemsClock SynchronizationPhysical TimeFault Tolerance