The Weakest Failure Detectors to SolveCertain Fundamental Problems in Distributed Computing \Lambda [Extended Abstract] y

ABSTRACT We determine the weakest failure detectors to solve several funda-mental problems in distributed message-passing systems, for all environments-- i.e., regardless of the number and timing of crashes.The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant ofconsensus in which processes have the option to decide `quit ' if a failure occurs), and solving non-blocking atomic commit. Categories and Subject Descriptors C.2.4 [Computer-Communication Networks]: Distributed Sys-tems--distributed applications, distributed databases, network operating systems; D.4.5 [Operating Systems]: Reliability--faulttolerance; F.1.1 [Computation by Abstract Devices]: Models of Computation--automata, relations among models; H.2.4 [DatabaseManagement]: Systems--concurrency, distributed databases, transaction processing General Terms Algorithms, Reliability, Theor