SOLVING AGREEMENT PROBLEMS WITH FAILURE DETECTORS - A SURVEY

This payer surveys problems related to achieving agreement in distribu ted systems. Various agreement problems can be specified as a variant of the basic consensus problem. Unfortunately, this fundamental proble m cannot be solved in asynchronous systems if crash failures can occur . In order to overcome this impossibility result Chandra and Toueg hav e augmented the asynchronous system model with the notion of failure d etectors. A failure detector is associated with each process of the di stributed computation and is responsible for detecting external failur es. Suspicions are essentially implemented using time-out mechanisms, which means that (1) the detection of a real failure is usually delaye d and (2) a failure detector can make mistakes by incorrectly suspecti ng a process to have crashed. In this paper, various classes of failur e detectors are presented. All are specified by a completeness propert y and an accuracy property. A completeness property puts a condition o n the detection of crashed processes, while an accuracy property restr icts the possible mistakes made by a failure detector. After reviewing the hierarchy of failure detector classes, two particular solutions t o the consensus problem are examined. In each case, a different class of failure detectors is used. The proposed solutions have liveness pro perties and deliver their expected results provided that a minimal set of well-defined conditions is satisfied. After a detailed presentatio n of the consensus problem, various agreement problems are reviewed an d their relationship with the consensus problem are underlined. Finall y, for each agreement problem, we indicate under which minimum assumpt ions a solution can be found.