On the relative execution times of distributed protocols

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.