Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. The Role of Inhibition in Asynchronous Consistent-Cut Protocols

The Role of Inhibition in Asynchronous Consistent-Cut Protocols

File(s)
89-995.ps (389.89 KB)
89-995.pdf (1.67 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6911
Collections
Computer Science Technical Reports
Author
Taylor, Kimberly E.
Abstract

We present results relevant to the development of consistent-cut protocols. Consistent-cut protocols are those which are based on finding a consistent global state in an underlying distributed computation; they are used for a variety of applications such as system checkpointing and deadlock detection. We formally define what it means for a protocol to be non-inhibitory, which intuitively means that it does not prevent any actions from occurring in an underlying system computation. We prove that there is no non-inhibitory consistent-cut protocols for FIFO systems of one message per bidirectional channel (up to $\frac {1}{2} (n^{2} - n$, for completely connected networks). We present two protocols, one non-inhibitory requiring up to two messages between each pair of neighboring nodes in a network and the other inhibitory and requiring only $3(n - 1)$ messages total. In most networks, these results illustrate a tradeoff between the amount of necessary communication and the willingness to inhibit actions of the underlying system. Additionally, our inhibitory protocol also works for non-FIFO systems, thus illustrating that the inhibitory condition is exactly what is required to develop consistent-cut protocols for non-FIFO systems which satisfy our model.

Date Issued
1989-04
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-995
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance