Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
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. © 1994.
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006