next up previous
Next: Mutual Exclusion: Using Timestamps Up: Figures in the book Previous: Verifying Clock Algorithms

Clocks of Different Dimensions

Figure: A direct-dependency clock algorithm
\fbox{\begin{minipage}{\textwidth}\sf
\begin{tabbing}
x\=xxxx\=xxxx\=xxxx\=xxxx\...
...,internal,t)$:\\
\> \>$t.v[t.p] := s.v[t.p]+1;$\\
\end{tabbing}\end{minipage}}

Figure: A sample execution of the direct-dependency clock algorithm.
\begin{figure}\vspace*{0.2in}
\begin{center}
\setlength{\unitlength}{0.8pt}\begi...
...5}}
\put(183, 37){2}
\put(215, 3){(0,2,3)}
\end{picture}\end{center}\end{figure}

Figure: State intervals
\begin{figure}\begin{center}
<tex2html_file> ...

Figure: Algorithm for maintaining matrix clock $M_k[\cdot,\cdot]$ at $P_k$.
\fbox{\begin{minipage}{\textwidth}\sf
\begin{tabbing}
x\=xxxx\=xxxx\=xxxx\=xxxx\...
...k] := M_k[k,k] + 1;$ // {increment local clock}\\
\end{tabbing}\end{minipage}}

Figure: Computing $pred.(pred.(k,n).i).j$
\begin{figure}\begin{center}
<tex2html_file> ...



Vijay K. Garg 2005-02-08