\section{Introduction}

%[[[I rewrote the intro extensively.]]]

Although current-day multiprocessors provide
sophisticated synchronization primitives for mutual exclusion, 
situations that require a register-based exclusion algorithm continue
to arise \cite{macblane,TUXEDO}.
Known mutual exclusion algorithms \cite{BL,Dijkstra,Katseff,Lamport}
require that 
both the number of read/write registers and the number of 
operations a process performs to access the critical region
be at least equal to the total number of processes in the system. 
The lower bound of Burns and Lynch \cite{BL}
implies that this linear complexity 
is optimal for deterministic algorithms, 
even if multi-writer registers are used.
This implies that such algorithms 
cannot be expected to perform well 
in systems that support thousands of concurrent processes
\cite{macblane,TUXEDO}.

Recently, several researchers \cite{Styer,Merritt-Taubenfeld}
have proposed ways of overcoming the linear lower bound on the number
of operations a process needs to perform.
For example, employing operating system support 
in a sophisticated way at process creation time,
Merritt and Taubenfeld provide an algorithm that 
limits the number of 
operations by a process to depend only on the number of processes 
concurrently accessing the critical region. 
%[[[Nancy: How does Eugene Styer do it?]]]
%[[[I don't know.  N.]]]
However, in both of these cases, the number of shared registers 
the algorithm requires is still at least equal to the total number of
processes in the system.
Also, using randomization, 
and based on the work of Lynch and Saias \cite{LS}, 
Kushilevits and Rabin \cite{KL} offer a new (but rather involved) 
algorithm that employs randomization to achieve fair mutual exclusion 
using a single $O (\log \log n)$-bit shared register.
However, this solution uses a powerful $n$-process {\it Test-and-Set}
shared variable, not a read/write register.

In this paper, we consider the mutual exclusion problem in a {\em real-time}
setting.
More particularly, we examine the benefits that can be obtained by using
available {\em timing information} in mutual exclusion algorithms.

Fischer \cite{Fischer-mutex} appears to have been the first to propose 
overcoming the Burns-Lynch lower bound of $n$ shared registers
for deadlock-free mutual exclusion by assuming timing constraints.
He has presented a truly simple mutual exclusion algorithm that uses
only a single shared multi-writer register. 
However, his algorithm has a major drawback:
it fails to guarantee mutual exclusion if the timing constraints are
not met. This is also the drawback of the  
elegant timing-based algorithm of 
Alur and Taubenfeld \cite{Alur-Taubenfeld}.
Ideally, a timing-based algorithm should not depend on its timing
constraints to guarantee basic safety properties, but only to ensure
liveness and performance properties.

In this paper, we give a simple and efficient timing-based mutual
exclusion algorithm that {\em always} guarantees mutual exclusion
(i.e.,  even when run asynchronously), 
and also avoids deadlock in case certain inexact timing constraints are met.
Specifically, we assume that the times between successive steps of
the same process are always in some known interval, $[c_1,c_2]$, of
real times.
This assumption is realistic in the real-time setting, if processes do
not get swapped out during the time when they are executing the
protocol, 
or even if they do get swapped out, but the
underlying processor scheduling algorithm ensures approximately
predictable execution speeds. (In fact, the algorithms we present require
that processes do not get swapped out only between two specific lines
of code, and not throughout the complete protocol.)
The algorithm uses only {\it two} shared read/write registers 
(a total of $\log n+1$ shared bits),
thus ``overcoming'' the $n$ register lower bound for asynchronous
algorithms.
We also prove that the problem cannot be solved with only one shared
register, so that our algorithm is optimal in terms of the number of
registers.

Next, we prove a lower bound for the time complexity of any
deadlock-free mutual exclusion protocol, as a function of the number of 
shared registers it employs.
The proof uses the techniques of \cite{BL}, extended to the
real-time setting.
This bound shows that our algorithm is near optimal, 
in terms of time complexity.

Finally, we show that two natural ways of weakening the timing 
assumptions lead, unfortunately, to an $n$ register lower bound.
Specifically, if we assume that the time bounds $[c_1,c_2]$ are fixed,
and always hold, but are {\em unknown to the processes}, 
or that the timing conditions are only {\it eventually} met, 
then we obtain a lower bound of $n$ on the number of read/write
registers required.

\absrem{ %%%%%%%%%%%%% Removed from Extended Abstract %%%%%%%%%%%%%%%5

All of the results are presented formally, 
in terms of the {\em timed automaton}
model of Merritt, Modugno and Tuttle \cite{MMT}.

[[[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}). I will leave this additional 
stuff out regarding randomization etc, but in the summer I will 
try to add them in to make the story complete]]]
} %%%%%%%%%%%%% Removed from Abstract %%%%%%%%%%%%%%%5
