Computing the Stabilization Times of SElf-Stabilizing Systems (Special Section on Concurrent Systems Technology)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2000-11-25
著者
-
Kikuno Tohru
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
Tsuchiya Tatsuhiro
Graduate School Of Information Science And Technology Osaka University
-
Tsuchiya Tatsuhiro
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
Tsuchiya Tatsuhiro
The Department Of Informatics And Mathematical Science Osaka University
-
TOKUDA Yusuke
the Department of Informatics and Mathematical Science, Osaka University
-
Tokuda Yusuke
The Department Of Informatics And Mathematical Science Osaka University
-
Tsuchiya Tatsuhiro
Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka Univ
-
Kikuno Tohru
The Department Of Informatics And Mathematical Science Osaka University
関連論文
- Feature Interaction Verification Using Unbounded Model Checking with Interpolation
- Probabilistic Model Checking of the One-Dimensional Ising Model
- An Effective Testing Method for Hardware Related Fault in Embedded Software(Software Engineering for Embedded Systems)
- Feature Interaction Detection by Bounded Model Checking(Dependable Communication)(Dependable Computing)
- Software Project Simulator for Effective Process Improvement (特集 〔情報処理学会〕創立40周年記念論文)
- Three-Mode Failure Model for Reliability Analysis of Distributed Programs (Special Issue on Fault-Tolerant Computing)
- Verifying Fault Tolerance of Concurrent Systems by Model Checking(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- A Hierarchical Approach to Dependability Evaluation of Distributed Systems with Replicated Resources
- Computing the Stabilization Times of SElf-Stabilizing Systems (Special Section on Concurrent Systems Technology)
- New Constructions for Nondominated k-Coteries
- Constructing a Bayesian Belief Network to Predict Final Quality in Embedded System Development(Software Engineering for Embedded Systems)
- Test Item Prioritizing Metrics for Selective Software Testing(Software Engineering)
- Enhancing Software Project Simulator toward Risk Prediction with Cost Estimation Capability(Special Section on Concurrent Systems Technology)
- Experimental Evaluation of Two-Phase Project Control for Software Development Process(Special Section on Concurrent Systems Technology)
- A New Verification Method Using Virtual System States for Responsive Communication Protocols and Its Application to a Broadcasting Protocol(Special Section on Concurrent Systems Technology)
- Timed Reachability Analysis Method for Communication Protocols Modeled by Extended Finite State Machines (Special Issue on Multimedia Communication and Distributed Processing)
- Experimental Evaluation of Processor Scheduling Algorithm for Parallel Logic Simulation Using Benchmark Circuits
- New 2-Factor Covering Designs for Software Testing(Regular Section)
- A BDD-based approach to reliability-optimal module allocation in networks (信頼性)
- SAT and SMT based model checking of concurrent systems (コンカレント工学)
- Parallelizing SDP(Sum of Disjoint Products)Algorithms for Fast Reliability Analysis
- An Energy-Efficient Broadcast Scheme for Multihop Wireless Ad Hoc Networks Using Variable-Range Transmission Power(Networks)
- Effective Scheduling of Duplicated Tasks for Fault Tolerance in Multiprocessor Systems
- Error Models and Fault-Secure Scheduling in Multiprocessor Systems
- Constructing Overlay Networks with Short Paths and Low Communication Cost