Bounded fairness for probabilistic distributed algorithms

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 publicationProceedings - 11th International Conference on Application of Concurrency to System Design, ACSD 2011
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages89-97
Number of pages9
ISBN (Print)978-1-61284-974-4
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event11th International Conference on Application of Concurrency to System Design, ACSD 2011 - Newcastle Upon Tyne, United Kingdom
Duration: 20 Jun 201124 Jun 2011
Conference number: 11

Publication series

NameInternational Conference on Application of Concurrency to System Design
PublisherIEEE
Volume2011
ISSN (Print)1550-4808

Conference

Conference11th International Conference on Application of Concurrency to System Design, ACSD 2011
Abbreviated titleACSD 2011
CountryUnited Kingdom
CityNewcastle Upon Tyne
Period20/06/1124/06/11

Keywords

  • Bounded fairness
  • Markov decision processes
  • Schedulers

Fingerprint

Dive into the research topics of 'Bounded fairness for probabilistic distributed algorithms'. Together they form a unique fingerprint.

Cite this