题目重点：从 send/recv/barrier 与 10 节点数据出发，比原始收集、局部频表归并和分布式选择，并区分精确众数与近似候选。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版总共 1000 个整数分布在 10 节点；众数定义为全局频次最高值，同频按最小值返回。题目未明确值域、元素字节宽度和 tie-break。
- 令每个值 b 字节、网络有效吞吐 β、局部读速率 ρ、固定消息延迟 α；原文速度描述不够完整，先用符号分析，代入具体数值前确认 bytes/sec 是吞吐还是每字节耗时。
- 精确模式下每个本地出现过的值与频次都可能影响全局众数；不能无条件只上传每个节点的 local mode。中位数按排序后第 500/501 个值的约定也需先固定。
解题路线
- 基线：每节点把原始元素送到 node 0，聚合后计算全局 Counter 和排序/选择。通信总量约 1000b 字节，中心入口最多约 900b；本地算法简单，用来校验任何优化解正确性。
- 精确众数优化：每节点先建 `(value,count)` 频表并发送；若各节点重复度高，唯一值数 u_i≪n_i，传输约 Σu_i·(b+count_bytes)。在全局值域大且几乎全不重复时，频表可能比原始值更大，需自适应选原始还是频表。
- 再分片归并：按稳定 hash(value) 把同一 value 的局部计数送到同一 owner，owner 累加后报告本分片最高候选；所有 owner 中再取全局最高。可用树形汇聚降低 root 热点，树的轮数约 log2(10)；环形 collective 可平摊带宽但轮次和消息切片成本不同。
- 中位数与众数核心不同：可发本地排序样本和边界，使用分布式 pivot/范围计数迭代缩小第 k 个值范围；若值域小，可直接按桶计数归并。精确终止时要能区分并列值和目标 rank，不能只平均 local median。
- 总时间要把每节点读入耗时、local hash/sort、α×消息轮数、网络字节/β、barrier 等待与 skew 加总；值分布偏斜时单个 owner 可能被热点 value 打满，频表压缩也可能显著更好。
手动走一遍
两节点训练例：节点 A 数据 [1,1,2]，节点 B 数据 [2,2,3]。各自 local mode 为 1 和 2，全局 Counter 为 1→2、2→3、3→1，答案 2；若只投票 local mode 而丢频数和其他值，在更一般数据下会错。10 节点、每节点 100 个 8 字节整数的基线传输约 8KB，若一节点只有 5 个不同值，上传它的频表可大幅减少字节，但消息数也要计。
规模与取舍
本地 Counter 期望 O(n_i) 时间和 O(u_i) 空间；全局精确模式 O(Σn_i) 总计算，传输原始方案 O(Nb)、频表方案 O(Σu_i(b+c)) 字节，c 为计数字节数。分布式 median 的轮数取决于值域与 pivot 质量，不能在未知分布下保证固定 O(log N) 次网络往返。
易错点与追问
容易失分的边界
- 只收每节点最频繁的值，可能漏掉每节点第二名但全局第一名。
- 每节点 local median 的平均数不是全局 median。
- 本地频表一定比原始值省通信的断言在全部值唯一时不成立。
- 按常见网络速度改写题目给的读/传输单位，不核对就得出唯一最优算法。
- 只算传输字节、不算固定消息延迟和 barrier 同步等待。
继续深挖
- 如果允许误差 ε 和置信度，heavy hitter sketch 或采样能省多少通信？
- 怎样按 skew 自适应选择中心汇聚、hash 分片或 tree aggregate？
- 求两个中位数位置而非一个时，重复值边界如何判定？
