[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Efficiency of semisynchronous versus asynchronous networks

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Thes-session problem is studied inasynchronous andsemisynchronous networks. Processes are located at the nodes of an undirected graphG and communicate by sending messages along links that correspond to the edges ofG. A session is a part of an execution in which each process takes at least one step; an algorithm for thes-session problem guarantees the existence of at leasts disjoint sessions. The existence of many sessions guarantees a degree of interleaving which is necessary for certain computations. It is assumed that the (real) time for message delivery is at mostd. In the asynchronous model it is assumed that the time between any two consecutive steps of any process is in the interval [0, 1]; in the semisynchronous model the time between any two consecutive steps of any process is in the interval [c, 1] for somec such that 0 <c ≤ 1,the synchronous model being the special case wherec = 1. All processes are initially synchronized and take a step at time 0.

For the asynchronous model, an upper bound ofdiam(G)(d + l)(s − 1) and a lower bound ofdiam(G)d(s − 1) are presented;diam(G) is thediameter ofG. For the semisynchronous model, an upper bound of 1 + min{⌊1/c⌋ + 1,diam(G)(d + 1)}(s − 2) is presented. The main result of the paper is a lower bound of 1 + min{⌊1/2c⌋,diam(G)d}(s − 2) for the time complexity of any semisynchronous algorithm for thes-session problem, under the assumption thatd ≥ (d/min{⌊1/2c⌋, diam(G)d}) + 2. These results imply a time separation between semisynchronous (in particular, synchronous) and asynchronous networks. Similar results are proved for the case where delays are not uniform.

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+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Arjomandi, M. Fischer, and N. Lynch, Efficiency of Synchronous versus Asynchronous Distributed Systems,Journal of the Association for Computing Machinery, Vol. 30, No. 3 (1983), pp. 449–456.

    Google Scholar 

  2. H. Attiya, C. Dwork, N. Lynch, and L. Stockmeyer, Bounds on the Time To Reach Agreement in the Presence of Timing Uncertainty,Journal of the Association for Computing Machinery, Vol. 14, No. 1 (1994), pp. 122–152.

    Google Scholar 

  3. H. Attiya and N. Lynch, Time Bounds for Real-Time Process Control in the Presence of Timing Uncertainty,Information and Computation, Vol. 110, No. 1 (1994), pp. 183–232.

    Google Scholar 

  4. B. Awerbuch, Complexity of Network Synchronization,Journal of the Association for Computing Machinery, Vol. 32, No. 4 (1985), pp. 804–823.

    Google Scholar 

  5. G. M. Baudet, Asynchronous Iterative Methods for Multi-Processors,Journal of the Association for Computing Machinery, Vol. 25, No. 2 (1978), pp. 226–244.

    Google Scholar 

  6. N. Lynch, Asynchronous versus Synchronous Computation (guest lecture), Lecture Notes for MIT 18.438: Network Protocols and Distributed Graph Algorithms, Spring 1989.

  7. N. Lynch and H. Attiya, Using Mappings To Prove Timing Properties,Distributed Computing, Vol. 6, No. 2 (1992), pp. 121–139.

    Google Scholar 

  8. M. Mavronicolas, Efficiency of Semi-Synchronous versus Asynchronous Systems: Atomic Shared Memory,Computers and Mathematics with Applications, to appear. Also: Technical Report TR-03-92. Aiken Computation Laboratory, Harvard University, January 1992.

  9. M. Mavronicolas, Timing-Based Distribution Computation: Algorithms and Impossibility Results, Ph.D. Thesis, Harvard University, 1992. Also: Technical Report TR-13-92, Aiken Computation Laboratory, Harvard University, July 1992.

  10. M. Merritt, F. Modugno, and M. Tuttle, Time Constrained Automata,Proceedings of the 2nd International Conference on Concurrency, pp. 408–423, Lecture Notes in Computer Science, Vol. 527, Springer-Verlag, Berlin, 1991.

    Google Scholar 

  11. G. Peterson and M. Fischer, Economical Solutions for the Critical Section Problem in a Distributed System,Proceedings of the 9th Association for Computer Machinery Symposium on Theory of Computing, pp. 91–97, 1977.

  12. I. Rhee and J. L. Welch, The Impact of Time on the Session Problem,Proceedings of the 11th Annual Association for Computing Machinery Symposium on Principles of Distributed Computing, pp. 191–202, August 1992.

  13. A. Segall, Distributed Network Protocols,IEEE Transactions on Information Theory, Vol. 29, No. 1 (1983), pp. 23–35.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The Technion, 32000, Haifa, Israel

    H. Attiya

  2. Aiken Computation Laboratory, Harvard University, 02138, Cambridge, MA, USA

    M. Mavronicolas

Authors
  1. H. Attiya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Mavronicolas
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

A preliminary version of this paper appeared in theProceedings of the 28th Annual Allerton Conference on Communication, Control, and Computing, October 1990, pp. 578–587. H. Attiya was partially supported by B. and G. Greenberg Research Fund (Ottawa) and by Techion V.P.R. funds. Part of this work was performed when she was at the Laboratory for Computer Science, MIT, supported by ONR Contract N00014-85-K-0168, by NSF Grant CCR-8915206, and by DARPA Contract N00014-87-K-0825. M. Mavronicolas was supported by ONR Contract N00014-91-J-1981. His current address is: Department of Computer Science, University of Cyprus, Cyprus, and Institute of Computer Science, Foundation of Research and Technology, Hellas, Greece.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Attiya, H., Mavronicolas, M. Efficiency of semisynchronous versus asynchronous networks. Math. Systems Theory 27, 547–571 (1994). https://doi.org/10.1007/BF01191625

Download citation

  • Received:

  • Accepted:

  • Issue Date:

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

Keywords

Search

Navigation