%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "chandraht96.ltx",
%%%     date      = "27 September 1996",
%%%     time      = "14:44:18 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  = "48760 118 472 4347",
%%%     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{ChandraHT96}

\title{The Weakest Failure Detector for Solving {Consensus}}

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

\Pages{685--722}

\Month{July}

\Year{1996}

\Volume{43}

\Number{4}

\maketitle

\begin{abstract}

We determine what information about failures is necessary and
sufficient to solve Consensus in asynchronous distributed systems
subject to crash failures. In Chandra and Toueg~[1996], it is shown
that $\diamond W$, a failure detector that provides surprisingly
little information about which processes have crashed, is sufficient
to solve Consensus in asynchronous systems with a majority of correct
processes. In this paper, we prove that to solve Consensus, any
failure detector has to provide at least as much information as
$\diamond W$. Thus, $\diamond W$ is indeed the weakest failure
detector for solving Consensus in asynchronous systems with a majority
of correct processes.

\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}
