The token distribution problem
The token distribution problem
复制标题
代币分配问题
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
E. Upfal
中科院分区：
文献类型：
--
作者：
D. Peleg;E. Upfal
提出了解决以下基本沟通问题的解决方案。假设n个令牌是任意分布在n个处理器之间的，没有处理器的含量超过k令牌。问题是指定一个有界度的网络拓扑和可以在处理器之间统一分配令牌的算法。第一个结果是紧密的$ theta（k + log n）$绑定了此问题的复杂性。还表明，可以在任何具有足够大的扩展因子的扩展器图上以$ o（k + log n）$确定求解此问题的大致版本。在这项工作的第二部分中，它显示了如何扩展对于类似的扩展器图上的确切分布问题的最佳概率算法的近似分布问题的解决方案。请注意，通过扩展器图的通信是问题解决方案的必要条件。这些结果直接应用于有效实施许多...
A solution to the following fundamental communication problem is presented. Suppose that n tokens are arbitrarily distributed among n processors with no processor having more than K tokens. The problem is to specify a bounded-degree network topology and an algorithm that can distribute the tokens uniformly among the processors.The first result is a tight $Theta (K + log n)$ bound on the complexity of this problem. It is also shown that an approximate version of this problem can be solved deterministically in $O(K + log n)$ on any expander graph with sufficiently large expansion factor.In the second part of this work, it is shown how to extend the solution for the approximate distribution problem to an optimal probabilistic algorithm for the exact distribution problem on a similar class of expander graphs. Note that communication through an expander graph is a necessary condition for an $O(K + log n)$ solution of the problem.These results have direct applications to the efficient implementation of many...