Title :
Bounded Fairness for Probabilistic Distributed Algorithms
Author :
Crouzen, Pepijn ; Hahn, Ernst Moritz ; Hermanns, Holger ; Dhama, Abhishek ; Theel, Oliver ; Wimmer, Ralf ; Braitling, Bettina ; Becker, Bernd
Author_Institution :
Saarland Univ., Saarbrucken, Germany
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.
Keywords :
Markov processes; distributed algorithms; formal verification; probability; Markov decision processes; faulty distributed algorithms; probabilistic distributed algorithms; quantitative model-checking; Algorithm design and analysis; Analytical models; Distributed algorithms; Markov processes; Probabilistic logic; Random variables; Transient analysis; Markov decision processes; bounded fairness; schedulers;
Conference_Titel :
Application of Concurrency to System Design (ACSD), 2011 11th International Conference on
Conference_Location :
Newcastle Upon Tyne
Print_ISBN :
978-1-61284-974-4
DOI :
10.1109/ACSD.2011.21