In: Desel, J.: Structures in Concurrency Theory, Proceedings of the International Workshop on Structures in Concurrency Theory (STRICT), Berlin, 11-13 May 1995, pages 175-189. 1995.
Abstract: A fundamental problem in debugging and monitoring distributed computations is to detect whether a state of the system satisfies some predicate. Cooper and Marzullo defined this problem as Possibly(F). This paper presents the first on-line algorithm using linear space which solves this problem in the general case, improving all existing algorithms both in time and space. It is particularly interesting for the detection of Possibly(F) on potentially infinite computations. To our knowledge, it is also he only algorithm of detection which do not use vectors of timestamps. The presented algorithm is based on structural properties of the consistent cuts lattice, leading to a new structure which seems promising for the study distributed computations: the consistent cuts tree.