This directory contains compressed postscripts files of various papers, mostly ones in which I am a co-author. I have, however, also included some other closely related papers (with their authors' kind permission). Following is a brief description of the papers contained in this directory. Comments on any paper you get from here are most welcome. --Vassos Hadzilacos ====================================================================== TusharThesis.ps.Z Tushar Deepak Chandra Unreliable failure detectors for reliable distributed systems 120 pp. This is the PhD thesis (Dept. of Computer Science, Cornell University) of Tushar Deepak Chandra. It combines the results contained in "failure.detectors.algorithms" and "failure.detectors.weakest". ====================================================================== failure.detectors.algorithms.ps.Z Tushar Chandra and Sam Toueg Unreliable failure detectors for reliable distributed systems 51 pp. (Published in the Journal of the ACM, 43(2):225-267, March 1996. Also issued as Cornell tech report #95-1535. Full version of a paper that first appeared in PODC 91.) If you read only one paper on failure detectors, this is the one. ====================================================================== failure.detectors.shared.memory.ps.Z Wai-Kau Lo and Vassos Hadzilacos Using failure detectors to solve Consensus in asynchronous shared-memory systems 16 pp. (The paper as it appears in WDAG 94.) Gives deterministic algorithms for Consensus in asynchronous shared-memory systems that use only atomic read-write registers, as well as some lower bounds and impossibility results. ====================================================================== failure.detectors.weakest.ps.Z Tushar Chandra, Vassos Hadzilacos and Sam Toueg The weakest failure detector for solving Consensus 43 pp. (Published in the Journal of the ACM, 43(4):225-267, July 1996. A slightly updated version of Cornell tech report #92-1293. Full version of a paper that first appeared in PODC 92.) Shows that the "eventually weak failure detector" of Chandra and Toueg is the weakest one that can be used to solve Consensus. ====================================================================== fault.tolerant.broadcasts.ps.Z Vassos Hadzilacos and Sam Toueg A modular approach to fault-tolerant broadcasts and related problems 83 pp. (Issued as TR94-1425, May 1994, Dept. of Computer Science, Cornell University.) Gives precise specifications of various types of fault-tolerant broadcasts, and uses these to derive a modular way of constructing more powerful broadcast algorithms from simpler ones. ====================================================================== gmsImpossibility.ps.Z Tushar Chandra, Vassos Hadzilacos, Sam Toueg and Bernadette Charron-Bost Impossibility of group membership in asynchronous systems 10 pp. (Issued as TR95-1548, Dept. of Computer Science, Cornell University.) Proves that (even) a small fragment of the functionality required by a primary-partition group membership service cannot be implemented in asynchronous distributed systems --- even if at most one process crashes, and communication is guaranteed to be reliable. ====================================================================== gmsSpecification.ps.Z Emmanuelle Anceaume, Bernadette Charron-Bost, Pascale Minet and Sam Toueg On the formal specification of group membership services 13 pp. (Issued as TR95-1534, Dept. of Computer Science, Cornell University.) Discusses problems in various published formal specifications for group membership services in asynchronous systems. ====================================================================== podc94.ps.Z Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti and Sam Toueg Wait-freedom vs. t-resiliency and the robustess of wait-free hierarchies 10 pp. (The paper as it appears is in PODC 94.) Shows that the consensus object type cannot be used to "boost" the consensus number of any other type. Using this it shows that a collection of types S can be used to implement t-resilient Consensus among n processes (for any n>t) if and only if S can be used to implement wait-free Consensus among t+1 processes (for all t>1). ====================================================================== shared.memory.faulty.ps.Z Prasad Jayanti, Tushar Chandra and Sam Toueg Fault-tolerant wait-free shared objects 57 pp. (Full version of the paper that appeared in STOC 92. Also issued as Cornell tech report #92-1298.) ====================================================================== wdag94.ps.Z Same as "failure.detectors.shared.memory.[dvi.Z,ps.Z]". ======================================================================