Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems
Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems
复制标题
Balls-into-leaves：同步消息传递系统中的亚对数重命名
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
N. Shavit
中科院分区：
文献类型：
--
作者：
Dan Alistarh;O. Denysyuk;L. Rodrigues;N. Shavit
我们考虑以下自然问题：n个容易发生故障的服务器，通过消息传递进行同步通信，必须将自己一对一地分配给n个不同的项目。现有文献提出了两种可能的方法来解决这个问题。首先，将其建模为同步消息传递系统中的严格重命名实例；对于确定性解，已知Θ（log n）个通信回合的紧界。其次，将场景建模为随机负载平衡的实例，其中存在优雅的次对数解决方案。然而，仔细检查发现，已知的负载平衡方案并不适用于我们的场景，因为它们要么不能容忍错误，要么不能确保一对一的分配。因此，人们很自然地会问，对于这个看似简单但有趣的问题，是否存在次对数解。在本文中，我们将这两种方法结合起来，针对一个强自适应对手，提供了一种新的严格重命名随机化解决方案，该方案以高概率在O（log log n）轮通信中终止。我们的解决方案称为balls -into- leaf，它将确定性方法与一种新的随机方案相结合，以获得完全平衡的分配。该算法将项目安排为树的叶子，参与者反复在叶子中进行随机选择。该算法在每一轮中交换信息，将参与者逐渐分成更小的群体，这些群体的随机选择不冲突。然后，我们将算法扩展到在O（log log f）轮w.h.p.中提前终止，其中f是实际的故障数。这些结果暗示了消息传递系统中严格重命名问题的确定性算法和随机算法之间的指数分离。
We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Θ(log n) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O(log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log f) rounds w.h.p., where f is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems.