[ main page ] [ back ]

28/2005 : How to Implement a Time-Free Perfect Failure Detector in Partially Synchronous Systems

RR Number
28/2005
Author(s)
G�rard Le Lann, Ulrich Schmid
Abstract
This paper introduces our partially synchronous Theta-Model, which is essentially the well-known FLP model augmented with a bound Theta on the ratio between the maximum and minimum end-to-end delays of messages simultaneously in transit between correct processes. We show that the Theta-Model admits the implementation of a perfect failure detector, which allows to employ classic solutions for solving important distributed computing problems like consensus. Since Theta may still hold when some assumed upper bound on the maximum delay is violated, those solutions work correctly in scenarios where synchronous implementations would fail. We show that our algorithm, which employs heartbeat messages and a timer-free timeout mechanism based upon synchronized heartbeat rounds, indeed satisfies the properties of a perfect failure detector and provides a number of attractive additional features.
Bibtex
@techreport{LS03,
  author =       "Gerard Le Lann and Ulrich Schmid",
  title =        "How to Implement a Time-Free Perfect Failure Detector in Partially Synchronous Systems",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-1, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2005",
  number =       "28/2005",
  note = {(Replaces Technical Report 183/1-127, Institut f\"ur Automation, TU Wien, 2003.)}
}
Download
Get fd.pdf - Adobe PDF-format, (251.7910 KB; posted at July 09 2013)

[ main page ] [ back ]