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
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
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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Random walks in peer-to-peer networks. https://app.cochat.ai/papers/10.1109/infcom.2004.1354487
- The paper
- Gkantsidis, C., Mihail, M., & Saberi, A. (2004). Random walks in peer-to-peer networks. IEEE INFOCOM 2004. https://doi.org/10.1109/infcom.2004.1354487
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.