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

An algorithm and two lower bounds are presented for the problem of constructing and maintaining routing schemes in dynamic networks. The algorithm distributively assigns addresses to nodes and constructs routing tables in a dynamically growing tree. The resulting scheme routes data messages over the shortest path between any source and destination, assigns addresses of O(log/sup 2/n) bits to each node, and uses in its routing table O(log/sup 3/n) bits of memory per incident link, where n is the final number of nodes in the tree. The amortized communication cost of the algorithm is O(log n) messages per node. Also given are two lower bounds on the tradeoff between the quality of routing schemes (i.e. their stretch factor) and their amortized communication cost in general dynamic networks.>