In: Lecture Notes in Computer Science, Vol. 579, pages 242-253. Springer-Verlag, 1991.
Abstract: This paper identifies a class of distributed algorithms described by a form of recurrence relations, and studies some of its properties. Examples of algorithms that can be represented by recurrence relations are marked graphs, schedulers, various synchronizers and clock synchronization algorithms. It is assumed that transmission delays are constant, and tight bounds on the rate of computation are derived. It is shown that the full rate of computation is reached within a polynomial number of steps