Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)
Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer · Foundations of Computer Science · 1992
We prove a lower bound of R(logra/loglogn) on the competitive ratio of any (deterministic or randomized) distributed algorithm for solving the mobile user problem introduced by Awerbuch and Peleg [AP], 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 R(1og n/ loglogn) 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, Kutten and Peleg [AKP] 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.