Distributed System Design: Global Median and Global Mode at Massive Scale

Context

You are designing a distributed analytics system that must compute the global median and the global mode over a dataset with hundreds of billions of records stored across many machines. The system should support both batch and streaming (including sliding windows) and be efficient, fault-tolerant, and scalable.

Assume records each contain a single value x (numeric for median; categorical or integer for mode). You may make minimal, explicit assumptions as needed.

Tasks

1. Specify data partitioning strategies (batch and streaming) to compute:
   • Global median
   • Global mode
2. Define local sketches/summaries computed on each worker.
3. Describe how reducers aggregate partial results.
4. Minimize network I/O (explain how and why).
5. Compare exact vs approximate approaches (quantile sketches, heavy-hitter sketches) with error/resource trade-offs.
6. Discuss handling data skew and hot keys.
7. Address fault tolerance and recovery.
8. Support incremental/streaming updates.
9. Provide time, space, and communication complexity.
10. Extend the design to a sliding-window median and mode over an unbounded stream.