Efficient distributed random walks with applications

DOI10.1145/1835698.1835745zbMath1315.68268arXiv0911.3195OpenAlexW2063832254MaRDI QIDQ5176199

Atish Das Sarma, Gopal Pandurangan, Danupon Nanongkai, Prasad Tetali

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.3195

zbMATH Keywords

random walksmixing timerandom samplingdistributed algorithmsrandom spanning treedecentralized computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15) Random walks on graphs (05C81)

Related Items (3)

Termination of amnesiac flooding ⋮ Distributed PageRank computation with improved round complexities ⋮ Sampling-based algorithm for link prediction in temporal networks

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

This page was built for publication: Efficient distributed random walks with applications