Compute Exact Mode and Median Across Distributed Nodes

# Compute Exact Mode and Median Across Distributed Nodes Ten worker nodes collectively hold 1,000 numeric elements. The elements are partitioned across nodes, and the network is the main bottleneck. Explain how to compute the exact mode and exact median while minimizing data movement. Discuss how the strategy changes for a small bounded value domain versus high-cardinality values, and for roughly uniform versus heavily skewed data. Compare useful tree, ring, shuffle, gather, and broadcast collective patterns. For the mode, break ties by returning the smallest value. For the median, sort the global multiset conceptually; with an even element count, return the arithmetic mean of the two middle values. ### Clarifying Questions to Ask - What numeric type and value range are used, and is exact arithmetic required for the even-count median? - How are elements currently partitioned, and may a node spill intermediate state to disk? - Are collectives supplied by the runtime, and what are their latency and bandwidth characteristics? - Is this a one-time computation or a repeated aggregation over changing data? ### Part 1 — Compute the exact mode Describe local aggregation and the minimum information that must cross the network for bounded and unbounded value domains. #### What This Part Should Cover - Local frequency maps or histograms. - Reduction when every node can hold the domain, or hash partitioning of distinct keys otherwise. - Deterministic tie handling and a final small reduction of local winners. - The effect of a hot value or high-cardinality uniform data on communication and load balance. ### Part 2 — Compute the exact median Present at least one exact strategy and explain when gathering all 1,000 elements is preferable to a more sophisticated distributed selection protocol. #### What This Part Should Cover - Local counts or sorted runs and a globally correct rank definition. - Histogram reduction for a bounded domain, or pivot-and-count / range-partition selection for a large domain. - How the two middle ranks are resolved when the total count is even. - Round trips, bytes moved, skew behavior, and termination. ### What a Strong Answer Covers - Starts with the small observed data size and compares simple gather cost against coordination overhead. - Gives exact, not approximate, mode and median algorithms. - Separates network volume from number of collective rounds and local memory cost. - Explains when tree, ring, shuffle, gather, and broadcast patterns fit the intermediate data shape. ### Follow-up Questions 1. How would the answer change for ten billion values rather than 1,000? 2. How would you recover if one node fails after contributing a partial aggregate? 3. When would an approximate heavy-hitter or quantile sketch be a better product decision?