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

Marzullo's Algorithm (NTP Clock Selection)

Finds the smallest confidence interval intersecting the maximum number of noisy time-server intervals in O(M log M) time, forming the core of NTP clock selection.

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
2
Code example
Not ready
Visualization
Ready
Aliases
NTP Clock Selection, Network Time Protocol Intersection Algorithm, Marzullo Interval Intersection

Overview

Marzullo's Algorithm takes M confidence intervals [offset_i - err_i, offset_i + err_i] from multiple time servers (as in Network Time Protocol / NTP) and identifies the tightest interval contained within the largest clique of mutually consistent servers ('truechimers') while rejecting faulty outlier servers ('falsetickers'). It sorts the 2M interval endpoints and sweeps a depth counter in O(M log M) time.

Core Concepts

confidence interval intersectiontruechimers vs falsetickersendpoint sweep-lineNTP clock selection

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(M log M)

Average

O(M log M)

Worst

O(M log M)

Space

O(M)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Marzullo's Algorithm (NTP Clock Selection) across input scales.

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

95 ns

Sub-microsecond~33
Est. Worst-Case TimeO(M log M)

95 ns

Sub-microsecond~33
Est. Working MemoryO(M)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Use Marzullo's Algorithm (or NTP's intersection algorithm) when synchronizing physical time across multiple noisy time servers where some servers may be faulty or suffer asymmetric network delay.
  • Use it whenever you need the maximum-consensus overlap of 1D uncertainty intervals.

When Not to Use

  • Avoid when you only need causal event ordering without wall-clock uncertainty bounds; use Lamport or Vector Clocks instead.

What It Does

  • Selects the tightest consensus time interval supported by the maximum number of overlapping server confidence intervals
  • Identifies and rejects faulty 'falseticker' time servers in Network Time Protocol (NTP)

Use Cases

  • Network Time Protocol (NTP) clock selection across multiple stratum servers
  • Fault-tolerant sensor fusion where each sensor reports a bounded confidence interval [v - e, v + e]
  • Distributed physical time synchronization resilient to asymmetric routing and faulty clocks

Inputs

  • M server time intervals [L_i, R_i] derived from offset +/- root dispersion/delay

Outputs

  • Consensus intersection interval [bestLow, bestHigh] and count of agreeing servers

Key Formulas (1)

Server Confidence Interval

Ik = [θk − δk / 2 − εk, θk + δk / 2 + εk]
I_k = [theta_k - delta_k / 2 - epsilon_k, theta_k + delta_k / 2 + epsilon_k]

Bounds true clock offset theta_k using round-trip delay delta_k and dispersion epsilon_k.

Pseudocode

  1. 1.Build list of 2M endpoint tuples: (L_i, -1) for interval start and (R_i, +1) for interval end
  2. 2.Sort tuples ascending by coordinate (breaking ties by placing -1 before +1)
  3. 3.Sweep through sorted tuples maintaining active overlap count cnt -= type
  4. 4.Whenever cnt > bestCount, update bestCount = cnt, bestLow = coord, and set bestHigh at the next tuple where cnt drops
  5. 5.Return [bestLow, bestHigh] and midpoint (bestLow + bestHigh) / 2

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. Build list of 2M endpoint tuples: (L_i, -1) for interval start and (R_i, +1) for interval end
  2. Sort tuples ascending by coordinate (breaking ties by placing -1 before +1)
  3. Sweep through sorted tuples maintaining active overlap count cnt -= type
  4. Whenever cnt > bestCount, update bestCount = cnt, bestLow = coord, and set bestHigh at the next tuple where cnt drops
  5. Return [bestLow, bestHigh] and midpoint (bestLow + bestHigh) / 2

Canonical Example

Input
Intervals: S1=[8, 12], S2=[9, 13], S3=[10, 11], Faulty S4=[20, 22]
Output
Consensus interval [10, 11] (supported by 3/4 servers: S1, S2, S3); midpoint = 10.5
Explanation
Sweeping the endpoints finds that [10, 11] lies inside 3 intervals while S4=[20, 22] is isolated as a falseticker.

Implementation Notes

  • Represent each interval [L, R] as two events (L, -1) and (R, +1), sort by coordinate, and track the interval spanning maximum overlap depth.

Common Pitfalls

  • Incorrect tie-breaking when sorting identical endpoint coordinates: start endpoints (-1) must be ordered consistently with end endpoints (+1) so single-point intersections are not missed.

Interactive Mechanism Walkthrough & State Debugger

Iterative Convergence & State Trajectory
Marzullo's Algorithm (NTP Clock Selection) 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: Build list of 2M endpoint tuples: (L_i, -1) for interval start and (R_i, +1) for interval end

Notes

Concept entry for Marzullo's Algorithm (NTP Clock Selection): verified code implementation pending.

Sources (1)

What each reference supports for this entry.

Marzullo (1984) — Maintaining the Time in a Distributed System

Paper

PhD dissertation and OSDIt paper introducing interval intersection for fault-tolerant time service, adopted in NTP.

Open source

Explore Next

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

Open discoveryOpen map
Improves onCristian's Algorithm

Distributed Systems · Core

Combines RTT confidence intervals from multiple Cristian server polls to tolerate faulty 'falseticker' servers.

Compare with this

Relationships

View full relationship page
Improves onCristian's Algorithm

Combines RTT confidence intervals from multiple Cristian server polls to tolerate faulty 'falseticker' servers.

Related Algorithms

Cristian's AlgorithmBerkeley AlgorithmInterval Tree

Tags

Distributed SystemsClock SynchronizationNtpInterval Sweep