{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:04:12Z","timestamp":1767261852267,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1023166"],"award-info":[{"award-number":["CCF-1023166"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 0701023, CCR 0910584"],"award-info":[{"award-number":["DMS 0701023, CCR 0910584"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"publisher","award":["M58110000"],"award-info":[{"award-number":["M58110000"]}],"id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2010-T2-2-082"],"award-info":[{"award-number":["MOE2010-T2-2-082"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS 0701023, CCR 0910584"],"award-info":[{"award-number":["DMS 0701023, CCR 0910584"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples.<\/jats:p>\n          <jats:p>\n            All previous algorithms that compute a random walk sample of length \u2113 as a subroutine always do so naively, that is, in\n            <jats:italic>O<\/jats:italic>\n            (\u2113) rounds. The main contribution of this article is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length \u2113 in\n            <jats:italic>\u00d5<\/jats:italic>\n            (\u221a\u2113\n            <jats:italic>D<\/jats:italic>\n            ) rounds (\n            <jats:italic>\u00d5<\/jats:italic>\n            hides polylog\n            <jats:italic>n<\/jats:italic>\n            factors where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes in the network) with high probability on an undirected network, where\n            <jats:italic>D<\/jats:italic>\n            is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive\n            <jats:italic>O<\/jats:italic>\n            (\u2113) bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. 2011]. We further extend our algorithms to efficiently perform\n            <jats:italic>k<\/jats:italic>\n            independent random walks in\n            <jats:italic>\u00d5<\/jats:italic>\n            (\u221a\n            <jats:italic>k<\/jats:italic>\n            \u2113\n            <jats:italic>D<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            ) rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling.\n          <\/jats:p>\n          <jats:p>\n            Our random-walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected unweighted) network which runs in\n            <jats:italic>\u00d5<\/jats:italic>\n            (\u221a\n            <jats:italic>mD<\/jats:italic>\n            ) rounds with high probability (\n            <jats:italic>m<\/jats:italic>\n            is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.\n          <\/jats:p>","DOI":"10.1145\/2432622.2432624","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T20:28:36Z","timestamp":1362515316000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Distributed Random Walks"],"prefix":"10.1145","volume":"60","author":[{"given":"Atish","family":"Das Sarma","sequence":"first","affiliation":[{"name":"eBay Research Labs"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University and Brown University"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"Search in power-law networks","author":"Adamic L. A.","year":"2001","journal-title":"Phys. Rev. 64."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(02)00028-X"},{"volume-title":"Proceedings of the 3rd International Workshop on Distributed Algorithms (WDAG; later called DISC). 1--12","author":"Bar-Ilan J.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS). 442--451","author":"Batu T.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 3rd International School and Symposium Advanced Distributed Systems (ISSADS). 231--240","author":"Bernard T.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015507"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11553762_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_15"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958171.1958176"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406029"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582745"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835745"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_10"},{"volume-title":"Proceedings of the IEEE INFOCOM. 2906--2910","author":"Das Sarma A.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.104"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1774088.1774369"},{"key":"e_1_2_1_23_1","unstructured":"Dubhashi D. P. Grandoni F. and Panconesi A. 2007. Distributed Algorithms via LP Duality and Randomization. In Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC.  Dubhashi D. P. Grandoni F. and Panconesi A. 2007. Distributed Algorithms via LP Duality and Randomization. In Handbook of Approximation Algorithms and Metaheuristics . Chapman and Hall\/CRC."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1054916.1054931"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1176982"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1526--1537","author":"Gkantsidis C.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM). 2591--2595","author":"Gkantsidis C.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 576--585","author":"Goyal N.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93409"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1246-6"},{"volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 13--21","author":"Kelner J. A.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039491"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.014"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0047-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"volume-title":"Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). IEEE","author":"Law C.","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863999"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/514191.514206"},{"key":"e_1_2_1_44_1","unstructured":"Lynch N. A. 1996. Distributed Algorithms. Morgan-Kaufmann San Francisco CA.   Lynch N. A. 1996. Distributed Algorithms . Morgan-Kaufmann San Francisco CA."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830500684X"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press New York.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.87"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.01.002"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993853"},{"key":"e_1_2_1_51_1","unstructured":"Pandurangan G. and Khan M. 2010. Algorithms and theory of computation handbook. Chapman & Hall\/CRC Chapter Theory of communication networks 27--27.   Pandurangan G. and Khan M. 2010. Algorithms and theory of computation handbook. Chapman & Hall\/CRC Chapter Theory of communication networks 27--27."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_53_1","unstructured":"Sami R. and Twigg A. 2008. Lower bounds for distributed markov chain problems. CoRR abs\/0810.5263.  Sami R. and Twigg A. 2008. Lower bounds for distributed markov chain problems. CoRR abs\/0810.5263 ."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151374.1151386"},{"volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1151--1161","author":"Zhong M.","key":"e_1_2_1_57_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432624","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:20Z","timestamp":1750234700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432624"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.1145\/2432622.2432624"],"URL":"https:\/\/doi.org\/10.1145\/2432622.2432624","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2013,2]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}