Abstract | ||
---|---|---|
A self-stabilizing system is one that converges to a legitimate state from any arbitrary state. Such an arbitrary state may be reachable due to wrong initialization or the occurrence of transient faults. Average recovery time of self-stabilizing systems is a key factor in evaluating their performance, especially in the domain of network and robotic protocols. This paper introduces a groundbreaking result on automated repair and synthesis of self-stabilizing protocols whose average recovery time is required to satisfy certain constraints. We show that synthesizing and repairing weak-stabilizing protocols under average recovery time constraints is NP-complete. To cope with the exponential complexity (unless P = NP), we propose a polynomial-time heuristic. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/ICDCS.2015.65 | 2015 IEEE 35th International Conference on Distributed Computing Systems |
Keywords | Field | DocType |
Synthesis,Repair,Fault-tolerance,Recovery | Heuristic,Computer science,Fault tolerance,Exponential complexity,Initialization,Distributed computing | Conference |
ISSN | Citations | PageRank |
1063-6927 | 1 | 0.37 |
References | Authors | |
14 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Saba Aflaki | 1 | 6 | 0.78 |
Fathiyeh Faghih | 2 | 11 | 4.33 |
Borzoo Bonakdarpour | 3 | 490 | 45.02 |