摘要: A weighted undirected network is Δ growth-bounded if the number of nodes at distance 2r around any given node most times r node. Given a with arbitrary names and e > 0, we present routing scheme that routes along paths stretch 1+e uses high probability only O(1/eO (log Δ)log5n) bit tables per
acm.org
sci-hub.se 参考文章(35)
Pierre Fraigniaud, Cyril Gavoille, A Space Lower Bound for Routing in Trees symposium on theoretical aspects of computer science. pp. 65- 75 ,(2002) , 10.1007/3-540-45841-7_4
David Peleg, Distributed Computing: A Locality-Sensitive Approach ,(1987)
Pierre Fraigniaud, Cyril Gavoille, Routing in Trees international colloquium on automata languages and programming. pp. 757- 772 ,(2001) , 10.1007/3-540-48224-5_62
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, None, Routing with improved communication-space trade-off international symposium on distributed computing. pp. 305- 319 ,(2004) , 10.1007/978-3-540-30186-8_22
John Kubiatowicz, Satish Rao, Sean Ma, Kirsten Hildrum, A note on the nearest neighbor in growth-restricted metrics symposium on discrete algorithms. pp. 560- 561 ,(2004) , 10.5555/982792.982874
Sariel Har-Peled, Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications symposium on computational geometry. pp. 150- 158 ,(2005) , 10.1145/1064092.1064117
C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment acm symposium on parallel algorithms and architectures. pp. 311- 320 ,(1997) , 10.1145/258492.258523
Kofi A. Laing, Brief announcement Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04. pp. 382- 382 ,(2004) , 10.1145/1011767.1011841
Baruch Awerbuch, David Peleg, Routing with Polynomial Communication-Space Srade-ff SIAM Journal on Discrete Mathematics. ,vol. 5, pp. 151- 162 ,(1992) , 10.1137/0405013
Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg, Improved routing strategies with succinct tables Journal of Algorithms. ,vol. 11, pp. 307- 341 ,(1990) , 10.1016/0196-6774(90)90017-9