DocumentCode :
2828770
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
fYear :
2011
fDate :
20-24 June 2011
Firstpage :
89
Lastpage :
97
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Application of Concurrency to System Design (ACSD), 2011 11th International Conference on
Conference_Location :
Newcastle Upon Tyne
ISSN :
1550-4808
Print_ISBN :
978-1-61284-974-4
Type :
conf
DOI :
10.1109/ACSD.2011.21
Filename :
5988921
Link To Document :
بازگشت