{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T21:09:57Z","timestamp":1635628197019},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1023166"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 0701023, CCR 0910584"]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher"},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"publisher","award":["M58110000"]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2010-T2-2-082"]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS 0701023, CCR 0910584"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"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 \n All previous algorithms that compute a random walk sample of length \u2113 as a subroutine always do so naively, that is, in\n 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 \u00d5<\/jats:italic>\n (\u221a\u2113\n D<\/jats:italic>\n ) rounds (\n \u00d5<\/jats:italic>\n hides polylog\n n<\/jats:italic>\n factors where\n n<\/jats:italic>\n is the number of nodes in the network) with high probability on an undirected network, where\n D<\/jats:italic>\n is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive\n 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 k<\/jats:italic>\n independent random walks in\n \u00d5<\/jats:italic>\n (\u221a\n k<\/jats:italic>\n \u2113\n D<\/jats:italic>\n +\n 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 \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 \u00d5<\/jats:italic>\n (\u221a\n mD<\/jats:italic>\n ) rounds with high probability (\n 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","source":"Crossref","is-referenced-by-count":18,"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","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"},{"key":"e_1_2_1_6_1","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_7_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_8_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_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"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE INFOCOM. 2906--2910","author":"Das Sarma A."},{"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"},{"key":"e_1_2_1_28_1","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_29_1","volume-title":"Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM). 2591--2595","author":"Gkantsidis C."},{"key":"e_1_2_1_30_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_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"},{"key":"e_1_2_1_35_1","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_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"},{"key":"e_1_2_1_41_1","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_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":"crossref","unstructured":"Muthukrishnan S. and Pandurangan G. 2010. Thresholding random geometric properties motivated by ad hoc sensor networks. J. Comput. Syst. Sci. 76 7 686--696. 10.1016\/j.jcss.2010.01.002 Muthukrishnan S. and Pandurangan G. 2010. Thresholding random geometric properties motivated by ad hoc sensor networks. J. Comput. Syst. Sci. 76 7 686--696. 10.1016\/j.jcss.2010.01.002","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.5555\/355459"},{"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"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1151--1161","author":"Zhong M."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T13:39:08Z","timestamp":1614519548000},"score":1,"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":"http:\/\/dx.doi.org\/10.1145\/2432622.2432624","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2013,2]]}}}