×
Baryshnikov, Y.; Coffman, E.; Jelenkovič, P.; Momčilović, P.; Rubenstein, D.

Flood search under the California split rule. (English) Zbl 1049.68151

Oper. Res. Lett. 32, No. 3, 199-206 (2004).
Summary: We consider flood search on a line and show that no algorithm can achieve an average-case competitive ratio of less than 4 when compared to the optimal off-line algorithm. We also demonstrate that the optimal scanning sequences are described by simple recursive relationships that yield surprisingly complex behavior related to Hamiltonian chaos.

Cited in 1 Document

MSC:

68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms

Keywords:

Flood search; Peer-to-peer systems; Expanding ring; Average case competitive analysis

Software:

Chord
Cite Review PDF
Full Text: DOI

References:

[1] Adamic, L.; Lukose, R.; Puniyani, A.; Huberman, B., Search in power-law networks, Phys. Rev. E, 64 (2001)
[2] Baeza-Yates, R.; Culberson, J.; Rawlins, G., Searching in the plane, Inform. and Comput., 106, 234-252 (1993) · Zbl 0781.68044
[3] I. Clarke, O. Sandberg, B. Wiley, T. Hong, Freenet: a distributed anonymous information storage and retrieval system, Proceedings of the Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000.; I. Clarke, O. Sandberg, B. Wiley, T. Hong, Freenet: a distributed anonymous information storage and retrieval system, Proceedings of the Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000. · Zbl 0977.68665
[4] E. Cohen, S. Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the ACM Sigcomm, Pittsburgh, PA, August 2002.; E. Cohen, S. Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the ACM Sigcomm, Pittsburgh, PA, August 2002.
[5] Gal, S., Search Games (1980), Academic Press: Academic Press New York · Zbl 0439.90102
[6] Jaillet, P.; Stafford, M., Online searching, Oper. Res., 49, 4, 501-515 (2001) · Zbl 1163.90528
[7] Jaillet, P.; Stafford, M., Noteonline searching/on the optimality of the geometric sequences for the \(m\) ray search, Oper. Res., 50, 4, 744-745 (2002) · Zbl 1163.90527
[8] Kao, M.-Y.; Reif, J., Searching in an unknown environmentan optimal randomized algorithm for the cow-path problem, Inform. and Comput., 131, 63-79 (1996) · Zbl 0876.68030
[9] R. Karp, E. Koutsoupias, C. Papadimitriou, S. Shenker, Algorithmic problems in congestion control, Proceedings of FOCS, Redondo Beach, CA, 2000.; R. Karp, E. Koutsoupias, C. Papadimitriou, S. Shenker, Algorithmic problems in congestion control, Proceedings of FOCS, Redondo Beach, CA, 2000.
[10] Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th Annual ACM International Conference on Supercomputing, New York, NY, June 2002.; Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th Annual ACM International Conference on Supercomputing, New York, NY, June 2002.
[11] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, A scalable content addressable network, Proceedings of ACM Sigcomm, San Diego, CA, 2001.; S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, A scalable content addressable network, Proceedings of ACM Sigcomm, San Diego, CA, 2001. · Zbl 1060.68544
[12] I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup service for Internet applications, Proceedings of ACM Sigcomm, San Diego, CA, 2001.; I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup service for Internet applications, Proceedings of ACM Sigcomm, San Diego, CA, 2001.
[13] Tabor, M., Chaos and Integrability in Nonlinear Dynamics: An Introduction (1989), Wiley: Wiley New York · Zbl 0682.58003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.