Adaptive Massively Parallel Algorithms for Cut Problems
Adaptive Massively Parallel Algorithms for Cut Problems
复制标题
用于解决问题的自适应大规模并行算法
DOI：
10.1145/3490148.3538576
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Saleh, Hamed
中科院分区：
文献类型：
--
作者：
Hajiaghayi, MohammadTaghi;Knittel, Marina;Olkowski, Jan;Saleh, Hamed
研究了自适应大规模并行计算（AMPC）模型中的加权最小割问题。2019年，Behnezhad等人推出了AMPC模型，作为大规模并行计算（MPC）模型的扩展。在过去的十年中，对高可扩展性算法的研究对许多大规模系统产生了重大影响。MPC模型是由Karloff等人于2010年推出的，它是对著名的实用框架（如MapReduce、Hadoop、Flume和Spark）的抽象，一直处于这一研究的前沿。虽然在为一系列问题创建高效的MPC算法方面已经取得了很大的进步，但最近的进展受到1 vs 2周期猜想[20]的限制，该猜想假设区分一个和两个周期的简单问题需要Ω（log n）个MPC轮。在AMPC模型中，即使通信受到限制（例如，在一轮中），每台机器也对分布式哈希表具有自适应读访问。在保持实用性的同时，这使算法能够绕过像1 vs 2周期猜想这样的限制。
We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. In 2019, Behnezhad et al. [3] introduced the AMPC model as an extension of the Massively Parallel Computation (MPC) model. In the past decade, research on highly scalable algorithms has had significant impact on many massive systems. The MPC model, introduced in 2010 by Karloff et al. [16], which is an abstraction of famous practical frameworks such as MapReduce, Hadoop, Flume, and Spark, has been at the forefront of this research. While great strides have been taken to create highly efficient MPC algorithms for a range of problems, recent progress has been limited by the 1-vs-2 Cycle Conjecture [20], which postulates that the simple problem of distinguishing between one and two cycles requires Ω(log n) MPC rounds. In the AMPC model, each machine has adaptive read access to a distributed hash table even when communication is restricted (i.e., in the middle of a round). While remaining practical [4], this gives algorithms the power to bypass limitations like the 1-vs-2 Cycle Conjecture.