• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International symposium on distributed computing >Gossip Protocols for Renaming and Sorting
【24h】

Gossip Protocols for Renaming and Sorting

机译：用于重命名和排序的八卦协议

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an n-node network supporting point-to-point communication, and in every round, each node exchanges information of size O(log n) bits with (at most) one other node. We first consider the renaming problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space {1,..., (1 + ε)n}, for any fixed ε ＞ 0. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,..., n}, in O(log~2 n) rounds. Next we study the following sorting problem. Nodes have consecutive IDs 1 up to n, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank k is located at the node with ID k. Jelasity and Kermarrec suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Ω(n) rounds. We prove that the same protocol works in O(log~2 n) rounds if peers are chosen according to a non-uniform power law distribution.
机译：我们为一些基本的分布式任务设计了有效的基于八卦的协议。该协议假定一个支持点对点通信的n节点网络，并且在每一轮中，每个节点与（最多）一个其他节点交换大小为O（log n）位的信息。我们首先考虑重命名问题，即从较小的ID空间向网络的所有节点分配不同的ID。我们提出了一种重命名协议，该协议使用自然的推或拉方法在节点之间划分ID空间，对于任何固定的ε＞ 0，ID空间为{1，...，（1 +ε）n}，实现对数舍入复杂度。该协议的变体解决了严格的重命名问题，其中每个节点在O（log〜2 n）次回合中的{1，...，n}中获得唯一的ID。接下来，我们研究以下排序问题。节点具有1到n的连续ID，并且它们接收数值作为输入。然后，他们必须交换这些输入，以便最终将等级k的输入放置在ID为k的节点上。 Jelasity和Kermarrec提出了一种简单自然的协议，其中节点与随机选择的统一对等节点交换值，但不难看出该协议需要Ω（n）次回合。我们证明，如果根据非均匀幂律分布选择对等方，则相同的协议可以在O（log〜2 n）轮中工作。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号