The Role of Inhibition in Asynchronous Consistent-Cut Protocols
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.