[CrouzenHHDTWBB11]
Bounded Fairness for Probabilistic Distributed Algorithms
In 11th International Conference on Application of Concurrency
to System Design (ACSD), pages 89-97, IEEE, 2011.
Downloads: pdf, bibURL: http://doi.ieeecomputersociety.org/10.1109/ACSD.2011.21
Abstract. This paper investigates quantitative dependability metrics for
distributed algorithms operating in the presence of sporadic or frequently
occurring faults. In particular, we investigate necessary revisions of
traditional fairness assumptions in order to arrive at useful metrics, without
adding hidden assumptions that may obfuscate their validity. We formulate
faulty distributed algorithms as Markov decision processes to incorporate both
probabilistic faults and non-determinism arising from concurrent execution. We
lift the notion of bounded fairness to the setting of Markov decision
processes. Bounded fairness is particularly suited for distributed algorithms
running on nearly symmetric infrastructure, as it is common for sensor network
applications. Finally, we apply this fairness notion in the quantitative
model-checking of several case studies.