Skip to main content
Springer Nature Link
Log in

The use of a synchronizer yields the maximum computation rate in distributed networks

  • Published:
Save article
View saved research
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We study the performance of networks whose operation is controlled by a simple synchronizer. In a previous paper we analyzed the performance of networks with negligible transmission delay. It was shown that full speed is achieved, for any wake-up pattern, by letting the network run free, without the use of a “firing-squad” mechanism or a scheduler.

In this paper we investigate the effect of fixed delays in the communication channels on the performance of a network in which there is a global clock, but there is no global start-up signal. We show that here, too, the maximum rate of computation is always reached, just by using the synchronizer and letting the network run free. To a certain extent, the wake-up pattern may influence the length of the transitory stage and the periodicity of the steady state, but not the ultimate rate. In any case, the length of the transitory stage is bounded polynomially, and the bound is tight, while the period may be of exponential length.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Netherlands)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. B. Awerbuch, Complexity of Network Synchronization,J. Assoc. Comput. Mach., Vol. 32, No. 4, Oct. 1985, pp. 804–823.

    Article  MathSciNet  MATH  Google Scholar 

  2. B. Awerbuch, Reducing Complexities of Distributed Maximum Flow and Breadth-First Search Algorithms by Means of Network Synchronization,Networks, Vol. 15, No. 4, Winter 1985, pp. 425–437.

    Article  MathSciNet  MATH  Google Scholar 

  3. B. Awerbuch, M. Sipser, Dynamic Networks are as Fast as Static Networks, inProc. 29th IEEE Symp. on Foundations of Computer Science, Oct. 1988, pp. 206–220.

  4. A. Brauer, On a Problem of Partitions,Amer. J. Math., Vol. 64, 1942, pp. 299–312.

    Article  MathSciNet  MATH  Google Scholar 

  5. V.C. Barbosa, E. Gafni, Concurrency in Heavily Loaded Neighborhood-Constrained Systems,ACM Trans. Programming Languages and Systems, Vol. 11, No. 4, Oct. 1989, pp. 562–584.

    Article  Google Scholar 

  6. C.T. Chou, I.S. Gopal, S. Zaks, Synchronizing Asynchronous Bounded-Delay Networks, Research Report RC-12274, IBM, Yorktown Heights, NY, Oct. 1986.

    Google Scholar 

  7. F. Commoner, A.W. Holt, S. Even, A. Pnueli, Marked Directed Graphs,J. Comput. System Sci., Vol. 5, No. 5, Oct. 1971, pp. 511–523.

    Article  MathSciNet  MATH  Google Scholar 

  8. K.M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems,ACM Trans. Comput. Systems, Vol. 3, No. 1, Feb. 1985, pp. 63–75.

    Article  Google Scholar 

  9. S. Even, S. Rajsbaum, Unison, Canon, and Sluggish Clocks in Networks Controlled by a Synchronizer,Math. Systems Theory, Vol. 28, No. 5, 1995, pp. 421–435.

    Article  MathSciNet  MATH  Google Scholar 

  10. A. Fekete, N. Lynch, L. Shrira, A Modular Proof of Correctness for a Network Synchronizer,Proc. 2nd Workshop on Distributed Algorithms, CWI, July 1987, pp. 219–256.

  11. H.J. Genrich,Einfache Nicht-Sequentielle Prozesse, Gesellschaft fur Mathematik und Datenverarbeitung, Birlinghoven, 1970.

    Google Scholar 

  12. G.H. Hardy, E.M. Wright,An Introduction to the Theory of Numbers, 4th edn., 1968, Oxford University Press, Oxford.

    Google Scholar 

  13. R.M. Karp, A Characterization of the Minimum Cycle Mean in a Digraph,Discrete Math., Vol. 23, 1978, pp. 309–311.

    MathSciNet  MATH  Google Scholar 

  14. E.F. Moore, The Firing Squad Synchronization Problem, inSequential Machines, Selected Papers, Addison-Wesley, Reading, MA, 1964, pp. 213–214.

    Google Scholar 

  15. Y. Malka, S. Moran, S. Zaks, A Lower Bound on the Period Length of a Distributed Scheduler,Algorithmica, Vol. 10, 1994, pp. 383–398.

    Article  MathSciNet  Google Scholar 

  16. Y. Malka, S. Rajsbaum, Analysis of Distributed Algorithms Based on Recurrence Relations, inProc. 5th Internat. Workshop on Distributed Algorithms, Delphi, Oct. 7–9, S. Toueget al. (eds.), LNCS, Vol. 579, Springer-Verlag, Berlin, 1991, pp. 242–253.

    Google Scholar 

  17. D. Peleg, J. Ullman, An Optimal Synchronizer for the Hypercube,SIAM J. Comput., Vol. 18, No. 2, 1989, pp. 740–747.

    Article  MathSciNet  MATH  Google Scholar 

  18. R. Reiter, Scheduling Parallel Computations,J. Assoc. Comput. Mach., Vol. 15, No. 4, Oct. 1968, pp. 590–599.

    Article  MATH  Google Scholar 

  19. S. Rajsbaum, M. Sidi, On the Performance of Synchronized Programs in Distributed Networks with Random Processing Times and Transmission Delays,IEEE Trans. Parallel Distrib. Systems, Vol. 5, No. 9, Sept. 1994, pp. 939–950.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Technion, Israel Institute of Technology, 32000, Haifa, Israel

    S. Even & S. Rajsbaum

Authors
  1. S. Even
    View author publications

    Search author on:PubMed Google Scholar

  2. S. Rajsbaum
    View author publications

    Search author on:PubMed Google Scholar

Additional information

An extended abstract of this paper appeared in STOC ’90. Part of this work was done while the authors visited the Computer Science Program, University of Texas at Dallas, Richardson, TX, USA. The first author is now visiting Bell Laboratories, Lucent Technologies, Murray Hill, NJ, USA, and was supported by the Fund for the Promotion of Research at the Technion. The second author’s current address is Instituto de Matematicas — U.N.A.M., Ciudad Universitaria, D.F. 04510, Mexico. rajsbaum@servidor.unam.mx

Rights and permissions

Reprints and permissions

About this article

Cite this article

Even, S., Rajsbaum, S. The use of a synchronizer yields the maximum computation rate in distributed networks. Theory of Computing Systems 30, 447–474 (1997). https://doi.org/10.1007/BF02679457

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/BF02679457

Keywords