%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "afekaps96.ltx",
%%%     date      = "16 May 1996",
%%%     time      = "14:58:6 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  = "64325 119 585 4665",
%%%     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{AfekAPS96}

\title{Local Management of a Global Resource in a Communication Network}

\author{Yehuda Afek \and Baruch Awerbuch \and Serge Plotkin \and Michael Saks}

\Pages{1--19}

\Month{January}

\Year{1996}

\Volume{43}

\Number{1}

\maketitle

\begin{abstract}

This paper introduces a new distributed data object called \emph{Resource
  Controller} that provides an abstraction for managing the consumption of a
  global resource in a distributed system. Examples of resources that may be
  managed by such an object include number of messages sent, number of nodes
  participating in the protocol, and total CPU time consumed. \par The Resource
  Controller object is accessed through a procedure that can be invoked at any
  node in the network. Before consuming a unit of resource at some node, the
  controlled algorithm should invoke the procedure at this node, requesting a
  \emph{permit} to consume a unit of the resource. The procedure returns either
  a \emph{permit} or a \emph{rejection}. \par The key characteristics of the
  Resource Controller object are the constraints that it imposes on the global
  resource consumption. An $(M, W)$-Controller guarantees that the total number
  of permits granted is at most $M$; it also ensures that, if a request is
  rejected, then at least $M - W$ permits are eventually granted, even if no
  more requests are made after the rejected one. \par In this paper, we
  describe several message and space-efficient implementations of the Resource
  Controller object. In particular, we present an $(M, W)$-Controller whose
  message complexity is $O(n \log^2 n \log(M/(W + 1)))$ where $n$ is the total
  number of nodes. This is in contrast to the $O(nM)$ message complexity of a
  fully centralized controller which maintains a global counter of the number
  of granted permits at some distinguished node and relays all the requests to
  that node.

\end{abstract}

\begin{categories}

C.2.3 [\textbf{Computer-Communication Networks}]: Network Operations;
C.2.4 [\textbf{Computer-Communication Networks}]: Distributed Systems;
F.2.2 [\textbf{Analysis of Algorithms and Problem Complexity}]:
Nonnumerical Algorithms and Problems; G.2.2 [\textbf{Discrete
Mathematics}]: Graph Theory

\end{categories}

\begin{terms}

Algorithms, Theory

\end{terms}

\begin{keywords}

Diffusing computations, distributed computation, distributed network
  management, resource management

\end{keywords}

\end{document}
