\documentclass{llncs}
\usepackage{listings}
\begin{document}
\pagestyle{myheadings}
\title{Three Concurrent Implementations\\of Red-Black Trees}
\titlerunning{Concurrent Red_Black Trees}
\author{Franck van Breugel}
\authorrunning{Franck van Breugel}
\institute{Department of Computer Science and Engineering, York University\\
4700 Keele Street, Toronto, Ontario, Canada, M3J 1P3}
\maketitle
\begin{abstract}
Three concurrent algorithms for red-black trees are presented.
Only the operations \lstinline{Contains} and \lstinline{Add} are
considered. The first algorithm exploits monitors. The second
algorithm is based on a solution of the readers-writers problem,
where the readers are processes that perform the \lstinline{Contains}
operation and the writers are the processes that perform the
\lstinline{Add} operation. The third algorithm is an adaptation
of the concurrent algorithm for AVL trees by Ellis to the setting
of red-black trees. In this algorithm, the processes lock nodes
of the tree. A node can be locked in three different ways and
different processes can have a lock on a node simultaneously.
All three algorithms have been implemented in Java. These
implementations are briefly discussed. Some properties of these
implementations have been checked by means of the model checker
Java PathFinder (JPF for short). For example, JPF did not detect
any deadlocks or uncaught exceptions.
\end{abstract}
\section{Introduction}
\section{Conclusion}
A lot of work has been done on the concurrent implementation
of data structures. We refer the reader to, for example,
\cite{MoirShavit05} for an overview. The concurrent red-black
tree algorithm described in Section~5 is an adaptation of the
concurrent algorithm for AVL trees as introduced by Ellis in
\cite{Ellis80}. Hanke \cite{Hanke99} also mentions that the
algorithm of Ellis can be adapted to red-black trees. Nurmi
and Soisalon-Soininen \cite{NurmiSoisalonSoininen96} present
a slightly different concurrent algorithm of red-black trees.
Also their work is based on the original work of Ellis.
\bibliographystyle{splncs}
\bibliography{paper}
\appendix
\section{Pseudocode for the Sequential Case}
\subsection{Pseudocode for the \lstinline{Contains} Operation}
The following pseudocode is based on the pseudocode found in
\cite[Section~13.2]{CormenLeisersonRivest89}.
\lstset{language=java,mathescape=true,numbers=left,numberstyle=\tiny}
\begin{lstlisting}[literate={:=}{{$\gets$}}1,emph={then},emphstyle=\bf]
Contains(e)
found := false
node := root
while node is not a leaf $\wedge$ $\neg$ found do
if e = element of node then
found := true
else if e < element of node then
node := left child of node
else
node := right child of node
return found
\end{lstlisting}
\end{document}