We consider the problem of distinguishing causally-consistent global states in
asynchronous distributed systems. Such states are fundamental to asynchronous systems,
because they correspond to possible simultaneous global states; their detection arises
in a variety of distributed applications, including global checkpointing, deadlock
detection, termination detection, and broadcasting. A consistent-cut protocol is a
protocol which in every run will designate for each processor a state, in such a way
that these states together form a consistent cut. We analyze the cost of achieving
causal consistency in terms of the extent to which a consistent-cut protocol delays
events of the underlying system. We refer to the delaying action of a protocol as
inhibition. A protocol using local inhibition may cause the delay of some of a
processor's events until that processor has performed some number of local actions; a
protocol using global inhibition may force the delay of some of a processor's events
until that processor has received some communication from other processors. Based on a
variety of system and protocol characteristics, including the ability to locally or
globally inhibit particular types of events, we give three impossibility results and
examine some existing protocols. We are then able to present a thirty-six case summary
of protocols and impossibility results for the determination of causally-consistent
states as a function of those characteristics. In particular, we demonstrate that local
inhibition is necessary and sufficient to solve this problem for general FIFO systems,
while global send inhibition is necessary and sufficient for general non-FIFO systems.