%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "attiyabd95.ltx",
%%%     date      = "20 November 1995",
%%%     time      = "21:41:30 EST",
%%%     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  = "51612 114 486 4296",
%%%     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{AttiyaBD95}

\title{Sharing Memory Robustly in Message-Passing Systems}

\author{Hagit Attiya \and Amotz Bar-Noy \and Danny Dolev}

\Pages{124--142}

\Month{January}

\Year{1995}

\Volume{42}

\Number{1}

\maketitle

\begin{abstract}

Emulators that translate algorithms from the shared-memory model to two
  different message-passing models are presented. Both are achieved by
  implementing a wait-free, atomic, single-writer multi-reader register in
  unreliable, asynchronous networks. The two message-passing models considered
  are a complete network with processor failures and an arbitrary network with
  dynamic link failures. \par These results make it possible to view the
  shared-memory model as a higher-level language for designing algorithms in
  asynchronous distributed systems. Any wait-free algorithm based on atomic,
  single-writer multi-reader registers can be automatically emulated in
  message-passing systems, provided that at least a majority of the processors
  are not faulty and remain connected. The overhead introduced by these
  emulations is polynomial in the number of processors in the system. \par
  Immediate new results are obtained by applying the emulators to known
  shared-memory algorithms. These include, among others, protocols to solve the
  following problems in the message-passing model in the presence of processor
  or link failures: multi-writer multi-reader registers, concurrent time-stamp
  systems, $l$-exclusion, atomic snapshots, randomized consensus, and
  implementation of data structures.

\end{abstract}

\begin{categories}

C.1.2[multiple-instruction-stream, multiple-data-stream processors (MIMD)];
  C.2.1[distributed networks]; C.2.4; D.4.1[concurrency,
  multiprocessing/multiprogramming, synchronization]; F.1.1[relations among
  models]

\end{categories}

\begin{terms}

Algorithms, Theory, Reliability

\end{terms}

\begin{keywords}

Atomic registers, emulation, fault-tolerance, message passing, processor and
  link failures, shared memory, and wait-freedom

\end{keywords}

\end{document}
