49/2011 : Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing

RR Number

49/2011

Conference

Proceedings 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11)

Author(s)

Heinrich Moser, Ulrich Schmid

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.

Bibtex

@inproceedings{MS11:sirocco,
 author = {Moser, Heinrich and Schmid, Ulrich},
 title = {Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Comput
ing},
 booktitle = {Proceedings 18th International Colloquium on
              Structural Information and Communication Complexity (SIROCCO'11)},
 series =    {LNCS},
 year =     {2011},
 isbn = {978-3-642-22211-5},
 location = {Gda\'nsk, Poland},
 pages = {42--53},
 numpages = {12},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg}
} 

Download

Get transform.pdf - Adobe PDF-format, (158.99 KB; posted at January 26 2012; )