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

Noga Alon, Gil Kalai, Moty Ricklin, Larry Stockmeyer

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We prove a lower bound of Ω(log n/log log n) on the competitive ratio of any (deterministic or randomized) distributed algorithm for solving the mobile user problem introduced by Awerbuch and Peleg (1989, 1990), on certain networks of n processors. Our lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. A similar Ω(log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving the distributed scheduling problem of Awerbuch, (1992) 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)
Pages (from-to)175-201
Number of pages27
JournalTheoretical Computer Science
Volume130
Issue number1
DOIs
StatePublished - Aug 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

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