Consistent global states of distributed systems: Fundamental concepts and mechanisms

Distributed systems that span large geographic distances or interconnect large numbers of components are adequately modeled as asynchronous systems. Given the uncertainties in such systems that arise from communication delays and relative speeds of computations, reasoning about global states has to be carried out using local, and often, imperfect information. In this paper, we consider global predicate evaluation as a canonical problem in order to survey concepts and mechanisms that are useful in coping with uncertainty in distributed computations. We illustrate the utility of the developed techniques by examining distributed deadlock detection and distributed debugging as two instances of global predicate evaluation.