.png){kind=icon}
返回
Self-stabilizing token distribution on trees with constant space
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2020.07.007.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 uniformly 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 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. First, a self-stabilizing token distribution algorithm that converges within O(nl) 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. Next, two novel mechanisms 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(nhl). All given algorithms have constant memory at each process and each link register. (C) 2020 The Author(s). Published by Elsevier Inc.
Keyword:
Token distribution
Self-stabilization
Constant space algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
.png){kind=icon}
