Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
复制标题
移动用户跟踪和分布式作业调度的竞争比下限
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
L. Stockmeyer
中科院分区：
文献类型：
--
作者：
N. Alon;G. Kalai;Moty Ricklin;L. Stockmeyer
作者证明了Omega（log n/log log n）的下限在任何（确定性或随机）分布式算法的竞争比率上，用于在n个处理器的某些网络上求解移动用户问题。下边界的各种网络（包括HyperCube，任何具有足够大的围栏的网络以及任何高度扩展的图形）的下限。对于任何分布式算法的最大作业延迟，用于解决这些网络中的任何分布式算法的最大作业延迟的竞争比率证明了类似的欧米茄（日志N/日志N）下限。这些证明将组合技术与线性代数的工具和谐波分析和谐波分析的工具结合在一起，特别是应用于超顺序上的顶点等法问题的概括，这可能具有独立的兴趣。<< etx >>
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.<<ETX>>