\documentclass[dvips]{beamer}

\mode<presentation>{\usetheme{Warsaw}}

\usepackage[english]{babel}
\usepackage{times}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{listings}
\usepackage{fancyvrb}

% colours
\setbeamercolor{structure}{fg=red}
\definecolor{green}{rgb}{0.2,0.7,0.2}

\title[Concurrent Red-Black Trees]{Concurrent Red-Black Trees}
\author{Franck van Breugel}
\institute{DisCoVeri Group, Department of Computer Science and Engineering\\
York University, Toronto}
\date{January 26, 2010}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}[fragile]{Red-Black Tree}
A \emph{red-black tree} is a binary search tree the nodes of
which are coloured either red or black and
\begin{itemize}
\item
the root is black,
\item
every leaf is black,
\item
if a node is red, then both its children are black,
\item
for every node, every path from that node to a leaf
contains the same number of black nodes.
\end{itemize}

[Bayer, 1972] and [Guibas and Sedgewick, 1978]

$$
\UseComputerModernTips
\xymatrix{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}{Red-Black Tree}
\begin{theorem}
A red-black tree with $n$ internal nodes has height at most
$2 \log_2(n + 1)$.
\end{theorem}

\begin{corollary}
The {\sc SET} operations {\sc ADD} and {\sc CONTAINS} can be implemented in $O(\log_2(n))$.
\end{corollary}
\end{frame}

\begin{frame}[fragile]{Java Class Library}
The class java.util.TreeSet

\medskip

\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
class TreeSet<T>
{
   boolean add(T element)
   boolean contains(T element)
   ...
}   
\end{lstlisting}

has been implemented by means of a red-black tree.

\bigskip

This implementation is \textcolor{red}{not} synchronized.
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
add(3);
add(1);
(add(2) || print(contains(1)))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
add(3);
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix{
& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
add(3);
add(1);
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dd] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Concurrent Operations on a Red-Black Tree}
\begin{lstlisting}[numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\mbox{add(2)}$ || $\underline{\mbox{print(contains(1))}}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dd] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}{Concurrent Red-Black Trees}
With the arrival of multicore machines, implementations of data structures 
such as Set should support concurrency.

\bigskip

In the remainder of this talk, three concurrent implementations of 
red-black trees are presented.
\end{frame}


\defverbatim[colored]\CodeB{
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
RedBlackTree : monitor
begin
  procedure add(element : int, 
                result added : boolean)
  procedure contains(element : int, 
                     result contains : boolean)
end
\end{lstlisting}}

\begin{frame}{The Monitor Solution}

\CodeB

\end{frame}

\begin{frame}{The Readers-Writers Solution}
The processes of the first class, named {\em writers}, must have
exclusive access, and the processes of the second class,
the {\em readers}, may share the resource with an unlimited number of 
other readers.
\end{frame}

\begin{frame}{The Readers-Writers Solution}
The processes of the first class, those that call {\sc ADD}, must have
exclusive access, and the processes of the second class,
those that call {\sc CONTAINS}, may share the red-black tree with an 
unlimited number of such processes. 
\end{frame}

\begin{frame}[fragile]{The Readers-Writers Solution}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
contains(element : int) : boolean
[manipulate shared variables, wait]
manipulate red-black tree
[manipulate shared variables, signal]
\end{lstlisting}
\end{frame}

\begin{frame}{My Paper}
Carla Schlatter Ellis.
Concurrent Search and Insertion in AVL Trees.
{\em IEEE Transactions on Computers}, 29(9):811--817, September 1980.

\medskip

Carla Schlatter Ellis.
{\em The Design and Evaluation of Algorithms for Parallel Processing}.
PhD thesis, University of Washington, Seattle, 1979.

\medskip

\includegraphics[scale=0.6]{ellis-old.eps}
\hfill
\includegraphics[scale=0.6]{ellis-new.eps}
\end{frame}

\begin{frame}[fragile]{The Main Idea}
Processes lock the nodes of the red-black tree
in three different ways:
\begin{itemize}
\item
$\rho$-lock: lock to read
\item
$\alpha$-lock: lock to exclude writers
\item
$\xi$-lock: exclusive lock
\end{itemize}

Although a node can be locked by multiple processes, there are
some restrictions.

$$
\UseComputerModernTips
\xymatrix@R=1ex{
*+<3ex>[o][F**:green]{\rho} \ar@{-}@*{[|(2)]}@(ul,dl)[] \ar@{-}@*{[|(2)]}[rr] && *+<3ex>[o][F**:yellow]{\alpha}\\
& *+<3ex>[o][F**:blue]{\xi}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb]
add(3);
add(1);
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:yellow][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:yellow][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]++[F**:yellow]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:yellow][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:yellow][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red]++[F**:blue][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:yellow][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:blue][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red]++[F**:blue][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:blue][white]{3} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:blue][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red]++[F**:blue][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[language=java,numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\underline{\mbox{add(2)}}$ || $\mbox{print(contains(1))}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:blue][white]{3} \ar@*{[|(2)]}[dd] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:blue][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red]++[F**:blue][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}[fragile]{Example Revisited}
\begin{lstlisting}[numbers=left,numberstyle=\tiny,frameround=tttt,frame=tlrb,mathescape=true]
$\mbox{add(3);}$
$\mbox{add(1);}$
($\mbox{add(2)}$ || $\underline{\mbox{print(contains(1))}}$)
\end{lstlisting}

$$
\UseComputerModernTips
\xymatrix@R=2ex{
&& *+<2ex>[o][F**:black]++[F**:blue][white]{3} \ar@*{[|(2)]}[dd] \ar@*{[|(2)]}[dr]\\
& *+<2ex>[o][F**:red]++[F**:blue][white]{1} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr] && *+<3ex>[o][F**:black]{}\\
*+<3ex>[o][F**:black]{} && *+<2ex>[o][F**:red]++[F**:blue][white]{2} \ar@*{[|(2)]}[dl] \ar@*{[|(2)]}[dr]\\
& *+<3ex>[o][F**:black]{} && *+<3ex>[o][F**:black]{}}
$$
\end{frame}

\begin{frame}{Looking Ahead}
Plan
\begin{itemize}
\item
implement all three algorithms
\item
compare their performance
\end{itemize}

Challenges
\begin{itemize}
\item
adjust algorithm for AVL trees to red-black trees
\item
modify red-black tree algorithms of [Cormen, Leiserson, Rivest and Stein, 2001]
\item
when a process unlocks a node, which of the processes
that are waiting to lock the node is chosen?
(not addressed in the paper, PhD thesis is not available)
\end{itemize}
\end{frame}

\end{document}