Proving time bounds for randomized distributed algorithms

DOI10.1145/197917.198117MaRDI QIDQ5361423zbMATH OpenOpenAlexFDO

Authors Isaac Saias, Roberto Segala, Nancy Lynch

Publication date 29 September 2017

Published in Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing - PODC '94 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9409221

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Abstract: A method of analyzing time bounds for randomized distributed algorithms is presented, in the context of a new and general framework for describing and reasoning about randomized algorithms. The method consists of proving auxiliary statements of the form U (t)->(p) U', which means that whenever the algorithm begins in a state in set U, with probability p, it will reach a state in set U' within time t. The power of the method is illustrated by its use in proving a constant upper bound on the expected time for some process to reach its critical region, in Lehmann and Rabin's Dining Philosophers algorithm.

Cited in

(9)

• Fair termination for parameterized probabilistic concurrent systems
• Switched PIOA: parallel composition via distributed scheduling
• Quantitative program logic and expected time bounds in probabilistic distributed algorithms.
• Testing probabilistic automata
• Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
• Fast and fair randomized wait-free locks
• Compositional verification of randomized distributed algorithms
• Task-structured probabilistic I/O automata
• Randomized dining philosophers without fairness assumption

This page was built for publication: Proving time bounds for randomized distributed algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361423)