Finding the Mode of Data Spread Across Many Machines

0) Problem Restatement

A huge multiset (a list of values with repeats) is split across W worker machines. Find the mode, the value that appears most often, exactly, without sending every raw item to one machine (too much network and memory). Anthropic asked this.

1) Why the Naive Ideas Fail

• Send everything to one machine: too much data (billions of items) for one machine's network and memory.
• Each worker returns its local mode, and pick the biggest: wrong. Example: worker 1 has {a:10, b:9}, worker 2 has {c:10, b:9}. The local modes are a and c (10 each), but globally b = 18 wins.

2) Exact Algorithm (MapReduce style)

1. Local count (combiner): each worker counts its own items with a hash map, value → count. This shrinks the data a lot when values repeat.
2. Shuffle by value: send each (value, local_count) to the worker hash(value) % W. Now all partial counts for a value arrive at the same worker.
3. Reduce: each worker sums the counts for the values it owns → exact global counts for its share of values → its local max (value, count).
4. Final: each worker sends just its best (value, count) to a coordinator, which picks the overall max. That's only W small messages.

flowchart LR
    W1["Worker 1: count locally"] -->|"hash(value)"| R1["Reducer A"]
    W1 --> R2["Reducer B"]
    W2["Worker 2: count locally"] --> R1
    W2 --> R2
    W3["Worker 3: count locally"] --> R1
    W3 --> R2
    R1 -->|"best (value, count)"| CO["Coordinator - global max"]
    R2 --> CO

This is correct because after the shuffle, every value's full count lives on exactly one reducer, so the max over reducers' maxima is the true mode.

3) Cost

• Network = the number of distinct (value, worker) pairs after local counting. When there are few distinct values, it's tiny. When almost all values are unique, it's close to the raw data (but then the mode's count is small anyway).
• Memory: each reducer holds counts only for its hash range. If it doesn't fit, sort and spill to disk (external aggregation), or use more reducers.

4) Handling Skew and Scale

• Skew: one value might be extremely common, sending huge partial counts to one reducer. Local combining already solves most of this (each worker sends one number per value, not every occurrence).
• Pruning trick (optional): each worker reports its top-k locally with counts, and a threshold algorithm can prove the winner without the full shuffle in many cases (the sum of the remaining possible counts can't beat the current best). It's useful when the data is very skewed.
• Approximate alternative: if an exact answer isn't required, each worker builds a Count-Min Sketch (fixed small memory, mergeable by adding arrays) plus a small heavy-hitter list. Merge the sketches and pick the top candidate. It needs far less network, with a small, bounded error.

5) Code Sketch (single process simulating workers)

from collections import Counter

def distributed_mode(partitions, num_reducers=4):
    reducers = [Counter() for _ in range(num_reducers)]
    for part in partitions:                      # each "worker"
        local = Counter(part)                    # 1) combine locally
        for value, c in local.items():           # 2) shuffle by hash
            reducers[hash(value) % num_reducers][value] += c
    best = [r.most_common(1)[0] for r in reducers if r]   # 3) reducer maxima
    return max(best, key=lambda vc: vc[1])       # 4) global max

print(distributed_mode([["a"]*10 + ["b"]*9, ["c"]*10 + ["b"]*9]))   # ('b', 18)

6) Wrap-Up

Local modes can be wrong, so count locally, hash-partition the (value, count) pairs so each value's complete count lands on one reducer, sum them there, take each reducer's max, and pick the global max from those few candidates. Local combining keeps network cost low and tames skew, spilling handles memory limits, and sketches give a cheap approximate answer when exactness isn't needed.