{\small 
\begin{thebibliography}{10}

\bibitem{Anderson}
James H. Anderson,
\newblock Composite Registers.
\newblock {\em Distributed Computing, 6(3)}, pages 141-154, April 1993.

\bibitem{AndersonM} 
M. Moir and J. Anderson. 
\newblock Wait-Free Algorithms for Fast, Long-Lived Renaming, 
\newblock {\em Science of Computer Programming 25}, 1995, pp. 1-39.

\bibitem{AH}
J. Aspnes, M. P. Herlihy,
\newblock Wait-Free Data Structures in the Asynchronous PRAM Model.
\newblock {\em Proceedings of the 3rd Annual ACM Symposium on Principles of
  Distributed Computing}, pages 377--408, July 1991. 
\newblock Also appeared as technical report.

\bibitem{AfekADGMS90-sub}
Yehuda Afek and Hagit Attiya and Danny Dolev and Eli Gafni and
Michael Merritt and Nir Shavit,
\newblock Atomic Snapshots of Shared Memory.
\newblock {\it Journal of the ACM, 40(4)}, pages 873-890, September 1993.

\bibitem{ABD}
H.~Attiya, A.~Bar-Noy, and D.~Dolev.
\newblock Sharing memory robustly in message-passing systems.
\newblock In {\em Proceedings of the 9th Annual ACM Symposium on Principles of
  Distributed Computing}, pages 377--408, August 1990.
 
\bibitem{Renaming}
H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk.
\newblock Renaming in an asynchronous environment.
\newblock {\em Journal of the ACM}, July 1990.
 
\bibitem{ALS}
H.~Attiya, N.~Lynch and N.~Shavit,
\newblock Are Wait-Free Algorithms Fast?
\newblock  In {\it Journal of the ACM}, Vol.~41, No.~4 (July 1994),
pages 725-763. 

\bibitem{AttiyaR95}
H. Attiya and S. Rajsbaum.
\newblock A combinatorial topology framework for wait-free
computability.
\newblock Preprint, 1995.
 
\bibitem{BMZ}
O.~Biran, S.~Moran, and S.~Zaks.
\newblock A combinatorial characterization of the distributed tasks which are
  solvable in the presence of one faulty processor.
\newblock In {\em Proceedings of the 7th Annual ACM Symposium on Principles of
  Distributed Computing}, pages 263--275, August 1988. 
 
\bibitem{BorowskyGafniPODC}
E. Borowsky and E. Gafni.
\newblock Immediate Atomic Snapshots and Fast Renaming.
\newblock {\em Proceedings of the 12th Annual ACM Symposium on
Principles of Distributed Computing}, pages 41--51, August 1993.

\bibitem{BorowskyGafni}
E.~Borowsky and E.~Gafni.
\newblock Generalized flp impossibility result for $t$-resilient asynchronous
  computations.
\newblock In {\em Proceedings of the 1993 ACM Symposium on Theory of
  Computing}, May 1993.
 
\bibitem{BGSIMM}
E.~Borowsky and E.~Gafni.
\newblock A Simple Algorithmically Reasoned Characterization of
Wait-free Computations.
\newblock In {\em Proceedings of the Sixteenth Annual ACM Symosium on Principles of
Distributed Computing}, August 1997. 

\bibitem{BG93}
E.~Borowsky and E.~Gafni.
\newblock The set consensus hierarchy.
\newblock Unpublished manuscript, November 1993.
 
\bibitem{Chaudhuri}
S.~Chaudhuri.
\newblock Agreement is harder than consensus: set consensus problems in totally
  asynchronous systems.
\newblock In {\em Proceedings of the Ninth Annual ACM Symosium on Principles of
Distributed Computing}. 
  
\bibitem{CHLT93}
S. Chaudhuri, M.P. Herlihy, N. Lynch, and M. Tuttle.
\newblock Tight Bounds for $k$-Set Agreement.
\newblock In {\em Proceedings of the 33rd ACM Symposium on Foundations of 
Computer
Science}, October 1993.
 
\bibitem{Fekete}
A.~Fekete.
\newblock Asymptotically optimal algorithms for approximate agreement.
\newblock In {\em Proceedings of the 5th Annual ACM Symposium on Principles of
  Distributed Computing}, August 1986.
 
\bibitem{FLP}
M.~Fischer, N.A. Lynch, and M.S. Paterson.
\newblock Impossibility of Distributed Commit with one faulty process.
\newblock {Journal of the ACM},32(2), April 1985.
 
\bibitem{GafniK95}
E. Gafni and E. Koutsoupias.
\newblock 3-processor tasks are undecidable.
\newblock PODC 95, Brief announcement, page 271.


%\bibitem{HLS97}
%G. Hoest, N. Lynch, and N. Shavit. 
%\newblock On the computational relation between the 
%Iterated Immediate Snapshot and MRMW Registers models.
%\newblock {\it Manuscript,} 
%Laboratory for Computer Science, Massachusetts Institute
%of Technology, Cambridge, MA 02139, 
%March 1997.

\bibitem{Gawlick92-tr}
R. Gawlick, 
\newblock Bounded Concurrent Time-Stamping Made Simple.
\newblock {\it Technical Report}, 
Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA 02139, MIT/LCS/TR-556, 
October 1992.

%\bibitem{BG94}
%E.~Borowsky and E.~Gafni.
%\newblock private communication.
 
%\bibitem{SPAA91a}
%M.P. Herlihy.
%\newblock Impossibility results for asynchronous {PRAM}.
%\newblock In {\em Proceedings of the 2nd Annual Symposium on Parallel
%  Algorithms and Architectures}, July 1991.
 
\bibitem{H}
M. P. Herlihy. 
\newblock Wait-Free Synchronization.
\newblock {\it ACM Transactions on Programming Languages and systems,} 
Vol.. 11, No.1, Jan 1991, Pages 124-129.

\bibitem{HerlihyR95}
M. Herlihy and S. Rajsbaum.
\newblock Algebraic spans.
\newblock {\em Proceedings of the 14th Annual ACM Symposium on
Principles of Distributed Computing}, pages 90-99, August 1995. 

\bibitem{HR94}
M. P. Herlihy and S. Rajsbaum.
\newblock Set Consensus Using Arbitrary Objects.
\newblock In {\em Proceedings of the 12th Annual ACM Symposium on Principles
of Distributed Systems}, August 1994, Los Angeles.
 
\bibitem{HerlihyR96}
 M.P. Herlihy and S. Rajsbaum.
    \newblock    On the Decidability of Distributed Decision Problems,
   \newblock     To appear in STOC'97.

\bibitem{HS93}
M.P. Herlihy and N.~Shavit.
\newblock The asynchronous computability theorem for $t$-resilient tasks.
\newblock In {\em Proceedings of the 1993 ACM Symposium on Theory of
  Computing}, Pages 111--120, May 1993.
%\newblock Full version available as a DEC technical report.
 
\bibitem{HS94}
M. P. Herlihy and N. Shavit.
\newblock A Simple Constructive Computability Theorem for Wait-free Computation.\newblock In {\em Proceedings of the 26th Annual Symposium on Theory of
Computing}, Pages 243-252, May 23-25, 1994.
 
\bibitem{HS95}
M. P. Herlihy and N. Shavit.
\newblock The Topological Structure of Asynchronous Computability.
\newblock Technical Report, Submitted for Journal publication, Brown University, 1995.

\bibitem{L86b}
L.  Lamport,
\newblock On interprocess communication, {P}art {II}:  Algorithms.
\newblock {\it Distributed Computing (1)2}, pages 86-101, April 1986.


\bibitem{Lynch-book}
Nancy A. Lynch,
\newblock Distributed Algorithms.
 \newblock {\it Morgan Kaufmann},
        San Mateo, California,
        1996.


\bibitem{Lynch-Tuttle}
N.A. Lynch And M.R. Tuttle.
\newblock An Introduction To Input/Output Automata.
\newblock MIT/LCS/TM-373, MIT Laboratory For Computer Science, Nov 1988.
								
\bibitem{LynchR95}
Nancy Lynch and Sergio Rajsbaum.
\newblock On the {B}orowsky-{G}afni simulation algorithm.
\newblock In {\em Proceedings of the Fourth ISTCS Israel Symposium on Theory of
  Computing and Systems}, pages 4--15, Jerusalem, Israel, June 1996. IEEE
  Computer Society.
%\newblock Also, short version appears in {\em Proceedings of the Fifteenth
%  Annual ACM Symposium on Principles of Distributed Computing}, Philadelphia,
%  PA, page 57, May 1996.

 
\bibitem{Munkres}
J.R. Munkres.
\newblock{\em Elements of Algebraic Topology}.
\newblock Addison-Wesley, Cambridge, 1996.

\bibitem{Neiger}
G. Neiger.
\newblock Set-Linearizability.
\newblock In {\em Proceedings of the 13th Annual ACM Symposium on Principles of
  Distributed Computing}, page 396, August 1994.

\bibitem{VitanyiA86}
Paul M. B. Vit\'{a}nyi and Baruch Awerbuch,
\newblock Atomic Shared Register Access by Asynchronous Hardware.
\newblock {\it 27th Annual IEEE Symposium on Foundations of Computer Science},
pages 233-243, Toronto, Ontario, Canada
October 1986.

%\Bibitem{Schenk} 
%Eric Schenk, 
%\newblock Faster Approximate Agreement with Multi-Writer
%Registers, 
%\newblock {\it Proceedings of the 36th Annual Symposium on Foundations of
%Computer Science}, (1995), pages 714-723.

\bibitem{schenk}
E. Schenk, 
\newblock Computability and Complexity Results for Agreement Problems in Shared
Memory Distributed Systems.
\newblock  {\it Doctoral Thesis}, Department of Computer Science, University of
Toronto, Canada,  September, 1996. 

\bibitem{SaksZaharoglou}
M.~Saks and F.~Zaharoglou.
\newblock Wait-free $k$-set agreement is impossible: The topology of public
  knowledge.
\newblock In {\em Proceedings of the 1993 ACM Symposium on Theory of
  Computing}, May 1993.
 
\bibitem{Spanier}
E.H. Spanier.
\newblock {\em Algebraic Topology}.
\newblock Springer-Verlag, New York, 1966.
 

\end{thebibliography}
} % end of small
