Self-Stabilizing Token Distribution with Constant-Space for Trees

Authors Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, Toshimitsu Masuzawa



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.31.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Yuichi Sudo
  • Graduate School of Information Science and Technology, Osaka University, Japan
Ajoy K. Datta
  • Department of Computer Science, University of Nevada, Las Vegas, USA
Lawrence L. Larmore
  • Department of Computer Science, University of Nevada, Las Vegas, USA
Toshimitsu Masuzawa
  • Graduate School of Information Science and Technology, Osaka University, Japan

Cite AsGet BibTex

Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Self-Stabilizing Token Distribution with Constant-Space for Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.31

Abstract

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be equal to nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. A self-stabilizing token distribution algorithm that converges within O(n l) asynchronous rounds and needs Theta(nh epsilon) redundant (or unnecessary) token moves is given, where epsilon = min(k,l-k) and h is the height of the tree network. Two novel ideas to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nh l). All algorithms given have constant memory at each process and each link register.

Subject Classification

ACM Subject Classification
  • Theory of computation → Self-organization
Keywords
  • token distribution
  • self-stabilization
  • constant-space algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Anish Arora and Mohamed G. Gouda. Load balancing: An exercise in constrainted convergence. In Proceedings of the 9th International Workshop on Distributed Algorithms, pages 183-197, 1995. Google Scholar
  2. Andrei Z. Broder, Alan M. Frieze, Eli Shamir, and Eli Upfal. Near-perfect token distribution. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming, pages 308-317, 1992. Google Scholar
  3. Alain Bui, Ajoy K Datta, Franck Petit, and Vincent Villain. Snap-stabilization and PIF in tree networks. Distributed Computing, 20(1):3-19, 2007. Google Scholar
  4. Ajoy K Datta, Laurence L Larmore, Toshimitsu Masuzawa, and Yuichi Sudo. A self-stabilizing minimal k-grouping algorithm. In Proceedings of the 18th International Conference on Distributed Computing and Networking, pages 3:1-3:10. ACM, 2017. Google Scholar
  5. Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Constant space self-stabilizing center finding in anonymous tree networks. In Proceedings of the International Conference on Distributed Computing and Networking, pages 38:1-38:10, 2015. Google Scholar
  6. EW Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the Association of Computing Machinery, 17:643-644, 1974. Google Scholar
  7. Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, and David Zuckerman. Tight analyses of two local load balancing algorithms. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 548-558, 1995. Google Scholar
  8. Kieran T. Herley. A note on the token distribution problem. Inf. Process. Lett., 38(6):329-334, 1991. Google Scholar
  9. Michael E. Houle, Antonios Symvonis, and David R. Wood. Dimension-exchange algorithms for load balancing on trees. In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, pages 181-196, 2002. Google Scholar
  10. Michael E. Houle, Ewan D. Tempero, and Gavin Turner. Optimal dimension-exchange token distribution on complete binary trees. Theor. Comput. Sci., 220(2):363-376, 1999. Google Scholar
  11. Michael E. Houle and Gavin Turner. Dimension-exchange token distribution on the mesh and the torus. Parallel Computing, 24(2):247-265, 1998. Google Scholar
  12. Luciano Margara, Alessandro Pistocchi, and Marco Vassura. Perfect token distribution on trees. In Proceedings of Structural Information and Communication Complexity, 11th International Colloquium, pages 221-232, 2004. Google Scholar
  13. D. Peleg. Distributed computing: a locality-sensitive approach, volume 5. Society for Industrial Mathematics, 2000. Google Scholar
  14. David Peleg and Eli Upfal. The generalized packet routing problem. Theor. Comput. Sci., 53:281-293, 1987. Google Scholar
  15. David Peleg and Eli Upfal. The token distribution problem. SIAM J. Comput., 18(2):229-243, 1989. Google Scholar
  16. Yuichi Sudo, Ajoy K. Datta, Laurence L. Larmore, and Toshimitsu Masuzawa. Constant-space self-stabilizing token distribution in trees. In Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 25-29, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail