\documentstyle[psfig,11pt]{article}
% white paper by Nir June 10th 1995 


\renewcommand{\topfraction}{.8}
\renewcommand{\bottomfraction}{1.}
\renewcommand{\floatpagefraction}{.8}
\renewcommand{\textfraction}{0.01}

% \remove{  
% ... text..
% } 
\newcommand{\remove}[1]{}

\setlength{\evensidemargin}{0.2in}
\setlength{\marginparwidth}{0.6in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{-0.1in}

\setlength{\textheight}{8.5in}
\setlength{\topmargin}{-0.25in}


\setlength{\textheight}{7.5in}
\setlength{\topmargin}{-0.25in}
%\setlength{\bottommargin}{-0.25in}
%\setlength{\headheight}{0.25in}
%\setlength{\headsep}{0in}

%%%%%%%%%%%%%%%%%%%%%% MACROS %%%%%%%%%%%%%%%%%


\newtheorem{definition}{Definition}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]

% to get nice proofs ...
\newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}
\newcommand{\qed}{\hfill\rule{2mm}{2mm}}




% MAC VERSION
%\newcommand{\dofigure}[1]{\epsfbox{#1}}
% UNIX VERSION
 \newcommand{\dofigure}[1]{\psfig{figure=#1}}
 \newcommand{\dopicture}[1]{\psfig{figure=#1}}
% NO GRAPHICS
%\newcommand{\dofigure}[1]{}

%%%%%%%%%%%%%%% Jims Macros %%%%%%%%%%%%%%%%%%%%
\remove{
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
%\newenvironment{proof}{{\bf Proof:}}{$\Box$\medskip}
\newenvironment{proof}{{\bf Proof:}}{\rule{1 ex}{0.8 em}}
\newenvironment{proofof}[1]{{\bf Proof of #1:}}{\rule{1 ex}{1 em}}
} % end remove

% a blank line
\def\blankline{\hbox{}}

% some arrows
%dashed arrow


\newcommand{\da}{\setlength{\unitlength}{1mm}
\hspace{1mm}
\begin{picture}(6.1,2)(0,-1)
\thinlines
\multiput(0.3,0)(1.5,0){3}{\line(1,0){1}}
\put(4.8,0){\vector(1,0){1}}
\end{picture}
\hspace{1mm}}
%full arrow
\newcommand{\fa}{\setlength{\unitlength}{1mm}
\hspace{1mm}
\begin{picture}(6.1,2)(0,-1)
\thinlines
\put(0.3,0){\vector(1,0){5.5}}
\end{picture}
\hspace{1mm}}

%A variety of techniques have been proposed for
%``speeding up'' mutual exclusion, ranging from low-level machine
%instructions to high-level language constructs \cite{Anderson89,L86d}.

\begin{document}

\pagestyle{myheadings}
\markboth{\sc Herlihy-Shavit}{\sc Herlihy-Shavit}

\newpage
\begin{center}
{\huge\bf Highly Concurrent Data Structures}
\end{center} 
\begin{center}
{\Large\bf Maurice Herlihy and Nir Shavit}
\end{center} 


\vspace{1cm}
We are interested in developing highly robust {\it shared data structures\/} 
for ``multi-scale'' computation, the diverse set of 
distributed and concurrent computing environments that scale from 
tightly coupled multiprocessors, to farms of workstations and 
local area networks. 

Traditionally, the design of concurrent data structures has centered
around the notion of {\em mutual exclusion}: ensuring that only one
process at a time is allowed to modify complex shared data objects,
and that processes periodically wait for all others to complete a
given part of code.  
A variety of techniques have been proposed for
efficiently implementing mutual exclusion, ranging from low-level machine
instructions to high-level language constructs \cite{Anderson89,L86d}.
Nevertheless, we argue that mutual exclusion based
coordination structures tend to be {\it centralized} and {\it tightly
synchronized}, and are thus poorly suited for todays {\it distributed}
and {\it asynchronous} networks and multiprocessor architectures.
This drawback is amplified in applications requiring fault-tolerance
and real-time performance.

For example, in a real-time system consisting of a pool of sensor and
actuator processes, processes might communicate via a shared queue.
When a sensor process detects a condition requiring a response, it
records the condition and places the record in the queue.  Whenever an
actuator process becomes idle, it dequeues an item from the queue and
takes appropriate action.  Since there is only a single queue, we are
guaranteed that idle processors will always find the next available
record.  The conventional way to prevent concurrent queue operations
from interfering is to execute each operation as a {\em critical
section}: only one process at a time is allowed to access the data
structure.  The resulting centralized and tightly synchronized
coordination algorithm, although widely used, has several significant drawbacks.
\begin{itemize}
\item
It is not fault-tolerant, as halted processes 
can cause all other processes attempting to access the queue to wait forever.
\item
It has a low degree of parallelism.
Synchronization forces faster processes to wait for slower processes.
Such waiting may be particularly undesirable in heterogeneous architectures,
where some processors may be much faster than others.
For example, a fast actuator process should not have to remain idle whenever
a much slower sensor process is enqueuing a new item.
\item 
It creates high degrees of contention.  Many processors may
attempt to access the queue concurrently.  Since only one can succeed
at a time, the other processors' repeated attempts may consume network
bandwidth, resulting in poor performance. This phenomena is sometimes
called a ``hot-spot'' \cite{HotSpot}.
\end{itemize}

Despite its drawbacks, this centralized mutually-exclusive approach is
still the common choice among designers of concurrent programs, mainly
because all known alternatives suffer, each of its own maladies [[[
Maurice-- rephrase]]] Know approaches to distributed data structure
design include:
\begin{itemize}
\item {\it Combining Tree Structures}, where concurrent requests in
multiple locations are merged concurrently down a tree, then answered
by some central location, and then distributed back. This approach
provides parallelism and low contention, but involves tight
synchronization and a significant overhead when loads are low.
Moreover, even slight fluctuations in request arrival times will cause
a large drop in performance, in other words, combining is not robust.

\item {Randomized Algorithms} \cite{RSU,BL}, where distribution and
small grain mutual exclusion are achieved at the price of giving up on
a deterministic termination guarantee.  This can be a significant
drawback when hard-deadline real-time applications are involved.

\item {\it Lock-free} and {\it wait-free} methods
\cite{Waitfree,PPOPP90} which attempt to eliminate the use of mutual
exclusion all together. Unfortunately, for most structures the
overhead involved in supporting such methods is too high to make them
desirable in practice.
\end{itemize}

\begin{figure}[b]
\begin{center}
\mbox{
\dopicture{ct48.eps}
}
\end{center}
\caption{Two Simple Counting Trees}
\label{figure: simptree}
\end{figure}

\section{The Distributed-Coordinated approach} [[ maurice -- edit etc]]]
Our goal is to replace traditional centralized and tightly
synchronized shared object designs with {\it highly distributed} and
{\it loosely coordinated} combinatorial data structures. An important
design objective is to avoid significantly modifying the implemented
data structure's original specification. Unlike wait-free/lock-free
algorithms \cite{Waitfree,PPOPP90}, our approach will not be to try
and eliminate critical sections altogether. Rather, we will aim to
change the way they are used, replacing strucures based on {\it
synchronization sequences\/} where processes wait for the arrival of
others, with {\it coordination points\/}, multiple points of
small-grain mutual exclusion and available hardware instructions to
post or collect information, mostly at their own pace.  These points
will be highly distributed throughout the data structure so as to
limit congestion. Finally, the structures will be reactive, that is,
will grow and shrink in size in response to load fluctuations. Becuse of their loosly 
coordinated design, this will require little overhead. We thus
expect the resulting algorithms to be substantially more robust (in
the face of load changes and timing fluctuations) than known tightly
synchronized parallelization methods such as {\it software combining}
\cite{Goodman}, and in contrast with randomized approaches
\cite{RSU,BL} provide {\it deterministic\/} termination guarantees.

\begin{figure}[t]
\begin{center}
\mbox{
\dopicture{dt8.eps}
}
\end{center}
\caption{The shared memory implementation of a diffracting tree}
\label{figure: smtree}
\end{figure}

Consider as an example our recent work on {\it Diffracting Trees\/}
\cite{SZ} and {\it Elimination Pools} \cite{ST95} which we describe
below.  {\it Diffracting trees} are a new form of {\it counting
network} structure \cite{AHS} for shared counting and
load-balancing. {\it Elimination pools} are a specialized variant of
diffracting trees that give superior performance in structures such as
shared queues. These structures have potential applications in both
tightly-coupled multiprocessing and computer network environments.

It is easiest to think of a {\it diffracting tree} as a distributed
way to implement a shared counter.  A diffracting tree is a balanced
binary tree of simple one-input two-output computing elements called
{\em balancers} that are connected to one another by wires.  Tokens
arrive on a balancer's input wire at arbitrary times, and are output
on its two output wires.  Intuitively one may think of a balancer as a
toggle mechanism, that given a stream of input tokens, repeatedly
sends one token to the left output wire and one to the right,
effectively balancing the number of tokens that have been output.  On
a computer the balancer would require just a single bit directing the
current passing token (``shepherded'' by a process) left or right,
and complemented by each traversing token.  To illustrate this
``counting'' property, consider an execution in which tokens traverse
the tree sequentially, one completely after the other.  The left-hand
side of Figure~\ref{figure: simptree} shows such an execution on a
tree of width $4$.  As can be seen, the tree moves input tokens to
output wires in increasing order modulo $4$.  Trees of balancers
having this property can easily be adapted to count the total number
of tokens that have entered the network.  Counting is done by adding a
``local counter'' to each output wire $i$, so that tokens coming out
of that wire are consecutively assigned numbers $i, i+4, i+(4 \cdot 2)
\ldots$

Though this structure is highly distributed, and tokens traverse it
independently, it would seem that we are back to square one since the
root balancer of the tree will be a a sequential bottleneck and source
of contention that is no better than having a single centralized counter.  
This would indeed be true if the balancer
were a bit toggled by each passing token.  However, one can replace
this construction with a more effective {\it diffracting balancer \/}
implementation based on the following simple observation: if an even
number of tokens pass through a balancer, once they leave the toggle
bit's state is unchanged. That is, if it was $0$ it will be $0$ and
if it was $1$ it will be $1$.  Thus, by having pairs of tokens collide
on independent locations in memory and then diffracted in a
coordinated manner one to the left and one to the right, both tokens
can leave the balancer without ever having to toggle the shared bit.
The toggle will only be accessed by processors that did not diffract.
As depicted in Figure~\ref{figure: smtree}, {\it diffracting trees}
implement this approach by adding a ``prism'' array in front of the
toggle bit of every balancer.  The prism is an inherently distributed
data structure that allows many diffractions to occur in parallel.
The tree structure
guarantees correctness of the output values, and a logarithmic time
termination guarantee. It is also highly fault
tolerant, and the delay or failure of any subset of processors will
not prevent others from successfully shepherding tokens through
the tree.

One can use a pair of diffracting trees to implement a highly
concurrent shared queue.  An even more effective concurrent queue is
created using an {\it elimination tree}, a diffracting data structure
that allows pairs of enqueue and dequeue requests that collide and be
``eliminated'' on the tree's prisms, exchanging values in almost
constant time.
 

\begin{figure*}[t]
\begin{center}
\mbox{\psfig{figure=POOL.WORK=0.T}}
\mbox{\psfig{figure=POOL.WORK=0.L}}\end{center}
\caption{Shared Queue: produce-consume benchmark}
\label{figure: prodcons}
\end{figure*}

Our empirical performance data shows that diffracting trees and
elimination pools substantially outperform all known techniques: they
scale better, giving higher throughput over a large number of
processors, and are more robust in terms of their ability to handle
unexpected latencies and differing loads.  
Figure ~\ref{figure: prodcons} displays the throughput and average latency of a
sensor-actuator queue benchmark on an Alewife \cite{Alewife}
multiprocessor using the Proteus Parallel Hardware Simulator
\cite{Proteus}. We compare the performance of queues based on a
width-32 elimination tree ({\tt Etree}) and a width-32 diffracting
tree ({\tt Dtree}) to the best known lock-based implementations: an
optimal width {\it software combining tree} ({\tt Ctree}) and
Mellor-Crummey and Scott's {\it queue-lock} ({\tt MCS}). The
centralized MCS locking technique maitains a constant throughput but
does not scale well due to lack of parallelism.  The parallel
combining tree based queue performs much better, but is {\it
substantially} outperformed by the diffracting tree, which has a fixed
average latency over a wide range of concurrency levels. The
elimination tree outperforms all of these techniques by utilizing high
levels of concurrency to match enqueues and dequeues in $O(1)$ steps,
so that the average latency improves as the load increases!


\section{Significance}
There is a growing realization that congestion and unpredictable
delays are a serious problem in modern multiprocessor
and network architectures.  To support real-time and fault-tolerant
performance and allow scalability over a wide range of available
systems, multiprocessing software must shift away from tight
synchronization and replace centralization by distribution.

Through the use of combinatorial constructions,  
the {\it distributed-coordinated\/} approach offers a way to 
replace tight synchronization with  
much looser forms of coordination, distributing work loads over
multiple locations, eliminating sequential bottlenecks, and lowering
the levels of memory and interconnect contention. 
Our planned research will 
couple novel theoretical results together with practical
considerations, in order to develop a library of concurrent data structures that 
(1) have detailed formal specifications, 
(2) have mathematically provable complexity, and resiliency properties,
and (3) exhibit scalable and robust performance on actual and simulated
multiprocessor machines.
We plan to publish our developed data structures in a collection of research papers
and provide a package of resulting implementation codes. 

Our distributed-coordinated approach has already yielded a variety of
counting network and diffracting tree based data structures \cite{HLS,SZ,ST95,Gio}
which experimentally outperform known solutions;
%which prove effective in practice;
we expect it will have important consequences
for real-time and fault-tolerant application development
and network protocol design.
 

\section{Methodology and Deliverables}
Our goal is to provide a library of highly concurrent designs for known data 
structures. Specifically, we plan to develop the following 
concurrent data structures: 

\begin{itemize}
\item Highly concurrent shared pools (see \cite{Manber}
\item Highly concurrent linearizable stacks  -- [[[to be added]]
\item Highly concurrent linearizable priority queues -- [[[to be added]]
our designs, which will be based on a new ``combining funnels'' methodology 
currently in development ...
\end{itemize}

{\small
\begin{thebibliography}{10}
\bibitem{Alewife}
A. Agarwal, D. Chaiken, K. Johnson, D. Krantz, J. Kubiatowicz,
K. Kurihara, B. Lim, G. Maa, and D. Nussbaum.
\newblock The MIT Alewife Machine: A Large-Scale
Distributed-Memory Multiprocessor.
\newblock To appear in {\it Scalable Shared Memory Multiprocessors},
Kluwer Academic Publishers, 1991.
\newblock Also as MIT Technical Report MIT/LCS/TM-454, June 1991.

\bibitem{Anderson89}
T.E. Anderson.
\newblock The performance implications of spin-waiting alternatives for
  shared-memory multiprocessors.
\newblock Technical Report 89-04-03, University of Washington, Seattle, WA
  98195, April 1989.
\newblock To appear, IEEE Transactions on Parallel and Distributed Systems.

\bibitem{Proteus}
E.A. Brewer, C.N. Dellarocas, A. Colbrook and W.E. Weihl.
\newblock {\sc Proteus:} A High-Performance Parallel-Architecture
Simulator. 
\newblock MIT Technical Report /MIT/LCS/TR-561, September 1991.


\bibitem{BL} R.D.~Blumofe, and C.E.~Leiserson. 
\newblock Scheduling Multithreaded Computations by  Work Stealing.
\newblock In {\it Proceeding of the 35th Symposium on Foundations of Computer Science,}
  pages 365-368, November 1994.

\bibitem{Goodman}
J.R. Goodman, M.K. Vernon, and P.J. Woest.
\newblock  Efficient Synchronization Primitives for Large-Scale
Cache-Coherent Multiprocessors,
Proceedings of the 3rd ASPLOS,
64--75, April 1989.

\bibitem{Waitfree}
M.P. Herlihy.
\newblock Wait-free synchronization.
\newblock {\em ACM Transactions on Programming Languages and Systems},
13(1):124--149, January 1991.

\bibitem{PPOPP90}
M.P. Herlihy.
\newblock A methodology for implementing highly concurrent data structures.
\newblock In {\em Proceedings of the Second ACM SIGPLAN Symposium on Principles  and Practice of Parallel Programming}, pages 197--206, Seattle, WA, March 14-16 1990.

\bibitem{L86d}
Lamport L.
\newblock The mutual exclusion problem. part II: Statement and solutions.
\newblock {\em J.~ ACM, 33}, 2 (Feb. 1986) 327--348.

\bibitem{HotSpot}
G.H. Pfister and A.~Norton.
\newblock `hot spot' contention and combining in multistage interconnection
  networks.
\newblock {\em IEEE Transactions on Computers}, C-34(11):933--938, November
  1985.

\bibitem{RSU}
L.~Rudolph, M.~Slivkin, and E.~Upfal.
\newblock A Simple Load Balancing Scheme for Task Allocation in Parallel
  Machines.
\newblock In {\em Proceedings of the 3rd ACM Symposium on Parallel Algorithms
  and Architectures}, pages 237--245, July 1991.

\bibitem{SZ}
N. Shavit and A. Zemach.
\newblock Diffracting Trees.
\newblock In {\em Proceedings of the Annual Symposium on Parallel 
Algorithms and Architectures (SPAA)}, June 1994.

\bibitem{ST95}
N. Shavit and D. Touitou.
\newblock Elimination Trees and the Construction of Stacks and Pools.
\newblock To appear in {\em Proceedings of the Annual Symposium on Parallel 
Algorithms and Architectures (SPAA)}, July 1995.
\end{thebibliography}
} %%%%%%%% end of small %%%%%%%%%%
%---------------------------------------------------------

\end{document}





