License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.31
URN: urn:nbn:de:0030-drops-100918
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10091/
Go to the corresponding LIPIcs Volume Portal

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

Self-Stabilizing Token Distribution with Constant-Space for Trees

pdf-format:
LIPIcs-OPODIS-2018-31.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{sudo_et_al:LIPIcs:2018:10091,
  author =	{Yuichi Sudo and Ajoy K. Datta and Lawrence L. Larmore and Toshimitsu Masuzawa},
  title =	{{Self-Stabilizing Token Distribution with Constant-Space for Trees}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10091},
  URN =		{urn:nbn:de:0030-drops-100918},
  doi =		{10.4230/LIPIcs.OPODIS.2018.31},
  annote =	{Keywords: token distribution, self-stabilization, constant-space algorithm}
}

Keywords: token distribution, self-stabilization, constant-space algorithm
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI