IEICE TRANSACTIONS on Fundamentals
Computing the Stabilization Times of Self-Stabilizing Systems
Summary :
A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.11 pp.2245-2252
- Publication Date
- 2000/11/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Concurrent Systems Technology)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuhiro TSUCHIYA, Yusuke TOKUDA, Tohru KIKUNO, "Computing the Stabilization Times of Self-Stabilizing Systems" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 11, pp. 2245-2252, November 2000, doi: .
Abstract: A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_11_2245/_p
Copy
@ARTICLE{e83-a_11_2245,
author={Tatsuhiro TSUCHIYA, Yusuke TOKUDA, Tohru KIKUNO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computing the Stabilization Times of Self-Stabilizing Systems},
year={2000},
volume={E83-A},
number={11},
pages={2245-2252},
abstract={A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.},
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - Computing the Stabilization Times of Self-Stabilizing Systems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2245
EP - 2252
AU - Tatsuhiro TSUCHIYA
AU - Yusuke TOKUDA
AU - Tohru KIKUNO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2000
AB - A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.
ER -
English
