Closed schedulers: a novel technique for analyzing asynchronous protocols

Summary Analyzing distributed protocols in various models often involves a careful analysis of the set ofadmissible runs, for which the protocols should behave correctly. In particular, the admissible runs assumed by at-resilient protocol are runs which are fair for all but at mostt processors. In this paper we defineclosed sets of runs, and suggest a technique to prove impossibility results fort-resilient protocols, by restricting the corresponding sets of admissible runs to smaller sets, which are closed, as follows: For each protocolPR and for each initial configurationc, the set of admissible runs ofPR which start fromc defines a tree in a natural way: the root of the tree is the empty run, and each vertex in it denotes a finite prefix of an admissible run; a vertexu in the tree has a sonv iffv is also a prefix of an admissible run, which extendsu by one atomic step.The tree of admissible runs described above may contain infinite paths which are not admissible runs. A set of admissible runs isclosed if for every possible initial configurationc, each path in the tree of admissible runs starting fromc is also an admissible run. Closed sets of runs have the simple combinatorial structure of the set of paths of an infinite tree, which makes them easier to analyze. We introduce a unified method for constructing closed sets of admissible runs by using a model-independent construction of closedschedulers, and then mapping these schedulers to closed sets of runs. We use this construction to provide a unified proof of impossibility of consensus protocols.Ronit Lubitch received her B.Sc. degree in Mathematics and Computer Science from Tel Aviv University in 1989, and her Master degree in Computer Science from the Technion, in 1993. From 1992 she is working in Graffiti Software Industries, which expertise in the design and development of advanced photo realistic rendering, and animation software systems.Shlomo Moran received his B.Sc. and Ph.D. degrees in Mathematics from the Technion in 1975 and 1979 resp. In 1979–1981 he was at the University of Minnesota as a visiting research specialist. In 1981 he joined the Computer Science Department at the Technion, where he is now a full professor. In 1985–1986 he visited at IBM T.J. Watson Research Center. In 1992–1993 he visited at AT&T Bell Laboratories and in Centrum voor Wiskunde en Informatica, Amsterdam. His research interests include distributed computing, Combinatorics and Graph Theory, and Complexity Theory.A preliminary extended version of this paper appeared in the Proceedings of 6-th International Workshop on Distributed Algorithms, Haifa, November 1992This work was supported in part by the Technion V.P.R. fund. Part of this research was conducted while this author was visiting at AT&T Bell Labs at Murray Hill and at CWI, Amsterdam