TY - GEN

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

AU - Alon, Noga

AU - Kalai, Gil

AU - Ricklin, Moty

AU - Stockmeyer, Larry

PY - 1992/1/1

Y1 - 1992/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84971761241&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84971761241&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267757

DO - 10.1109/SFCS.1992.267757

M3 - Conference contribution

AN - SCOPUS:84971761241

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 334

EP - 343

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

Y2 - 24 October 1992 through 27 October 1992

ER -