%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "chandrat96.ltx",
%%%     date      = "7 June 1996",
%%%     time      = "13:44:10 EDT",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "08911 119 497 4504",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{ChandraT96}

\title{Unreliable Failure Detectors for Reliable Distributed Systems}

\author{Tushar~Deepak Chandra \and Sam Toueg}

\Pages{225--267}

\Month{March}

\Year{1996}

\Volume{43}

\Number{2}

\maketitle

\begin{abstract}

We introduce the concept of unreliable failure detectors and study how they can
  be used to solve Consensus in asynchronous systems with crash failures. We
  characterise unreliable failure detectors in terms of two
  properties---completeness and accuracy. We show that Consensus can be solved
  even with unreliable failure detectors that make an infinite number of
  mistakes, and determine which ones can be used to solve Consensus despite any
  number of crashes, and which ones require a majority of correct processes. We
  prove that Consensus and Atomic Broadcast are reducible to each other in
  asynchronous systems with crash failures; thus, the above results also apply
  to Atomic Broadcast. A companion paper shows that one of the failure
  detectors introduced here is the weakest failure detector for solving
  Consensus [Chandra et al.\ 1992].

\end{abstract}

\begin{categories}

C.2.4 [\textbf{Computer-Communication Networks}]: Distributed
Systems---\emph{distributed applications\textup; distributed
databases\textup; network operating systems}; C.4 [\textbf{Performance
of Systems}]---\emph{reliability, availability, and serviceability};
D.1.3 [\textbf{Programming Techniques}]: Concurrent
Programming---\emph{distributed programming}; D.4.5 [\textbf{Operating
Systems}]: Reliability---\emph{fault-tolerance}; F.1.1
[\textbf{Computation by Abstract Devices}]: Models of
Computation---\emph{automata\textup; relations among models}; F.1.2
[\textbf{Computation by Abstract Devices}]: Modes of
Computation---\emph{parallelism and concurrency}; H.2.4
[\textbf{Database Management}]: Systems---\emph{concurrency\textup;
distributed systems\textup; transaction processing}

\end{categories}

\begin{terms}

Algorithms, Reliability, Theory

\end{terms}

\begin{keywords}

agreement problem, asynchronous systems, atomic broadcast, \emph{Byzantine
  Generals'} problem, commit problem, consensus problem, crash failures,
  failure detection, fault-tolerance, message passing, partial synchrony,
  processor failures

\end{keywords}

\end{document}
