Now showing items 1-20 of 42

    • Asynchronous Consensus and Byzantine Protocols in Faulty Environments 

      Bracha, Gabriel; Toueg, Sam (Cornell University, 1983-06)
      A consensus protocol enables a system of $n$ aynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes can only die, malicious processes can also ...
    • An Authenticated Byzantine Generals Algorithm with Early Stopping 

      Perry, Kenneth J.; Toueg, Sam (Cornell University, 1984-06)
      A protocol that solves the authenticated Byzantine General's Problem is presented. It is proved correct and shown to exhibit early stopping under the condition that fewer than half the processes are faulty.
    • Automatically Increasing the Fault-Tolerance of Distributed Algorithms 

      Neiger, Gilbert A.; Toueg, Sam (Cornell University, 1990-01)
    • Checkpointing and Rollback-Recovery for Distributed Systems 

      Koo, Richard; Toueg, Sam (Cornell University, 1985-10)
      We consider the problem of bringing a distributed system to a consistent state after transient failures. We address the two components of this problem by describing a distributed algorithm to create consistent checkpoints, ...
    • Correctness Proof of Ben-Or's Randomized Consensus Algorithm 

      Aguilera, Marcos Kawazoe; Toueg, Sam (Cornell University, 1998-05)
      We present a correctness proof for Ben-Or's Randomized Consensus Algorithm for the case in which processes can fail by crashing, and a majority of processes is correct. This is the first time that the proof of Ben-Or's ...
    • Distributed Agreement in the Presence of Processor and Communication Faults 

      Perry, Kenneth J.; Toueg, Sam (Cornell University, 1984-05)
      A model of distributed computation is proposed in which processes may fail by not sending or receiving the messages specified by a protocol. The solution to the Byzantine Generals Problem for this model is presented. Our ...
    • A Distributed Algorithm for Generalized Deadlock Detection 

      Bracha, Gabriel; Toueg, Sam (Cornell University, 1983-06)
      An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any $N$ available resources from a pool of size $M$. This is a ...
    • Distributed Snapshots In Spite of Failures 

      Shah, Amitabh; Toueg, Sam (Cornell University, 1984-07)
      An extension of the Chandy-Lamport algorithm ([Chan84]) to find global states of distributed systems is presented where benign failures of processes and channels are permitted. The scope of the algorithm in detecting ...
    • Effects of Message Loss on Distributed Termination 

      Koo, Richard; Toueg, Sam (Cornell University, 1987-03)
      We study the problem of termination in distributed systems with faulty communication channels. We show that for asynchronous systems, protocols that guarantee knowledge gain via message transfers cannot be guaranteed to ...
    • Engineering: Cornell Quarterly, Vol.20, No.2 (Autumn 1985): Twenty Years of Computer Science at Cornell 

      Gries, David; Teitelbaum, Tim; Reps, Thomas; Schneider, Fred B.; Babaoglu, Ozalp; Birman, Kenneth P.; Toueg, Sam; Krafft, Dean B.; Solworth, Jon A.; Duke, Diane; Fish, Michele (Internet-First University Press, 1985)
      IN THIS ISSUE: Twenty Years of Computer Science at Cornell /2 David Gries ... Immediate Computation or How to Keep a Personal Computer Busy /12 Tim Teitelbaum and Thomas Reps ... Reaching Agreement: A Fundamental Task Even ...
    • Exposure to Deadlock for Communicating Processes is Hard to Detect 

      Raeuchle, Thomas; Toueg, Sam (Cornell University, 1983-05)
      It is shown that the applicability of global state analysis as a tool for proving correctness of communication protocols is rather limited. Brand, et al. showed that reachability of global deadlock states for protocols ...
    • Failure Detection and Consensus in the Crash-Recovery Model 

      Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (Cornell University, 1998-06)
      We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable ...
    • Fault-tolerant Wait-free Shared Objects 

      Jayanti, Prasad; Chandra, D. Chandra; Toueg, Sam (Cornell University, 1996-01)
      Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the ...
    • Heartbeat: A Timeout-Free Failure Detector for Quiescent ReliableCommunication 

      Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (Cornell University, 1997-05)
      We study the problem of achieving reliable communication with quiescent algorithms (i.e., algorithms that eventually stop sending messages) in asynchronous systems with process crashes and lossy links. We first show that ...
    • Implementation Issues In Clock Synchronization 

      Beck, Micah; Srikanth, T. K.; Toueg, Sam (Cornell University, 1986-05)
      We present some results from an experimental implementation of a recent clocks synchronization algorithm. This algorithm was designed to overcome arbitrary processor failures, and to achieve optimal accuracy, i.e., the ...
    • Maintaining Availability in Partitioned Replicated Databases 

      El Abbadi, Amr; Toueg, Sam (Cornell University, 1987-08)
      In a replicated database, a data item may have copies residing on several sites. A replica control protocol is necessary to ensure that data items with several copies behave as if they consist of a single copy, as far as ...
    • A Modular Approach to Fault-Tolerant Broadcasts and Related Problems 

      Hadzilacos, Vassos; Toueg, Sam (Cornell University, 1994-05)
      NO ABSTRACT SUPPLIED
    • On Quiescent Reliable Communication 

      Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (Cornell University, 1998-06)
      We study the problem of achieving reliable communication with quiescent algorithms (i.e., algorithms that eventually stop sending messages) in asynchronous systems with process crashes and lossy links. We first show that ...
    • On the Formal Specification of Group Membership Services 

      Anceaume, Emmanuelle; Charron-Bost, Bernadette; Minet, Pascale; Toueg, Sam (Cornell University, 1995-08)
      The problem of group membership has been the focus of much theoretical and experimental work on fault-tolerant distributed systems. This has resulted in a voluminous literature and several formal specifications of ...
    • On the Impossibility of Group Membership 

      Chandra, Tushar Deepak; Hadzilacos, Vassos; Toueg, Sam; Charron-Bost, Bernadette (Cornell University, 1995-10)
      We prove that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspected ...