Sam Toueg
PhD Princeton University, 1979

My research interests include distributed computing, fault-tolerance and real-time. I work on methodologies, paradigms, and algorithms for fault-tolerant distributed systems, in both message-passing and shared-memory systems. My long-term goal is to bridge the gap between theoretical results and the need for efficient and practical solutions.

A well-known result of fault-tolerant distributed computing states that the Consensus problem cannot be solved in asynchronous systems. This impossibility result stems from the inherent difficulty of determining whether a process has crashed or is merely very slow. In previous work with Tushar D. Chandra and Vassos Hadzilacos, we determined exactly how much information about failures is necessary and sufficient to solve Consensus. We first showed one can use W, an unreliable failure detector that can make an infinite number of mistakes, to solve Consensus. We then proved that to solve Consensus, any failure detector has to provide at least as much information about failures as W. Thus, W is the weakest failure detector for solving Consensus in asynchronous systems. We are now exploring the practicality of implementing W and of building applications that rely on W for their correctness. In this context, we are focusing on the Group Membership Problem (GMP). We showed that even a small fragment of GMP cannot be solved in asynchronous systems with failures, exactly as with Consensus. We are now investigating failure detector-based solutions to this problem.

A concurrent system consists of processes communicating via shared objects. A shared object is wait-free if each process that accesses this object is guaranteed to get a response even if all the other processes crash. We are exploring wait-free hierarchies of object types, where each object (type) is as-signed to a level that corresponds to its ability in implementing other wait-free objects. In a previous work, Prasad Jayanti (a former PhD student at Cornell) has shown that a well-known hierarchy (Herlihy's) is not robust: roughly speaking, in this hierarchy there is an object at level 2 that can be used to implement wait-free objects at any level. In collaboration with Jayanti, we are now exploring the question of whether robust wait-free hierarchies exist. In this context, we showed that no wait-free hierarchy exists for a special class of objects, the so-called "non-oblivious" or "hard-wired" ones.

University Activities

Professional Activities



Return to:
1994-1995 Annual Report Home Page
Departmental Home Page

If you have questions or comments please contact:

Last modified: 26 November 1995 by Denise Moore (