More Web Proxy on the site http://driver.im/

article

A lower bound on the period length of a distributed scheduler

Authors:

Shmuel ZaksAuthors Info & Claims

Algorithmica, Volume 10, Issue 5

Pages 383 - 398

https://doi.org/10.1007/BF01769705

Published: 01 November 1993 Publication History

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.

References

[1]

B. Awerbuch, Complexity of network synchronization, J. Assoc. Comput. Mach., 32 (1985), 804-823.

Digital Library

[2]

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

[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.

[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.

Digital Library

[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.

Digital Library

[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.

[9]

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

[10]

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

[11]

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

[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.

[13]

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

[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 in Proc. 3rd Agean Workshop on Computing, AWOC 88, Corfu, June 1988, Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, Berlin, 1988, pp. 351-360.

[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.

[16]

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

[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.

Cited By

Charron-Bost BFügger MWelch JWidder J(2015)Time Complexity of Link Reversal RoutingACM Transactions on Algorithms10.1145/264481511:3(1-39)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2644815
Charron-Bost BFügger MWelch JWidder J(2011)Full reversal routing as a linear dynamical systemProceedings of the 18th international conference on Structural information and communication complexity10.5555/2032229.2032243(101-112)Online publication date: 26-Jun-2011
https://dl.acm.org/doi/10.5555/2032229.2032243
Charron-Bost BGaillard AWelch JWidder JMeyer auf der Heide FBender M(2009)Routing without orderingProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584034(145-153)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584034
Show More Cited By

A lower bound on the period length of a distributed scheduler
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

The Impact of Critical Sporadic Jobs on Gang Scheduling Performance in Distributed Systems

A commonly used task scheduling algorithm for parallel and distributed systems is gang scheduling. In this paper, we study gang scheduling performance in the presence of critical sporadic jobs. A simulation model is used to ...
A lower bound for the job insertion problem

This note deals with the job insertion problem in job-shop scheduling: Given a feasible schedule of n jobs and a new job which is not scheduled, the problem is to find a feasible insertion of the new job into the schedule which minimises the makespan. ...
Using schedulers to test probabilistic distributed systems
Abstract
Formal methods are one of the most important approaches to increasing the confidence in the correctness of software systems. A formal specification can be used as an oracle in testing since one can determine whether an observed behaviour is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 10, Issue 5

November 1993

75 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 1993 Springer-Verlag New York Inc.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 1993

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Charron-Bost BFügger MWelch JWidder J(2015)Time Complexity of Link Reversal RoutingACM Transactions on Algorithms10.1145/264481511:3(1-39)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2644815
Charron-Bost BFügger MWelch JWidder J(2011)Full reversal routing as a linear dynamical systemProceedings of the 18th international conference on Structural information and communication complexity10.5555/2032229.2032243(101-112)Online publication date: 26-Jun-2011
https://dl.acm.org/doi/10.5555/2032229.2032243
Charron-Bost BGaillard AWelch JWidder JMeyer auf der Heide FBender M(2009)Routing without orderingProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584034(145-153)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584034
Yeh HZhu X(2005)Resource-sharing system scheduling and circular chromatic numberTheoretical Computer Science10.1016/j.tcs.2004.12.005332:1-3(447-460)Online publication date: 28-Feb-2005
https://dl.acm.org/doi/10.1016/j.tcs.2004.12.005

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents