%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% draft by Nancy and Nir
% Latex and read.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Edited by Nir, April 1992.
% Revised by Nancy, for the RTSS abstract, April 26, 1992.
% Revised by Nir, for the final RTSS abstract, September, 1992.

\documentstyle[11pt%,twocolumn
]{article}
%\input macros   

%%%%%%%%%%%%%%%%%%%%% MACROS %%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}

\newtheorem{definition}{De
finition}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]

% to get nice proofs ...
\newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}
\newcommand{\qed}{\hfill\rule{2mm}{2mm}}

% this command enables to remove a whole part of the text
% from the printout
% to use it just enter
% \remove{
% before the text to be excluded and
% }
% after the text
\newcommand{\remove}[1]{}

% ABSREM is a command has two versions, the first removes 
% from the printout all stuff relating to LONG version.
% To get the long version, comment out the first 
% and use the second. 
% The first that is used to get the short version is
%\newcommand{\absrem}[1]{}
% use second version below to get long version of paper
\newcommand{\absrem}[1]{#1}

\newcommand{\send}{\ms{send}}
\newcommand{\tend}{\ms{tend}}

% some arrows
%dashed arrow
\newcommand{\da}{\setlength{\unitlength}{1mm}
\hspace{1mm}
\begin{picture}(6.1,2)(0,-1)
\thinlines
\multiput(0.3,0)(1.5,0){3}{\line(1,0){1}}
\put(4.8,0){\vector(1,0){1}}
\end{picture}
\hspace{1mm}}
%full arrow
\newcommand{\fa}{\setlength{\unitlength}{1mm}
\hspace{1mm}
\begin{picture}(6.1,2)(0,-1)
\thinlines
\put(0.3,0){\vector(1,0){5.5}}
\end{picture}
\hspace{1mm}}

% marginal comment
\newcommand{\comment}[1]{\marginpar{\tiny #1}}

%other useful things
\newcommand{\ang}[1]{\langle{#1}\rangle}
\newcommand{\infinity}{\infty}

%% Macros from Danny to define time
%% LOCAL
% Time and date in the form January 1, 1985 and 23:59.  Note that
% \time is the count of minutes after midnight, built into Tex.
% \MonthDayYear differs from \today by giving the full month name.

\newcount\hour  \newcount\minutes  \hour=\time  \divide\hour by 60
\minutes=\hour  \multiply\minutes by -60  \advance\minutes by \time
\def\Month{\ifcase\month\or January\or February\or March\or April\or May\or June
  August\or September\or October\or November\or December\fi}
\def\Day{\number\day}
\def\Year{\number\year}
\def\Hour{\number\hour}
\def\Minutes{\ifnum\minutes<10 0\fi\number\minutes}
\def\MonthDayYear{\Month \space\Day, \Year}
\def\MonthYear{\Month, \Year}
\def\HourMinutes{\Hour:\Minutes}

\def\draft{\sc (Draft of \MonthDayYear at \HourMinutes)}



%%%%%%%%%%%%%%%%%%%%% END MACROS %%%%%%%%%%%%%%%%%


%\input largepage

%%%%%%%%%%%%%%%%%%%%% LARGEPAGE %%%%%%%%%%%%%%%%%

% Page size parameters were set to IEEE standard by Nir

%\setlength{\evensidemargin}{0.2in}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{-0.1in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}
\setlength{\marginparwidth}{0.6in}
% \setlength{\itemsep}{-\parsep}
%\renewcommand{\topfraction}{.9}
%\renewcommand{\textfraction}{.1}
\newcommand{\ol}{\setlength{\itemsep}{0pt.}\begin{enumerate}}
\newcommand{\eol}{\end{enumerate}\setlength{\itemsep}{-\parsep}}

%\setlength{\parskip}{\medskipamount}
%\setlength{\itemsep}{-\parsep}
\renewcommand{\topfraction}{.99}
\renewcommand{\textfraction}{.01}

% From paper with Mike
%\newcommand{\act}[1]{{         \tt #1}}
%\newcommand{\act}[1]{{\footnotesize {\bf #1}}}
\newcommand{\act}[1]{{\sf #1}}
\newcommand{\UQ}{\act{UpdateRequest}}
\newcommand{\SQ}{\act{ScanRequest}}
\newcommand{\SR}{\act{ScanReturn}}
\newcommand{\UR}{\act{UpdateReturn}}
\newcommand{\U}{\act{Update}}
\newcommand{\SN}{\act{Scan}}
\newcommand{\RQ}{\act{Request}}
\newcommand{\RT}{\act{Return}}
\newcommand{\Read}{\act{Read}}
\newcommand{\Write}{\act{Write}}

% From paper with Maurice
\def\Input{{\cal I}}
\def\Output{{\cal O}}
\def\dim{\hbox{\it dim\/}}
\def\ids{\hbox{\it ids\/}}
\def\lift{\hbox{\it lift\/}}
\newcommand{\States}[1]{{\em States\/}$(#1)$}
\newcommand{\In}[1]{{\em In\/}$(#1)$}
\newcommand{\Out}[1]{{\em Out\/}$(#1)$}
\newcommand{\Steps}[1]{{\em Steps\/}$(#1)$}
\def\Anchor{\hbox{\it Anchor\/}}
\def\RETURN{\hbox{\sc RETURN\/}}
\def\FINISH{\hbox{\sc FINISH\/}}
\def\CALL{\hbox{\sc CALL\/}}
\def\START{\hbox{\sc START\/}}
\newcommand{\ms}[1]{#1}

\def\cD{{\cal D}}
\def\eps{{\varepsilon}}
\def\config{{\it config}}
\def\exec{{\it exec}}
\begin{document}
%%%%%%% added by nir to get page numbering %%%%%%%%%%%
%\begin{titlepage}
\title{\bf Timing-Based Mutual Exclusion\footnotemark[1]}
%\author{
%\begin{tabular}[t]{c@{\extracolsep{8em}}c}
%N. Lynch & N. Shavit \\
%\\
%MIT & MIT\\ 
%Lab. for Computer Science & and Tel-Aviv University\\
%545 Technology Square &  Dept. of Computer Science \\
%Cambridge MA 02139 & Ramat-Aviv, Israel 69978 
%\end{tabular}}




\author{Nancy Lynch\footnotemark[2]
        \and Nir Shavit\footnotemark[3]}

\date{}
%\date{\sc Draft of \today}


\pagestyle{plain}

\maketitle

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\footnotetext[1]{This work was supported by ONR contracts N00014-85-K-0168
                 and N00014-91-J-1046,
                 by NSF grants CCR-8611442 and CCR-8915206,
                 by DARPA contracts N00014-87-K-0825 and N00014-89-J-1988,
                 and by Draper Laboratories grant DL-H-441640}
\footnotetext[2]{Laboratory for Computer Science, MIT, Cambridge, MA 02139.}
\footnotetext[3]{Laboratory for Computer Science, MIT, and Tel-Aviv University,
Tel-Aviv 69978, Israel.}

\begin{abstract}
{\small
Known asynchronous $n$-process deadlock-free mutual exclusion algorithms
require $O(n)$ read/write registers and $O(n)$ operations 
to access the critical region, rendering them impractical 
for large scale applications.

%[[[
Burns and Lynch have shown that $n$ registers are necessary for
solving this problem, in the asynchronous setting.
%]]]

%Several researchers have recently proposed ways to overcome 
%this bound by employing operating system support at process creation 
%time. 
%[[[I omitted this because I don't see that Merritt et al are
%overcoming the bound on the number of registers.  Seems to contradict
%what's said above.]]]

%[[[
This paper examines the benefits that can be obtained by using
{\em timing information} in mutual exclusion algorithms.
First, a simple and efficient timing-based mutual exclusion 
algorithm is given.
This algorithm always guarantees mutual exclusion 
(i.e.,  even when run asynchronously), 
and also avoids deadlock in case certain (realistic)
inexact timing constraints are met.
The algorithm uses only {\em two} shared read/write registers 
(a total of $\log n +1$ bits), 
thus ``overcoming'' the $n$ register lower bound for asynchronous
algorithms.
It is proved that the problem cannot be solved with only one shared
register, so that this algorithm is optimal in terms of the number of
registers.

Second, a lower bound is proved for the time complexity of
any deadlock-free mutual exclusion protocol, 
as a function of the number of shared registers it employs.
This bound shows that the algorithm described above is near optimal, 
in terms of time complexity.
Finally, it is shown that two natural ways of weakening the timing 
assumptions lead (unfortunately) to an $n$ register lower bound.
%]]]
} % end of small
\end{abstract}
%\end{titlepage}
\renewcommand{\thefootnote}{\arabic{footnote}}
\input intro
\input model
\input lamport
\input timed
\input weaken
\input bib
%\input model-defs
\end{document}

