Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Quiescent Reliable Communication and Quiescent Consensus inPartitionable Networks
Authors: Aguilera, Marcos Kawazoe
Chen, Wei
Toueg, Sam
Keywords: computer science
technical report
Issue Date: Jun-1997
Publisher: Cornell University
Abstract: 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., algorithms that eventually stop sending messages. We first tackle the problem of reliable communication for partitionable networks by extending the results of [ACT97a]. In particular, we generalize the specification of the heartbeat failure detector HB, show how to implement it, and show how to use it to achieve quiescent reliable communication. We then turn our attention to the problem of consensus for partitionable networks. We first show that, even though this problem can be solved using a natural extension of less than or greater than S, such solutions are not quiescent --- in other words, less than or greater than S alone is not sufficient to achieve quiescent consensus in partitionable networks. We then solve this problem using less than or greater than S and the quiescent reliable communication primitives that we developed in the first part of the paper. Our model of failure detectors for partitionable networks, a natural extension of the model in [CT96], is also a contribution of this paper.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
97-1632.pdf316.21 kBAdobe PDFView/Open
97-1632.ps237.6 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us