[ main ] [ back ]

43/2010 : Real-Time Analysis of Round-based Distributed Algorithms

RR Number
43/2010
Conference
Proceedings of the 1st International Real-Time Scheduling Open Problems Seminar (RTSOPS'10), in conjunction with 22nd Euromicro Conference on Real-Time Systems (ECRTS'10)
Author(s)
Alexander Kößler, Heinrich Moser, Ulrich Schmid
Abstract
Despite decades of research on networked fault-tolerant distributed systems, sound results on their real-time properties only exist for time-triggered synchronous systems: Given that classic distributed computing models are based on state machines with zero-time computing steps, queueing effects and scheduling are inherently abstracted away. We have developed a real-time distributed computing model based on non-zero-time jobs, which allows to reason about real-time properties of general distributed algorithms. In addition, we identified Min-Max-Plus algebra as a promising candidate for the real-time analysis of partially synchronous fault-tolerant distributed algorithms, where classic real-time analysis techniques are inapplicable as there are no time-triggered periodic job invocations.
Bibtex
@inproceesings{KMS10:RTSOPS,
  author =       "Alexander K{"o}{ss}ler and Heinrich Moser and Ulrich Schmid",
  title =        "Real-Time Analysis of Round-based Distributed Algorithms",
  booktitle =      "Proceedings of the 1st International Real-Time Scheduling Open Problems Seminar (RTSOPS'10), in conjunction with 22nd Euromicro Conference on Real-Time Systems (ECRTS'10)",
  year =         "2010",
  month =        "Jul.",
  location = "Brussels",
  pages = "9-11",
 note = "Published as as TR under https://www.cs.york.ac.uk/ftpdir/reports/2010/YCS/455/YCS-2010-455.pdf",
}
Download
Get main.pdf - Adobe PDF-format, (52.9775 KB; posted at July 09 2013; )

[ main ] [ back ]