TY - JOUR
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
N1 - Funding Information:
Correspondence to: L. Stockmeyer, IBM Research Division, Almaden Research Center, 650 Harry Road, San Jose, CA 95120, USA. Email: [email protected]. *A preliminary version of this paper appeared in: Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science (1992) 334-343. **Research supported in part by a United States Israeli BSF grant. Work performed in part while visiting Bellcore, Morristown, NJ. ***Work performed in part while visiting the IBM Almaden Research Center, San Jose. CA.
PY - 1994/8/1
Y1 - 1994/8/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0028484183&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028484183&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(94)90158-9
DO - 10.1016/0304-3975(94)90158-9
M3 - Article
AN - SCOPUS:0028484183
SN - 0304-3975
VL - 130
SP - 175
EP - 201
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -