On the relative execution times of distributed protocols

Gurdip Singh, Arthur J. Bernstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A formalism for comparing the average execution time of distributed protocols is provided. The comparisons are made independently of the properties of the network on which the protocols are executed. The formalism takes into account computation time, the time to transfer information, the time spent by a site waiting to synchronize with other sites, and the overlap among them. A framework in which the information transfer and synchronization requirements of a protocol are separately and explicitly specified is developed. A knowledge formalism is used to specify the protocol's specification requirements. Transformations on protocols which may change the synchronization structure, the information transferred, or the amount of local computation are defined. It is shown that, if a sequence of such transformations can be applied to a protocol to obtain another protocol, the final protocol runs at least as fast as the initial. Two notions of comparison, containment and reducibility, are given, and their properties are explored. Several protocols, including those for atomic commitment and snapshot recording, are analyzed to illustrate the technique.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference on Distributed Computing Systems
PublisherIEEE Computer Society
Pages80-87
Number of pages8
StatePublished - 1990
Externally publishedYes
EventProceedings of the 10th International Conference on Distributed Computing Systems - ICDCS-10 - Paris, Fr
Duration: May 28 1990Jun 1 1990

Other

OtherProceedings of the 10th International Conference on Distributed Computing Systems - ICDCS-10
CityParis, Fr
Period5/28/906/1/90

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On the relative execution times of distributed protocols'. Together they form a unique fingerprint.

  • Cite this

    Singh, G., & Bernstein, A. J. (1990). On the relative execution times of distributed protocols. In Proceedings - International Conference on Distributed Computing Systems (pp. 80-87). IEEE Computer Society.