{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:55:14Z","timestamp":1761807314574},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>Random walk is a means of network node sampling that requires little index maintenance and can function on almost all connected network topologies. With careful guidance, node samples following a desired probability distribution can be generated with the only requirement that the sampling probabilities of each visited node and its direct neighbors are known at each walk step. This paper describes a broad range of network applications that can benefit from such guided random walks in dynamic and decentralized settings. This paper also examines several key issues for implementing random walks in self-organizing networks, including the convergence time of random walks, impact of dynamic network changes and particularly resulted walker losses, and the difficulty of pacing walk steps without synchronized clocks between network nodes. Our result suggests that with proper management, these issues do not cause significant problems under many realistic network environments.<\/jats:p>","DOI":"10.1145\/1151374.1151386","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T22:35:32Z","timestamp":1161210932000},"page":"49-55","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Random walk based node sampling in self-organizing networks"],"prefix":"10.1145","volume":"40","author":[{"given":"Ming","family":"Zhong","sequence":"first","affiliation":[{"name":"University of Rochester"}]},{"given":"Kai","family":"Shen","sequence":"additional","affiliation":[{"name":"University of Rochester"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","author":"Adamic L.","year":"2001","journal-title":"Search in Power Law Networks. Physical Review, (64):46135--46143"},{"key":"e_1_2_1_2_1","first-page":"509","volume":"286","author":"Barab\u00e1si A.","year":"1999","journal-title":"Emergence of Scaling in Random Networks. Science"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015507"},{"key":"e_1_2_1_4_1","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press London UK 1985.  B. Bollob\u00e1s. Random Graphs. Academic Press London UK 1985."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633043"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_15"},{"key":"e_1_2_1_9_1","first-page":"77","article-title":"Expos\u00e9 de la th\u00e9orie des cha\u00eenes simples constantes de Markov \u00e1 un nombre fini d'\u00e9tats","volume":"2","author":"Doeblin W.","year":"1938","journal-title":"Math\u00e9matique de l'Union Interbalkanique"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354487"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498436"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007919"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380796"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1251460.1251479"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863999"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/514191.514206"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946323"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_24_1","unstructured":"D. Randall. Mixing. A Tutorial in the IEEE FOCS 2003.   D. Randall. Mixing. A Tutorial in the IEEE FOCS 2003."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_26_1","first-page":"329","volume-title":"Distributed Object Location and Routing for Large-scale Peer-to-Peer Systems. In Proc. of IFIP\/ACM Middleware Conference","author":"Rowstron A.","year":"2001"},{"key":"e_1_2_1_27_1","first-page":"281","volume-title":"Proc. of the First USENIX\/ACM Symp. on Networked Systems Design and Implementation (NSDI)","author":"Shen K.","year":"2004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_29_1","volume-title":"Proc. of the 5th International Workshop on Peer-to-Peer Systems (IPTPS)","author":"Zhong M.","year":"2006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498342"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1151374.1151386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:02:52Z","timestamp":1672261372000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1151374.1151386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1151374.1151386"],"URL":"https:\/\/doi.org\/10.1145\/1151374.1151386","relation":{},"ISSN":["0163-5980"],"issn-type":[{"value":"0163-5980","type":"print"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}