On the relative execution times of distributed protocols

Gurdip Singh, Arthur J. Bernstein

Research output: Contribution to journalArticlepeer-review


We provide a formalism for comparing the average execution time of distributed protocols in a manner independent 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 and the overlap among them. We define transformations on protocols which may change the synchronization structure, the information transferred or the amount of local computation. We show that if a sequence of such transformations can be applied to a protocol to obtain another protocol, then the final protocol runs at least as fast as the initial protocol. Different sets of tranformations give rise to different notions of comparison. We develop two such notions and explore their properties. We also give results which relate our notion of protocol transformation to transformational techniques for protocol design.

Original languageEnglish (US)
Pages (from-to)203-235
Number of pages33
JournalInternational Journal of Parallel Programming
Issue number3
StatePublished - Jun 1991
Externally publishedYes


  • Distributed protocol
  • execution time
  • knowledge logic
  • partial order
  • synchronization structure

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems


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

Cite this