\documentstyle[12pt,epic,eepic]{article}
%\setlength{\oddsidemargin}{-.1 in}
%\setlength{\evensidemargin}{-.3 in}
\setlength{\evensidemargin}{.0 in}
\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8in}
\setcounter{page}{1}

%
% this command enables to remove a whole part of the text 
% from the printout
% to use it just enter
% \remove{  
% before the {\rm text} to be {\rm excluded} and
% } 
% after the text
\newcommand{\remove}[1]{}
\newcommand{\bef}{\rightarrow}
\newcommand{\notbef}{\not \rightarrow}
\newcommand{\SimpleFor}{{\small\bf for} \/}

\newcommand{\drawop}[4]{
\put(#1,#2){\line(0,1){5}
\makebox(#3,15)[c]{#4}}
\put(#1,#2){\line(0,-1){5}}
\put(#1,#2){\line(1,0){#3}
\line(0,1){5}}
\put(#1,#2){\line(1,0){#3}
\line(0,-1){5}}
}


\newcommand{\pendingop}[4]{
\put(#1,#2){\line(0,1){5}
\makebox(#3,15)[c]{#4}}
\put(#1,#2){\line(0,-1){5}}
\put(#1,#2){\line(1,0){#3}
\makebox(0,0)[bl]{...}}
}

%\newfont{\frtntt}{cmtt10 scaled\magstep2}
%\newfont{\svtnsf}{cmss10 scaled\magstep3}

\newcommand{\domin}[2]{
\setlength{\unitlength}{0.012500in}%
\begin{picture}(12,26)(57,727)
\thicklines
\put( 57,727){\framebox(12,26){}}
\put( 57,740){\line( 1, 0){ 12}}
\put( 61,745){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\sixrm #1}}}
\put( 61,731){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\sixrm #2}}}
\end{picture}
}

\begin{document}

\section{Time-Stamp Systems}

In many computer applications, it is important to establish the
ordering among items. For example, in a database system, one could
have a set of records, say $A$ and $B$, and want to continuously
record which item was last updated.  A simple way to do this is to add
to each item a ``label,'' a natural number that is increased every
time the record is updated. For items $A$ and $B$, we can denote their
respective labels $l(A)$ and $l(B)$, and the ``update time'' order
among labels as $<_{T}$. If at some point $l(A) <_{T} l(B)$, and $A$
is updated, then $l(A)$ can be set to $l(B)+1$ changing the order to
$l(B) <_{T} l(A)$, and indicating that $A$ was the last item to be
updated. Unfortunately, this kind of scheme introduces a problem when
we try and implement it. The problem is that on a computer, the labels
are stored each in a register, and registers are of bounded size. If
the labels grow too big, the registers will overflow and the order of
their values will no longer describe the order of updates to the
items. For example, if the register has only two bits, $l(A)=2$ and
$l(B)=3$.  Then if $A$ is updated, it will get set to $l(B)+1$ which
overflows the register so $l(B)+1=4 mod 4 =0$ so $l(A) <_{T} l(B)$,
contrary to what we actually wanted to achieve.

Is this problem solvable without labels that are of unbounded size? To
solve this problem, we need to be able to design a {\it finite} set of
labels and an ordering among them so that the order among labels
reflects the real order of updates at any time. Such a system is
called a bounded time-stamp system.

A time-stamp system is an abstract data type that allows two types of
operations:
\begin{enumerate}
\item Label.
\item Scan (read the labels and return 
the order between them).
\end{enumerate}
Label operations assign a new higher label, and scans return an order among all labels. 


\begin{figure}[phtb]
\framebox[\textwidth]{
\begin{picture}(470,50)
\drawop{30}{22}{50}{label}
\drawop{90}{22}{50}{label}
\drawop{150}{22}{50}{label}
\drawop{210}{22}{50}{label}
\drawop{270}{22}{50}{scan}
\drawop{330}{22}{50}{scan}
\drawop{390}{22}{50}{label}
\end{picture}}
\caption{An execution of labels and scans.}
\label{L5:FIG9}
\end{figure}


We can mathematically model time-stamp systems as graphs. The
"unbounded time-stamps" we use the directed acyclic graph $T = (G, <_{T})$,
where $G$ is the set of vertices which represent the various labels
and $<_{T}$ is the set of edges which represent the order between
them.  The unbounded time-stamp system described above is represented
by the infinite tournament graph in labels Figure \ref{L5:FIG10}. A
tournament graph is a directed graph that has a single directed edge
between any two vertices.
\begin{figure}[phtb]
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\framebox[\textwidth]{
\begin{picture}(140,50)(0,110)
\put(18.00,124.00){\circle{6.00}}
\put(48.00,124.00){\circle{6.00}}
\put(78.00,124.00){\circle{6.00}}
\put(108.00,124.00){\circle{6.00}}
\put(118.00,124.00){\circle{1.00}}
\put(128.00,124.00){\circle{1.00}}
\put(138.00,124.00){\circle{1.00}}
\put(111.00,124.00){\vector(0,0){0.00}}
\put(111.00,124.00){\vector(0,0){0.00}}
\put(105.00,124.00){\vector(-1,0){24.00}}
\put(75.00,124.00){\vector(-1,0){24.00}}
\put(45.00,124.00){\vector(-1,0){24.00}}
\put(48.00,127.00){\line(-4,1){15.00}}
\put(33.00,130.67){\vector(-4,-1){15.00}}
\put(78.00,127.00){\line(-3,1){43.00}}
\put(35.00,141){\vector(-4,-3){17.00}}
\put(108.00,127.00){\line(-4,1){46.00}}
\put(62.00,138.67){\vector(-4,-3){14.00}}
\put(108.00,127.00){\line(-3,1){73.00}}
\put(35.00,151.33){\vector(-2,-3){16.33}}
\put(17,123){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(47,123){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\put(77,123){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\put(107,123){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   4   }}}
\end{picture}}
\caption{The  unbounded natural number based time-stamp system.}
\label{L5:FIG10}
\end{figure}

The unbounded tournament graph is acyclic, which is what it is easy to
keep the order among labels. One can think of the execution of a
sequence of label and scan operations as a {\it pebble game} on this
graph. For $n$ objects that we wish to label, we have $n$ different
colored pebbles, and since this is a tournament graph, there is an
order among any set of pebbles, determined by the order of the
edges. If there is a directed edge $(A,B)$ (from $A$ to $B$) then
$l(B) <_{T} l(A)$. As can be seen, on the graph of the unbounded
tournament graph of Figure~\ref{L5:FIG10}, it is easy to pick a vertex
which dominates all others with pebbles on it. This choice always
gives a correct total ordering of labels since there are no cycles in
the graph.

However, if the values of the labels are bounded, this property may
well be lost, and we need a more sophisticated graph and pebbling
game. One time stamps system method due to Israeli and Li, defines a
domain of labels (vertexes) and an ordering among them $<_{T}$ for
some $k$ possible pebbles as follows. Define the following (cyclic)
tournament graph $T^k$ inductively: $T^1$ is the single vertex, $T ^
{2}$ is the graph in Figure \ref{L5:FIG11}, and $T ^{k} = T ^{2}
\otimes T ^{k-1}$.  The $\otimes$ is the graph multiplication
operator. Graph multiplication $G_1 \otimes G_2 $ is the operation
that creates a new graph $G_3$ by taking $G_2$, replacing every node
by a graph of type $G_2$, and then directing all edges among the newly
inserted vertexes according to the order in $G_1$, creating a new
tournament graph.

\begin{figure}[phtb]
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\framebox[\textwidth]{
\begin{picture}(125,38)(0,110)
\put(55.00,135.00){\circle{6.00}}
\put(75.00,135.00){\circle{6.00}}
\put(65.00,120.00){\circle{6.00}}
\put(72.00,135.00){\vector(-1,0){14.00}}
\put(55.00,132.00){\vector(1,-1){9.00}}
\put(66.00,123.00){\vector(3,4){7.27}}
\put(54,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(74,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\put(64,119){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\end{picture}}
\caption{A Sequential Time Stamp System graph for two processes.}
\label{L5:FIG11}
\end{figure}

The pebble game among two pebbles on $T^2$ is straightforward: In
order to illustrate how the pebble game played let us consider the
following run of three pebbles in a $T ^{3}= T^2 \otimes T^2$ graph
which is shown in Figure~\ref{L5:FIG12}:


\begin{figure}[phtb]
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\framebox[\textwidth]{
\begin{picture}(125,150)(0,30)
\put(25.00,135.00){\circle{6.00}}
\put(45.00,135.00){\circle{6.00}}
\put(35.00,120.00){\circle{6.00}}
\put(95.00,135.00){\circle{6.00}}
\put(115.00,135.00){\circle{6.00}}
\put(105.00,120.00){\circle{6.00}}
\put(70.00,76.00){\circle{6.00}}
\put(60.00,61.00){\circle{6.00}}
\put(80.00,61.00){\circle{6.00}}
\put(42.00,135.00){\vector(-1,0){14.00}}
\put(25.00,132.00){\vector(1,-1){9.00}}
\put(36.00,123.00){\vector(3,4){7.27}}
\put(112.00,135.00){\vector(-1,0){14.00}}
\put(95.00,132.00){\vector(1,-1){9.00}}
\put(106.00,123.00){\vector(3,4){7.27}}
\put(69.00,73.00){\vector(-3,-4){7.29}}
\put(63.00,61.00){\vector(1,0){14.00}}
\put(80.00,64.00){\vector(-1,1){9.00}}
\thicklines
\put(86.00,128.00){\vector(-1,0){39.00}}
\put(37.00,111.00){\vector(1,-2){17.67}}
\put(86.00,76.00){\vector(1,2){18.00}}
\put(34,144){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(24,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(44,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\put(34,119){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\put(104,144){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\put(94,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(114,134){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\put(104,119){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\put(69,85){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\put(69,75){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   1   }}}
\put(59,60){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   2   }}}
\put(79,60){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlrm   3   }}}
\end{picture}}
\caption{A Sequential Time Stamp System graph for three processes.}
\label{L5:FIG12}
\end{figure}


The notation $l(A) = (i, j)$ means that process $A$ is in graph $i$ at
vertex $j$. This would correcpond to a label with two numbers, ``ij'',
lexicoraphically ordered. At the beginning there are three objects $A$
and $B$ with the following labels: $l(A) = (1, 3)$, $l(B) = (1, 1)$,
and $l(C) = (2, 1)$.  This implies that $l(B) <_{T} l(A)$ and both are
greater than $l(C)$.  A and B can continuously assign new labels by
cycling around inside the number 2 $T^2$ structure (note that if $l(B)
<_{T} l(A)$ and $A$ wishes to change to a higher label, staying with
the same label suffices to dominate all others). If $C$ wishes to get
a new label, it cannot pick a node on $T^2$ graph number 2, since this
is a time-stamp sub-graph for 2 pebbles and it is full with $A$ and
$B$.  Thus, $C$ picks $l(C)=(3,1)$ which dominates both $A$ and
$B$. If again $A$ wishes to move, it picks $l(A)=(3,3)$ which
dominates $C$ and $B$. If $B$ now moves, its pebble will go to
$l(B)=(2,1)$ and so on. The time-stamp system for $k$ labels extends
in the same way to a $T^k$ graph.

\section{Bibliography}
\begin{itemize}
\item A. Israeli and M. Li: ``Bounded Time-Stamps'', 28th FOCS, 1987.
\item D. Dolev and N. Shavit: ``Bounded Concurrent Time-Stamps systems are constructible'',STOC 1989.
\end{itemize}
\section{Question for Tutorial}
\begin{itemize}
\item 
The sequential time-stamp system of Israeli-Li above, has a range of
$O(3^n)$ different label values for $n$ processes (each possible label
value is a node in the $T^n$ graph).  Devise a sequential time-stamp
system that uses less than $O(3^n)$ values (hint -- try for $O(n2^n)$
labels. Second hint -- think of each label as an array of $n+\log n$ bits)
\end{itemize}\
\end{document}

