Skip to main content

How Good is Weak Stabilization?

Publication Type
Year of Publication
2013
Conference/Journal Name
In International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Publisher
Springer
Abstract
A weak-stabilizing system is one that guarantees only the possibility of convergence to a correct behavior; i.e., a recovery path may
visit an execution cycle before reaching a good behavior. To our knowledge, there has been no work on analyzing the power and performance of weak-stabilizing algorithms. In this paper, we investigate a metric for characterizing the recovery time of weak-stabilizing algorithms. This metric is based on expected mean value of recovery steps for resuming a correct behavior. Our method to evaluate this metric is based on probabilistic state exploration. We show that different weak-stabilizing algorithms perform differently during recovery, because of their structure (e.g., the length and reachability of cycles). We also introduce an automated technique that can improve the performance of implementation of weak-stabilizing algorithms through state encoding.