The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Random walks in peer-to-peer networks
Abstract
We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achieves better results than flooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its horizon does not change much. For construction, we argue that an expander can he maintained dynamically with constant operations per addition. The key technical ingredient of our approach is a deep result of stochastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical properties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such connectivity is desired, and believed to hold, in every reasonable network and network model). This property has been previously used in complexity theory for construction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random bits to savings in processing overhead.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
The algebraic eigenvalue problem
Wilkinson, J. H. (1965) · Cited by 5,833
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
Search and replication in unstructured peer-to-peer networks
Lv, Q., Cao, P., Cohen, E., Li, K., & Shenker, S. J. (2014) · International Conference on Supercomputing · doi:10.1145/2591635.2667182 · Cited by 1,612
Making gnutella-like P2P systems scalable
Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., & Shenker, S. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.864000 · Cited by 1,082
(2001) · Cited by 1,052
An Introduction to Probability Theory and its Applications
Grubbs, F. E. (1967) · Technometrics · doi:10.1080/00401706.1967.10490472 · Cited by 1,017
Trawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 1,000
Alon, N., & Spencer, J. H. (2000) · Wiley eBooks · doi:10.1002/0471722154 · Cited by 949
Reversible Markov Chains and Random Walks on Graphs
Aldous, D., & Fill, J. A. (2014) · Cited by 946
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems links, objects, time and space---structure in hypermedia systems - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
On distinguishing between Internet power law topology generators
Bu, T., & Towsley, D. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019309 · Cited by 516
Spectra of random graphs with given expected degrees
Chung, F., Lu, L., & Vu, V. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0937490100 · Cited by 492
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Algorithms for Random Generation and Counting: A Markov Chain Approach
Sinclair, A. (1993) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-0323-0 · Cited by 380
The Spectra of Random Graphs with Given Expected Degrees
Chung, F., Lu, L., & Vu, V. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129089 · Cited by 207
Dill, S., Kumar, R., Mccurley, K. S., Rajagopalan, S., Sivakumar, D., & Tomkins, A. (2002) · ACM Transactions on Internet Technology · doi:10.1145/572326.572328 · Cited by 197
Building low-diameter P2P networks
Pandurangan, G., Raghavan, P., & Upfal, E. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959925 · Cited by 191
Distributed construction of random expander networks
Law, C., & Siu, K.-Y. (2004) · doi:10.1109/infcom.2003.1209234 · Cited by 159
Aldous, D. (1987) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964800000267 · Cited by 133
Conductance and congestion in power law graphs
Gkantsidis, C., Mihail, M., & Saberi, A. (2003) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/781027.781046 · Cited by 117
Self-citationBroder, A., & Karlin, A. R. (1989) · Journal of Theoretical Probability · doi:10.1007/bf01048273 · Cited by 113
Cited by
Transport layer identification of P2P traffic
Karagiannis, T., Broido, A., Faloutsos, M., & claffy, K. (2004) · Proceedings of the 4th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1028788.1028804 · Cited by 708
Walking in Facebook: A Case Study of Unbiased Sampling of OSNs
Gjoka, M., Kurant, M., Butts, C. T., & Markopoulou, A. (2010) · 2010 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2010.5462078 · Cited by 671
Falkon: a Fast and Light-weight tasK executiON framework
Raicu, I., Zhao, Y., Dumitrescu, C., Foster, I., & Wilde, M. (2007) · Proceedings of the 2007 ACM/IEEE conference on Supercomputing · doi:10.1145/1362622.1362680 · Cited by 299
Optimal and scalable distribution of content updates over a mobile social network
Ioannidis, S., Chaintreau, A., & Massoulie, L. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062058 · Cited by 281
A survey on content-centric technologies for the current Internet: CDN and P2P solutions
Passarella, A. (2012) · Computer Communications · doi:10.1016/j.comcom.2011.10.005 · Cited by 226
Metadata
- Authors
- Gkantsidis, C., Mihail, M., & Saberi, A.
- Venue
- IEEE INFOCOM 2004
- Publisher
- IEEE
- Published
- 2004-12-23
- Volume
- 1
- Pages
- 120-130
- OpenAlex
- W2107082801
- Cited by
- 525
- References
- 27
- FWCI
- 24.58
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.