Bounded Fairness for Probabilistic Distributed Algorithms

Pepijn Crouzen, Ernst Moritz Hahn, Holger Hermanns, Abhishek Dhama, Oliver E. Theel, Ralf Wimmer, Bettina Braitling, Bernd Becker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

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.
Original languageEnglish
Title of host publication11th International Conference on Application of Concurrency to System Design, ACSD 2011, Newcastle Upon Tyne, UK, 20-24 June, 2011
Pages89-97
Number of pages9
DOIs
Publication statusPublished - 2011
Externally publishedYes

Fingerprint Dive into the research topics of 'Bounded Fairness for Probabilistic Distributed Algorithms'. Together they form a unique fingerprint.

  • Cite this

    Crouzen, P., Hahn, E. M., Hermanns, H., Dhama, A., Theel, O. E., Wimmer, R., Braitling, B., & Becker, B. (2011). Bounded Fairness for Probabilistic Distributed Algorithms. In 11th International Conference on Application of Concurrency to System Design, ACSD 2011, Newcastle Upon Tyne, UK, 20-24 June, 2011 (pp. 89-97) https://doi.org/10.1109/ACSD.2011.21