The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -