Talks and Poster Presentations (with Proceedings-Entry):
H. Moser, U. Schmid:
"Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing";
Talk: Structural Information and Communication Complexity,
Gdansk;
06-26-2011
- 06-29-2011; in: "Proceedings 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11)",
Springer Berlin / Heidelberg,
(2011),
ISBN: 978-3-642-22211-5;
42
- 53.
English abstract:
We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptible state transitions employed in our real-time model, scheduling and queuing effects (which are inherently abstracted away in classic zero step-time models, sometimes leading to overly optimistic time complexity results) can be accurately modeled. Our results thus make fault-tolerant distributed algorithms amenable to a sound real-time analysis, without sacrificing the wealth of algorithms and correctness proofs established in classic distributed computing research. By means of an example, we demonstrate that real-time algorithms generated by transforming classic algorithms can be competitive even w.r.t. optimal real-time algorithms, despite their comparatively simple real-time analysis.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-22212-2_5
Created from the Publication Database of the Vienna University of Technology.