Distributed Approximation Algorithm for Resource Clustering
作者： Olivier Beaumont , Nicolas Bonichon , Philippe Duchon , Hubert Larchevêque
DOI: 10.1007/978-3-540-69355-0_7
关键词: Overlay network 、 Task (computing) 、 Scale (descriptive set theory) 、 Order (ring theory) 、 Cluster (physics) 、 Cluster analysis 、 k-medians clustering 、 Algorithm 、 Context (language use) 、 Mathematics
摘要: In this paper, we consider the clustering of resources on large scale platforms. More precisely, target parallel applications consisting independant tasks, where each task is to be processed a different cluster. context, cluster should enough so as hold and process task, maximal distance between two hosts belonging same small in order minimize latencies intra-cluster communications. This corresponds maximum bin covering with an extra constraint. We describe distributed approximation algorithm that computes resource coordinates i¾? O(log2n) steps O(nlogn) messages, nis overall number hosts. prove provides ratio $\frac{1}{3}$.
archives-ouvertes.fr
springer.com
sci-hub.st 参考文章(10)
Jehoshua Bruck, Matthew Cook, Massimo Franceschetti, A Geometric Theorem for Approximate Disk Covering Algorithms California Institute of Technology. ,(2001)
William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees workshop on algorithms and data structures. pp. 437- 449 ,(1989) , 10.1007/3-540-51542-9_36
Janos Csirik, Claire Kenyon, David S. Johnson, Better approximation algorithms for bin covering symposium on discrete algorithms. pp. 557- 566 ,(2001) , 10.5555/365411.365533
Robert Sedgewick, J. Ian Munro, Thomas Papadakis, Deterministic skip lists symposium on discrete algorithms. pp. 367- 375 ,(1992)
S.F Assmann, D.S Johnson, D.J Kleitman, J.Y.-T Leung, On a dual version of the one-dimensional bin packing problem Journal of Algorithms. ,vol. 5, pp. 502- 525 ,(1984) , 10.1016/0196-6774(84)90004-X
David P. Anderson, Jeff Cobb, Eric Korpela, Matt Lebofsky, Dan Werthimer, SETI@home: an experiment in public-resource computing Communications of The ACM. ,vol. 45, pp. 56- 61 ,(2002) , 10.1145/581571.581573
Edmond Appia, Vivaldi Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM '04. ,vol. 34, pp. 15- 26 ,(2004) , 10.1145/1015467.1015471
D.P. Anderson, BOINC: A System for Public-Resource Computing and Storage grid computing. pp. 4- 10 ,(2004) , 10.1109/GRID.2004.14
Russ Cox, Frank Dabek, Frans Kaashoek, Jinyang Li, Robert Morris, Practical, distributed network coordinates acm special interest group on data communication. ,vol. 34, pp. 113- 118 ,(2004) , 10.1145/972374.972394
James Aspnes, Gauri Shah, Skip graphs symposium on discrete algorithms. pp. 384- 393 ,(2003) , 10.5555/644108.644170