Flood search under the california split rule.pdf

Flood Search under the California Split Rule Y. Baryshnikov1, E. Coffman2,?,?, P. Jelenkovic?2,?, P. Momc?ilovic?2,? and D. Rubenstein2,? 1. Bell Labs 2. Department of Electrical Engineering Lucent Technologies Columbia University Murray Hill, NJ 07974 New York, NY 10027 ymb@ {egc, predrag, petar, danr}@ November 2002, revised August 2003 Abstract We consider flood search on a line and show that no algorithm can achieve an average-case compet- itive 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. Keywords: Flood search, peer-to-peer systems, expanding ring, average case competitive analysis 1 Introduction Since a major portion of traffic in the Internet is attributed to file swapping, overlay peer-to-peer (P2P) networks are one of the most popular applications on the Web. Since such networks are fully distributed, the efficiency of their operation highly depends on one’s ability to locate information in them. Two types of P2P networks have received considerable attention: structured and unstructured. Structured networks form an overlay and configure information in a specific way that allows clients to search efficiently (see e.g., [3, 11, 12]). For example, file xyz is always stored in a part of the overlay having files with similar characteristics like the values of a distributed hash function. Thus, when a client searches for xyz it only needs to examine a small number of specific ”places”. Such an approach seems very reasonable when most of the clients belong to the same entity and are willing to cooperate, such as would be the case when a client is required to store xyz even if it has no interest in it. However, most of the operational P2P networks (e.g., Gnutella, KaZaA) are formed by clients that have little or no incentive to perform social functions at their own ex