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

A lower bound on the period length of a distributed scheduler

  • Published:
Algorithmica Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Ad-scheduling of a graphG is a sequence of rounds, each consisting of some of the nodes of the graph, such that the distance between any two nodes participating in the same round is greater thand. Ad-scheduler is a protocol that determines ad-scheduling ofG. A 1-scheduler is applicable to process scheduling in a resource-sharing system, and to proper communication scheduling of the half-duplex model in communication networks. A 2-scheduler can be used as a collision-free protocol for radio networks.

In this paper a simpled-scheduler is analyzed. We first discuss basic properties of this scheduling, and give a complete characterization of this scheduling for trees and cycles. We study the period length of this scheduling, and the main result is a worst-case exponential lower bound for this 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+ 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. B. Awerbuch, Complexity of network synchronization,J. Assoc. Comput. Mach.,32 (1985), 804–823.

    Google Scholar 

  2. V. C. Barbosa, Concurrency in Systems with Neighborhood Constraints, Ph.D. Dissertation, Computer Science Department, University of California, Los Angeles, CA, 1986.

    Google Scholar 

  3. V. C. Barbosa and E. Gafni, Concurrency in systems with neighborhood constraints,Proc. Conf. on Distributed Computing Systems, 1987, pp. 448–455.

  4. C. T. Chou, I. Cidon, I. Gopal, and S. Zaks, Synchronizing Asynchronous Bounded Delay Networks, RC 12274, IBM T. J. Watson Research Center, Yorktown Heights, NY, October 1986.

    Google Scholar 

  5. I. Chlamtac and S. Kutten, A spatial reuse TDMA/FDMA for mobile multi-hop radio networks,INFOCOM Conf. Proc., March 1985, pp. 385–393.

  6. K. M. Chandy and J. Misra, The drinking philosophers problem,ACM Trans. Program. Languages Systems,6(4) (1984), 632–646.

    Google Scholar 

  7. I. Chlamtac and S. Pinter, Distributed nodes organization algorithm for channel access in a multiple-hop dynamic radio network,IEEE Trans. Comput.,36(6) (1987), 728–737.

    Google Scholar 

  8. I. Cidon and M. Sidi, A Distributed Assignment Algorithm for Multi-Hop Packet-Radio Networks, RC 12563 (#56508), IBM Communications/Computer Science, IBM T. J. Watson Research Center, Yorktown Heights, NY, 1987.

    Google Scholar 

  9. S. Even,Graph Algorithms, Computer Science Press, Rockville, MD, 1979.

    Google Scholar 

  10. S. Even, O. Goldreich, S. Moran, and P. Tong, On the NP-completeness of certain network testing problems,Networks,14 (1984), 1–24.

    Google Scholar 

  11. M. Golumbic,Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

    Google Scholar 

  12. E. Gafni and D. P. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology,IEEE Trans. Comm.,29(1) (1985), 11–18.

    Google Scholar 

  13. M. R. Garey and D. S. Johnson,Computers and Interactability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.

    Google Scholar 

  14. Y. Malka, S. Moran, and S. Zaks, Analysis of a Distributed Scheduler for Communication Networks, Technical Report #495, Computer Science Department, Technion-Israel Institute of Technology, Haifa, Feb. 1988. An extended abstract appeared inProc. 3rd Agean Workshop on Computing, AWOC 88, Corfu, June 1988, Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, Berlin, 1988, pp. 351–360.

    Google Scholar 

  15. Y. Malka and S. Rasjbaum, Analysis of distributed algorithms based on recurrence relations,Proc. 5th International Workshop on Distributed Algorithms (WDAG), Delphi, Greece, October 1991 (S. Toueg, P. G. Spirakis, and L. Kirousis, eds.), Lecture Notes in Computer Science, Vol. 579, Springer-Verlag, Berlin, 1991, pp. 242–253.

    Google Scholar 

  16. W. Narkiewitz and S. Kanematsu,Number Theory, World Scientific, Singapore, 1983.

    Google Scholar 

  17. A. A. Schoone and J. van Leeuwen, Simulation of Parallel Algorithms on a Distributed Network, Technical Report RUU-CS-86-1, Department of Computer Science, University of Utrecht, January 1986.

  18. A. S. Tanenbaum,Computer Networks, Prentice-Hall, Englewood Cliffs, NJ, 1981.

    Google Scholar 

Download references

Author information

Author notes

  1. Yossi Malka

    Present address: IBM Science and Technology, Matam, Haifa, Israel

Authors and Affiliations

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

    Yossi Malka, Shlomo Moran & Shmuel Zaks

Authors
  1. Yossi Malka
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shlomo Moran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shmuel Zaks
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by C. L. Liu.

The research of Shmuel Zaks was supported by the Fund for Research in Electronics, Computers, and Communications adminstered by the Israeli Academy of Sciences and Humanities.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Malka, Y., Moran, S. & Zaks, S. A lower bound on the period length of a distributed scheduler. Algorithmica 10, 383–398 (1993). https://doi.org/10.1007/BF01769705

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation