SONDe, a Self-Organizing Object Deployment Algorithm in Large-Scale Dynamic Systems
作者： Vincent Gramoli , Anne-Marie Kermarrec , Erwan Le Merrer , Didier Neveux
关键词:
摘要: We present the design, correctness, and analysis of SONDe, a simple fully decentralized object deployment algorithm for highly requested systems. Given an (service or data), SONDe provides node with constant upper bound (h) on number logical hops to access holder (provider), thus making tunable predictable communication latency between any provider. In addition, is able dynamically adapt providers reflect load variations experienced in localized portions system. Each individually decides be provider, based observation its h-hops neighborhood. show theoretically that self-stabilizes independent-dominating set providers. Finally simulation results, conducted over different network topologies, demonstrate efficiency approach confirm theoretical analysis.
sydney.edu.au 
sci-hub.se 参考文章(21)
Paola Alimonti, Tiziana Calamoneri, Improved Approximations of Independent Dominating Set in Bounded Degree Graphs workshop on graph theoretic concepts in computer science. pp. 2- 16 ,(1996) , 10.1007/3-540-62559-3_2
Paola Alimonti, Non-oblivious Local Search for MAX 2-CCSP with Application to MAX DICUT workshop on graph theoretic concepts in computer science. pp. 2- 14 ,(1997) , 10.1007/BFB0024483
Kang Shin, Hani Jamjoom, Sugih Jamin, Self-Organizing Network Services ,(1999)
Chunlin Yang, Jie Wu, Dominating-Set-Based Searching in Peer-to-Peer Networks Grid and Cooperative Computing. pp. 332- 339 ,(2004) , 10.1007/978-3-540-24679-4_67
Ted Herman, Sébastien Tixeuil, A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks Algorithmic Aspects of Wireless Sensor Networks. pp. 45- 58 ,(2004) , 10.1007/978-3-540-27820-7_6
Erwan Le Merrer, Vincent Gramoli, Anne-Marie Kermarrec, Aline C. Viana, Marin Bertier, Energy aware self-organizing density management in wireless sensor networks international workshop on decentralized resource sharing in mobile computing and networking. pp. 24- 29 ,(2006) , 10.1145/1161252.1161259
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker, Search and replication in unstructured peer-to-peer networks international conference on supercomputing. pp. 84- 95 ,(2002) , 10.1145/2591635.2667182
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Torsten Suel, Rajmohan Rajaraman, Lujun Jia, An efficient distributed algorithm for constructing small dominating sets Distributed Computing. ,vol. 15, pp. 193- 205 ,(2002) , 10.1017/S00446-002-0078-0
Réka Albert, Albert-László Barabási, Statistical mechanics of complex networks Reviews of Modern Physics. ,vol. 74, pp. 47- 97 ,(2001) , 10.1103/REVMODPHYS.74.47