### 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 language | English (US) |
---|---|

Pages (from-to) | 175-201 |

Number of pages | 27 |

Journal | Theoretical Computer Science |

Volume | 130 |

Issue number | 1 |

DOIs | |

State | Published - Aug 1 1994 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- 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

*Theoretical Computer Science*,

*130*(1), 175-201. https://doi.org/10.1016/0304-3975(94)90158-9