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