Compositional Verification of Randomized Distributed Algorithms

Author: Roberto Segala

Appears: Proceedings of Compositionality - The Significant Difference, Malente/Holstein, Germany, LNCS 1536, pages 515--540, September 1997.

Abstract: We study compositionality issues for the analysis of randomized distributed algorithms. We identify three forms of compositionality that we call process compositionality, property compositionality, and feature compositionality. Process and property compositionality are widely known in the literature, while feature compositionality, although used extensively, does not appear to be emphasized as much. We show how feature compositionality is important for the analysis of randomized systems.

Download the paper from the publisher.

Download an author-created copy of the paper (© Springer-Verlag).