The Token Distribution Problem
Authors:
- 1 April 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (2) , 229-243
Abstract
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-to-one and one-to-many communication requests, as well as to the solution of load-balancing problems in distributed systems.
Keywords
This publication has 15 references indexed in Scilit:
- Deterministic Simulation of Idealized Parallel Computers on More Realistic OnesSIAM Journal on Computing, 1987
- The generalized packet routing problemTheoretical Computer Science, 1987
- Eigenvalues and expandersCombinatorica, 1986
- Explicit expanders and the Ramanujan conjectures1986
- Parallel Communication With Limited Buffers1984
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- Efficient Schemes for Parallel CommunicationJournal of the ACM, 1984
- A Scheme for Fast Parallel CommunicationSIAM Journal on Computing, 1982
- On the Distribution of the Number of Successes in Independent TrialsThe Annals of Mathematical Statistics, 1956
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952