Strong stable properties in distributed systems

Summary A stable property in a distributed system is a global property which once true, remains true forever. This paper refines this notion by formally introducing the concept ofstrong stable properties. A strong stable property has the nice property that it can be correctly evaluated on the consistent part of uncoordinated snapshots. Termination and deadlock are shown to be strong stable properties, whereas distributed garbage is not. We also show how to derive a simple generic algorithm for the detection of a strong stable property. The generic algorithm is illustrated by two examples: termination detection and deadlock detection. Incidentally the paper presents a very simple algorithm for termination detection. Andre Schiper has been a professor of Computer Science at EPFL (Federal Institute of Technology in Lausanne, Switzerland) since 1985, leading the Operating Systems laboratory. He graduated in Physics from the Federal Institute of technology in Zürich and received his Ph.D. in Computer Science from EPFL in 1980. In 1981–82 he spent one year at the University of Rennes, France. From 1983 to 1985, he was professor at the Engineering School in Yverdon, Switzerland. Between 1989 and 1991 André Schiper was head of the Department of Computer Science of EPFL, and during the academic year 1992–93 he was on sabbatical leave at Cornell University, Ithaca (NY). His research interests are in the areas of operating systems, distributed and fault-tolerant distributed systems, and parallelism. He is currently involved in the European Esprit project BROADCAST whose objective is the design and implementation of large scale distributed computing systems. Alain Sandoz graduated in Mathematics from the University of Neuchâtel, Switzerland, in 1984 and in Computer Science from the Federal Institute of Technology in Lausanne, Switzerland, in 1988. He received his Ph.D. in Computer Science from the Federal Institute of Technology in Lausanne in 1992. His dissertation was concerned with modelling causal relationships between transactions in distributed and replicated database systems. From 1992 to 1994 he was involved in research on fault-tolerant and large scale distributed computing systems. He is currently working on the development of information systems for the Swiss government.