% MAC VERSION
%\documentstyle{article}
%\input epsf
%\newcommand{\dofigure}[1]{\epsfbox{:#1}}
% UNIX VERSION
\documentstyle[psfig]{article}
\newcommand{\dofigure}[1]{\psfig{figure=#1}}
% NO GRAPHICS
%\newcommand{\dofigure}[1]{}


%\special{header=mac.MDII.pro}

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

\newtheorem{definition}{Definition}[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}}

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

% a blank line
\def\blankline{\hbox{}}


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

\setlength{\parskip}{\medskipamount}
\setlength{\itemsep}{-\parsep}


\newcommand{\ol}{\setlength{\itemsep}{0pt.}\begin{enumerate}}
\newcommand{\eol}{\end{enumerate}\setlength{\itemsep}{-\parsep}}


\newcommand{\figline}{\rule{20pc}{.02in}}
\hyphenation{diff-rac-ting diff-rac-tion diff-rac-ted dis-tri-bu-ted}
\hyphenation{co-or-di-na-tion}
\hyphenation{dis-tri-bu-ted pro-te-us ale-wife inc-re-ment}

\newcommand{\fullname}{diffracting}
\newcommand{\Fullname}{Diffracting}
\newcommand{\fullion}{Diffraction}


\begin{document}
\title{\bf A Steady State Analysis of \Fullname\ Trees \\
%\title{\bf Combinatorial Modelling of \Fullname\ Trees \\
%{\large\sc (Extended Abstract)}
 }

\author{Nir Shavit \thanks{MIT and Tel-Aviv University. 
Supported by National Science Foundation grant CCR-9520298.
Contact Author: {\tt shanir@theory.lcs.mit.edu}.}
\and Eli Upfal \thanks{The Weizmann Institute, Israel, and IBM
Almaden Research Center, California. Work at the Weizmann Institute
supported in part by the Norman D. Cohen Professorial Chair
of Computer Science, a MINERVA grant, and a grant from the Israeli
Academy of Science. } 
\and Asaph Zemach \thanks{Tel-Aviv University. Supported by an Eshkol Fellowship
from the Israeli Ministry of Science.}} 
\maketitle

%\toappear{}

\remove{%%%%%%%%%%%%%%
\begin{center}
Department of Computer Science, \\
School of Mathematics,\\
Tel-Aviv University,\\
Tel-Aviv 69978, Israel.\\
Contact: shanir@math.tau.ac.il
\end{center}
} %%%%%%%%%

%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\footnotetext[1]{Contact Author: {\tt shanir@theory.lcs.mit.edu}}
%\renewcommand{\thefootnote}{\arabic{footnote}}
%{\def\thempfn{}z Z
%\footnotetext{This work was supported by a Digitial Equipment Corporation
%ERP Equipment Grant \\
%{\it Keywords:} Shared Counters, Counting Networks, Diffracting Trees, Load Balancing,
%Concurrent Data Structures, Randomization.}} 

\input{abs}
\input{intro}
\input{dtrees}
\input{combi4}
\input{res}
\input{conc}

%\bibliographystyle{plain}
%\bibliography{simplex}
\begin{thebibliography}{10}
\input{bib}
\end{thebibliography}

%\input{appendix}

\end{document}


