分布式计算中位数算法

“分布式寻找中位数” 这篇1982年的《计算机与系统科学》期刊文章“Finding the Median Distributively”由Michael Rodeh发表，探讨了如何在分布式环境中通过通信进程计算一袋（可能包含重复元素）2n个数字的中位数。每个进程都拥有部分数字，并且假设它们的内存是不重叠的。对于两个进程，文章提出了一种算法，该算法的时间和空间复杂度为线性，而通信复杂度为2log n。此外，还推导出了通信复杂度的下界为log n，表明所提出的算法在常数因子内是通信复杂度最优的。 1. 引言 寻找一袋数字的中位数是一个长期以来吸引许多研究者的问题。Blum等人[1]开发了第一个线性时间复杂度的中位数查找算法，而Schiinhaus等人[6]则提出了一个在最坏情况下执行比较次数更少的算法。在这两种算法中，都假设所有的数字存储在一个处理器的内存中。然而，当数字的数量超过内存大小时，就需要寻找能够在辅助存储上操作的算法。 2. 分布式中位数计算 Rodeh的文章关注的是在分布式系统中的中位数计算，其中数据分布在多个具有本地内存的进程中。这种设置允许处理大到无法一次性加载到单个处理器内存的数据集。 3. 提出的算法 文章中描述的算法适用于两个进程的情况，每个进程持有一部分数字。它能在保持线性时间和空间复杂度的同时，有效地协调进程间的通信以确定中位数。通信复杂度为2log n，这意味着算法需要进行的通信量是数据规模对数的两倍。 4. 通信复杂度的下界 作者进一步证明了在分布式环境下找到中位数的通信复杂度至少为log n，这表明他们提出的算法在通信效率方面接近最优。没有比这个更低的通信复杂度意味着在解决这个问题时，任何其他算法至少需要同样数量的信息交换。 5. 结论 Rodeh的工作提供了一个在分布式环境下的中位数查找算法，它在保持计算效率的同时，优化了通信成本。这对于处理大规模数据分布在网络中的情况具有重要意义，尤其是在计算资源有限但网络通信可以容忍的系统中。 这篇文章为分布式计算环境中的中位数问题提供了重要的理论贡献，不仅给出了一个高效的解决方案，而且确立了其通信复杂度的理论界限。这为后续的分布式计算研究提供了基础和参考。