In: Proc. of 22nd ACM Symp. on the Theory of Computation (STOC), pages 95-105. 1990.
Abstract: The behavior of a network controlled by a simple synchronizer is analyzed. This synchronizer is an abstraction of an arbitrary synchronizer, of a marked graph, and of several other distributed algorithms. It is assumed that transmission delays are constant, and tight bounds on the rate ofcomputation are derived. It is shown that the full rate of computation is reached within a polynomial number of steps