Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling

Noga Alon, Gil Kalai, Moty Ricklin, Larry Stockmeyer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

The authors prove a lower bound of Omega (log n/log log n) on the competitive ratio of any (deterministic or randomised) distributed algorithm for solving the mobile user problem on certain networks of n processors. The lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. A similar Omega (log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving a distributed scheduling problem on any of these networks. The proofs combine combinatorial techniques with tools from linear algebra and harmonic analysis and apply, in particular, a generalization of the vertex isoperimetric problem on the hypercube, which may be of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages334-343
Number of pages10
ISBN (Electronic)0818629002
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
CountryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Kalai, G., Ricklin, M., & Stockmeyer, L. (1992). Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. In Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 (pp. 334-343). [267757] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267757