Shared Global States in Distributed Computations

摘要

A consistent observation of a given distributed computation is a sequence of global states that could be produced by executing that computation on a monoprocessor system. Therefore a distributed execution generally accepts several consistent observations. This paper investigates global states shared by all such observations. A necessary and sufficient condition characterizing these states is first given. Then, an algorithm that computes shared global states is described.