Now showing items 1-8 of 8

    • 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 ...
    • 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 ...
    • 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 ...
    • 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 Weakest Failure Detector for Quiescent Reliable Communication 

      Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (Cornell University, 1997-07)
      We consider 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, and show that, ...
    • Quiescent Reliable Communication and Quiescent Consensus inPartitionable Networks 

      Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (Cornell University, 1997-06)
      We consider partitionable networks with process crashes and lossy links, and focus on the problems of reliable communication and consensus for such networks. For both problems we seek algorithms that are quiescent, i.e., ...
    • Revisiting the Weakest Failure Detector for Uniform Reliable Broadcast 

      Aguilera, Marcos Kawazoe; Toueg, Sam; Deianov, Borislav (Cornell University, 1999-04)
      Uniform Reliable Broadcast (URB) is a communication primitive that requires that if a process delivers a message, then all correct processes also deliver this message. A recent PODC paper [HR99] uses Knowledge Theory to ...
    • A Simple Bivalency Proof that t-Resilient Consensus Requires t+1 Rounds 

      Aguilera, Marcos Kawazoe; Toueg, Sam (Cornell University, 1998-09)
      We use a straightforward bivalency argument borrowed from [FLP85] to show that in a synchronous system with up to t crash failures solving consensus requires at least t+1 rounds. The proof is simpler and more intuitive ...