% Lower

\section{Adding More Registers}

%[[[
In this section, we present our second main result, a lower bound on
the time complexity of any deadlock-free mutual exclusion algorithm, 
in the timed setting.
Our lower bound is expressed as a function of the number $k$ of shared 
registers used by the algorithm.
Specifically, it is of the form $e(k) C c_2$, where $e(k)$
is a function of $k$.
The value of $e(k)$ decreases rapidly with $k$.  Thus, the
bound is probably only interesting when $k$ is small and when $C$, the
timing uncertainty, is large.
%It's worthwhile to try to get an algorithm for $k$ as small as
%possible, in order to make the upper and lower bounds as close as we
%can make them.
Note that we do {\em not} yet have any corresponding upper bounds that
decrease similarly with increasing $k$; finding algorithms exhibiting
such upper bounds (or removing the dependency of the lower bound on
the number of registers) remains as future work.
%]]]

For a particular $k$, we define $e(k)$
by means of a recursive definition of a fast-growing function 
$f(j,k)$, $1 \leq j \leq k$.
Specifically, we define $f(1,k) = 1$, and
$f(j+1,k) = ({k \choose j} + 1) f(j,k) + {k \choose j} (2 j + 1)$,
$1 \leq j \leq k - 1$.
Then we define $e(k) = 1 / (f(k,k) + 1)$.
%[[[
Thus, $e(k)$ is a rapidly-decreasing function of $k$.
%]]]

\begin{lemma}
\label{relate e and f}
$1 \geq f(j,k) e(k) + e(k)$ for all $j$, $1 \leq j \leq k$.
\end{lemma}

\absrem{
\begin{proof}
By definition of $e$, 
we have $e(k) = 1 / (f(k,k) + 1)$,
i.e., that $1 = f(k,k) e(k) + e(k)$.
Since $f(j,k)$ is a monotone nondecreasing function of $j$,
the result follows.
\end{proof}
} % end absrem

\begin{theorem}
Suppose $C \geq 2$.
There is no $[c_1, c_2]$ timed algorithm providing mutual exclusion 
with deadlock-freedom for $n \geq 2$ asynchronous processes,
that uses only $k < n$ shared read/write register, and that takes time
$b < e(k) C c_2$.
\end{theorem}

\begin{proof}
(Sketch)
Suppose there is such an algorithm, with time bound $b < e(k) C c_2$.
%[[[
We follow the main ideas of the construction of Burns and Lynch
\cite{BL}, for the asynchronous impossibility proof (of 
our Theorem \ref{thm: BL}) to construct a bad execution.
This time, however, the bad execution, as well as the
auxiliary executions used along the way, must satisfy the timing
constraints, which makes the construction considerably harder than before.
%]]]

The construction we carry out involves only $k+1$ of the $n$
processes, those numbered $p_1, p_2, \ldots, p_{k+1}$.
\absrem{%%%%%%%%%%%%%%%%%%%%%%%%%%
We carry out a recursive construction similar to the one in \cite{BL}.
This time,} %%%%%%%%%%%%%%%%%%%%%%
For any $j = 1, \ldots, k$, 
starting from any configuration in which all processes are
in their remainder regions,
we obtain a finite timed execution of $p_1, \ldots, p_j$ only,
satisfying the timing constraints,
and leading to a point at which $p_1, \ldots, p_j$ ``nullify'' $j$ distinct
registers.
(The definition of a process $p_i$ ``nullifying'' a register $v$
is as in \cite{BL}: $p_i$ is about to write register $v$ at its next step,
and moreover, anything process $p_i$ has written since last leaving its
remainder region has already been overwritten without being read by other processes.)
Moreover, the execution has the additional timing property that 
for all $i$, $1 \leq i \leq j$, 
$\ms{ltime}(i) \geq \ms{now} + e(k) c_2$ and $\ms{ftime}(i) \leq
\ms{now}$.
\absrem{%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Here, $\ms{now}$ denotes the current time at the designated point in
the execution,
and $\ms{ftime}(i)$ and $\ms{ltime}(i)$ denote the
first and last times at which the next step of process $i$ might
occur.
}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
That is, the timing constraints permit process $i$ to wait at least
time $e(k) c_2$ before taking its next step, but do not impose any
lower bound on the time at which it might take that step.
Furthermore, the total time required for the execution is at most 
$f(j,k) e(k) c_2$.

%Once we obtain this recursive result, we can complete the proof
%as follows. 
\absrem{%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We apply this result for the special case where $j = k$. 
obtaining a finite timed execution of $p_1, \ldots, p_k$ only,
satisfying the timing constraints,
leading to a point where $p_1, \ldots, p_k$ nullify all $k$ registers,
and for all $i$,
$1 \leq i \leq k$, 
$\ms{ltime}(i) \geq \ms{now} + e(k) c_2$ and 
$\ms{ftime}(i) \leq \ms{now}$.
} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We apply this result for the special case where $j = k$. 
Now let the last process, $p_{k+1}$, enter the system, taking steps as
fast as it can.
We claim it should be able
to proceed to its critical region before any of the other processes
take their next steps.  This is because of the upper bound on the
algorithm, the fact that $p_{k+1}$ cannot tell that any other process
is outside its remainder region,
and the fact that $\ms{ltime}(i) \geq \ms{now} + e(k) c_2$ for all
$i$, $1 \leq i \leq k$.
(The upper bound is $e(k) C c_2$ for all computations that satisfy the
timing constraints; we can stretch the given fast computation of
$p_{k+1}$ so that the time between its steps is always $c_2$, and an
upper bound of $e(k) C c_2$ for this slower computation implies an
upper bound of $e(k) c_2$ on the fast computation.)
But then we can let $p_{k+1}$ remain in its critical region while the
rest of the processes proceed normally, still observing the timing
assumptions. We first allow all the processes to write the registers
they are nullifying.
\absrem{The timing assumptions allow this round-like
behavior, because once one process takes a step, the upper bound for
its next step is $c_2$, which is at least as great as any other
process' new value of $\ms{last}$.
} % end absrem
Once they have done this, they have hidden all information about
$p_{k+1}$ being in the critical region, so some other process
will eventually
proceed into its critical region, thereby violating mutual exclusion.
This is a contradiction.

It remains to carry out the recursive construction.
Basis:  $j = 1$.
Just let $p_1$ enter, going fast.
Within time at most $e(k) c_2$,
it must go to the critical region, and in order to do so,
it must write some register, say $v$.
\absrem{
(If it does not, it is hidden while in the critical region and this
can cause a violation of mutual exclusion.)
[[[Need to put a lemma in here.  Maybe merge with prior lemma 3.5.]]]
} % end absrem
Let $p_1$ stop at a particular point in this interval, when it is about to write some $v$ for the
first time.  It is hidden, and ready to write, so it nullifies $v$.
Moreover, stopping just when time $c_1$ has elapsed after the prior step
ensures that $\ms{ftime}(1) \leq \ms{now}$,
and since $\ms{ltime}(1) = \ms{now} + c_2 - c_1$, since $C \geq 2$
we also have $\ms{ltime}(1) \geq \ms{now} + e(k) c_2$.
The total time required for this is at most $e(k) c_2 = f(1,k) e(k)
c_2$, which suffices.

Inductive step: 
Suppose we have the result for $j \leq k - 1$.
\absrem{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
starting from any configuration in which all processes are
in their remainder regions,
there is a finite timed execution of $p_1, \ldots, p_j$,
satisfying the timing constraints, and 
leading to a point at which $p_1, \ldots, p_j$ nullify $j$ distinct
registers, and moreover, for all $i$,
$1 \leq i \leq j$, 
$\ms{ltime}(i) \geq \ms{now} + e(k) c_2$ and $\ms{ftime}(i) \leq
\ms{now}$.
Finally, the total time required for the execution is at most 
$f(j,k) e(k) c_2$.
} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Starting from any configuration in which all processes are
in their remainder regions,
we wish to obtain the analogous timed execution for $p_1, \ldots,
p_{j+1}$.
\absrem{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
That is, we want a finite timed execution of $p_1, \ldots, p_{j+1}$,
satisfying the timing constraints, and 
leading to a point at which $p_1, \ldots, p_{j+1}$ nullify $j+1$ distinct
registers,
and moreover, for all $i$, $1 \leq i \leq j+1$, 
$\ms{ltime}(i) \geq \ms{now} + e(k) c_2$ and $\ms{ftime}(i) \leq
\ms{now}$.
Finally, the total time required for the execution should be at most 
$f(j+1,k) e(k) c_2$.
} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As in \cite{BL}, we construct a ``spine'' execution; 
this time, the spine execution will satisfy the timing constraints.
Constructing the spine involves 
applying the inductive hypothesis to get $p_1, \ldots, p_j$ nullifying
$j$ registers, with all $\ms{ltime}$ values at least 
$\ms{now} + e(k) c_2$ and all $\ms{ftime}$ at most $\ms{now}$, 
all within time at most $f(j,k) e(k) c_2$.
Then we repeatedly do the following:

Allow all of $p_1, \ldots, p_j$ to write at time exactly $e(k) c_2$
after the stopping point, with no other intervening steps.  
Then use the deadlock-freedom 
hypothesis to allow all these processes to proceed to
their critical regions, one at a time, and from there, to their
remainder regions.  
(Each will only spend time $0$ in the critical region.)
Do this using a fast execution fragment, so the upper bound for each
process to go critical is $e(k) c_2$, and then to go to its remainder
region is another $e(k) c_2$.
After some time, all will be back in their remainder region.  
Then apply the inductive hypothesis once again to get
$p_1, \ldots, p_j$ nullifying
$j$ registers, with all $\ms{ltime}$ values at least 
$\ms{now} + e(k) c_2$ and all
$\ms{ftime}$ values at most $\ms{now}$,
again within time at most $f(j,k) e(k) c_2$.

So, we repeatedly have $p_1, \ldots, p_j$ nullifying a set of $j$
registers.
Sometime within the first ${k \choose j} + 1$ times this happens, the same
set of $j$ registers will be nullified.
Call this set $V$.
We claim that the time until the second point where $V$ is nullified is at
most 
$({k \choose j} + 1) f(j,k) e(k) c_2 + {k \choose j} (2 j + 1) e(k) c_2$.
The first term in this sum describes the total time taken for all the
uses of the inductive hypothesis.
The second term describes the total time for the processes to
overwrite and then to proceed back to their remainder regions.
Note that by definition of $f$, this time bound expression is equal to 
$f(j+1,k) e(k) c_2$.

Now we use this spine to help us construct the desired execution of
$p_1, \ldots, p_{j+1}$.
We run the spine just until the first time $V$ described above is
nullified.
Then we insert some steps of $p_{j+1}$, running fast, just until it is
about to write something not in $V$.
This must happen within time $e(k) c_2$, since $p_{j+1}$ doesn't know
there is anyone else there and must go critical by $e(k) c_2$ in a
fast execution in which it operates alone.
%[[[
It must write something not in $V$, since otherwise its writes could
be overwritten by the nullifying processes $p_1, \ldots, p_j$, who
would thereby hide $p_{j+1}$ in the critical region and lead to a
violation of mutual exclusion.
%]]]
Just before it writes something not in $V$, we stop $p_{j+1}$ and now
allow the rest of the spine to proceed as before, just until the
second time that $V$ is nullified.
We claim that we are allowed to stop $p_{j+1}$ for that length of
time, because the length of time for the spine is at most 
$f(j+1,k) e(k) c_2$,
the upper bound on step time for $p_{j+1}$ is $c_2$,
and $f(j+1,k) e(k) c_2 \leq c_2$.
(This latter fact follows from the fact that 
$1 \geq f(j+1,k) e(k)$,
which in turn follows from Lemma \ref{relate e and f}.)

We claim that the resulting execution has the required properties.
The inductive hypothesis already tells us that the $\ms{ftime}$ and
$\ms{ltime}$ values for processes $p_1, \ldots p_j$ are as required.
We must show that the values for $p_{j+1}$ are also appropriate.
Since at least two steps have occurred for some particular process
since $p_{j+1}$ was stopped, 
it must be that $\ms{ftime}(j+1) \leq \ms{now}$.
It remains to consider the value of $\ms{ltime}(j+1)$.
To see that $\ms{ltime}(j+1) \geq \ms{now} + e(k) c_2$, it suffices to
show that $c_2 \geq f(j+1,k) e(k) c_2 + e(k) c_2$.
But Lemma \ref{relate e and f} implies that 
$1 \geq f(j+1,k) e(k) + e(k)$,
which immediately implies this inequality.
\end{proof}

\section{Weaker Timing Assumptions}
We show that weakening the timing model by assuming 
that the bounds $[c_1,c_2]$ are unknown, or that 
the timing conditions are only {\it eventually} met, 
leads to a lower bound of $n$ on the number of read/write registers
required, just as in the asynchronous case.

%\subsection{The Resilient Model}

In the {\it resilient} timing model, 
we again consider a fixed pair, $[c_1, c_2]$, of bounds
for the time between steps in the trying or exit region,
as in the timed model.
However, now we only consider those executions in which
the time bounds hold {\em eventually}.
We prove the following theorem by a variation of the 
\cite{BL} proof. 
\absrem{  %%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Impossibility of Mutual Exclusion and Deadlock-Freedom
with Fewer than $n$ Registers}
} %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}
\label{resilient-imposs-me-da}
There is no $[c_1, c_2]$ resilient algorithm providing mutual exclusion 
with deadlock-freedom for $n \geq 2$ asynchronous processes
that uses fewer than $n$ shared read/write registers.
\end{theorem}

\absrem{ %%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
Another variant of the BL proof.
This time, we show inductively on $j$ that, from any system state in which
everyone is in the remainder region, 
there is some prefix of an execution of the algorithm 
(note there are no timing requirements for a prefix)
that leads to $j$ processes nullifying $j$ registers.

For the base, $j = 1$, just allow process $1$ to enter, with the time
bounds satisfied, and use {\em deadlock-freedom} to have it reach
the critical region; on the way, it must write a register,
as usual.
[[[Gee, we could use some general theorems about stuff like this,
since right now I am having to re-think the little arguments over and
over for all the models.
So far, I don't know how to do this, since each case seems to be just
a little bit different.]]]

For the inductive step, for $j+1$, we proceed by constructing a spine
as usual.
This time, 
the spine gets constructed by using the inductive hypothesis to bring
in the $j$ processes, then having them all write,
then having the execution continue with the time bounds satisfied,
so that we can use the {\em deadlock-freedom} hypothesis to get all 
the $j$ processes return to their remainder region.  
Then we repeat this as usual, until a set $V$ repeats.

Now we consider the side execution of process $j+1$ from the first
of the two points where processes $1, \ldots ,j$ 
are paused ready to write $V$.
If we consider the values of all the shared registers at this point,
they are consistent with all processes being in their remainder
regions.
Let $s$ be the analogous state in which all processes are in their remainder
regions and the registers have the same values.
Then from $s$, 
there is an execution of process $j+1$
in which it goes on its own to the critical region.
(Consider an execution satisfying the timing constraints and use {\em
deadlock-freedom} to show this.)
Also, we claim that process $j+1$ must write some register not in $V$ 
along the way.
If not, then the same kind of contradiction as before arises:
here, process $j+1$ can execute a ``sped-up'' version of this
execution starting from the point where processes $1, \ldots, j$ are
paused at $V$, getting all the way to its critical region
(this may violate the timing constraints, but is still an allowable
prefix of an execution);
then processes $1, \ldots j$ can continue the spine,
overwriting everything written by process $j+1$, 
thereby hiding it in the critical region.  

Now construct the main execution by inserting the sped-up steps of
process $j+1$, just up to the point where it is about to write a
register not in $V$, into the spine as usual.
This involves not only speeding up process $j+1$ for a while, to
squeeze its steps in before the other processes write,
but then also pausing process $j+1$ for a long time while the spine
executes. 
Thus, the time constraints are not necessarily satisfied in the
execution being constructed.
However, $p_{j+1}$ is hidden from all the others, 
so they will still continue to execute the spine as before, and will
wind up with $j + 1$ registers nullified.

The special case of the inductive step for $j = n$ clearly implies the
need for $n$ registers.
\end{proof}

[[[Whew!  There was more going on above than I thought.  We probably
need some general lemmas that cover several models, because the
arguments seem repetitive.]]]

\begin{remark}
It seems that the proof above still holds in case the executions are
slightly further restricted, ensuring that even in the portion of the
of execution where the bounds are not observed, there is not
occurrence of two consecutive steps of the same process having exactly
the same associated real time.
This remark gets used in the following subsection.
We might change the definition of this resilient model just
to rule out $0$-time steps, because we only have a lower bound result
for this case, and it is a stronger result when stated for the more
restricted set of executions.
\end{remark}

} %%%%%%%%%%%%%% end abstract remove %%%%%%%%%%%%%%

%\subsection{The Unknown Bound Model}

In the {\it unknown bound} timing model, 
we consider those executions in which there
exist some time bounds $[c_1, c_2]$, $0 < c_1 \leq c_2 < \infty$, that
hold throughout the execution.
However, the time bounds are allowed to be {\em different} in
different executions, in other words, unknown to the processes.
We prove the following 
theorem by a reduction from the previous result.
\absrem{ %%%%%%%%%%%%%%
\subsubsection{Impossibility of Mutual Exclusion and Deadlock-Freedom
with Fewer than $n$ Registers}
} %%%%%%%%%%%%%%%%%

\begin{theorem}
There is no unknown bound algorithm providing mutual exclusion 
with deadlock-freedom for $n \geq 2$ asynchronous processes
that uses fewer than $n$ shared read/write registers.
\end{theorem}

\absrem{ %%%%%%%%%%%%%%%%
\begin{proof}
This follows by a reduction from the previous result.
Suppose for the purpose of contradiction that we have an algorithm $A$
that has the properties above, for its ``unknown bound'' executions.
Now fix any $[c_1, c_2]$, where $0 < c_1 \leq c_2 < \infty$.
Then we claim that $A$ also has the same properties for its
``$[c_1, c_2]$-resilient'' executions.
(Here, we have to use the stronger definition of 
``$[c_1, c_2]$-resilient execution'' alluded to in Remark \ref{}, where
$0$ time between steps of the same process is not permitted.)

For, consider any $[c_1, c_2]$-resilient execution $\alpha$.
Past some point in $\alpha$, the bounds $[c_1,c_2]$ are always
observed.  There are only a finite number of events occurring before
the bounds start to hold.
So there exist $[d_1,d_2]$, $0 < d_1 \leq d_2 < \infty$, such that the
entire execution $\alpha$ observes the bounds $[d_1,d_2]$.
This means that $\alpha$ is an ``unknown bound'' execution.
Thus, we have actually shown that any
$[c_1, c_2]$-resilient execution of $A$ is also an unknown bound
execution of $A$.

Since we have assumed that the unknown bound executions of $A$ all
have the desired properties, this implies that all the
$[c_1, c_2]$-resilient execution of $A$ also satisfy the properties.
But then $A$'s existence is in contradiction to Theorem 
\ref{resilient-imposs-me-da}.
\end{proof}

\subsection{Randomized Models}

[[[Comment: Nancy: This is Nir's.  I haven't thought about this. 
Nir: Yes, this is Nir's but not for the abs, its for the summertime, 
when the livin is easy...]]]

We also show that [[[$n$]]] read/write registers are necessary if 
one replaces the timing assumptions by 
other well established assumptions such as 
the availability of coins (randomization),
or stochastic assumptions on scheduling (as in exponential 
backoff schemes \cite{Aggarwal}). 

[[[
Nancy, variations on the BL should give us this. I think 
your method can also be extended to the randomized case,
since as far as I can tell, you do not need to assume that 
the scheduler knows where a process is about to write.
Nir]]]



\section{
%Conclusions and 
Further Work}


\subsection{Summary of Results}

[[[To be written.]]]



There are many directions in which this work should be extended.
Both the upper and lower bounds should be tightened, and time bounds should be 
proven for asynchronous mutual exclusion, where the number of shared registers is at
least as great as the number of processes. Other directions would be an
analysis of the effects of randomization on our upper and lower bounds,
consideration of fairness properties rather than just deadlock-freedom, and
the introduction of contention on the shared registers as a factor in the analysis. 


Work that remains to be done includes the following.
\begin{enumerate}
\item 
Strengthening either the upper or the lower bounds, to better
understand the dependency of the time complexity of timing-based
mutual exclusion on the number of shared registers.

\item 
Obtaining time bounds for asynchronous mutual exclusion
algorithms, in the case where the number of shared registers is at
least as great as the number of processes.

\item
Extending the results to include consideration of fairness properties
rather than just deadlock-freedom.

\item
Considering the impact on the complexity and possibility results of
allowing randomization in the algorithms.

\item 
Considering alternative architectures;
for example, we have assumed that only the contending processes are
allowed to participate in the algorithm.
What is the impact on the results, as well as the practical
feasibility, of allowing the critical region to be allocated by a
special ``supervisor'' process running on a dedicated processor?
What is the impact of taking contention on the shared registers into
account?
\end{enumerate}


\subsection{Strengthening the Results}

[[[The upper and lower bounds are not that tight.
E.g., for the 2-register case, there is a substantial difference
between the constants in the lower and upper bounds.
(around 1/10 vs. 1?)
It would be nice to close this gap further.

Also, note that the lower bound degrades badly as I increase the
number of registers.  Yet we have no such tradeoff for the upper
bound.  Is there some way to take advantage of the existence of more
registers to cut down the running time?]]]

\subsection{Randomization}

[[[To be written.]]]

\subsection{Time Complexity for the Asynchronous Case}

[[[It would be nice to be able to say something about
the time complexity for the asynchronous case, 
with $n$ registers and $n$ processes.  
The algorithm in the BL paper uses time approx. $n c_2$, I believe.  
This has no dependence on $C$, of course, but does have a dependence on $n$.
Is this necessary?  Can this problem be solved in approx. $c_2$, without
the $n$?  If not, then in approx. $(log n) c_2 $?
Remember, that we are allowed to use multi-writer, multi-reader
registers, 
whereas the algorithm in [BL] was for the single-writer case.

This reminds
me of the place we got stuck trying to prove a big lower bound, in our
paper with Hagit.  Does Cook-Dwork-Reischuk say anything about this
kind of problem?  Is there an easy or known solution?
]]] [[[ Comment: Yes, very interesting, since the question you really want an 
answer to is whether needing registers 
means each process has to read them all.
]]]

\subsection{Supervisor Model}
[[[ Comment: Answer to supervisor model.
Nancy, the current trend in hardware 
and parallel systems is for fast MIMD parallel machines 
that multiplex many processes and tasks, using a distributed OS,
in order not to waste CPU cycles. 
The supervisor model defeats this purpose. 
Either process $p_0$ is multiplexed, 
or it is a single phisical processor. 
In the first case the alg cannot be used on OS level,
since it assumes lower level mutex by the multiplexing OS
(and generates an overhead of context switching and swapping).
In the second case, the dedicated processor 
will be *wasting* zillions of CPU cycles reading shared vaiables
if there is a low demand for mutex. Thus, the response time will be low, but 
the total number of operation per entry truely impractical. 
To get best utilization of the CPU's, one should have processes
spend mutex cycles only when they wish to perform mutex.
So the supervisor model is of no interest given 
the problem we wish to solve and today's machines.
]]]
[[[I'm not so sure about this.  What's wrong with wasting one
processor?  I don't think processor utilization ought to be that
important in the long run.  N.]]]

In the olden days, the assumption we have made in this paper, that
processes can only participate when in their trying and exit regions,
was common, and was based on the realities of time-shared
single-processor machines.  For ***????true parallel????*** 
processors, this assumption is no longer so reasonable.

If we drop this assumption, then all our impossibility results fall
apart.
In fact, it seems that some simple and efficient algorithms become
possible.
E.g., suppose we have a separate process $p_0$ that is always around,
and functions as a scheduler.
Then other processes, when they arrive, could keep trying to record
this fact in register $x$.
The supervisor
\begin{quote} 
********keeps reading $x$*******  (BAD BAD BAD)
\end{quote}
 till it sees some index $i$ there,
and then informs $i$ it can go critical by writing $i$ into register
$y$.
When a process leave the critical region, it writes $0$ into $x$ and
$y$.
Needs work, but that's the idea.  Takes only constant times $c_2$,
even in asynchronous case, and satisfies DA.

What about one register here?  --> only without deadlock freedom.

What is actually wrong with such algorithms?  Maybe they do indicate
that our other results are really only of theoretical interest.
Is there a practical (patentable?) algorithm we can get using a
supervisor?
(A joke, a joke.).]]]

\subsection{Fairness}

[[[Extend some of these results to consider various fairness properties
such as no-lockout.]]]
} %%%%%%%%%%%%%% end remove %%%%%%%%
\section{Acknowledgments}


Many thanks go to Faith Fich for her interest and attention, and for
many helpful suggestions on the results and proofs.
We also thank Victor Luchangco who helped with the proof of
Lemma~\ref{invt-alg2}.   
\remove{
\begin{itemize}
\item Get bib and refs right.
\item Styer description
\item Lamport - which paper?
\end{itemize}
} % end remove
