RFC 4981
Survey of Research towards Robust Peer-to-Peer Networks: Search Methods
Survey of Research towards Robust Peer-to-Peer Networks: Search Methods ✨
Network Working Group · J. Risson & T. Moors · University of New South Wales 🎓 Request for Comments: 4981 · Category: Informational · September 2007 🌸
okay so this is RFC 4981, and it's a 🦋 survey 🦋 rather than a spec. It's marked Informational, so it's sharing knowledge, not setting rules. The authors are J. Risson and T. Moors from the University of New South Wales. The header doesn't list anything it obsoletes or updates, so it's standing on its own. It's part 1 of 23, so stay tuned bestie 💖
Status of This Memo 📝
bestie, this memo is here to give info to the Internet community, and it does not define an Internet standard of any kind. Distribution is unlimited, so you can share it as much as you want 🫶
IESG Note 🧾
this RFC is not a candidate for any level of Internet Standard, and the IETF is totally clear that it doesn't vouch for whether this RFC is fit for any purpose. Publishing it wasn't based on IETF review, except for IESG review checking for conflicts with IETF work. The RFC Editor picked to publish it at their own discretion. If you want the full scoop, check out RFC 3932 🔍
Abstract 💜
okay so P2P has been getting researched like crazy for the last five years, which is why this survey is so needed 🔥 P2P is giving disruptive-technology energy: it can pool enormous storage and processing power while keeping the cost of joining and scaling super low 💅
failures happen all the time when you've got massive numbers of distributed peers, but one failure might hurt less than it would in a conventional setup 🫠 So the real key to P2P being more than casual file sharing is robustness 👑
this survey starts by putting P2P search methods inside an overall P2P taxonomy 🗺️ Then it looks at indexes for simple key lookup, like the ones built on Plaxton trees, rings, tori, butterflies, de Bruijn graphs, and skip graphs 🦋 It also explores indexes for keyword lookup, information retrieval, and data management ✨ Last but not least, it reviews early efforts to optimize range, multi-attribute, join, and aggregation queries over P2P indexes 🎀
wherever the primary literature makes it possible, the robustness mechanisms and metrics get highlighted all the way through 🌈 Tea: the low-level mechanisms that matter most for robustness aren't really well isolated in the literature yet 🙈 The authors wrap up with recommendations for future research, so the mystery is ready for someone to solve 🧚
Table of Contents 📚
1. Introduction ....................................................3
1.1. Related Disciplines ........................................6
1.2. Structured and Unstructured Routing ........................7
1.3. Indexes and Queries ........................................9
2. Index Types ....................................................10
2.1. Local Index (Gnutella) ....................................10
2.2. Central Index (Napster) ...................................12
2.3. Distributed Index (Freenet) ...............................13
3. Semantic Free Index ............................................15
3.1. Origins ...................................................15
3.1.1. Plaxton, Rajaraman, and Richa (PRR) ................15
3.1.2. Consistent Hashing .................................16
3.1.3. Scalable Distributed Data Structures (LH*) .........16
3.2. Dependability .............................................17
3.2.1. Static Dependability ...............................17
3.2.2. Dynamic Dependability ..............................18
3.2.3. Ephemeral or Stable Nodes -- O(log n) or
O(1) Hops ..........................................19
3.2.4. Simulation and Proof ...............................20
3.3. Latency ...................................................21
3.3.1. Hop Count and the O(1)-Hop DHTs ....................21
3.3.2. Proximity and the O(log n)-Hop DHTs ................22
3.4. Multicasting ..............................................23
3.4.1. Multicasting vs. Broadcasting ......................23
3.4.2. Motivation for DHT-based Multicasting ..............23
3.4.3. Design Issues ......................................24
3.5. Routing Geometries ........................................25
3.5.1. Plaxton Trees (Pastry, Tapestry) ...................25
3.5.2. Rings (Chord, DKS) .................................27
3.5.3. Tori (CAN) .........................................28
3.5.4. Butterflies (Viceroy) ..............................29
3.5.5. de Bruijn (D2B, Koorde, Distance Halving, ODRI) ....30
3.5.6. Skip Graphs ........................................32
4. Semantic Index .................................................33
4.1. Keyword Lookup ............................................34
4.1.1. Gnutella Enhancements ..............................36
4.1.2. Partition-by-Document, Partition-by-Keyword ........38
4.1.3. Partial Search, Exhaustive Search ..................39
4.2. Information Retrieval .....................................39
4.2.1. Vector Model (PlanetP, FASD, eSearch) ..............41
4.2.2. Latent Semantic Indexing (pSearch) .................43
4.2.3. Small Worlds .......................................43
5. Queries ........................................................44
5.1. Range Queries .............................................45
5.2. Multi-Attribute Queries ...................................48
5.3. Join Queries ..............................................50
5.4. Aggregation Queries .......................................50
6. Security Considerations ........................................52
7. Conclusions ....................................................52
8. Acknowledgments ................................................53
9. References .....................................................54
9.1. Informative References ....................................54Part 1 of 23 done, bestie! 🌈 Next up: Section 1, Introduction 💖
1. Introduction ✨
okay so bestie, peer-to-peer (P2P) networks have three vibes that make them P2P: they're self-organizing, they do symmetric communication, and they have distributed control [1]. 💜 A self-organizing P2P network "automatically adapts to the arrival, departure and failure of nodes" [2]. The communication is symmetric because peers act as both clients and servers 🫶. There's no centralized directory or control point, so nobody's the boss 👑. USENET servers and BGP peers have these traits too [3], but the focus here is the flurry of research since 2000 🔥. The leading examples are Gnutella [4], Freenet [5], Pastry [2], Tapestry [6], Chord [7], the Content Addressable Network (CAN) [8], pSearch [9], and Edutella [10] 🦋. Some people have suggested that peers are inherently unreliable [11], and others have assumed well-connected, stable peers [12]. Tea, but make it complicated 🍓.
This critical survey of P2P academic literature is so warranted, given how intense recent research has been 😭. At the time of writing, one research database lists over 5,800 P2P publications [13]. That's a lot of reading, periodt 💀. One vendor surveyed P2P products and deployments [14], there's also a tutorial survey of leading P2P systems [15], and DePaoli and Mariani recently reviewed the dependability of some early P2P systems at a high level [16]. The need for a critical survey was also flagged in the peer-to-peer research group of the Internet Research Task Force (IRTF) [17] 🌸.
P2P is potentially a disruptive technology with loads of applications, but this potential won't be realized unless it's demonstrated to be robust 💅. A massively distributed search technique may yield numerous practical benefits for applications [18] ✨. A P2P system has the potential to be more dependable than architectures that rely on a small number of centralized servers 🛡️. It also has the potential to evolve better from small configurations. The capital outlays for high performance servers can be reduced and spread over time if a P2P assembly of general purpose nodes is used 💖. A similar argument motivated the deployment of distributed databases, since one thousand, off-the-shelf PC processors are more powerful and much less expensive than a large mainframe computer [19] 🧚. Storage and processing can be aggregated to achieve massive scale, and wasteful partitioning between servers or clusters can be avoided 🌈. As Gedik and Liu put it, if P2P is going to find its way into applications other than casual file sharing, then reliability needs to be addressed [20]. Literally the whole point 🎀.
The taxonomy of Figure 1 divides the entire body of P2P research literature along four lines: search, storage, security, and applications 🗺️. This survey concentrates on the search aspects. A P2P search network consists of an underlying index (Sections 2 to 4) and queries that propagate over that index (Section 5) 🔍.
Search [18, 21-29]
Semantic-Free Indexes [2, 6, 7, 30-52]
Plaxton Trees
Rings
Tori
Butterflies
de Bruijn Graphs
Skip Graphs
Semantic Indexes [4, 53-71]
Keyword Lookup
Peer Information Retrieval
Peer Data Management
Queries [20, 22, 23, 25, 32, 38, 41, 56, 72-100]
Range Queries
Multi-Attribute Queries
Join Queries
Aggregation Queries
Continuous Queries
Recursive Queries
Adaptive Queries
Storage
Consistency & Replication [101-112]
Eventual consistency
Trade-offs
Distribution [39, 42, 90, 92, 113-131]
Epidemics, Bloom Filters
Fault Tolerance [40, 105, 132-139]
Erasure Coding
Byzantine Agreement
Locality [24, 43, 47, 140-160]
Load Balancing [37, 86, 100, 107, 151, 161-171]
Security
Character [172-182]
Identity
Reputation and Trust
Incentives
Goals [25, 27, 71, 183-197]
Availability
Authenticity
Anonymity
Access Control
Fair Trading
Applications [1, 198-200]
Memory [32, 90, 142, 201-222]
File Systems
Web
Content Delivery Networks
Directories
Service Discovery
Publish / Subscribe ...
Intelligence [223-228]
GRID
Security...
Communication [12, 92, 119, 229-247]
Multicasting
Streaming Media
Mobility
Sensors...
Figure 1: Classification of P2P Research LiteratureThis survey is concerned with two questions. The first is "How do P2P search networks work?" This foundation is important given the pace and breadth of P2P research in the last five years 🏃♀️. In Section 2, we classify indexes as local, centralized and distributed. Since distributed indexes are becoming dominant, they get closer attention in Sections 3 and 4 👀. Section 3 compares distributed P2P indexes for simple key lookup. In particular, it looks at their origins (Section 3.1), dependability (Section 3.2), latency (Section 3.3), and their support for multicast (Section 3.4). It classifies those indexes according to their routing geometry (Section 3.5), which means Plaxton trees, rings, tori, butterflies, de Bruijn graphs and skip graphs 🧩. Section 4 reviews distributed P2P indexes that support keyword lookup (Section 4.1) and information retrieval (Section 4.2) 📚. Section 5 probes the embryonic research on P2P queries, in particular range queries (Section 5.1), multi-attribute queries (Section 5.2), join queries (Section 5.3), and aggregation queries (Section 5.4) 💜.
The second question is "How robust are P2P search networks?" Insofar as it's available in the research literature, we tease out the robustness mechanisms and metrics throughout Sections 2 to 5 🔎. Unfortunately, robustness is often more sensitive to low-level design choices than it is to the broad P2P index structure, and these underlying design choices are seldom isolated in the primary literature [248] 🙈. Furthermore, there has been little consensus on P2P robustness metrics (Section 3.2). Section 8 gives recommendations to address these important gaps 🩷.
1.1. Related Disciplines 💅
Peer-to-peer research draws on numerous distributed systems disciplines 🌐. Networking researchers will recognize familiar issues of naming, routing, and congestion control 🚦. P2P designs need to address routing and security issues across network region boundaries [152]. Networking research has traditionally been host-centric. The Web's Universal Resource Identifiers are naturally tied to specific hosts, which makes object mobility a challenge [216] 🥲.
P2P work is data-centric [249] 🗃️. P2P systems for dynamic object location and routing have borrowed heavily from the distributed systems corpus. Some have used replication, erasure codes, and Byzantine agreement [111], and others have used epidemics for durable peer group communication [39] 🦠.
Similarly, P2P research is set to benefit from database research [250] 🧠. Database researchers will recognize the need to reapply Codd's principle of physical data independence, which means decoupling data indexes from the applications that use the data [23]. It was the invention of appropriate indexing mechanisms and query optimizations that enabled data independence. Database indexes like B+ trees have an analog in P2P's distributed hash tables (DHTs). Wide-area P2P query optimization is a ripe, but challenging, area for innovation 🍒.
More flexible distribution of objects comes with increased security risks 🚨. There are opportunities for security researchers to deliver new methods for availability, file authenticity, anonymity, and access control [25]. Proactive and reactive mechanisms are needed to deal with large numbers of autonomous, distributed peers. To build robust systems from cooperating but self-interested peers, issues of identity, reputation, trust, and incentives need to be tackled 🤝. Although it's beyond the scope of this paper, robustness against malicious attacks also ought to be addressed [195] 🛡️.
Possibly the largest portion of P2P research has majored on basic routing structures [18], which is where research on algorithms really comes to the fore 🧮. Should the overlay be "structured" or "unstructured"? Are the two approaches competing or complementary? Comparisons of the "structured" approaches (hypercubes, rings, toroids, butterflies, de Bruijn, and skip graphs) have weighed the amount of routing state per peer and the number of links per peer against overlay hop counts. While "unstructured" overlays initially used blind flooding and random walks, overheads usually trigger some structure, for example, super-peers and clusters 🌀.
P2P applications rely on cooperation between these disciplines 🫂. Applications have included file sharing, directories, content delivery networks, email, distributed computation, publish-subscribe middleware, multicasting, and distributed authentication. Which applications will be suited to which structures? Are there adaptable mechanisms that can decouple applications from the underlying data structures? What are the criteria for selecting applications that are amenable to a P2P design [1]? 🤔
Robustness is emphasized throughout the survey, and we're particularly interested in two aspects 🎯. The first is dependability, which was a leading design goal for the original Internet [251]. It deserves the same status in P2P. The measures of dependability are well established: reliability, a measure of the mean-time-to-failure (MTTF); availability, a measure of both the MTTF and the mean-time-to-repair (MTTR); maintainability; and safety [252] 📏. The second aspect is the ability to accommodate variation in outcome, which one could call adaptability. Its measures have yet to be defined. In the context of the Internet, it was only recently acknowledged as a first-class requirement [253] 🌟. In P2P, it means planning for the tussles over resources and identity. It means handling different kinds of queries and accommodating changeable application requirements with minimal intervention. It also means "organic scaling" [22], whereby the system grows gracefully, without a priori data center costs or architectural breakpoints 🌱.
In the following section, we discuss one notable omission from the taxonomy of P2P networking in Figure 1, which is routing 🛣️.
1.2. Structured and Unstructured Routing ✨
okay so P2P routing algorithms got sorted into two buckets: "structured" or "unstructured" 💅. Peers in unstructured overlay networks join by connecting to any existing peers [254]. In structured overlays, the identifier of the joining peer determines the set of peers that it connects to [254]. Early Gnutella was unstructured -- keyword queries were flooded widely [255]. Napster [256] had decentralized content and a centralized index, so it only partially satisfies the distributed control criteria for P2P systems 🙈
Early structured algorithms included Plaxton, Rajaraman and Richa (PRR) [30], Pastry [2], Tapestry [31], Chord [7], and the Content Addressable Network [8]. Mishchke and Stiller recently classified P2P systems by the presence or absence of structure in routing tables and network topology [257] 🧚
Some people have cast unstructured and structured algorithms as competing alternatives. Unstructured approaches have been called "first generation", implicitly inferior to the "second generation" structured algorithms [2, 31]. When generic key lookups are required, these structured, key-based routing schemes can guarantee location of a target within a bounded number of hops [23]. The broadcasting unstructured approaches, however, may have large routing costs, or fail to find available content [22]. Despite the apparent advantages of structured P2P, several research groups are still pursuing unstructured P2P 🦋
There have been two main criticisms of structured systems [61]. The first relates to peer transience, which in turn, affects robustness. Chawathe, et al. opined that highly transient peers are not well supported by DHTs [61]. P2P systems often exhibit "churn", with peers continually arriving and departing. One objection to concerns about highly transient peers is that many applications use peers in well-connected parts of the network. The Tapestry authors analyzed the impact of churn in a network of 1000 nodes [31]. Others opined that it is possible to maintain a robust DHT at relatively low cost [258]. Very few papers have quantitatively compared the resilience of structured systems. Loguinov, Kumar, et al. claimed that there were only two such works [24, 36] 😭
The second criticism of structured systems is that they do not support keyword searches and complex queries as well as unstructured systems. Given the current file-sharing deployments, keyword searches seem more important than exact-match key searches in the short term. Paraphrased, "most queries are for hay, not needles" [61] 🌾💀
More recently, some have justifiably seen unstructured and structured proposals as complementary, and have devised hybrid models [259]. Their starting point was the observation that unstructured flooding or random walks are inefficient for data that is not highly replicated across the P2P network. Structured graphs can find keys efficiently, irrespective of replication. Castro, et al. proposed Structella, a hybrid of Gnutella built on top of Pastry [259]. Another design used structured search for rare items and unstructured search for massively replicated items [54] 🫶
However, the "structured versus unstructured routing" taxonomy is becoming less useful, for two reasons, Firstly, most "unstructured" proposals have evolved and incorporated structure. Consider the classic "unstructured" system, Gnutella [4]. For scalability, its peers are either ultrapeers or leaf nodes. This hierarchy is augmented with a query routing protocol whereby ultrapeers receive a hashed summary of the resource names available at leaf nodes. Between ultrapeers, simple query broadcast is still used, though methods to reduce the query load here have been considered [260]. Secondly, there are emerging schema-based P2P designs [59], with super-node hierarchies and structure within documents. These are quite distinct from the structured DHT proposals 👑
1.3. Indexes and Queries ✨
Given that most, if not all, P2P designs today assume some structure, a more instructive taxonomy would describe the structure. In this survey, we use a database taxonomy in lieu of the networking taxonomy, as suggested by Hellerstein, Cooper, and Garcia-Molina [23, 261]. The structure is determined by the type of index (Sections 2 , 3, and 4). Queries feature in lieu of routing (Section 5). The DHT algorithms implement a "semantic-free index" [216]. They are oblivious of whether keys represent document titles, meta-data, or text. Gnutella-like and schema-based proposals have a "semantic index" 🎀
Index engineering is at the heart of P2P search methods. It captures a broad range of P2P issues, as demonstrated by the Search/Index Links model [261]. As Manber put it, "the most important of the tools for information retrieval is the index -- a collection of terms with pointers to places where information about documents can be found" [262]. Sen and Wang noted that a "P2P network" usually consists of connections between hosts for application-layer signaling, rather than for the data transfer itself [263]. Similarly, we concentrate on the "signaled" indexes and queries 💜
Our focus here is the dependability and adaptability of the search network. Static dependability is a measure of how well queries route around failures in a network that is normally fault-free. Dynamic dependability gives an indication of query success when nodes and data are continually joining and leaving the P2P system. An adaptable index accommodates change in the data and query distribution. It enables data independence, in that it facilitates changes to the data layout without requiring changes to the applications that use the data [23]. An adaptable P2P system can support rich queries for a wide range of applications. Some applications benefit from simple, semantic-free key lookups [264]. Others require more complex, Structured Query Language (SQL)-like queries to find documents with multiple keywords, or to aggregate or join query results from distributed relations [22] 🌸
2. Index Types 🍓
A P2P index can be local, centralized, or distributed. With a local index, a peer only keeps the references to its own data, and does not receive references for data at other nodes. The very early Gnutella design epitomized the local index (Section 2.1). In a centralized index, a single server keeps references to data on many peers. The classic example is Napster (Section 2.2). With distributed indexes, pointers towards the target reside at several nodes. One very early example is Freenet (Section 2.3). Distributed indexes are used in most P2P designs nowadays -- they dominate this survey 🌈
P2P indexes can also be classified as non-forwarding and forwarding. When queries are guided by a non-forwarding index, they jump to the node containing the target data in a single hop. There have been semantic and semantic-free one-hop schemes [138, 265, 266]. Where scalability to a massive number of peers is required, these schemes have been extended to two hops [267, 268]. More common are the forwarding P2Ps, where the number of hops varies with the total number of peers, often logarithmically. The related trade-offs between routing state, lookup latency, update bandwidth, and peer churn are critical to total system dependability ⭐
2.1. Local Index (Gnutella) 🌸
Okay so purely local data indexes in P2P are getting rare 🥺. In these designs, peers flood queries super widely and only index their own content. The payoff is rich queries, because the search isn't stuck to a simple key lookup ✨. The downside is a massive pile of query traffic with zero guarantee of a match, even when the match is out there on the network 💀. In the early Gnutella days, peers found each other by broadcasting 'ping' messages over the P2P network, and the 'pong' replies were used to build the node index. Then small 'query' messages, each carrying a list of keywords, got broadcast, and the peers with matching filenames responded [4].
There have been loads of attempts to make local-index P2P networks more scalable 🦋. Gnutella uses fixed time-to-live (TTL) rings, where the query's TTL is set less than 7-10 hops [4]. Small TTLs cut down on network traffic and the load on peers, but they also lower the chances of a successful query hit 😭. One paper reported, perhaps a little too bluntly, that the fixed "TTL-based mechanism does not work" [67]. To fix this TTL selection problem, they proposed an expanding ring, known elsewhere as iterative deepening [29]. It uses successively larger TTL counters until there is a match 🧚. The flooding, ring, and expanding ring methods all increase network load with duplicated query messages. A random walk, where an unduplicated query wanders around the network, does reduce the network load, but it massively increases the search latency 🙈. One solution is to replicate the query k times at each peer. Called random k-walkers, this technique can be paired with TTL limits, or with periodic checks with the query originator, to cap the query load [67].
Adamic, Lukose, et al. suggested that random walk searches be directed to nodes with a higher degree, meaning larger numbers of inter-peer connections [269]. They assumed that higher-degree peers are also capable of higher query throughputs. However, without some balancing design rule, those peers would get swamped with the entire P2P signaling traffic 💀. Beyond these approaches, there is the 'directed breadth-first' algorithm [29]. It forwards queries within a subset of peers chosen by heuristics based on previous performance, like the number of successful query results ✨. Another algorithm, called probabilistic flooding, has been modeled using percolation theory [270].
Several measurement studies have looked into locally indexed P2Ps 👀. Jovanovic noted Gnutella's power law behaviour [70]. Sen and Wang compared the performance of Gnutella, Fasttrack [271], and Direct Connect [263, 272, 273]. At the time, only Gnutella used local data indexes. All three schemes now use distributed data indexes, with hierarchy in the form of Ultrapeers (Gnutella), Super-Nodes FastTrack), and Hubs (Direct Connect). It was found that a very small percentage of peers have a very high degree, and that the total system dependability is at the mercy of those peers 😱. While peer uptime and bandwidth were heavy-tailed, they did not fit well with the Zipf distribution. Fortunately for Internet Service Providers, measures aggregated by IP prefix and Autonomous System (AS) were more stable than measures for individual IP addresses 🫶. A study of University of Washington traffic found that Gnutella and Kazaa together contributed 43% of the university's total TCP traffic [274]. It also reported a heavy-tailed distribution, with 600 external peers (out of 281,026) delivering 26% of Kazaa bytes to internal peers. Furthermore, objects retrieved from the P2P network were typically three orders of magnitude larger than Web objects. 300 objects contributed to almost half the total outbound Kazaa bandwidth 🤯. Others reported Gnutella's topology mismatch, where only 2-5% of P2P connections link peers in the same Autonomous System (AS), despite over 40% of peers being in the top 10 ASs [65]. Together these studies underscore the significance of multimedia sharing applications 🎀. They motivate interesting caching and locality solutions to the topology mismatch problem.
These same studies bear out one main dependability lesson: total system dependability may be sensitive to the dependability of high-degree peers 👑. The designers of Scamp turned this observation into the design heuristic, "have the degree of each node be of nearly equal size" [153]. They analyzed a system of N peers, with mean degree c.log(n), where link failures occur independently with probability e. If d>0 is fixed and c>(1+d)/(-log(e)), then the probability of graph disconnection goes to zero as N->infinity. Otherwise, if c<(1-d)/(-log(e)), then the probability of disconnection goes to one as N->infinity. They presented a localizer, which finds approximate minima to a global function of peer degree and arbitrary link costs using only local information 🧠. The Scamp overlay construction algorithms could support any of the flooding and walking routing schemes above, or other epidemic and multicasting schemes for that matter. Resilience to high churn rates was identified for future study 🔮.
2.2. Central Index (Napster) 💅
Centralized schemes like Napster [256] are a big deal, because they were the first to show the P2P scalability that comes from separating the data index from the data itself 🔥. Ultimately, 36 million Napster users lost their service, and not because of a technical failure. It happened because the single administration was vulnerable to the legal challenges of record companies [275] 💔.
There has been little research on P2P systems with central data indexes since then 🥀. Such systems have also been called 'hybrid' because the index is centralized but the data is distributed. Yang and Garcia-Molina devised a four-way classification of hybrid systems [276]. Unchained servers are where users whose index is on one server do not see other servers' indexes. Chained servers are where the server that receives a query forwards it to a list of servers if it does not own the index itself. Full replication is where all centralized servers keep a complete index of all available metadata. Hashing is where keywords are hashed to the server where the associated inverted list is kept 🧩. The unchained architecture was used by Napster, but it has the disadvantage that users do not see all indexed data in the system. Strictly speaking, the other three options illustrate the distributed data index, not the central index. The chained architecture was recommended as the optimum for the music-swapping application at the time. The methods by which clients update the central index were classified as batch or incremental, with the optimum determined by the query-to-login ratio 📊. Measurements were derived from a clone of Napster called OpenNap[277]. Another study of live Napster data reported wide variation in the availability of peers, a general unwillingness to share files (20-40% of peers share few or no files), and a common understatement of available bandwidth so as to discourage other peers from sharing one's link [202] 🙃.
Influenced by Napster's early demise, the P2P research community may have prematurely turned its back on centralized architectures 😤. Chawathe, Ratnasamy, et al. opined that Google and Yahoo demonstrate the viability of a centralized index. They argued that "the real barriers to Napster-like designs are not technical but legal and financial" [61] 💯. Even this view may be a little too harsh on centralized architectures. It implies that they always have an up-front capital hurdle that is steeper than for distributed architectures. The closer one looks at scalable 'centralized' architectures, the less the distinction with 'distributed' architectures seems to matter 🤔. For example, it is clear that Google's designers consider Google a distributed, not centralized, file system [278]. Google demonstrates the scale and performance possible on commodity hardware, but it still has a centralized master that is critical to the operation of each Google cluster. Time may prove that the value of emerging P2P networks, regardless of the centralized-versus-distributed classification, is that they smooth the capital outlays and remove the single points of failure across the spectra of scale and geographic distribution 🌈.
2.3. Distributed Index (Freenet) 🎀
okay so the big early P2P proposal for a distributed index was Freenet [5, 71, 279] 🌸 its main vibe was anonymity for peers, but it also came up with a genuinely iconic indexing scheme 🔥 files get identified by low-level "content-hash" keys and by "secure signed-subspace" keys. the signed-subspace ones mean only a file owner can write to a file, while literally anyone can read it 🔐
here's how searching works: the requesting peer first checks its local table for the node with keys closest to the target ✨ that node gets the query and does the same thing, checking for either a match or another node with keys close to the target. eventually the query either finds the target or runs past its time-to-live (TTL) limits 💀 the response then walks back the successful query path in reverse, and at each peer it leaves behind a new routing table entry (the requested key and the data holder) 🦋 the insert message is similar: it steps toward the target node, updating routing table entries as it goes, and then stores the file there 💖
Fun fact: early Gnutella used breadth-first flooding, but Freenet went with a more economic depth-first search [280] 💅
an initial assessment looked at Freenet's robustness, and in a network of 1000 nodes, the median query path length stayed under 20 hops even when 30% of nodes failed 🧚 the Freenet designers called this "surprisingly robust against quite large failures" [71] but ngl, that same datapoint might be outside meaningful operating bounds 🙈 like, how many applications are actually useful when the first quartile of queries has path lengths of several hundred hops in a network of only 1000 nodes, per Figure 4 of [71]? 😭 and there's been no analysis of Freenet's dynamic robustness yet. how does it perform when nodes are continually arriving and departing? 🤔
there have been both criticisms and extensions of the early Freenet work 🍓 Gnutella people admitted Freenet's avoidance of query broadcasting was good [281], but they had two complaints: the exact file name is needed to construct a query, and exactly one match comes back per query. DHT-based P2P designs (per Section 3) have similar vibes, where a precise query gets a precise response 🎯 this isn't surprising since Freenet also uses a hash function to generate keys. the difference is that DHT query routing has firmer theoretical foundations 🧠
another difference from DHTs: when a new node joins a Freenet network, it takes time to build an index that helps with efficient query routing 😬 the inventor admitted this is damaging for a user's first impressions [282] ☹️ the proposal was to download a copy of routing tables from seed nodes at startup, even though the new node might be far from the seed node 🙃 Mache, Gilbert, et al. saw this slow startup and decided to amend the overlay after failed requests and place extra index entries on successful requests 🛠️ they claim almost an order of magnitude reduction in average query path length [280] 👑
Clarke also pointed out the lack of locality or bandwidth information for making efficient query routing decisions [282] 👀 his idea was for each node to gather response times, connection times, and the proportion of successful requests for each entry in the query routing table ✨ then when searching for a key that isn't in its own routing table, a node estimates response times from the routing metrics of the nearest known keys, and picks the node that can retrieve the data fastest 🏃♀️ the response time heuristic assumes that nodes close in the key space have similar response times 🤍 that assumption came from early deployment observations that Freenet peers seemed to specialize in parts of the keyspace, but it has not been justified analytically 🤷♀️
Kronfol pointed out Freenet can't do keyword searches [283] 💜 he suggested peers cache lists of weighted keywords so they can route queries to documents, using Term Frequency Inverse Document Frequency (TFIDF) measures and inverted indexes (Section 4.2.1) 📚 with this, a peer can route queries for simple keyword lists or more complicated conjunctions and disjunctions of keywords 🧩 but robustness analysis and simulation of Kronfol's proposal are still open questions 🫶
The vast majority of P2P proposals in the following sections rely on a distributed index. 🌈
3. Semantic Free Index 🦋
okay so many of today's distributed network indexes are semantic 💖 a semantic index is human-readable. it might associate information with other keywords, a document, a database key, or even an administrative domain 🏢 it makes it super easy to tie objects to network providers, companies, or organizations, as the Domain Name System (DNS) shows 🌐 but it can also start legal tussles and frustrate content replication and migration [216] 😤
Distributed Hash Tables (DHTs) were proposed to give us semantic-free, data-centric references ✨ DHTs let you find an object's persistent key in a very large, constantly changing set of hosts 🌊 they're typically designed for [23]:
- a) low degree. If each node keeps routing information for only a small number of other nodes, the impact of high node arrival and departure rates is contained 🧸
- b) low hop count. The hops and delay from the extra indirection are minimized 🏃♀️
- c) greedy routing. Nodes independently calculate a short path to the target. At each hop, the query moves closer to the target; and 🎯
- d) robustness. A path to the target can be found even when links or nodes fail 💪
3.1. Origins 🕰️
to understand where recent DHTs came from, you have to look at three contributions from the 1990s 📼 the first two, Plaxton, Rajaraman, and Richa (PRR) [30] and Consistent Hashing [49], were published within one month of each other 👯 the third, the Scalable Distributed Data Structure (SDDS) [52], was curiously ignored by significant structured P2P designs even though it had some similar goals [2, 6, 7] 😭 it's been briefly referenced in other P2P papers [46, 284-287] 🥺
3.1.1. Plaxton, Rajaraman, and Richa (PRR) 🌟
PRR is the most recent of the three ✨ it influenced the designs of Pastry [2], Tapestry [6], and Chord [7] 🔥 its big value is that it can locate objects using fixed-length routing tables [6] 💅 objects and nodes get a semantic-free address, for example a 160-bit key 🔑 every node is effectively the root of a spanning tree 🌳 a message routes toward an object by matching longer address suffixes, until it hits either the object's root node or another node with a 'nearby' copy 🎯 it can route around link and node failure by matching nodes with a related suffix 🛣️
the scheme has several disadvantages [6], though 😬: global knowledge is needed to construct the overlay; an object's root node is a single point of failure; nodes cannot be inserted and deleted; and there's no mechanism for queries to avoid congestion hot spots 🔥🙃
3.1.2. Consistent Hashing 🧁
Consistent Hashing [288] strongly influenced the designs of Chord [7] and Koorde [37] 💖 Karger, et al. introduced it in the context of the Web-caching problem [49] 🌐 web servers could conceivably use standard hashing to place objects across a network of caches, and clients could use the same approach to find the objects 🔍 with normal hashing, most object references would move whenever caches are added or deleted 😵💫 but Consistent Hashing is "smooth" 🧈 when caches are added or deleted, the minimum number of object references move so load balancing is maintained ⚖️ it also makes sure the total number of caches responsible for a particular object stays limited 🎀
Litwin's Linear Hashing (LH*) scheme needs 'buckets' to be added one at a time, in sequence [50], whereas Consistent Hashing lets them be added in any order [49] 🙌 there's still an open Consistent Hashing problem about the fraction of items moved when a node is inserted [165] 🧐 Extended Consistent Hashing was recently proposed to randomize queries over the spread of caches, significantly reducing load variance [289] 📉 fun bit: Karger [49] mentioned an older DHT algorithm by Devine that used "a novel autonomous location discovery algorithm that learns the buckets' locations instead of using a centralized directory" [51] 🕵️♀️✨
3.1.3. Scalable Distributed Data Structures (LH*) 🧚♀️
Devine's main reference point was Litwin's work on SDDSs and the associated LH* algorithm [52] 📖 an SDDS satisfies three design requirements: files grow to new servers only when existing servers are well loaded; there is no centralized directory; and basic operations like insert, search, and split never require atomic updates to multiple clients 🧩 Honicky and Miller suggested the first requirement could be a limitation, since expansion to new servers isn't under administrative control [286] 🤨 Litwin recently noted a bunch of similarities and differences between LH* and Chord [290] 🧃 he found that both implement key search 🔎 and although LH* refers to clients and servers, nodes can operate as peers in both 🤝
Chord 'splits' nodes when a new node is inserted, while LH* schedules 'splits' to avoid overload ⚡ Chord requests travel O(log n) hops, while LH* client requests need, at most, two hops to find the target 🎯 Chord stores a small number of 'fingers' at each node 🪝 LH* servers store N/2 to N addresses, while LH* clients store 1 to N addresses 📇 this trade-off between hop count and index size affects system robustness, and it's giving striking similarity to the recent one- and two-hop P2P schemes in Section 2 👀 the arrival and departure of LH* clients doesn't disrupt LH* server metadata at all 🙌 given the size of the index, the arrival and departure of LH* servers are likely to cause more churn than Chord nodes do 🌪️
unlike Chord, LH* has a single point of failure, the split coordinator 😱 it can be replicated 🔁 alternatively, it can be removed in later LH* variants, though details haven't progressed for lack of practical need [290] 🤷♀️
3.2. Dependability 🛡️
we make four overall observations about their dependability ✨ dependability metrics fall into two categories: static dependability, a measure of performance before recovery mechanisms take over; and dynamic dependability, for the most likely case in massive networks where there is continual failure and recovery ("churn") 🌊💜
3.2.1. Static Dependability ✨
Observation A: Static dependability comparisons show that no O(log n) DHT geometry is significantly more dependable than the other O(log n) geometries. 💅
Okay so Gummadi, et al. compared the tree, hypercube, butterfly, ring, XOR, and hybrid geometries. 🫶 In these geometries, nodes generally know about O(log n) neighbors and route to a destination in O(log n) hops, where N is the number of nodes in the overlay. Gummadi, et al. asked "Why not the ring?" 👑 Their conclusion was that only the ring and XOR geometries permit flexible choice of both neighbors and alternative routes [24].
Then Loguinov, et al. added the de Bruijn graph to the comparison [36]. 🦋 They concluded that the classical analyses, for example the probability that a particular node becomes disconnected, yield no major differences between the resilience of Chord, CAN, and de Bruijn graphs. 😭 But when they used bisection width (the minimum edge count between two equal partitions) and path overlap (the likelihood that backup paths will encounter the same failed nodes or links as the primary path), they argued for the superior resilience of the de Bruijn graph. 🔥
In short, ring, XOR, and de Bruijn graphs all permit flexible choice of alternative paths, but only in de Bruijn are the alternate paths independent of each other [36]. 💜
3.2.2. Dynamic Dependability 🌈
Observation B: Dynamic dependability comparisons show that DHT dependability is sensitive to the underlying topology maintenance algorithms. 🧚
Li, et al. give the best comparison to date of several leading DHTs during churn [291]. ✨ They relate the disparate configuration parameters of Tapestry, Chord, Kademlia, Kelips, and OneHop to fundamental design choices. For each of these DHTs, they plotted the optimal performance in terms of lookup latency (milliseconds) and fraction of failed lookups. 🍓
The results led to several important insights about the underlying algorithms, for example: increasing routing table size is more cost-effective than increasing the rate of periodic stabilization; learning about new nodes during the lookup process sometimes eliminates the need for stabilization; and parallel lookups reduce latency due to timeouts more effectively than faster stabilization. 🙈 Similarly, Zhuang, et al. compared keep-alive algorithms for DHT failure detection [292]. Such algorithmic comparisons can significantly improve the dependability of DHT designs. 💖
In Figure 2, we propose a taxonomy for the topology maintenance algorithms that influence dependability. 🎀 The algorithms can be classified by how nodes join and leave, how they first detect failures, how they share information about topology updates, and how they react when they receive information about topology updates.
Normal Updates
Joins (passive; active) [293]
Leaves (passive; active) [293]
Fault Detection [292]
Maintenance
Proactive (periodic or keep-alive probes)
Reactive (correction-on-use, correction-on-failure) [294]
Report
Negative (all dead nodes, nodes recently failed)
Positive (all live nodes; nodes recently recovered) [292]
Topology Sharing: yes/ no [292]
Multicast Tree (explicit, implicit) [267, 295]
Gossip (timeouts; number of contacts) [39]
Corrective Action
Routing
Rerouting actions
(reroute once; route in parallel [291]; reject)
Routing timeouts
(TCP-style, virtual coordinates) [296]
Topology
Update action (evict/ replace/ tag node)
Update timeliness (immediate, periodic[296], delayed [297])
Figure 2: Topology Maintenance in Distributed Hash Tables3.2.3. Ephemeral or Stable Nodes -- O(log n) or O(1) Hops 🦋
Observation C: Most DHTs use O(log n) geometries to suit ephemeral nodes. The O(1) hop DHTs suit stable nodes and deserve more research attention. 👑
Most of the DHTs in Section 3.5 assume that nodes are ephemeral, with expected lifetimes of one to two hours. 🌸 Therefore, they mostly use an O(log n) geometry. The common assumption is that maintenance of full routing tables in the O(1) hop DHTs will consume excessive bandwidth when nodes are continually joining and leaving.
The corollary is that, when they run on stable infrastructure servers [298], most of the DHTs in Section 3.5 are less than optimal -- lookups take many more hops than necessary, wasting latency and bandwidth budgets. 😭 The O(1) hop DHTs suit stable deployments and high lookup rates.
For a churning 1024-node network, Li, et al. concluded that OneHop is superior to Chord, Tapestry, Kademlia, and Kelips in terms of latency and lookup success rate [291]. For a 3000-node network, they concluded that "OneHop is only preferable to Chord when the deployment scenario allows a communication cost greater than 20 bytes per node per second" [291]. 🙈
This apparent limitation needs to be put in context. They assumed that each node issues only one lookup every 10 minutes and has a lifetime of only 60 minutes. 💅 It seems reasonable to expect that in some deployments, nodes will have a lifetime of weeks or more, a maintenance bandwidth of tens of kilobits per second, and a load of hundreds of lookups per second. O(1) hop DHTs are superior in such situations. 🔥
OneHop can scale at least to many tens of thousands of nodes [267]. The recent O(1) hop designs [267, 295] are vastly outnumbered by the O(log n) DHTs in Section 3.5. Research on the algorithms of Figure 2 will also yield improvements in the dependability of the O(1) hop DHTs. 🌈
3.2.4. Simulation and Proof 🔮
Observation D: Although not yet a mature science, the study of DHT dependability is helped by recent simulation and formal development tools. ✨
While there are recent reference architectures [294, 298], much of the DHT literature in Section 3.5 does not lend itself to repeatable, comparative studies. The best comparative work to date [291] relies on the Peer-to-Peer Simulator (P2PSIM) [299]. At the time of writing, it supports more DHT geometries than any other simulator. As the study of DHTs matures, we can expect to see the simulation emphasis shift from geometric comparison to a comparison of the algorithms of Figure 2. 🎀
P2P correctness proofs generally rely on less-than-complete formal specifications of system invariants and events [7, 45, 300]. Li and Plaxton expressed concern that "when many joins and leaves happen concurrently, it is not clear whether the neighbor tables will remain in a 'good' state" [47]. 😭
While acknowledging that guaranteeing consistency in a failure-prone network is impossible, Lynch, Malkhi, et al. sketched amendments to the Chord algorithm to guarantee atomicity [301]. More recently, Gilbert, Lynch, et al. gave a new algorithm for atomic read/write memory in a churning distributed network, suggesting it to be a good match for P2P [302]. Lynch and Stoica show in an enhancement to Chord that lookups are provably correct when there is a limited rate of joins and failures [303].
Fault Tolerant Active Rings is a protocol for active joins and leaves that was formally specified and proven using B-method tools [304]. A good starting point for a formal DHT development would be the numerous informal API specifications [22, 305, 306]. Such work could be informed by other efforts to formally specify routing invariants [307, 308]. 🧠
3.3. Latency 💜
The key metrics for DHT latency are:
- Shortest-Path Distance and Diameter. In graph theory, the shortest-path distance is the minimum number of edges in any path between two vertices of the graph. Diameter is the largest of all shortest-path distances in a graph [309]. Networking synonyms for distance on a DHT are "hop count" and "lookup length". 🍓
- Latency and Latency Stretch. Two types of latency are relevant here -- network-layer latency and overlay latency. Network-layer latency has been referred to as "proximity" or "locality" [24]. Stretch is the cost of an overlay path between two nodes, divided by the cost of the direct network path between those nodes [310]. Latency stretch is also known as the "relative delay penalty" [311]. 🌸
3.3.1. Hop Count and the O(1)-Hop DHTs 🧚
Hop count gives an approximate indication of path latency. O(1)-hop DHTs have path latencies lower than the O(log n)-hop DHTs [291]. This significant advantage is often overlooked on account of concern about the messaging costs to maintain large routing tables (Section 3.2.3). Such concern is justified when the mean node lifetime is only a few hours and the mean lookup interval per node is more than a few seconds (the classic profile of a P2P file-sharing node). 🙈
However, for a large, practical operating range (node lifetimes of days or more, lookup rates of over tens of lookups per second per node, up to ~100,000 nodes), the total messaging cost in O(1) hop DHTs is lower than in O(log n) DHTs [312]. Lookups and routing table maintenance contribute to the total messaging cost. If a deployment fits this operating range, then O(1)-hop DHTs will give lower path latencies and lower total messaging costs. ✨ An additional merit of the O(1)-hop DHTs is that they yield lower lookup failure rates than their O(log N)-hop counterparts [291].
Low hop count can be achieved in two ways: each node has a large O(N) index of nodes; or the object references can be replicated on many nodes. 🦋 Beehive [313], Kelips [39], LAND [310], and Tulip [314] are examples of the latter category. Beehive achieves O(1) hops on average and O(log n) hops in the worst case, by proactive replication of popular objects. Kelips replicates the 'file index'. It incurs O(sqrt(N)) storage costs for both the node index and the file index. LAND uses O(log n) reference pointers for each stored object and an O(log n) index to achieve a worst-case 1+e stretch, where 0<e. The Kelips-like Tulip [314] requires 2 hops per lookup. Each node maintains 2sqrt(N)log(N) links to other nodes and objects are replicated on O(sqrt(N)) nodes. 💖
The DHTs with a large O(N) node index can be divided into two groups: those for which the index is always O(N); and those for which the index opportunistically ranges from O(log n) to O(N). 👑 Linear Hashing (LH*) servers [52], OneHop [267], and 1h-Calot [295] fall into the former category. EpiChord [315] and Accordion [316] are examples of the latter. 🌈
3.3.2. Proximity and the O(log n)-Hop DHTs ✨
okay so if you DON'T go with single-hop DHTs, hop count is kind of a weak way to measure how long a path takes 🙈 one hop can be super slow if it crosses an ocean or bounces off a satellite. so lots of DHT designs try to cut latency by caring about how close nodes are to each other 🌍💖 Gummadi, et al. sorted the proximity methods into three buckets [24]:
- Proximity Neighbor Selection (PNS). The nodes in the routing table get picked based on how long the direct hop to them takes ⏱️ that latency might get measured directly [317], or estimated with one of several synthetic coordinate systems [150, 154, 318]. as a lower bound on PNS performance, Dabek, et al. showed that lookups on O(log n) DHTs take at least 1.5 times the average roundtrip time of the underlying network [154]. 😭🫶
- Proximity Route Selection (PRS). at lookup time, the next-hop node gets chosen based on how long the direct hop to that node takes 🦋 PRS is less effective than PNS, but it might complement it [24]. some of the routing geometries in Section 3.5 don't support PNS and/or PRS [24] 💅
- Proximity Identifier Selection (PIS). here the node identifiers actually indicate geographic position 🗺️ PIS messes with load balancing, makes correlated failures more likely, and isn't used much [24]. honestly kind of a red flag tbh 💀
the Gummadi, et al. proximity study assumed recursive routing, but they suggested PNS would also beat PRS with iterative routing [24] ✨ and Dabek, et al. found that recursive lookups take 0.6 times as long as iterative lookups [150]. recursive main character energy 👑
beyond using proximity info directly, redundancy can help dodge slow paths and servers 🛡️ you can increase the number of replicas [150], use parallel lookups [291, 316], use alternate routes on failure [150], or use multiple gateway nodes to enter the DHT [317]. more options, more slay 💜
3.4. Multicasting 🦋
3.4.1. Multicasting vs. Broadcasting
okay so "multicasting" here just means sending a message to a subset of an overlay's nodes 🎀 those nodes explicitly join and leave this subset, which is called a "multicast group". "broadcasting" is basically a special case of multicasting where the message goes to every node in the overlay 📣 broadcasting leans on overlay membership messages, so it doesn't need any extra group membership messaging 🙌 Castro, et al. said multicasting on structured overlays is either "flooding" (one overlay per group) or "tree-based" (one tree per group) [319]. these are just synonyms for broadcasting and multicasting, respectively 🌸
the first DHT-based multicasting designs were CAN multicast [320], Scribe [241], Bayeux [242], and i3 [231]. they were built on CAN [8], Pastry [2], Tapestry [31], and Chord [7] respectively 🧚 then El-Ansary, et al. came up with the first DHT-based broadcasting scheme [321], and it was based on Chord 💖
multicast trees can be built with reverse-path forwarding or forward-path forwarding 🌈 Scribe uses reverse-path forwarding [241], and Bayeux uses forward-path forwarding [242]. Borg, a multicast design based on Pastry, mixes forward-path and reverse-path forwarding to minimize latency [237] ✨ so many choices, periodt
3.4.2. Motivation for DHT-based Multicasting
multicasting is the perfect bestie for DHT search 🫶 DHTs are naturally great at exact match queries, but with multicasting they can handle way more complex queries. multicasting also makes it possible to spread out and collect global information 🌍
take aggregation queries like minimum, maximum, count, sum, and average (Section 5.4) 📊 a node at the root of a dissemination tree might multicast a query like that [322]. the leaf nodes send their local results back toward the root node, and each successive parent aggregates the results so the root can eventually compute the global result 🌳 these kinds of queries can help monitor the capacity and health of the overlay itself 💅
so why even bother with structured overlays for multicasting? 🤔 back in Section 2.1 we saw that Gnutella can multicast complex queries without them [4]. Castro, et al. asked the iconic question, "Should we build Gnutella on a structured overlay?" [259]. they admitted their study was preliminary, but they did conclude that "we see no reason to build Gnutella on top of an unstructured overlay" [259] 👑 the supposedly high maintenance costs of structured overlays were outweighed by the query cost savings. the structured overlay made sure nodes were only visited once during a complex query, and it also helped accurately limit the total number of nodes visited 🎯
Pai, et al. acknowledged that multicast trees based on structured overlays help with simple routing rules, low delay, and low delay variation [323] ✨ but they went with unstructured, gossip-based multicasting for reliability reasons 🫠 here's the drama: data loss near the tree root affects all subtended nodes, interior node failures have to be repaired quickly, and interior nodes end up disseminating more than their fair share of traffic, which gives leaf nodes a "free ride" 🙈 the most promising research direction is to improve on the Bimodal Multicasting approach [324]. it combines the bandwidth efficiency and low latency of structured, best-effort multicasting trees with the reliability of unstructured gossip protocols 🦋 a true glow-up
3.4.3. Design Issues
none of the early structured overlay multicast designs addressed all of the following issues [325] 😭
- Heterogeneous Node Capacity. nodes are not all the same 💅 they differ in processing, memory, and network capacity, and multicast throughput is mostly decided by the node with the smallest throughput [325]. to limit the multicasting load on a node, one might cap its out-degree. if that same node gets more join requests, it refers them to its children ("pushdown") [240]. Bharambe, et al. explored several pushdown strategies but found them inadequate for dealing with heterogeneity [326]. they concluded the heterogeneity issue is still open and should be addressed before deploying DHTs for high-bandwidth multicasting applications 🔥 independently, Zhang et al. partially tackled heterogeneity by letting nodes in their CAM-Chord and CAM-Koorde designs vary out-degree according to the node's capacity [325]. however, they didn't mention the "pushdown" issue at all. they never described topology maintenance when the out-degree limit is reached 💀
- Reliability (Dynamic Membership). if a multicast tree is going to be resilient, it has to survive dynamic membership 🛡️ there are a few ways to handle that: make sure the root node of the multicasting tree doesn't handle all join or leave requests for the group [242]; use multiple interior-node-disjoint trees to avoid single points of failure in tree structures [322]; or split the root node into several replicas and partition members across them [241]. for example, Bayeux requires the root node to track all group membership changes, whereas Scribe doesn't [241] 🙃 CAN-multicast uses a single, well-known host to bootstrap the join operations [320]. the earliest DHT-based broadcasting work by El-Ansary, et al. didn't address dynamic membership at all [321]. Ghodsi, et al. tackled it in a later paper, giving two broadcast algorithms that accommodate routing table inconsistencies [327]. one of them gets a more optimal multicasting network but at the cost of greater correction overhead 🧩 and Splitstream, based on Scribe and Pastry, redundantly stripes content across multiple interior-node-disjoint multicast trees, so if one interior node fails, only one stripe is lost [240] 🌈 that's a whole vibe
- Large Any-Source Multicast Groups. any group member should be allowed to send multicast messages 📣 and the group should scale to a very large number of hosts 🌏 CAN-based multicast was the first application-level multicast scheme to scale to groups of several thousands of nodes without restricting the service model to a single source [320]. Bayeux scales to large groups but has a single root node for each multicast group. it only supports the any-source model by having the root node act as a reflector for multiple senders [242] 🦋
3.5. Routing Geometries 🗺️
okay so in Sections 3.5.1 to 3.5.6, we're going to introduce the main geometries for simple key lookup and survey their robustness mechanisms 🧚✨ stay tuned, it's about to get SO good 💖
3.5.1. Plaxton Trees (Pastry, Tapestry) 🌳
Okay so bestie, work started in March 2000 on Tapestry [6, 155], a structured, fault-tolerant, wide-area Dynamic Object Location and Routing (DOLR) system 🦋. DHTs fix where replicas live, but a DOLR API lets apps control object placement [31] 💅. Tapestry's basic location and routing scheme follows Plaxton, Rajaraman, and Richa (PRR) [30], but it fixes PRR's robustness shortcomings from Section 3.1 🔥. PRR gives each object one root node, while Tapestry uses several so there isn't a single point of failure 🙈. Unlike PRR, Tapestry lets nodes be inserted and deleted ✨. PRR needed a total ordering of nodes, but Tapestry uses 'surrogate routing' to pick root nodes one step at a time 🧚. The PRR algorithm doesn't deal with congestion, but Tapestry can put object copies close to the nodes making lots of queries 👑. PRR nodes only know about the nearest replica, but Tapestry nodes can choose from a set of replicas (for example, to get the most up to date one) 💖. To detect routing faults, Tapestry uses TCP timeouts and UDP heartbeats, falls back on sequential secondary neighbours for rerouting, and has a 'second chance' window so recovery can happen without the overhead of a full node insertion 😭. Its dependability was measured on a testbed of about 100 machines and on simulations of about 1000 nodes 🌈. Successful routing rates and maintenance bandwidths were measured during instantaneous failures and ongoing churn [31] 🎀.
Pastry, like Tapestry, uses Plaxton-like prefix routing [2] 🌸. Just like Tapestry, Pastry nodes keep O(log n) neighbours and route to a target in O(log n) hops 💅. The only real difference is how it handles network locality and replication [2] 🫶. Each Pastry node keeps a 'leaf set' and a 'routing table' 🦋. The leaf set holds l/2 node IDs on either side of the local node ID in the node ID space ✨. The routing table, in row r, column c, points to a node ID that shares the same r-digit prefix as the local node but has a digit of c in position r+1 🍓. A Pastry node periodically probes its leaf set and routing table nodes, with a period of Tls for the leaf set and Trt for the routing table, and a timeout of Tout ⭐. Mahajan, Castry, et al. looked at the trade-offs between reliability and maintenance cost in terms of l, Tls, Trt, and Tout [328] 🧐. They concluded that earlier worries about excessive maintenance cost in a churning P2P network were unfounded, but suggested follow-up work covering a wider range of reliability targets, maintenance costs, and probe periods 💜. Rhea Geels, et al. concluded that existing DHTs fail at high churn rates [329] 😭. Building on a Pastry implementation from Rice University, they found that most lookups failed to complete when churn was excessive 💀. They guessed that short-lived nodes often left the network while lookups hadn't timed out yet, but no evidence was given to back that up 🙈. They identified three design issues that affect DHT performance under churn: reactive versus periodic recovery of peers, lookup timeouts, and choice of nearby neighbours 🔥. Reactive recovery added traffic to links that were already congested, so the authors used periodic recovery in their design 🌊. For lookup timeouts, they backed an exponentially weighted moving average of each neighbour's response time, rather than a fixed timeout or 'virtual coordinate' schemes 👑. For choosing nearby neighbours, 'global sampling' worked better than simply sampling a 'neighbour's neighbours' or 'inverse neighbours' 🎀. Castro, Costa, et al. refuted the idea that DHTs can't cope with high churn rates [330] 💅. By adding methods for continuous detection and repair, their MSPastry implementation got shorter routing paths and a maintenance overhead of less than half a message per second per node 🏆.
There have been newer proposals built on these early Plaxton-like schemes 🧚. Kademlia uses a bit-wise exclusive or (XOR) metric for the 'distance' between 160-bit node identifiers [45] 🦋. Each node keeps a list of contact nodes for each section of the node space between 2^i and 2^(i+1) away from itself (0.i<160) 🌸. Longer-lived nodes are deliberately given preference on this list, since it's been found in Gnutella that the longer a node has been active, the more likely it is to stay active ⏳. Like Kademlia, Willow uses the XOR metric [32] 💖. It has a Tree Maintenance Protocol that 'zippers' together broken segments of a tree 🤌. Where other schemes use DHT routing to add new peers inefficiently, Willow can merge disjoint or broken trees in O(log n) parallel operations ✨.
3.5.2. Rings (Chord, DKS) 💍
Chord is the prototypical DHT ring, so let's sketch how it works first 🫶. Chord maps nodes and keys onto an identifier ring [7, 34] ⭕. It supports one main operation: finding a node with the given key 🔑. It uses Consistent Hashing (Section 3.1) to minimise disruption of keys when nodes join and leave the network 🎀. However, Chord peers only need to track O(log n) other peers, not all peers as in the original consistent hashing proposal [49] 😤. It enables concurrent node insertions and deletions, improving on PRR 🔥. Compared to Pastry, it has a simpler join protocol 🧠. Each Chord peer tracks its predecessor, a list of successors, and a finger table 🌈. Using the finger table, each hop covers at least half the remaining distance around the ring to the target node, giving an average lookup hop count of (1/2)log n(base 2) 📉. Each Chord node runs a periodic stabilization routine that updates predecessor and successor pointers to cater to newly added nodes 🔄. All successors of a given node need to fail for the ring to fail 😬. A departure could be treated the same as a failure, but a departing Chord node first notifies its predecessor and successors, which improves performance 💜.
In their definitive paper, Chord's inventors critiqued its dependability under churn [34] 🧐. They proved things about how the Chord network behaves when nodes fail in a stable network, but stressed that such proofs aren't enough for the general case of a perpetually churning network 💀. An earlier paper had asked, "For lookups to be successful during churn, how regularly do the Chord stabilization routines need to run?" [331] 🤔. Stoica, Morris, et al. modelled a range of node join/departure rates and stabilization periods for a Chord network of 1000 nodes 🧪. They measured the number of timeouts (caused by a finger pointing to a departed node) and lookup failures (caused by nodes that temporarily point to the wrong successor during churn) 📊. They also modelled the 'lookup stretch', the ratio of the Chord lookup time to the optimal lookup time on the underlying network 📏. They showed that recursive lookups have a latency advantage over iterative lookups, but there's still room to reduce delay ⚡. For further work, the authors proposed improving resilience to network partitions by using a small set of known nodes or 'remembered' random nodes 🧠. To reduce the number of messages per lookup, they suggested increasing the size of each step around the ring, done via a larger number of fingers at each node 🪜. Much of the paper assumed independent, equally likely node failures, but analysis of correlated node failures, caused by massive site or backbone failures, will matter more in some deployments 🌪️. The paper didn't try to recommend a fixed optimal stabilization rate 🙅. Liben-Nowell, Balakrishnan, et al. had suggested that the optimum stabilization rate might evolve according to measurements of peers' behaviour [331], but no such mechanism has been devised yet 🫠.
Alima, El-Ansary, et al. considered the communication costs of Chord's stabilization routines, called 'active correction', to be excessive [332] 😤. Two other robustness issues also motivated their Distributed K-ary Search (DKS) design, which is similar to Chord 🌟. Firstly, the total system should evolve toward an optimum balance between the number of peers, the lookup hop count, and the size of the routing table ⚖️. Secondly, lookups should be reliable: P2P algorithms should be able to guarantee a successful lookup for key/value pairs that have been inserted into the system 🔐. A similar lookup-correctness issue was raised elsewhere by one of Chord's authors: "Is it possible to augment the data structure to work even when nodes (and their associated finger lists) just disappear?" [333] 🫣. Alima, El-Ansary, et al. asserted that P2Ps using active correction, like Chord, Pastry, and Tapestry, can't give that kind of guarantee 🚫. They propose an alternate 'correction-on-use' scheme, where expired routing entries are corrected by information piggybacking on lookups and insertions 🎁. A prerequisite is that lookup and insertion rates are significantly higher than node arrival, departure, and failure rates 📈. Correct lookups are guaranteed in the presence of simultaneous node arrivals, or up to f concurrent node departures, where f is configurable 💅.
3.5.3. Tori (CAN) 🍩
Ratnasamy, Francis, et al. developed the Content-Addressable Network (CAN), another early DHT that's widely referenced alongside Tapestry, Pastry, and Chord [8, 334] 🌷. It's arranged as a virtual d-dimensional Cartesian coordinate space on a d-torus 🧩. Each node is responsible for a zone in this coordinate space 🗺️. The designers used a heuristic thought to be important for large, churning P2P networks: keep the number of neighbours independent of system size 🧘. So its design differs a lot from Pastry, Tapestry, and Chord 💅. Where those have O(log n) neighbours per node and O(log n) hops per lookup, CAN has O(d) neighbours and an O(dn^(1/d)) hop count 📐. When CAN's system-wide parameter d is set to log(n), CAN converges to their profile 🪄. If the number of nodes grows, a major rearrangement of the CAN network may be required [151] 🏗️. The CAN designers considered building on PRR, but opted for the simple, low-state-per-node CAN algorithm instead 🫶. They had reasoned that a PRR-based design wouldn't perform well under churn, since node departures and arrivals would affect a logarithmic number of nodes [8] 😵💫.
There have been preliminary assessments of CAN's resilience 🛟. When a node leaves CAN in an orderly fashion, it passes its own Virtual ID (VID), its neighbours' VIDs and IP addresses, and its key/value pairs to a takeover node 🎁. If a node leaves abruptly, its neighbours send recovery messages towards the designated takeover node 🚨. CAN makes sure the recovery messages reach the takeover node, even if nodes die simultaneously, by maintaining a VID chain with Chord's stabilization algorithm 🔗. Some initial 'proof of concept' resilience simulations were run using the Network Simulator (NS) [335] for up to a few hundred nodes 🧪. Average hop counts and lookup failure probabilities were plotted against the total number of nodes for various node failure rates [8] 📈. The CAN team documented several open research questions about state/hop count trade-offs, resilience, load, locality, and heterogeneous peers [44, 334] 🌈✨
3.5.4. Butterflies (Viceroy) 🦋
okay so Viceroy approximates a butterfly network [46] 🦋 It generally has constant degree like CAN, and like Chord, Tapestry, and Pastry, it has logarithmic diameter ✨ The glow-up is that its diameter is better than CAN's and its degree is better than Chord's, Tapestry's, and Pastry's 💅 Like most DHTs, it uses Consistent Hashing 🫶 When a peer joins the Viceroy network, it gets a random but permanent 'identity' and picks its 'level' within the network 🎀 Each peer keeps general ring pointers ('predecessor' and 'successor'), level ring pointers ('nextonlevel' and 'prevonlevel'), and butterfly pointers ('left', 'right', and 'up') 🌸 When a peer leaves, it usually hands its key pairs to a successor and tells other peers to find a replacement 🧚
The Viceroy paper kinda skipped over robustness 🙈 It explicitly assumed that peers do not fail [46]. It also assumed that join and leave operations don't overlap, so it could dodge the mess of concurrency mechanisms like locking 😭 Kaashoek and Karger were pretty critical of Viceroy's complexity [37], and they pointed out its fault-tolerance blind spot 💀 Li and Plaxton suggested that constant-degree algorithms deserve more attention [47] 👑 They gave a few pros and cons: a limited degree may increase the risk of a network partition, or make it harder to use local neighbours (for the simple reason that there are less of them). On the flip side, it may be easier to reason about the correctness of fixed-degree networks 💜 One of the Viceroy authors has since proposed constant-degree peers in a two-tier, locality-aware DHT [310]. The lower degree each lower-tier peer maintains purportedly improves network adaptability 🌈 Another Viceroy author has since explored an alternative bounded-degree graph for P2P, namely the de Bruijn graph [336] 🦋
3.5.5. de Bruijn (D2B, Koorde, Distance Halving, ODRI) 🌈
de Bruijn graphs have had loads of refinements since they first showed up [337, 338] 🤓 Schlumberger was the first to use them for networking [339]. Two research teams independently came up with the 'generalized' de Bruijn graph, which fits a flexible number of nodes in the system [340, 341] ✨ Rowley and Bose studied fault-tolerant rings overlaid on the de Bruijn graph [342]. Lee, Liu, et al. devised a two-level de Bruijn hierarchy, where clusters of local nodes are interconnected by a second-tier ring [343] 🍓
Many of the algorithms we've talked about are 'greedy', meaning each time a query is forwarded, it gets closer to the destination 🏃♀️ Unfortunately, greedy algorithms are generally suboptimal. For a given degree, the routing distance is longer than it needs to be [344] 😭 Unlike these earlier P2P designs, de Bruijn graphs of degree k achieve an asymptotically optimal diameter of log n, where n is the number of nodes in the system, and k can be varied to improve resilience 💖 If there are O(log n) neighbours per node, the de Bruijn hop count is O(log n/log log n) 🧮 To show how big the practical win is, picture a network with one million nodes of degree 20: Chord has a diameter of 20, while de Bruijn has a diameter of 5 [36] 🔥 In 2003 there was a quick succession of de Bruijn proposals: D2B [345], Koorde [37], Distance Halving [132, 336], and the Optimal Diameter Routing Infrastructure (ODRI) [36] 🎀
Fraigniaud and Gauron kicked off the D2B design with an informal problem statement: keys should be evenly distributed, lookup latency should be small, traffic load should be evenly distributed, and updates of routing tables and redistribution of keys should be fast when nodes join or leave the network 🫶 They defined a node's "congestion" as the probability that a lookup will traverse it 👑 Besides its optimal de Bruijn diameter, they highlighted D2B's merits: a constant expected update time when nodes join and leave (O(log n) with high probability (w.h.p.)), and an expected node congestion of O((log n)/n) (O(((log n)^2)/n) w.h.p.) [345] 💅 D2B's resilience only got a passing mention 🙈
Koorde extends Chord to reach the optimal de Bruijn degree/diameter trade-off above [37] ✨ Unlike D2B, Koorde doesn't constrain how node identifiers are picked. Also unlike D2B, it handles concurrent joins, by extending Chord's functionality 🧚 Kaashoek and Karger looked at Koorde's resilience against a pretty harsh failure scenario, quoting: "in order for a network to stay connected when all nodes fail with probability of 1/2, some nodes must have degree omega(log n)" [37] 💀 They sketched a mechanism to raise Koorde's degree for that stricter fault tolerance, but that means losing de Bruijn's constant degree advantage 😭 Similarly, to get a constant-factor load balance, Koorde would have to give up its degree optimality 🌸 They suggested that being able to trade degree (and so maintenance overhead) against expected hop count may matter a lot for churning systems 🔥 They also flagged an open problem: find a load-balanced, degree-optimal DHT 🦋 Datta, Girdzijauskas, et al. showed that for arbitrary key distributions, de Bruijn graphs fail to meet the dual goals of load balancing and search efficiency [346] 🙈 They asked the question, "(Is there) a constant routing table sized DHT which meets the conflicting goals of storage load balancing and search efficiency for an arbitrary and changing key distribution?" 🤔
Distance Halving was also inspired by de Bruijn [336] and shares its optimal diameter 💜 Naor and Wieder argued for a two-step "continuous-discrete" approach to its design. The correctness of its algorithms is proven in a continuous setting, and then the algorithms are mapped to a discrete space 🌈 The source x and target y are points on the continuous interval [0,1), and data items are hashed to that same interval 🎀 <str> is a string that decides how messages leave any point on the ring: if bit t of the string is 0, the left leg is taken, and if it is 1, the right leg is taken. <str> grows by one bit each hop, which gives a sequence for stepping around the ring 🧚 A lookup has two phases. In the first, the lookup message (carrying the source, target, and the random string) hops toward the midpoint of the source and target. On each hop, the distance between <str>(x) and <str>(y) gets halved, thanks to the specific 'left' and 'right' functions ✨ In the second phase, the message steps 'backward' from the midpoint to the target, removing the last bit in <str> at each hop 💖 'Join' and 'leave' algorithms were outlined, but recovery times and message load under churn weren't considered 😭 Using the Distance Halving properties, the authors devised a caching scheme to relieve congestion in a large P2P network. They also modified the algorithm to be more robust against random faults [132] 👑
Solid comparisons of DHT resilience are rare, but Loguinov, Kumar, et al. actually give us one in their ODRI paper [36] 🫶 They compare Chord, CAN, and de Bruijn on routing performance, graph expansion, and clustering. To start, they give the optimal diameter (the maximum hop count between any two nodes in the graph) and the average hop count for graphs of fixed degree 🍓 De Bruijn graphs converge to both optima and beat Chord and CAN on both counts 🔥 These optima affect both delay and aggregate lookup load. They present two clustering measures, edge expansion and node expansion, which are interesting for resilience 🌸 Unfortunately, after decades of de Bruijn research, there's still no exact solution 🙈 De Bruijn was also shown to be superior in terms of path overlap: "de Bruijn automatically selects backup paths that do not overlap with the best shortest path or with each other" [36] 💅
3.5.6. Skip Graphs 🧚
Skip Graphs have been pursued by two research camps [38, 41] 👑 They build on the earlier Skip Lists [347, 348]. Unlike earlier balanced trees, the Skip List is probabilistic: its insert and delete operations don't need tree rearrangements, so they're faster by a constant factor ✨ A Skip List is made of layers of ordered linked lists. All nodes participate in the bottom layer 0 list. Some of those nodes join the layer 1 list with some fixed probability. A subset of the layer 1 nodes joins the layer 2 list, and so on 🌈 A lookup can zip through the list by traversing the sparse upper layers until it's close to, or at, the target 🏃♀️ Unfortunately, nodes in the upper layers of a Skip List are potential hot spots and single points of failure 💀 Unlike Skip Lists, Skip Graphs provide multiple lists at each level for redundancy, and every node participates in one of the lists at each level 🎀
Each node in a Skip Graph has theta(log n) neighbours on average, like some of the preceding DHTs 🫶 The Skip Graph's main edge over the DHTs is its support for prefix and proximity search. DHTs hash objects to a random point in the graph, so they give no guarantees about where the data is stored. Nor do they guarantee that the path to the data stays within one administration as far as possible [38] 😭 Skip Graphs, on the other hand, allow location-sensitive name searches. For example, to find the document docname on the node user.company.com, the Skip Graph might step through its ordered lists for the prefix com.company.user [38] 🍓 Alternatively, to find an object with a numeric identifier, an algorithm might search the lowest layer of the Skip Graph for the first digit, the next layer for the next digit, and so on until all digits are resolved 🧮 Being ordered, Skip Graphs also make range searches easy 💖 In each of these examples, the Skip Graph can be arranged so the path to the target, as far as possible, stays within an administrative boundary 👑 If one administration is detached from the rest of the Skip Graph, routing can continue within each partition 🌸 Mechanisms have been devised to merge disconnected segments [157], though for now, segments are re-merged one at a time. A parallel merge algorithm has been flagged for future work 🔥
The advantages of Skip Graphs come at a cost, bestie 💀 To provide range queries and data placement flexibility, Skip Graph nodes need many more pointers than their DHT counterparts, and more pointers means more maintenance traffic 😭
Another shortcoming of at least one of the early proposals was that no algorithm was given to assign keys to machines. As a result, there are no guarantees on system-wide load balancing or on the distance between adjacent keys [100] 🙈 Aspnes, Kirsch, et al. have recently devised a scheme to cut the inter-machine pointer count from O(mlogm), where m is the number of data elements, to O(nlog n), where n is the number of nodes [100] 🎀 They proposed a two-layer scheme: one layer for the Skip Graph itself, and a second 'bucket layer'. Each machine is responsible for a number of buckets, and each bucket elects a representative key. Nodes locally adjust their load: they accept additional keys if they're below their threshold, or disperse keys to nearby nodes if they're above it 🧚 There still appear to be numerous open issues. Simulations have been done but analysis is outstanding, mechanisms are required to handle the arrival and departure of nodes, and there were only brief hints about how to handle nodes with different capacities 🥺🫶
4. Semantic Index ✨
okay so semantic indexes are all about capturing how objects relate to each other 🦋 DHTs are the semantic-free crew. They have firmer theoretic foundations and they guarantee that a key can be found if it exists, which is iconic. But on their own they don't capture the relationship between a document's name and its content or metadata 🙈 Semantic P2P designs do capture that. The catch is that their design is often driven by heuristics, so they may not guarantee that scarce items will be found 💀
so what could semantically indexed P2Ps add to an already crowded field of distributed information architectures? 🤔 On one extreme, you've got the distributed relational database management systems (RDBMSs), with their strong consistency guarantees [284]. They give you strong data independence, the flexibility of SQL queries, and strong transactional semantics -- Atomicity, Consistency, Isolation and Durability (ACID) [349] 💅 They also guarantee the query response is complete, meaning every matching result comes back. The price is performance 😭 They scale to perhaps 1000 nodes, as shown in Mariposa [350, 351], or they need query caching front ends to keep the load under control [284]. Database research has "arguably been cornered into traditional, high-end, transactional applications" [72] 🥲
then there are distributed file systems, like the Network File System (NFS) or the Serverless Network File Systems (xFS). They have little data independence, low-level file retrieval interfaces, and varied consistency [284] 🧚
and today's eclectic mix of Content Distribution Networks (CDNs) generally takes the load off primary servers by redirecting Web requests to a nearby replica 🌈 Some of them intercept the HTTP requests at the DNS level and then use consistent hashing to find a replica [23]. Consistent hashing was actually a forerunner to the DHT approaches above, so CDNs are generally stuck with the same simple key lookups 🍓
the opportunity for semantically indexed P2Ps, then, is to provide the best of all these worlds, but on a whole new level 👑
so the opportunity is to provide:
- a) graduated data independence, consistency, and query flexibility, and
- b) probabilistically complete query responses, across
- c) very large numbers of low-cost, geographically distributed, dynamic nodes. 🫶
4.1. Keyword Lookup
okay P2P keyword lookup makes the most sense once you look at two things: the structure of the underlying index, and the algorithms that route queries over that index 🌸 Figure 3 sums up the next few paragraphs by sorting the keyword query algorithms, index structures, and metrics into buckets ✨ Honestly, the research has mostly been obsessed with scalability, not dependability 💅 Very few studies have actually measured how much network churn messes things up. One exception is the work by Chawathe, et al. on the Gia system [61]. Gia combined algorithms from Figure 3 (receiver-based flow control, biased random walk, and one-hop replication) and got 2-4 orders of magnitude improvement in query success rates in churning networks 🔥 that's a glow-up!!
QUERY
Query routing
Flooding: Peers only index local files so queries must propagate
widely [4]
Policy-based: Choice of the next hop node: random; most/least
recently used; most files shared; most results [265, 352]
Random walks: Parallel [67] or biased random walks [61, 66]
Query forwarding
Iterative: Nodes perform iterative unicast searches of ultrapeers,
until the desired number of results is achieved. See Gnutella
UDP Extension for Scalable Searches (GUESS) [265, 353]
Recursive
Query flow control
Receiver-controlled: Receivers grant query tokens to senders, so
as to avoid overload [61]
Reactive: sender throttles queries when it notices receivers are
discarding packets [61, 66]
Dynamic Time To Live: In the Dynamic Query Protocol, the sender
adjusts the time-to-live on each iteration based on the number
of results received, the number of connections left, and the
number of nodes already theoretically reached by the search [354]
INDEX
Distribution
Compression: Leaf nodes periodically send ultrapeers compressed
query routing tables, as in the Query Routing Protocol [260]
One hop replication: Nodes maintain an index of content on their
nearest neighbors [61, 352]
Partitioning
By document [210]
By keyword: Use an inverted list to find a matching document,
either locally or at another peer [21]. Partition by keyword
sets [355]
By document and keyword: Also called Multi-Level Partitioning [21]
METRIC
Query load: Queries per second per node/link [65, 265]
Degree: The number of links per node [66, 352]. Early P2P networks
approximated power-law networks, where the number of nodes with L
links is proportional to L^(-k), where k is a constant [65]
Query delay: Reported in terms of time and hop count [61, 66]
Query success rate: The "Collapse Point" is the per-node query rate
at which the query success rate drops below 90% [61]. See
also [61, 265, 352].
Figure 3: Keyword Lookup in P2P Systems4.1.1. Gnutella Enhancements ✨
okay so bestie, perhaps the most widely referenced P2P system for simple keyword match is Gnutella [4] 🌸 Gnutella queries contain a string of keywords, and Gnutella peers answer when they have files whose names contain all the keywords 💖 As discussed in Section 2.1, early versions of Gnutella did not forward the document index 🙈 Queries were flooded and peers searched their own local indexes for filename matches 💀 An early review highlighted numerous areas for improvement [65] 🧚 It was estimated that the query traffic alone from 50,000 early-generation Gnutella nodes would amount to 1.7% of the total U.S. Internet backbone traffic at December 2000 levels 😭 It was speculated that high-degree Gnutella nodes would impede dependability 🫶 An unnecessarily high percentage of Gnutella traffic crossed Autonomous System (AS) boundaries -- a locality mechanism may have found suitable nearby peers 🍓
Fortunately, there have since been numerous enhancements within the Gnutella Developer Forum ✨ At the time of writing, it has been reported that Gnutella has almost 350,000 unique hosts, of which nearly 90,000 accept incoming connections [356] 🔥 One of the main improvements is that an index of filename keywords, called the Query Routing Table (QRT), can now be forwarded from 'leaf peers' to its 'ultrapeers' [260] 👑 Ultrapeers can then ensure that the leaves only receive queries for which they have a match, dramatically reducing the query traffic at the leaves 💅 Ultrapeers can have connections to many leaf nodes (~10-100) and a small number of other ultrapeers (<10) [260] 🌈 Originally, a leaf node's QRT was not forwarded by the parent ultrapeer to other ultrapeers 🎀 More recently, there has been a proposal to distribute aggregated QRTs amongst ultrapeers [357] 🦋 To further limit traffic, QRTs are compressed by hashing, according to the Query Routing Protocol (QRP) specification [281] ✨ This same specification claims QRP may reduce Gnutella traffic by orders of magnitude, but cautions that simulation is required before mass deployment 💜 A known shortcoming of QRP was that the extent of query propagation was independent of the popularity of the search terms 😭 The Dynamic Query Protocol addressed this [358] 💖 It required leaf nodes to send single queries to high-degree ultrapeers that adjust the queries' time-to-live (TTL) bounds according to the number of received query results 🌸 An earlier proposal, called the Gnutella UDP Extension for Scalable Searches (GUESS) [353], similarly aimed to reduce the number of queries for widely distributed files 🧚 GUESS reuses the non-forwarding idea (Section 2) 🫶 A GUESS peer repeatedly queries single ultrapeers with a TTL of 1, with a small timeout on each query to limit load 🍓 It chooses the number of iterations and selects ultrapeers so as to satisfy its search needs 👑 For adaptability, a small number of experimental Gnutella nodes have implemented eXtensible Markup Language (XML) schemas for richer queries [359, 360] 💅 None of the above Gnutella proposals explicitly assess robustness 💀
The broader research community has recently been leveraging aspects of the Gnutella design 🌈 Lv, Ratnasamy, et al. exposed one assumption implicit in some of the early DHT work -- that designs "such as Gnutella are inherently not scalable, and therefore should be abandoned" [66] 🎀 They argued that by making better use of the more powerful peers, Gnutella's scalability issues could be alleviated 🦋 Instead of its flooding mechanism, they used random walks ✨ Their preliminary design to bias random walks towards high capacity nodes did not go as far as the ultrapeer proposals in that the indexes did not move to the high-capacity nodes 💜 Chawathe, Ratnasamy, et al. chose to extend the Gnutella design with their Gia system, in response to the perceived shortcomings of DHTs in Section 1.2 [61] 😭 Compared to the early Gnutella designs, they incorporated several novel features 💖 They devise a topology adaptation algorithm so that most peers are attached to high-degree peers 🌸 They use a random walk search algorithm, in lieu of flooding, and bias the query load towards higher-degree peers 🧚 For 'one-hop replication', they require all nodes to keep pointers to content on adjacent peers 🫶 To implement a receiver-controlled token-based flow control, a peer must have a token from its neighbouring peer before it sends a query to it 🍓 Chawathe, Ratnasamy, et al. show by simulations that the combination of these features provides a scalability improvement of three to five orders of magnitude over Gnutella "while retaining significant robustness" 🔥 The main robustness metrics they used were the 'collapse point' query rate (the per-node query rate at which the successful query rate falls below 90%) and the average hop count immediately prior to collapse 👑 Their comparison with Gnutella did not take into account the Gnutella enhancements above -- this was left as future work 💅 Castro, Costa, and Rowstron argued that if Gnutella were built on top of a structured overlay, then both the query and overlay maintenance traffic could be reduced [259] 🌈 Yang, Vinograd, et al. explore various policies for peer selection in the GUESS protocol, since the issue is left open in the original proposal [265] 🎀 For example, the peer initiating the query could choose peers that have been "most recently used" or that have the "most files shared" 🦋 Various policy pitfalls are identified 💀 For example, good peers could be overloaded, victims of their own success ✨ Alternatively, malicious peers could encourage the querying peer to try inactive peers 🙈 They conclude that a "most results" policy gives the best balance of robustness and efficiency 💜 Like Castro, Costa, and Rowstron, they concentrated on the static network scenario 😭 Cholvi, Felber, et al. very briefly describe how similar "least recently used" and "most often used" heuristics can be used by a peer to select peer 'acquaintances' [352] 💖 They were motivated by the congestion associated with Gnutella's TTL-limited flooding 🌸 Recognizing that the busiest peers can quickly become overloaded central hubs for the entire network, they limit the number of acquaintances for any given peer to 25 🧚 They sketch a mechanism to decrement a query's TTL multiple times when it traverses "interested peers" 🫶 In summary, these Gnutella-related investigations are characterized by a bias for high-degree peers and very short directed query paths, a disdain for flooding, and concern about excessive load on the 'better' peers 🍓 Generally, the robustness analysis for dynamic networks (content updates and node arrivals/departures) remains open 👑
4.1.2. Partition-by-Document, Partition-by-Keyword 💅
One aspect of P2P keyword search systems has received particular attention: should the index be partitioned by document or by keyword? 🌈 The issue affects scalability 🎀 To be partitioned by document, each node has a local index of documents for which it is responsible 🦋 Gnutella is a prime example ✨ Queries are generally flooded in systems partitioned by document 💜 On the other hand, a peer may assume responsibility for a set of keywords 😭 The peer uses an inverted list to find a matching document, either locally or at another peer 💖 If the query contains several keywords, inverted lists may need to be retrieved from several different peers to find the intersection [21] 🌸 The initial assessment by Li, Loo, et al. was that the partition-by-document approach was superior [210] 🧚 For one scenario of a full-text Web search, they estimated the communications costs to be about six times higher than the feasible budget 🫶 However, wanting to exploit prior work on inverted list intersection, they studied the partition-by-keyword strategy 🍓 They proposed several optimizations that put the communication costs for a partition-by-keyword system within an order of magnitude of feasibility 👑 There had been a couple of prior papers that suggested partitioned-by-keyword designs incorporate DHTs to map keywords to peers [355, 361] 💅 In Gnawali's Keyword-set Search System (KSS), the index is partitioned by sets of keywords [355] 🌈 Terpstra, Behnel, et al. point out that by keeping keyword pairs or triples, the number of lists per document in KSS is squared or tripled [362] 🎀 Shi, Guangwen, et al. interpreted the approximations of Li, Loo, et al. to mean that neither approach is feasible on its own [21] 🦋 Their Multi-Level Partitioning (MLP) scheme incorporates both partitioning approaches ✨ They arrange nodes into a group hierarchy, with all nodes in the single 'level 0' group, and with the same nodes sub-divided into k logical subgroups on 'level 1' 💜 The subgroups are again divided, level by level, until level l 😭 The inverted index is partitioned by document between groups and by keyword within groups 💖 MLP avoids the query flooding normally associated with systems partitioned by document, since a small number of nodes in each group process the query 🌸 It reduces the bandwidth overheads associated with inverted list intersection in systems partitioned solely by keyword, since groups can calculate the intersection independently over the documents for which they are responsible 🧚 MLP was overlaid on SkipNet, per Section 3.5.6 [38] 🫶 Some initial analyses of communications costs and query latencies were provided 🍓
4.1.3. Partial Search, Exhaustive Search 🦋
Much of the research above addresses partial keyword search 💅 Daswani, et al. highlighted the open problem of efficient, comprehensive keyword search [25] 🌈 How can exhaustive searches be achieved without flooding queries to every peer in the network? 🎀 Terpstra, Behnel et al. couched the keyword search problem in rendezvous terms: dynamic keyword queries need to 'meet' with static document lists [362] 💜 Their Bitzipper scheme is partitioned by document 😭 They improved on full flooding by putting document metadata on 2sqrt(n) nodes and forwarding queries through only 6sqrt(n) nodes 💖 They reported that Bitzipper nodes need only 1/166th of the bandwidth of full-flooding Gnutella nodes for an exhaustive search 🌸 An initial comparison of query load was given 🧚 There was little consideration of either static or dynamic resilience; that is, of nodes failing, of documents continually changing, or of nodes continually joining and leaving the network 🫶
🎀 Okay, that's the keyword lookup section wrapped up! More parts are coming, so stay tuned, bestie 🦋✨
4.2. Information Retrieval ✨
okay so the field of Information Retrieval (IR) has been glowing up since the 1950s 🌸 [363]. Someone formalized a taxonomy for IR models [262], and it has four elements 💅: a representation of documents in a collection, a representation of user queries, a framework describing relationships between document representations and queries, and a ranking function that quantifies an ordering amongst documents for a particular query. Three main issues drive current IR research -- information relevance, query response time, and user interaction with IR systems 🎀. The dominant IR trends for searching large text collections are also threefold [262]. Collections are getting huge 📈. Search mechanisms are getting more complicated so they can exploit document structure, handle heterogeneous document collections, and deal with document errors. Compression is so in right now -- it may be quicker to search compact text or retrieve it from external devices 🧚. In a distributed IR system, query processing has four parts. Firstly, particular collections are targeted for the search. Secondly, queries are sent to the targeted collections. Then the queries are evaluated at the individual collections. Finally, the results from the collections are collated ✨.
So how do P2P networks differ from distributed IR systems? 🤔 Bawa, Manku, et al. presented four differences [62]. They suggested that a P2P network is typically larger, with tens or hundreds of thousands of nodes 🌈. It is usually more dynamic, with node lifetimes measured in hours ⏳. They also suggested that a P2P network is usually homogeneous, with a common resource description language. And it lacks the centralized "mediators" found in many IR systems that take responsibility for selecting collections, for rewriting queries, and for merging ranked results 👑. These distinctions are generally aligned with the peer characteristics in Section 1. One might add that P2P nodes display more symmetry -- peers are often both information consumers and producers 🫶. Daswani, Garcia-Molina, et al. pointed out that, while there are IR techniques for ranked keyword search at moderate scale, research is still needed so that ranking mechanisms stay efficient at the larger scale that P2P designs target [25]. Joseph and Hoshiai surveyed several P2P systems using metadata techniques from the IR toolkit [60]. They described an assortment of IR techniques and P2P systems, including various metadata formats, retrieval models, bloom filters, DHTs, and trust issues 🦋.
In the paragraphs that follow, we survey P2P work that has incorporated information retrieval models, particularly the Vector Model and the Latent Semantic Indexing Model 💜. We omit the P2P work based on Bayesian models. Some have pointed to such work [60], but made no explicit mention of the model [364]. One early paper on P2P content-based image retrieval also leveraged the Bayesian model [365]. For the former two models, we briefly describe the design and then try to highlight robustness aspects. On robustness, we are again stymied for lack of prior work 😭. Honestly, a search across all proceedings of the Annual ACM Conference on Research and Development in Information Retrieval for the words "reliable", "available", "dependable", or "adaptable" did not return any results at the time of writing 💀. Meanwhile, a standard text on distributed database management systems [366] contains a whole chapter on reliability 📚. IR research concentrates on performance measures. The common ones are recall, the fraction of the relevant documents that has been retrieved, and precision, the fraction of the retrieved documents that is relevant [262]. Ideally, an IR system would have high recall and high precision 🍓. Unfortunately, techniques favouring one often disadvantage the other [363] 🙈.
4.2.1. Vector Model (PlanetP, FASD, eSearch) 🎀
The vector model [367] represents both documents and queries as term vectors, where a term could be a word or a phrase 🌸. If a document or query has a term, the weight of the corresponding dimension of the vector is non-zero. The similarity of the document and query vectors gives an indication of how well a document matches a particular query 💖.
The weighting calculation is critical across the retrieval models 🔥. Amongst the numerous proposals for the probabilistic and vector models, there are some commonly recurring weighting factors [363]. One is term frequency: the more a term is repeated in a document, the more important the term is. Another is inverse document frequency: terms common to many documents give less information about the content of a document. Then there is document length. Larger documents can bias term frequencies, so weightings are sometimes normalized against document length. The expression "TFIDF weighting" refers to the whole collection of weighting calculations that incorporate term frequency and inverse document frequency, not just to one of them 🧮. Two weighting calculations have been particularly dominant -- Okapi [368] and pivoted normalization [369]. A distributed version of Google's Pagerank algorithm has also been devised for a P2P environment [370]. It allows incremental, ongoing Pagerank calculations while documents are inserted and deleted 🌊.
A couple of early P2P systems leveraged the vector model 🦋. Building on it, PlanetP divided the ranking problem into two steps [215]. In the first, peers are ranked for the probability that they have matching documents. In the second, higher-priority peers are contacted and the matching documents are ranked. An Inverse Peer Frequency, analogous to the Inverse Document Frequency, is used to rank relevant peers. To further constrain the query traffic, PlanetP contacts only the first group of m peers to retrieve a relevant set of documents. In this way, it repeatedly contacts groups of m peers until the top k document rankings are stable. While the PlanetP designers first quantified recall and precision, they also considered reliability 🫶. Each PlanetP peer has a global index with a list of all other peers, their IP addresses, and their Bloom filters. That's a lot of shared info, and it needs to be maintained 😵💫. Klampanos and Jose saw this as PlanetP's primary shortcoming [371]. Each Bloom filter summarized the set of terms in the local index of each peer. The time to propagate changes, be they new documents or peer arrivals/departures, was studied by simulation for up to 1000 peers. The reported propagation times were in the hundreds of seconds ⏰. Design workarounds were required for PlanetP to be viable across slower dial-up modem connections. For future work, the authors were considering some sort of hierarchy to scale to larger numbers of peers 🌱.
A second early system using the vector model is the Fault-tolerant, Adaptive, Scalable Distributed (FASD) search engine [283] 🔍. It extended the Freenet design (Section 2.3) for richer queries. The original Freenet design could find a document based on a globally unique identifier. Kronfol's design added the ability to search, for example, for documents about "apples AND oranges NOT bananas" 🍎🍊. It uses a TFIDF weighting scheme to build a document's term vector. Each peer calculates the similarity of the query vector and local documents, then forwards the query to the best downstream peer. Once the best downstream peer returns a result, the second-best peer is tried, and so on. Simulations with 1000 nodes gave an indication of the query path lengths in various situations -- when routing queries in a network with constant rates of node and document insertion, when bootstrapping the network in a "worst-case" ring topology, or when failing randomly and specifically selected peers 🧪. Kronfol claimed excellent average-case performance -- less than 20 hops to retrieve the same top n results as a centralized search engine ✨. There were, however, numerous cases where the worst-case path length was several hundred hops in a network of only 1000 nodes 💀.
In parallel, there have been some P2P designs based on the vector model from the University of Rochester -- pSearch [9, 372] and eSearch [373] 🌈. The early pSearch paper suggested a couple of retrieval models, one of which was the Vector Space Model, to search only the nodes likely to have matching documents. To obtain approximate global statistics for the TFIDF calculation, a spanning tree was constructed across a subset of the peers. For the m top terms, the term-to-document index was inserted into a Content-Addressable Network [334]. A variant that mapped terms to document clusters was also suggested. eSearch is a hybrid of the partition-by-document and partition-by-term approaches (Section 4.1.2). eSearch nodes are primarily partitioned by term. Each is responsible for the inverted lists for some top terms. For each document in the inverted list, the node stores the complete term list. To reduce the size of the index, the complete term lists for a document are only kept on nodes that are responsible for top terms in the document 🧩. eSearch uses the Okapi term weighting to select top terms. It relies on the Chord DHT [34] to associate terms with nodes storing the inverted lists. It also uses automatic query expansion, which takes the significant terms from the top document matches and automatically adds them to the user's query to find additional relevant documents 🔁. The eSearch performance was quantified in terms of search precision, the number of retrieved documents, and various load-balancing metrics 📊. Compared to the more common proposals for partitioning by keywords, eSearch consumed 6.8 times the storage space to achieve faster search times 💾⚡.
4.2.2. Latent Semantic Indexing (pSearch) 🦋
okay so next up is Latent Semantic Indexing (LSI) [374] 💅 and its whole vibe is that it maps both the document vectors and the query vectors into a concept space with fewer dimensions. The starting point is a t*N weighting matrix, where t is the total number of indexed terms and N is the total number of documents, and the matrix elements could be TFIDF rankings 📊. Then singular value decomposition shrinks this matrix down to fewer dimensions while keeping the more significant term-to-document mappings ✨. Baeza-Yates and Ribeiro-Neto said LSI's value is a novel theoretic framework, but that its practical performance advantage for real document collections had yet to be proven [262] 🙈. Not me being like "hmm, receipts pls" 💀
pSearch incorporated LSI [9] 🌸 and by placing the indices for semantically similar documents close together in the network, Tang, Xu, et al. touted significant bandwidth savings compared to the early full-flooding variant of Gnutella [372] 🔥. They plotted the number of nodes visited by a query 📈. They also looked at the trade-off with accuracy, which is the percentage match between the documents returned by the distributed pSearch algorithm and those from a centralized LSI baseline 🎀.
Then in a more recent update to the pSearch work, Tang, Dwarkadas, et al. summarized LSI's shortcomings [375] 😭. First, for large document collections, its retrieval quality is inherently inferior to Okapi. Second, singular value decomposition eats excessive memory and computation time 💀. So the authors used Okapi for searching while still keeping LSI for indexing 🫶. With Okapi, they picked the next node to search and picked documents on the searched nodes. With LSI, they made sure similar documents clustered near each other, which optimized the network search costs 💜. When retrieving a small number of top documents, the precision of LSI+Okapi approached that of Okapi 🍓. However, if you retrieve a large number of documents, LSI+Okapi precision is inferior 🥲. The authors want to improve this in future work ⭐.
4.2.3. Small Worlds 🌍
The "small world" concept originally described how people are interconnected by short chains of acquaintances [376] 🧚. Kleinberg was struck by the algorithmic lesson of the small world, namely "that individuals using local information are collectively very effective at constructing short paths between two points in a social network" [377] 👑. Small world networks have a small diameter and a large clustering coefficient (a large number of connections amongst relevant nodes) [378] ✨.
The small world idea has had a limited impact on peer-to-peer algorithms 🥺. It has influenced only a few unstructured [62, 378-380] and structured [344, 381] algorithms. The most promising work on "small worlds" in P2P networks is the work concerned with the information retrieval metrics, precision and recall [62, 378, 380] 💖.
5. Queries 🎀
Database research suggests directions for P2P research 🔍. Hellerstein observed that, while work on fast P2P indexes is well underway, P2P query optimization remains a promising topic for future research [23] 🦋. Kossman reviewed the state of the art of distributed query processing and highlighted areas for future research: simulation and query optimization for networks of tens of thousands of servers and millions of clients; non-relational data types (e.g., XML, text, and images); and partial query responses since on the Internet, "failure is the rule rather than the exception" [19] 😭. A primary motivation for the P2P system, PIER, was to scale from the largest database systems of a few hundred nodes to an Internet environment in which there are over 160 million nodes [22] 🌈. Litwin and Sahri have also considered ways to combine distributed hashing, more specifically the Scalable Distributed Data Structures, with SQL databases, and they claim to be first to implement scalable distributed database partitioning [382] 💅. Motivated by the lack of transparent distribution in current distributed databases, they measure query execution times for Microsoft SQL servers aggregated by means of an SDDS layer 📊. One of their starting assumptions was that it is too challenging to change the SQL query optimizer 🙈.
Database research also suggests the approach to P2P research 🧠. Researchers of database query optimization were divided between those looking for optimal solutions in special cases and those using heuristics to answer all queries [383] ⚖️. Gribble, et al. cast query optimization in terms of the data placement problem, which is to "distribute data and work so the full query workload is answered with lowest cost under the existing bandwidth and resource constraints" [250] 💜. They pointed out that even the static version of this problem is NP-complete in P2P networks 💀. So research on massive, dynamic P2P networks will likely progress using both strategies of early database research, which are heuristics and special-case optimizations 🫶.
If P2P networks are going to be adaptable, and if they are to support a wide range of applications, then they need to accommodate many query types [72] 🌸. Up to this point, we have reviewed queries for keys (Section 3) and keywords (Sections 4.1. and 4.2). Unfortunately, a major shortcoming of the DHTs in Section 3.5 is that they primarily support exact-match, single-key queries 😤. Skip Graphs support range and prefix queries, but not aggregation queries 🥹. Here we probe below the language syntax to identify the open research issues associated with more expressive P2P queries [25] 🔎. Triantafillou and Pitoura observed the disparate P2P designs for different types of queries and so outlined a unifying framework [76] 🧩. To classify queries, they considered the number of relations (single or multiple), the number of attributes (single or multiple), and the type of query operator 🗂️. They described numerous operators: equality, range, join, and "special functions" 🎀. The latter referred to aggregation (like sum, count, average, minimum, and maximum), grouping and ordering 🍓. The following sections approximately fit their taxonomy: range queries, multi-attribute queries, join queries and aggregation queries 🦄. There has been some initial P2P work on other query types, namely continuous queries [20, 22, 73], recursive queries [22, 74], and adaptive queries [23, 75] ✨. For these, we defer to the primary references 🙏.
5.1. Range Queries
okay so bestie, range queries in P2P networks were flagged by Huebsch, et al. [22] as a big important open research issue 👀✨ like, in parallel databases, range partitioning was a whole performance thing so a transaction usually only needs data from one disk or node 💅 [22]. longest prefix match is a range search too, and it's giving main character energy in routing for voice and data networks alike 🌈. and sometimes users want broad, inexact queries but only need a few answers, so finding similar ranges matters too [77] 🎀. Figure 4 has the roundup of range search proposals on P2P and SDDS indexes, and since the Scalable Distributed Data Structure (SDDS) was a huge influence on modern Distributed Hash Tables (DHTs) [49-51], we're including the ongoing SDDS range search work too 🫶
PEER-TO-PEER (P2P)
Locality Sensitive Hashing (Chord) [77]
Prefix Hash Trees (unspecified DHT) [78, 79]
Space Filling Curves (CAN) [80]
Space Filling Curves (Chord) [81]
Quadtrees (Chord) [82]
Skip Graphs [38, 41, 83, 100]
Mercury [84]
P-Grid [85, 86]
SCALABLE DISTRIBUTED DATA STRUCTURES (SDDS)
RP* [87, 88]
Figure 4: Solutions for Range Queries on P2P and SDDS Indexesso the P2P range papers split into two camps 🧚: the ones that lean on an underlying DHT (the first five entries in Figure 4) and the ones that don't (the next three) 🦋. Bharambe, Agrawal, et al. argued DHTs are inherently ill-suited to range queries [84] 💀. the exact feature that makes DHTs great at load balancing, randomized hash functions, is the same thing that works against range queries 🙈. hashing ranges is one possible fix, but that can need a priori partitioning. if the partitions are too big, they risk overload 😭. if they're too small, there may be too many hops 🍓.
despite all that, there have been several DHT-based range query proposals ✨. if you hash ranges to nodes, overlapping ranges can totally end up on different nodes 🫠. Gupta, Agrawal, et al. use locality sensitive hashing so that, with high probability, similar ranges land on the same node [77] 💖. they propose one family of locality sensitive hash functions, called min-wise independent permutations 🌸. they plotted partitions per node and path length against the total number of peers. for a 1000-node network, the hop count distribution was very similar to exact-matching Chord 🔥. but was it load-balanced? 👀 for the same network with 50,000 partitions, the number of partitions per node varied by over two orders of magnitude (first and ninety-ninth percentiles) 😬. the Prefix Hash Tree is a trie where prefixes get hashed onto any DHT 🌳. the preliminary analysis suggests efficient doubly logarithmic lookup, balanced load, and fault resilience [78, 79] ✨.
Andrzejak and Xu were maybe the first to propose a mapping from ranges to DHTs [80] 👑. they use the Hilbert curve, one particular Space Filling Curve, over a Content Addressable Network (CAN) construction (Section 3.5.3) 🦋. they keep two properties: nearby ranges map to nearby CAN zones, and if a range is split into two sub-ranges, the sub-range zones partition the zone of the primary range 💅. they measured path length and load proxy (total messages and nodes visited) for three ways of propagating range queries: brute force, controlled flooding, and directed controlled flooding 📊.
Schmidt and Parashar also pushed Space Filling Curves for range queries over a DHT [81] 🌈. but they point out that while Andrzejak and Xu use an inverse Space Filling Curve to map a one-dimensional space to d-dimensional zones, they map a d-dimensional space back down to a one-dimensional index 🫶. that setup lets you search across multiple attributes (Section 5.2) 💜. Tanin, Harwood, et al. suggested quadtrees over Chord [82] and gave preliminary simulation results for query response times ⭐.
since DHTs are naturally limited to exact-match, single-key queries, researchers looked at other P2P indexes for range searches 🎀. several were based on Skip Graphs [38, 41], which, unlike DHTs, don't need randomizing hash functions, so they can do range searches 🧚. unfortunately, they aren't load balanced [83] 😭. for example, in SkipNet [48], hashing was added to balance load, so the Skip Graph could support range searches or load balancing, but not both 🙃. one load-balancing fix relies on an increased number of 'virtual' servers [168], but Bharambe, Agrawal, et al. rejected that idea in their search for a system that does both range search and load balancing [84] 🚫. the virtual servers work assumed load imbalance comes from hashing, meaning skewed data insertions and deletions. sometimes the imbalance comes from a skewed query load instead 👀. in those cases, extra virtual servers can increase routing hops and the number of pointers a Skip Graph needs to maintain 😵💫.
Ganesan, Bawa, et al. came up with a different load-balancing method [83] 🌸. they proposed two Skip Graphs: one to index the data itself, and one to track load at each node 💖. each node can figure out the load on its neighbours and which nodes are the most (least) loaded 🫧. they devise two algorithms: NBRADJUST balances load across neighbouring nodes, and using REORDER, empty nodes can take over some of the tuples on heavily loaded nodes 🔥. their simulations focus on skewed storage load rather than skewed query load, but they guess the same approach could work for query load too 🤔.
other range query proposals skip both the DHT and the Skip Graph entirely 🦋. Bharambe, Agrawal, et al. set their Mercury design apart with multi-attribute range queries and explicit load balancing [84] 💅. in Mercury, nodes are grouped into routing hubs, and each hub handles different query attributes 🏠. it doesn't use hashing, but it's loosely similar to the DHT approaches: nodes inside hubs are arranged in rings, like Chord [34], and for efficient routing within hubs, k long-distance links are used, like Symphony [381] 🌀. range lookups need O(((log n)^2)/k) hops 📐. random sampling estimates the average load on nodes and finds the lightly loaded parts of the overlay 🎯. Symphony assumed nodes are responsible for ranges of roughly equal size, but Mercury's random sampling can find where a range starts, even for non-uniform ranges [84] 🙌. P-Grid [42] does support range queries, thanks to the key ordering in its tree structures 🌲. Ganesan, Bawa, et al. critiqued its capabilities [83]: P-Grid assumes fixed-capacity nodes, there's no formal characterization of imbalance ratios or balancing costs, and every P-Grid periodically contacts other nodes for load information 😤.
the work on Scalable Distributed Data Structures (SDDSs) has moved along in parallel with P2P work and has dealt with range queries too 🎀. like the DHTs above, the early SDDS Linear Hashing (LH*) schemes weren't order-preserving [52] 🫠. to make range queries possible, Litwin, Niemat, et al. built a Range Partitioning variant, RP* [87] 💫. there are options to drop the index, add indexes to clients, or add them to servers 🧩. in the variant without an index, every query goes out via multicasting, and the other variants use some multicasting too 📡. the initial RP* paper suggested scalability to thousands of sites, but a more recent RP* simulation was capped at 140 servers [88] 🧢. in that work, Tsangou, Ndiaye, et al. looked at TCP and UDP mechanisms for servers to send range query results back to clients ⚡. the main metrics were search and response times ⏱️. among commercial parallel database management systems, they reported the largest one seems to only scale to 32 servers (SQL Server 2000) 💀. for future work they planned to look at aggregating query results, instead of opening a connection between the client and every single server with a response 🧠.
all in all, there are lots of open research questions on P2P range queries 🔭. how realistic is it to maintain global load statistics given how big and dynamic P2P networks are? 🤯 simulations at larger scales are required 📈. proposals should account for both storage load (insert and delete messages) and query load (lookup messages) 💅. simplifying assumptions need to be attacked 🗡️. for example, how well do these solutions work in networks with heterogeneous nodes, where maximum message loads and index sizes depend on the node? 🥺💖
5.2. Multi-Attribute Queries ✨
okay so there's been some work on multi-attribute P2P queries, but as late as September 2003 people were still saying nobody had found an efficient solution yet [76] 😭
An early big moment came from SDDSs over aggregated commodity nodes. k-RP* [89] uses the multi-dimensional binary search tree (aka the k-d tree, where k indicates the number of dimensions of the search index) [384] 🌳 It builds on the RP* work from the last section and inherits its range search and partial match skills. Like the other SDDSs, k-RP* indexes can fit into RAM for very fast lookup ⚡ Litwin and Neimat said the future work is a) a formal analysis of the range search termination algorithm and the k-d paging algorithm, b) a comparison with other multi-attribute structures (quad-trees and R-trees), and c) exploring query processing, concurrency control, and transaction management for k-RP* files [89]. On that last point, some people think transactions don't really matter for supporting complex queries in P2P networks [72] 🙄
Next up, Hodes, Czerwinski, et al. were building a secure wide-area Service Discovery Service (SDS) 🔐 and looked at three designs for multi-criteria search: Centralization, Mapping, and Flooding [90]. These line up with the index classes from Section 2 (Central, Distributed, and Local). They ruled out the centralized, Napster-like index because of its single point of failure risk 💀 They looked at the hash-based mappings from Section 3, but figured data couldn't be partitioned well enough. A document that matches lots of criteria would get wastefully stored in lots of partitions. Full flooding got rejected for not scaling. So they came up with a query filtering technique, kinda like Gnutella's query routing protocol (Section 4.1) 🦋 Nodes push proactive summaries of their data instead of waiting for a query, and the summaries get aggregated and stored throughout a server hierarchy to guide later queries. Their prototype measured total load on the system, but not load distribution. For future work, the indexing needs to be flexible enough to change with query and storage workloads. A mesh topology might be better than their hierarchy, since query misses wouldn't have to propagate up to root servers. That choice is basically like BGP meshes vs. DNS trees 🌸
More recently, Cai, Frank, et al. came out with the Multi-Attribute Addressable Network (MAAN) [91] 💖 They built on Chord to support both multi-attribute and range queries, and they claimed to be the first to handle both query types in a structured P2P system. Each MAAN node has O(log n) neighbours, where N is the number of nodes. MAAN multi-attribute range queries need O(log n+N*Smin) hops, where Smin is the minimum range selectivity across all attributes. Selectivity is the ratio of the query range to the entire identifier range. The paper assumed a locality preserving hash function would keep load balanced, but as Section 5.1 covered, Bharambe, Agrawal, et al. showed the problems with that assumption [84] 🙈 MAAN also required the schema to be fixed and known in advance, and adaptable schemas were recommended for later. The authors admitted there's a selectivity breakpoint where full flooding beats their scheme, which is kinda begging for a query resolution algorithm that adapts to the profile of queries 👑
Cai and Frank followed up with RDFPeers [55] 🧚 They stood out from other RDF proposals by a) guaranteeing they'll find query results if they exist and b) dropping the need to define a fixed schema ahead of time. They hashed <subject, predicate, object> triples onto MAAN and reported routing hop metrics for their implementation. Load imbalance across nodes got reduced to less than one order of magnitude, but the measurement was the number of triples stored per node, and skewed query loads weren't considered at all 😬 They plan to improve load balancing with the virtual servers from Section 5.1 [168] ✨
5.3. Join Queries 🎀
Two research teams have done some first-round work on P2P join operations. Harren, Hellerstein, et al. started with a three-layer architecture: storage, DHT, and query processing. They implemented the join by modifying an existing Content Addressable Network (CAN) simulator, and reported "significant hot-spots in all dimensions: storage, processing, and routing" [72] 🔥 Their design kept evolving in the context of PIER, a distributed query engine based on CAN [22, 385] 🌈 They implemented two equi-join algorithms. In their design, a key is built from the "namespace" and the "resource ID". There's a namespace for each relation, and the resource ID is the primary key for base tuples in that relation. Queries get multicast to all nodes in the two namespaces (relations) being joined.
The first algorithm is a DHT version of the symmetric hash join. Each node in the two namespaces finds the relevant tuples and hashes them into a new query namespace. The resource ID in that new namespace is the concatenation of the join attributes. The second one is called "fetch matches", and here one of the relations is already hashed on the join attributes. Each node in the second namespace finds the tuples that match the query and fetches the matching tuples from the first relation 🫶 They also used the symmetric semi-join rewrite and the Bloom filter rewrite to cut down on the high bandwidth overheads of the symmetric hash join. For an overlay of 10,000 nodes, they simulated the delay to retrieve tuples and the aggregate network bandwidth for all four schemes. The first prototype ran on a cluster of 64 PCs, and it's since been expanded to PlanetLab 🌍
Triantafillou and Pitoura thought multicasting to huge numbers of peers was inefficient [76] 🙅♀️ So they set aside a limited number of special peers called range guards. The domain of the join attributes got divided, with one partition per range guard. Join queries were only sent to range guards, which is where they got executed. Picking range guards efficiently and doing a quantitative evaluation of their proposal were left for future work 🍓
5.4. Aggregation Queries 💅
Aggregation queries always rely on tree structures to combine results from a huge number of nodes. Examples are Count, Sum, Maximum, Minimum, Average, Median, and Top-K [92, 386, 387] 🧮 Figure 5 is the cheat sheet for the tree and query characteristics that affect dependability.
Tree type: Doesn't use DHT [92], use internal DHT trees [95], use
independent trees on top of DHTs
Tree repair: Periodic [93], exceptional [32]
Tree count: One per key, one per overlay [56]
Tree flexibility: Static [92], dynamic
Query interface: install, update, probe [98]
Query distribution: multicast [98], gossip [92]
Query applications: leader election, voting, resource location,
object placement and error recovery [98, 388]
Query semantics
Consistency: Best-effort, eventual [92], snapshot / interval /
single-site validity [99]
Timeliness [388]
Lifetime: Continuous [97, 99], single-shot
No. attributes: Single, multiple
Query types: Count, sum, maximum, minimum, average, median, top k
[92, 386, 387]
Figure 5: Aggregation Trees and Queries in P2P NetworksKey: Astrolabe [92]; Cone [93]; Distributed Approximative System
Information Service (DASIS) [95]; Scalable Distributed Information
Management System (SDIMS) [98]; Self-Organized Metadata Overlay
(SOMO) [56]; Wildfire [99]; Willow [32]; Newscast [97]The big design choices for aggregation trees come down to how the overlay uses DHTs, how it repairs itself when things fail, how many aggregation trees there are, and whether the tree is static or dynamic (Figure 5) 🌲 Astrolabe is one of the most influential P2P designs in Figure 5, and yet it makes no use of DHTs at all [92] 🤯 Other designs use the internal trees of Plaxton-like DHTs, and others build independent tree structures on top of DHTs. Most of the designs repair the aggregation tree with periodic mechanisms, similar to the ones the DHTs use themselves. Willow is the exception [32]: it uses a Tree Maintenance Protocol to "zip" disjoint aggregation trees together when there are major failures ⚡ Yalagandula and Dahlin found that reconfigurations at the aggregation layer are costly, so they suggested more research into techniques that cut down the cost and frequency of those reconfigurations [98]. A lot of the designs use multiple aggregation trees, each rooted at the DHT node responsible for the aggregation attribute. On the flip side, the Self-Organized Metadata Overlay [56] uses a single tree, which makes it vulnerable to a single point of failure at its root 😬
At the time of writing, researchers have only just started looking at how queries perform when there's churn 🌪️ Most designs are for best-effort queries. Bawa, et al. came up with a stronger consistency model called Single-Site Validity [99] to qualify how accurate results are when there's churn. The price was a five-fold increase in message load compared to an efficient but best-effort Spanning Tree 💸 Gossip mechanisms are resilient to churn, but they delay aggregation results and rack up high message costs for aggregation attributes with small read-to-write ratios 🫠
6. Security Considerations 🔐
An initial list of references to research on P2P security is given in Figure 1, Section 1 📚 This document addresses P2P search. P2P storage, security, and applications are recommended for further investigation in Section 8 👀
7. Conclusions ✨
okay so P2P research basically splits into four buckets: search, storage, security, and applications 🫶 this critical survey focused on search methods, and it is SO good 🔥 P2P networks have been sorted by whether they have an index (structured or unstructured) and where that index lives (local, centralized, or distributed). But ngl, the big reveal is that most of them have evolved some structure anyway, like indexes at superpeers or indexes defined by DHT algorithms 💅 For location, the distributed index is the most common one. The survey also split indexes into semantic and semantic-free, and it critiqued P2P work on the major query types 🌸 Most of the work is from 2000 or later, but we traced important building blocks back to the 1990s 🦋
The whole point of this survey was to answer one question: "How robust are P2P search networks?" 🎀 That question is key to whether P2P tech can actually get deployed. Balakrishnan, Kaashoek, et al. argued that the P2P architecture is seriously appealing. The startup and growth barriers are low, they can pool enormous storage and processing resources, and "the decentralized and distributed nature of P2P systems gives them the potential to be robust to faults or intentional attacks" [18] 😭 BUT, and this is a big but, if P2P wants to be a disruptive technology beyond casual file sharing, then robustness needs to be practically verified [20] 👑
The best comparative research on P2P dependability has been done in the context of Distributed Hash Tables (DHTs) [291] 🧚 The whole DHT body of research boils down to four main observations about dependability (Section 3.2) 💖 First, static dependability comparisons show that no O(log n) DHT geometry is significantly more dependable than the other O(log n) geometries. Second, dynamic dependability comparisons show that DHT dependability is sensitive to the underlying topology maintenance algorithms (Figure 2) 🙈 Third, most DHTs use O(log n) geometries to suit ephemeral nodes, whereas the O(1) hop DHTs suit stable nodes, and those deserve more research attention 🍓 Fourth, although the study of DHT dependability isn't a mature science yet, it's being helped by recent simulation tools that support multiple DHTs [299] ✨
We make the following four suggestions for future P2P research 🌈
- Complete the companion P2P surveys for storage, security, and applications. A rough outline has been suggested in Figure 1, along with references. The need for such surveys was highlighted within the peer-to-peer research group of the Internet Research Task Force (IRTF) [17] 💜
- P2P indexes are maturing, but P2P queries are still embryonic 🌸 Work on more expressive queries over P2P indexes started to gain momentum in 2003, but it remains fraught with efficiency and load issues 💀
- Isolate the low-level mechanisms that affect robustness 🔥 Comparing the robustness of DHT geometries (like rings versus de Bruijn graphs) has limited value, because robustness is highly sensitive to the underlying topology maintenance algorithms (Figure 2) 🦋
- Build consensus on robustness metrics and their acceptable ranges 👑 This paper teased out numerous measures that impinge on robustness. For example: the median query path length for a failure of x% of nodes, bisection width, path overlap, the number of alternatives available for the next hop, lookup latency, average live bandwidth (bytes/node/sec), successful routing rates, the number of timeouts (caused by a finger pointing to a departed node), lookup failure rates (caused by nodes that temporarily point to the wrong successor during churn), and clustering measures (edge expansion and node expansion) 🫶 Application-level robustness metrics need to drive a consistent assessment of the underlying search mechanics 🎀
8. Acknowledgments 🫶
This document was adapted from a paper in Elsevier's Computer Networks:
J. Risson & T. Moors, Survey of Research towards Robust Peer-to-Peer Networks: Search Methods, Computer Networks 51(7)2007.
We thank Bill Yeager, Ali Ghodsi, and several anonymous reviewers for thorough comments that significantly improved the quality of earlier versions of this document 💖 bestie gratitude, periodt ✨
9. References 📚
9.1. Informative References
[1] M. Roussopoulos, M. Baker, D. Rosenthal, T. Guili, P. Maniatis, and J. Mogul, 2 P2P of Not 2 P2P?, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[2] A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, IFIP/ACM Middleware 2001, Nov 2001.
[3] B. Yeager and B. Bhattacharjee, Peer-to-Peer Research Group Charter, http://www.irtf.org/charters/p2prg.html (2003)
[4] T. Klingberg and R. Manfredi, Gnutella 0.6, (2002)
[5] I. Clarke, A Distributed Decentralised Information Storage and Retrieval System, Undergraduate Thesis, 1999.
[6] B. Zhao, J. Kubiatowicz, and A. Joseph, Tapestry: an infrastructure for fault-tolerant wide-area location and routing, Report No. UCB/CSD-01-1141 2001.
[7] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Kaashoek, F. Dabek, and H. Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proc. ACM SIGCOMM 2001 2001, pp. 149-160.
[8] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, A scalable content-addressable network, Proc. of the conf. on Applications, technologies, architectures and protocols for computer communications, August 27-31 2001, pp. 161-172.
[9] C. Tang, Z. Xu, and M. Mahalingam, pSearch: information retrieval in structured overlays, First Workshop on Hot Topics in Networks. Also Computer Communication Review, Volume 33, Number 1, January 2003, Oct 28-29 2002.
[10] W. Nejdl, S. Decker, and W. Siberski, Edutella Project, RDF-based Metadata Infrastructure for P2P Applications, http://edutella.jxta.org/ (2003)
[11] K. Aberer and M. Hauswirth, Peer-to-peer information systems: concepts and models, state-of-the-art, and future systems, ACM SIGSOFT Software Engineering Notes, Proc. 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on foundations of software engineering 26 (5) (2001)
[12] L. Zhou and R. van Renesse, P6P: a peer-to-peer approach to internet infrastructure, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[13] Citeseer, Citeseer Scientific Literature Digital Library, http://citeseer.ist.psu.edu/ (2004)
[14] D. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, and Z. Xu, Peer-to-Peer Computing, HP Technical Report, HPL-2002-57 2002.
[15] K. Aberer and M. Hauswirth, An overview on peer-to-peer information systems, Workshop on Distributed Data and Structures WDAS-2002 2002.
[16] F. DePaoli and L. Mariani, Dependability in Peer-to-Peer Systems, IEEE Internet Computing 8 (4) (2004) 54-61.
[17] B. Yeager, Proposed research tracks, Email to the Internet Research Task Force IRTF P2P Research Group, Nov 10 2003.
[18] H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, Looking up data in P2P systems, Communications of the ACM 46 (2) (2003) 43-48.
[19] D. Kossmann, The state of the art in distributed query processing, ACM Computing Surveys 32 (4) (2000) 422-469.
[20] B. Gedik and L. Liu, Reliable peer-to-peer information monitoring through replication, Proc. 22nd Int'l Symp. on Reliable Distributed Systems, 6-8 Oct 2003, pp. 56-65.
[21] S.-M. Shi, Y. Guangwen, D. Wang, J. Yu, S. Qu, and M. Chen, Making peer-to-peer keyword searching feasible using multi-level partitioning, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[22] R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, and I. Stoica, Querying the Internet with PIER, Proc. 29th Int'l Conf. on Very Large Databases VLDB'03, September 2003.
[23] J. M. Hellerstein, Toward network data independence, ACM SIGMOD Record 32 (3) (2003) 34-40.
[24] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proc. 2003 conference on Applications, Technologies, Architectures and Protocols for Computer Communications 2003, pp. 381-394.
[25] N. Daswani, H. Garcia-Molina, and B. Yang, Open Problems in Data- sharing Peer-to-peer Systems, The 9th Int'l Conf. on Database Theory (ICDT 2003), Siena, Italy, 8-10 January (2003)
[26] B. Cooper and H. Garcia-Molina, Studying search networks with SIL, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
[27] M. Bawa, Q. Sun, P. Vinograd, B. Yang, B. Cooper, A. Crespo, N. Daswani, P. Ganesan, H. Garcia-Molina, S. Kamvar, S. Marti, and M. Schlossed, Peer-to-peer research at Stanford, ACM SIGMOD Record 32 (3) (2003) 23-28.
[28] B. Yang and H. Garcia-Molina, Improving search in peer-to-peer networks, Proc. 22nd IEEE Int'l Conf. on Distributed Computing Systems, July 2002.
[29] B. Yang and H. Garcia-Molina, Efficient search in peer-to-peer networks, Proc. 22nd Int'l Conf. on Distributed Computing Systems, July 2-5 2002.
[30] C. Plaxton, R. Rajaraman, and A. Richa, Accessing nearby copies of replicated objects in a distributed environment, ACM Symp. on Parallel Algorithms and Architectures (1997)
[31] B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz, Tapestry: A Resilient Global-Scale overlay for Service Deployment, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 41-53.
[32] R. van Renesse and A. Bozdog, Willow: DHT, aggregation and publish/subscribe in one protocol, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[33] P. Ganesan, G. Krishna, and H. Garcia-Molina, Canon in G Major: Designing DHTs with Hierarchical Structure, Proc. Int'l Conf. on Distributed Computing Systems ICDCS 2004 2004.
[34] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Kaashoek, F. Dabek, and H. Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Trans. on Networking 11 (1) (2003) 17-32.
[35] S. Rhea, T. Roscoe, and J. Kubiatowicz, Structured Peer-to-Peer Overlays Need Application-Driven Benchmarks, Proc. 2nd Int'l Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
[36] D. Loguinov, A. Kumar, and S. Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proc. 2003 conference on Applications, Technologies, Architectures and Protocols for Computer Communications, August 25-29 2003, pp. 395-406.
[37] F. Kaashoek and D. Karger, Koorde: A simple degree-optimal hash table, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, 20-21 February 2003.
[38] N. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, SkipNet: A Scalable Overlay Network with Practical Locality Properties, Proc. Fourth USENIX Symp. on Internet Technologies and Systems USITS'03, March 2003.
[39] I. Gupta, K. Birman, P. Linga, A. Demers, and R. Van Renesse, Kelips: Building an efficient and stable P2P DHT through increased memory and background overhead, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, Feb 20-21 2003.
[40] J. Cates, Robust and Efficient Data Management for a Distributed Hash Table, Master's Thesis, May 2003.
[41] J. Aspnes and G. Shah, Skip graphs, Proc. 14th annual ACM-SIAM symposium on discrete algorithms (2003) 384-393.
[42] K. Aberer, P. Cudre-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, and R. Schmidt, P-Grid: a self-organizing structured P2P system, ACM SIGMOD Record 32 (3) (2003) 29-33.
[43] B. Zhao, Y. Duan, L. Huang, A. Joseph, and J. Kubiatowicz, Brocade: landmark routing on overlay networks, First Int'l Workshop on Peer-to-Peer Systems IPTPS'02, March 2002.
[44] S. Ratnasamy, S. Shenker, and I. Stoica, Routing algorithms for DHTs: some open questions, Proc. First Int'l Workshop on Peer to Peer Systems, IPTPS 2002, March 2002.
[45] P. Maymounkov and D. Mazieres, Kademlia: A peer-to-peer information system based on the XOR metric, Proc. First Int'l Workshop on Peer to Peer Systems, IPTPS 2002, March 7-8 2002.
[46] D. Malkhi, M. Naor, and D. Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proc. 21st annual symposium on principles of distributed computing PODC, July 21-24 2002, pp. 183-192.
[47] X. Li and C. Plaxton, On name resolution in peer to peer networks, Proc. ACM SIGACT Annual Workshop on Principles of Mobile Computing POMC'02 2002, pp. 82-89.
[48] N. Harvey, J. Dunagan, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, SkipNet: A Scalable overlay Network with Practical Locality Properties, Microsoft Research Technical Report MSR-TR- 2002-92 (2002)
[49] D. Karger, E. Lehman, T. Leighton, R. Panigraphy, M. Levin, and D. Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, ACM Symp. on Theory of Computing (1997)
[50] W. Litwin, M. Neimat, and D. Schneider, LH* - a scalable, distributed data structure, ACM Trans. on Database Systems (TODS) 21 (4) (1996) 480-525.
[51] R. Devine, Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm, Proc. 4th Int'l Conf. on Foundations of Data Organizations and Algorithms 1993.
[52] W. Litwin, M.-A. Niemat, and D. Schneider, LH* - Linear Hashing for Distributed Files, Proc. ACM Int'l Conf. on Mngt. of Data SIGMOD, May 1993, pp. 327-336.
[53] C. Tempich, S. Staab, and A. Wranik, Remindin': semantic query routing in peer-to-peer networks, Proc. 13th conference on World Wide Web, New York, NY, USA, May 17-20 (2004) 640-649.
[54] B. T. Loo, R. Huebsch, I. Stoica, and J. M. Hellerstein, The case for a hybrid P2P search infrastructure, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[55] M. Cai and M. Frank, RDFPeers: a scalable distributed RDF repository based on a structured peer-to-peer network, Proc. 13th conference on World Wide Web, May 17-20 2004, pp. 650-657.
[56] Z. Zhang, S.-M. Shi, and J. Zhu, SOMO: Self-organized metadata overlay for resource management in P2P DHTs, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, Feb 20-21 2003.
[57] B. Yang and H. Garcia-Molina, Designing a super-peer network, Proc. 19th Int'l Conf. on Data Engineering ICDE, March 2003.
[58] I. Tatarinov, P. Mork, Z. Ives, J. Madhavan, A. Halevy, D. Suciu, N. Dalvi, X. Dong, Y. Kadiyska, and G. Miklau, The Piazza peer data management project, ACM SIGMOD Record 32 (3) (2003) 47-52.
[59] W. Nejdl, W. Siberski, and M. Sintek, Design Issues and Challenges for RDF- and schema-based peer-to-peer systems, ACM SIGMOD Record 32 (3) (2003) 41-46.
[60] S. Joseph and T. Hoshiai, Decentralized Meta-Data Strategies: Effective Peer-to-Peer Search, IEICE Trans. Commun. E86-B (6 June) (2003) 1740-1753.
[61] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, Making gnutella-like P2P systems scalable, Proc. 2003 conference on Applications, Technologies, Architectures and Protocols for Computer Communications, August 25-29 2003, pp. 407-418.
[62] M. Bawa, G. S. Manku, and P. Raghavan, SETS: search enhanced by topic segmentation, Proc. 26th annual international ACM SIGIR conference on Research and Development in Information Retrieval 2003, pp. 306-313.
[63] H. Sunaga, M. Takemoto, and T. Iwata, Advanced peer to peer network platform for various services - SIONet Semantic Information Oriented Network, Proc. Second Int'l Conf. on Peer to Peer Computing, Sept 5-7 2002, pp. 169-170.
[64] M. Schlosser, M. Sintek, S. Decker, and W. Nejdl, HyperCuP - Hypercubes, Ontologies and P2P Networks, Springer Lecture Notes on Computer Science, Agents and Peer-to-Peer Systems Vol. 2530 (2002)
[65] M. Ripeanu, A. Iamnitchi, and P. Foster, Mapping the Gnutella network, IEEE Internet Computing 6 (1) (2002) 50-57.
[66] Q. Lv, S. Ratnasamy, and S. Shenker, Can Heterogeneity Make Gnutella Scalable?, Proc. 1st Int'l Workshop on Peer-to-Peer Systems IPTPS2002, March 7-8 2002.
[67] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, Search and replication in unstructured peer to peer networks, Proc. 16th international conference on supercomputing, June 22-26 2002, pp. 84-95.
[68] V. Kalogaraki, D. Gunopulos, and D. Zeinalipour-Yasti, XML schemas: integration and translation: A local search mechanism for peer to peer networks, Proc. 11th ACM international conference on Information and Knowledge management 2002, pp. 300- 307.
[69] O. Babaoglu, H. Meling, and Montresor, Anthill: a framework for the development of agent-based peer-to-peer systems, Proc. IEEE Int'l Conf. on Distributed Computer systems 2002, pp. 15-22.
[70] M. Jovanovic, Modeling large-scale peer-to-peer networks and a case study of Gnutella, Master's Thesis 2001.
[71] I. Clarke, O. Sandberg, B. Wiley, and T. Hong, Freenet: A Distributed Anonymous Information Storage and Retrieval System. Springer, New York, USA, 2001.
[72] J. Harren, J. Hellerstein, R. Huebsch, B. Loo, S. Shenker, and I. Stoica, Complex queries in DHT-based peer-to-peer networks, Proc. First Int'l Workshop on Peer to Peer Systems IPTPS 2002, March 2002.
[73] B. Gedik and L. Liu, PeerCQ: A Decentralized and Self-Configuring Peer-to-Peer Information Monitoring System, Proc. 23rd Int'l Conf. on Distributed Computing Systems ICDCS2003, May 19-22 2003.
[74] B. T. Loo, R. Huebsch, J. M. Hellerstein, T. Roscoe, and I. Stoica, Analyzing P2P Overlays with Recursive Queries, Technical Report, CSD-04-1301, January 14 2004.
[75] R. Avnur and J. Hellerstein, Eddies: continuously adaptive query processing, Proc. 2000 ACM SIGMOD international conference on Management of Data 2000, pp. 261-272.
[76] P. Triantafillou and T. Pitoura, Towards a unifying framework for complex query processing over structured peer-to-peer data networks, Proc. First Int'l Workshop on Databases, Information Systems and Peer-to-Peer Computing DBISP2P, Sept 7-8 2003, pp. 169-183.
[77] A. Gupta, D. Agrawal, and A. E. Abbadi, Approximate range selection queries in peer-to-peer systems, Proc. First Biennial Conf. on Innovative Data Systems Research CIDR 2003 2003.
[78] S. Ratnasamy, P. Francis, and M. Handley, Range queries in DHTs, Technical Report IRB-TR-03-009, July 2003.
[79] S. Ramabhadran, S. Ratnasamy, J. Hellerstein, and S. Shenker, Brief announcement: prefix hash tree, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, PODC 2004, July 25-28 2004, pp. 368-368.
[80] A. Andrzejak and Z. Xu, Scalable, efficient range queries for grid information services, Proc. Second IEEE Int'l Conf. on Peer to Peer Computing, September 2002.
[81] C. Schmidt and M. Parashar, Enabling flexible queries with guarantees in P2P systems, IEEE Internet Computing 8 (3) (2004) 19-26.
[82] E. Tanin, A. Harwood, and H. Samet, Indexing distributed complex data for complex queries, Proc. National Conf. on Digital Government Research 2004, pp. 81-90.
[83] P. Ganesan, M. Bawa, and H. Garcia-Molina, Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems, Proc. 30th Int'l Conf. on Very Large Data Bases VLDB 2004, 29 August - 3 September 2004.
[84] A. Bharambe, M. Agrawal, and S. Seshan, Mercury: Supporting Scalable Multi-Attribute Range Queries, SIGCOMM'04, Aug 30-Sept 3 2004.
[85] K. Aberer, Scalable Data Access in P2P Systems Using Unbalanced Search Trees, Workshop on Distributed Data and Structures WDAS-2002 2002.
[86] K. Aberer, A. Datta, and M. Hauswirth, The Quest for Balancing Peer Load in Structured Peer-to-Peer Systems, Technical Report IC/2003/32 2003.
[87] W. Litwin, M.-A. Neimat, and D. Schneider, RP*: a family of order-preserving scalable distributed data structures, Proc. 20th Int'l Conf. on Very Large Data Bases VLDB'94, September 12-15 1994.
[88] M. Tsangou, S. Ndiaye, M. Seck, and W. Litwin, Range queries to scalable distributed data structure RP*, Proc. Fifth Workshop on Distributed Data and Structures, WDAS 2003, June 2003.
[89] W. Litwin and M.-A. Neimat, k-RP*s: a scalable distributed data structure for high-performance multi-attributed access, Proc. Fourth Int'l Conf. on Parallel and Distributed Information Systems (1996) 120-131.
[90] T. Hodes, S. Czerwinski, B. Zhao, A. Joseph, and R. Katz, An architecture for secure wide-area service discovery, Wireless Networks 8 (2/3) (2002) 213-230.
[91] M. Cai, M. Frank, J. Chen, and P. Szekely, MAAN: A Multi-Attribute Addressable Network for Grid Information Services, Proc. Int'l Workshop on Grid Computing, November 2003.
[92] R. van Renesse, K. P. Birman, and W. Vogels, Astrolabe: A robust and scalable technology for distribute system monitoring, management and data mining, ACM Trans. on Computer Systems 21 (2) (2003) 164-206.
[93] R. Bhagwan, G. Varghese, and G. Voelker, Cone: Augmenting DHTs to support distributed resource discovery, Technical Report, CS2003-0755, July 2003.
[94] K. Albrecht, R. Arnold, and R. Wattenhofer, Join and Leave in Peer-to-Peer Systems: The DASIS Approach, Technical Report 427, Department of Computer Science, November 2003.
- [95] K. Albrecht, R. Arnold, and R. Wattenhofer, Aggregating information in peer-to-peer systems for improved join and leave, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, 25-27 August 2004.
- [96] A. Montresor, M. Jelasity, and O. Babaoglu, Robust aggregation protocol for large-scale overlay networks, Technical Report UBLCS-2003-16, December 2003.
- [97] M. Jelasity, W. Kowalczyk, and M. van Steen, An Approach to Aggregation in Large and Fully Distributed Peer-to-Peer Overlay Networks, Proc. 12th Euromicro Conf. on Parallel, Distributted and Network based Processing PDP 2004, February 2004.
- [98] P. Yalagandula and M. Dahlin, A scalable distributed information management system, SIGCOMM'04, Aug 30-Sept 3 2004.
- [99] M. Bawa, A. Gionis, H. Garcia-Molina, and R. Motwani, The price of validity in dynamic networks, Proc. 2004 ACM SIGMOD Int'l Conf. on the management of data 2004, pp. 515-526.
- [100] J. Aspnes, J. Kirsch, and A. Krishnamurthy, Load Balancing and Locality in Range-Queriable Data Structures, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing PODC 2004, July 25-28 2004.
- [101] G. On, J. Schmitt, and R. Steinmetz, The effectiveness of realistic replication strategies on quality of availability for peer-to-peer systems, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, Sept 1-3 2003, pp. 57-64.
- [102] D. Geels and J. Kubiatowicz, Replica management should be a game, Proc. SIGOPS European Workshop, September 2003.
- [103] E. Cohen and S. Shenker, Replication strategies in unstructured peer to peer networks, Proc. 2002 conference on applications, technologies, architectures and protocols for computer communications 2002, pp. 177-190.
- [104] E. Cohen and S. Shenker, P2P and multicast: replication strategies in unstructured peer to peer networks, Proc. 2002 conference on applications, technologies, architectures and protocols for computer communications 2002, pp. 177-190.
- [105] H. Weatherspoon and J. Kubiatowicz, Erasure coding vs replication: a quantative comparison, Proc. First Int'l Workshop on Peer to Peer Systems IPTPS'02, March 2002.
- [106] D. Lomet, Replicated indexes for distributed data, Proc. Fourth Int'l Conf. on Parallel and Distributed Information Systems, December 18-20 1996, pp. 108-119.
- [107] V. Gopalakrishnan, B. Silaghi, B. Bhattacharjee, and P. Keleher, Adaptive Replication in Peer-to-Peer Systems, Proc. 24th Int'l Conf. on Distributed Computing Systems ICDCS 2004, March 23-26 2004.
- [108] S.-D. Lin, Q. Lian, M. Chen, and Z. Zhang, A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [109] A. Adya, R. Wattenhofer, W. Bolosky, M. Castro, G. Cermak, R. Chaiken, J. Douceur, J. Howell, J. Lorch, and M. Thiemer, Farsite: federated, available and reliable storage for an incompletely trusted environment, ACM SIGOPS Operating Systems Review, Special issue on Decentralized storage systems (2002) 1- 14.
- [110] A. Rowstron and P. Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings ACM SOSP'01, October 2001, pp. 188-201.
- [111] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz, Maintenance-Free Global Data Storage, IEEE Internet Computing 5 (5) (2001) 40-49.
- [112] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, Oceanstore: An Architecture for global-scale persistent storage, Proc. Ninth Int'l Conf. on Architecture Support for Programming Languages and Operating Systems ASPLOS 2000, November 2000, pp. 190-201.
- [113] K. Birman, The Surprising Power of Epidemic Communication, Springer-Verlag Heidelberg Lecture Notes in Computer Science Volume 2584/2003 (2003) 97-102.
- [114] P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola, Introducing reliability in content-based publish-subscribe through epidemic algorithms, Proc. 2nd international workshop on Distributed event-based systems 2003, pp. 1-8.
- [115] P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola, Epidemic Algorithms for Reliable Content-Based Publish-Subscribe: An Evaluation, The 24th Int'l Conf. on Distributed Computing Systems (ICDCS-2004), Mar 23-26, Tokyo University of Technology, Hachioji, Tokyo, Japan (2004)
- [116] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, Epidemic algorithms for replicated data management, Proc. Sixth ACM Symp. on Principles of Distributed Computing 1987, pp. 1-12.
- [117] P. Eugster, R. Guerraoiu, A. Kermarrec, and L. Massoulie, Epidemic information dissemination in distributed systems, IEEE Computer 37 (5) (2004) 60-67.
- [118] W. Vogels, R. v. Renesse, and K. Birman, The power of epidemics: robust communication for large-scale distributed systems, ACM SIGCOMM Computer Communication Review 33 (1) (2003) 131-135.
- [119] S. Voulgaris and M. van Steen, An epidemic protocol for managing routing tables in very large peer to peer networks, Proc. 14th IFIP/IEEE Workshop on Distributed Systems: Operations and Management, October 2003.
- [120] I. Gupta, On the design of distributed protocols from differential equations, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing PODC 2004, July 25-28 2004, pp. 216-225.
- [121] I. Gupta, K. Birman, and R. van Renesse, Fighting fire with fire: using randomized gossip to combat stochastic scalability limits, Cornell University Dept of Computer Science Technical Report, March 2001.
- [122] K. Birman and I. Gupta, Building Scalable Solutions to Distributed Computing Problems using Probabilistic Components, Submitted to the Int'l Conf. on Dependable Systems and Networks DSN-2004, Dependable Computing and Computing Symp. DCCS, June 28- July 1 2004.
- [123] A. Ganesh, A.-M. Kermarrec, and L. Massoulie, Peer-to-peer membership management for gossip-based protocols, IEEE Trans. on Computers 52 (2) (2003) 139-149.
- [124] N. Bailey, Epidemic Theory of Infectious Diseases and its Applications, Second Edition ed. Hafner Press, 1975.
- [125] P. Eugster, R. Guerraoiu, S. Handurukande, P. Kouznetsov, and A.- M. Kermarrec, Lightweight probabilistic broadcast, ACM Trans. on Computer Systems 21 (4) (2003) 341-374.
- [126] H. Weatherspoon and J. Kubiatowicz, Efficient heartbeats and repair of softstate in decentralized object location and routing systems, Proc. SIGOPS European Workshop, September 2002.
- [127] G. Koloniari and E. Pitoura, Content-based Routing of Path Queries in Peer-to-Peer Systems, Proc. 9th Int'l Conf. on Extending DataBase Technology EDBT, March 14-18 2004.
- [128] A. Mohan and V. Kalogaraki, Speculative routing and update propagation: a kundali centric approach, IEEE Int'l Conf. on Communications ICC'03, May 2002.
- [129] G. Koloniari, Y. Petrakis, and E. Pitoura, Content-Based Overlay Networks for XML Peers Based on Multi-Level Bloom Filters, Proc. First Int'l Workshop on Databases, Information Systems and Peer-to-Peer Computing DBISP2P, Sept 7-8 2003, pp. 232-247.
- [130] G. Koloniari and E. Pitoura, Bloom-Based Filters for Hierarchical Data, Proc. 5th Workshop on Distributed Data and Structures (WDAS) (2003)
- [131] B. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13 (7) (1970) 422-426.
- [132] M. Naor and U. Wieder, A Simple Fault Tolerant Distributed Hash Table, Second Int'l Workshop on Peer-to-Peer Systems (IPTPS 03), Berkeley, CA, USA, 20-21 February (2003)
- [133] P. Maymounkov and D. Mazieres, Rateless codes and big downloads, Second Int'l Workshop on Peer-to-Peer Systems, IPTPS'03, February 20-21 2003.
- [134] M. Krohn, M. Freedman, and D. Mazieres, On-the-fly verification of rateless erasure codes for efficient content distribution, Proc. IEEE Symp. on Security and Privacy, May 2004.
- [135] J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, Informed content delivery across adaptive overlay networks, Proc. 2002 conference on applications, technologies, architectures and protocols for computer communications 2002, pp. 47-60.
- [136] J. Plank, S. Atchley, Y. Ding, and M. Beck, Algorithms for High Performance, Wide-Area Distributed File Downloads, Parallel Processing Letters 13 (2) (2003) 207-223.
- [137] M. Castro, P. Rodrigues, and B. Liskov, BASE: Using abstraction to improve fault tolerance, ACM Trans. on Computer Systems 21 (3) (2003) 236-269.
- [138] R. Rodrigues, B. Liskov, and L. Shrira, The design of a robust peer-to-peer system, 10th ACM SIGOPS European Workshop, Sep 2002.
- [139] H. Weatherspoon, T. Moscovitz, and J. Kubiatowicz, Introspective failure analysis: avoiding correlated failures in peer-to-peer systems, Proc. Int'l Workshop on Reliable Peer-to-Peer Distributed Systems, Oct 2002.
- [140] F. Dabek, R. Cox, F. Kaashoek, and R. Morris, Vivaldi: A Decentralized Network Coordinate System, SIGCOMM'04, Aug 30-Sept 3 2004.
- [141] E.-K. Lua, J. Crowcroft, and M. Pias, Highways: proximity clustering for massively scaleable peer-to-peer network routing, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, August 25-27 2004.
- [142] F. Fessant, S. Handurukande, A.-M. Kermarrec, and L. Massoulie, Clustering in Peer-to-Peer File Sharing Workloads, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [143] T. S. E. Ng and H. Zhang, Predicting internet network distance with coordinates-based approaches, IEEE Infocom 2002, The 21st Annual Joint Conf. of the IEEE Computer and Communication Societies, June 23-27 2002.
- [144] K. Hildrum, R. Krauthgamer, and J. Kubiatowicz, Object Location in Realistic Networks, Proc. Sixteenth ACM Symp. on Parallel Algorithms and Architectures (SPAA 2004), June 2004, pp. 25-35.
- [145] P. Keleher, S. Bhattacharjee, and B. Silaghi, Are Virtualized Overlay Networks Too Much of a Good Thing?, First Int'l Workshop on Peer-to-Peer Systems IPTPS, March 2002.
- [146] A. Mislove and P. Druschel, Providing administrative control and autonomy in structured peer-to-peer overlays, The 3rd Int'l Workshop on Peer-to-Peer Systems, June 9-12 2004.
- [147] D. Karger and M. Ruhl, Diminished Chord: A Protocol for Heterogeneous SubGroup Formation in Peer-to-Peer Networks, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [148] B. Awerbuch and C. Scheideler, Consistent, order-preserving data management in distributed storage systems, Proc. Sixteenth ACM Symp. on Parallel Algorithms and Architectures SPAA 2004, June 27-30 2004, pp. 44-53.
[149] M. Freedman and D. Mazieres, Sloppy Hashing and Self-Organizing Clusters, Proc. 2nd Int'l Workshop on Peer-to-Peer Systems IPTPS
[150] F. Dabek, J. Li, E. Sit, J. Robertson, F. Kaashoek, and R. Morris, Designing a DHT for low latency and high throughput, Proc. First Symp. on Networked Systems Design and Implementation (NSDI'04), San Francisco, California, March 29-31 (2004) 85-98.
[151] M. Ruhl, Efficient algorithms for new computational models, Doctoral Dissertation, September 2003.
[152] K. Sollins, Designing for scale and differentiation, Proc. ACM SIGCOMM workshop on Future Directions in network architecture, August 25-27 2003.
[153] L. Massoulie, A. Kermarrec, and A. Ganesh, Network awareness and failure resilience in self-organizing overlay networks, Proc. 22nd Int'l Symp. on Reliable Distributed Systems, SRDS'03, Oct 6-8 2003, pp. 47-55.
[154] R. Cox, F. Dabek, F. Kaashoek, J. Li, and R. Morris, Practical,distributed network coordinates, ACM SIGCOMM Computer Communication Review 34 (1) (2004) 113-118.
[155] K. Hildrum, J. Kubiatowicz, S. Rao, and B. Zhao, Distributed object location in a dynamic network, Proc. 14th annual ACM symposium on parallel algorithms and architectures 2002, pp. 41- 52.
[156] X. Zhang, Q. Zhang, G. Song, and W. Zhu, A Construction of Locality-Aware Overlay Network: mOverlay and its Performance, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 18-28.
[157] N. Harvey, M. B. Jones, M. Theimer, and A. Wolman, Efficient recovery from organization disconnects in Skipnet, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, Feb 20-21 2003.
[158] M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, Lighthouses for scalable distributed location, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
[159] K. Gummadi, S. Saroui, S. Gribble, and D. King, Estimating latency between arbitrary internet end hosts, Proc. SIGCOMM IMW 2002, November 2002.
[160] Y. Liu, X. Liu, L. Xiao, L. Ni, and X. Zhang, Location-aware topology matching in P2P systems, Proc. IEEE Infocomm, Mar 7-11 2004.
[161] G. S. Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, PODC 2004, July 25-28 2004, pp. 197-205.
[162] J. Gao and P. Steenkiste, Design and Evaluation of a Distributed Scalable Content Delivery System, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 54-66.
[163] X. Wang, Y. Zhang, X. Li, and D. Loguinov, On zone-balancing of peer-to-peer networks: analysis of random node join, Proc. joint international conference on measurement and modeling of computer systems, June 2004.
[164] D. Karger and M. Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proc. Sixteenth ACM Symp. on Parallel Algorithms and Architectures SPAA 2004, June 27-30 2004.
[165] D. Karger and M. Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[166] M. Adler, E. Halperin, R. Karp, and V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, Proc. 35th ACM symposium on Theory of Computing 2003, pp. 575-584.
[167] C. Baquero and N. Lopes, Towards peer to peer content indexing, ACM SIGOPS Operating Systems Review 37 (4) (2003) 90-96.
[168] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, Load balancing in structured P2P systems, Proc. 2nd Int'l Workshop on Peer-to-Peer Systems, IPTPS'03, February 20-21 2003.
[169] J. Byers, J. Considine, and M. Mitzenmacher, Simple Load Balancing for Distributed Hash Tables, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
[170] P. Castro, J. Lee, and A. Misra, CLASH: A Protocol for Internet- Scale Utility-Oriented Distributed Computing, Proc. 24th Int'l Conf. on Distributed Computing Systems ICDCS 2004, March 23-26 2004.
[171] A. Stavrou, D. Rubenstein, and S. Sahu, A Lightwight, Robust P2P System to Handle Flash Crowds, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 6-17.
[172] A. Selcuk, E. Uzun, and M. R. Pariente, A reputation-based trust management system for P2P networks, Fourth Int'l Workshop on Global and Peer-to-Peer Computing, April 20-21 2004.
[173] T. Papaioannou and G. Stamoulis, Effective use of reputation in peer-to-peer environments, Fourth Int'l Workshop on Global and Peer-to-Peer Computing, April 20-21 2004.
[174] M. Blaze, J. Feigenbaum, and J. Lacy, Trust and Reputation in P2P networks, http://www.neurogrid.net/twiki/bin/view/Main/ReputationAndTrust (2003)
[175] E. Damiani, D. C. di Vimercati, S. Paraboschi, P. Samarati, and F. Violante, A reputation-based approach for choosing reliable resources in peer to peer networks, Proc. 9th conference on computer and communications security 2002, pp. 207-216.
[176] S. Marti, P. Ganesan, and H. Garcia-Molina, DHT routing using social links, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[177] G. Caronni and M. Waldvogel, Establishing trust in distributed storage providers, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, 1-3 Sept 2003, pp. 128-133.
[178] B. Sieka, A. Kshemkalyani, and M. Singhal, On the security of polling protocols in peer-to-peer systems, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, 25-27 August 2004.
[179] M. Feldman, K. Lai, I. Stoica, and J. Chuang, Robust Incentive Techniques for Peer-to-Peer Networks, ACM E-Commerce Conf. EC'04, May 2004.
[180] K. Anagnostakis and M. Greenwald, Exchange-based Incentive Mechanism for Peer-to-Peer File Sharing, Proc. 24th Int'l Conf. on Distributed Computing Systems ICDCS 2004, March 23-26 2004.
[181] J. Schneidman and D. Parkes, Rationality and self-Interest in peer to peer networks, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
[182] C. Buragohain, D. Agrawal, and S. Subhash, A game theoretic framework for incentives in P2P systems, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, 1-3 Sept 2003, pp. 48-56.
[183] W. Josephson, E. Sirer, and F. Schneider, Peer-to-Peer Authentication with a Distributed Single Sign-On Service, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[184] A. Fiat and J. Saia, Censorship resistant peer to peer content addressable networks, Proc. 13th annual ACM-SIAM symposium on discrete algorithms 2002, pp. 94-103.
[185] N. Daswani and H. Garcia-Molina, Query-flood DoS attacks in gnutella, Proc. 9th ACM Conf. on Computer and Communications Security 2002, pp. 181-192.
[186] A. Singh and L. Liu, TrustMe: anonymous management of trust relationships in decentralized P2P systems, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, Sept 1-3 2003.
[187] A. Serjantov, Anonymizing censorship resistant systems, Proc. Second Int'l Conf. on Peer to Peer Computing, March 2002.
[188] S. Hazel and B. Wiley, Achord: A Variant of the Chord Lookup Service for Use in Censorship Resistant Peer-to-Peer Publishing Systems, Proc. Second Int'l Conf. on Peer to Peer Computing, March 2002.
[189] M. Freedman and R. Morris, Tarzan: a peer-to-peer anonymizing network layer, Proc. 9th ACM Conf. on Computer and Communications Security (2002) 193-206.
[190] M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica, Free-Riding and Whitewashing in Peer-to-Peer Systems, 3rd Annual Workshop on Economics and Information Security WEIS04, May 2004.
[191] L. Ramaswamy and L. Liu, FreeRiding: a new challenge for peer-to-peer file sharing systems, Proc. 2003 Hawaii Int'l Conf. on System Sciences, P2P Track, HICSS2003, January 6-9 2003.
[192] T.-W. Ngan, D. Wallach, and P. Druschel, Enforcing fair sharing of peer-to-peer resources, Second Int'l Workshop on Peer-to-Peer Systems, IPTPS'03, 20-21 February 2003.
[193] L. Cox and B. D. Noble, Samsara: honor among thieves in peer-to-peer storage, Proc. nineteenth ACM symposium on Operating System Principles 2003, pp. 120-132.
[194] M. Surridge and C. Upstill, Grid security: lessons for peer-to-peer systems, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, Sept 1-3 2003, pp. 2-6.
[195] E. Sit and R. Morris, Security considerations for peer-to-peer distributed hash tables, First Int'l Workshop on Peer-to-Peer Systems, March 2002.
[196] C. O'Donnel and V. Vaikuntanathan, Information leak in the Chord lookup protocol, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, 25-27 August 2004.
[197] K. Berket, A. Essiari, and A. Muratas, PKI-Based Security for Peer-to-Peer Information Sharing, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, 25-27 August 2004.
[198] B. Karp, S. Ratnasamy, S. Rhea, and S. Shenker, Spurring adoption of DHTs with OpenHash, a public DHT service, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[199] J. Considine, M. Walfish, and D. G. Andersen, A pragmatic approach to DHT adoption, Technical Report,, December 2003.
[200] G. Li, Peer to Peer Networks in Action, IEEE Internet Computing 6 (1) (2002) 37-39.
[201] A. Mislove, A. Post, C. Reis, P. Willmann, P. Druschel, D. Wallach, X. Bonnaire, P. Sens, J.-M. Busca, and L. Arantes-Bezerra, POST: A Secure, Resilient, Cooperative Messaging System, 9th Workshop on Hot Topics in Operating Systems, HotOS, May 2003.
[202] S. Saroiu, P. Gummadi, and S. Gribble, A measurement study of peer-to-peer file sharing systems, Proc. Multimedia Computing and Networking 2002 MMCN'02, January 2002.
[203] A. Muthitacharoen, R. Morris, T. Gil, and B. Chen, Ivy: a read/write peer-to-peer file system, ACM SIGOPS Operating Systems Review, Special issue on Decentralized storage systems, December 2002, pp. 31-44.
[204] A. Muthitacharoen, R. Morris, T. Gil, and B. Chen, A read/write peer-to-peer file system, Proc. 5th Symp. on Operating System Design and Implementation (OSDI 2002), Boston, MA, December (2002)
[205] F. Annexstein, K. Berman, M. Jovanovic, and K. Ponnavaikko, Indexing techniques for file sharing in scalable peer to peer networks, 11th IEEE Int'l Conf. on Computer Communications and Networks (2002) 10-15.
[206] G. Kan and Y. Faybishenko, Introduction to Gnougat, First Int'l Conf. on Peer-to-Peer Computing 2001 2001, pp. 4-12.
[207] R. Gold and D. Tidhar, Towards a content-based aggregation network, Proc. First Int'l Conf. on Peer to Peer Compuuting 2001, pp. 62-68.
okay bestie, the reading list keeps going 📚✨
- [208] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, Wide-area cooperative storage with CFS, Proc. 18th ACM symposium on Operating System Principles 2001, pp. 202-215.
- [209] M. Freedman, E. Freudenthal, and D. Mazieres, Democratizing content publication with coral, Proc. First Symp. on Networked Systems Design and Implementation NSDI'04, March 29-31 2004, pp. 239-252.
- [210] J. Li, B. T. Loo, J. Hellerstein, F. Kaashoek, D. Karger, and R. Morris, On the Feasibility of Peer-to-Peer Web Indexing and Search, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
- [211] S. Iyer, A. Rowstron, and P. Druschel, Squirrel: a decentralized peer-to-peer web cache, Proc. 21st annual symposium on principles of distributed computing 2002, pp. 213-222.
- [212] M. Bawa, R. Bayardo, S. Rajagopalan, and E. Shekita, Make it fresh, make it quick: searching a network of personal webservers, Proc. 12th international conference on World Wide Web 2003, pp. 577-586.
- [213] B. T. Loo, S. Krishnamurthy, and O. Cooper, Distributed web crawling over DHTs, Technical Report, CSD-04-1305, February 9 2004.
- [214] M. Junginger and Y. Lee, A self-organizing publish/subscribe middleware for dynamic peer-to-peer networks, IEEE Network 18 (1) (2004) 38-43.
- [215] F. Cuenca-Acuna, C. Peery, R. Martin, and T. Nguyen, PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities, Proc. 12th international symposium on High Performance Distributed Computing (HPDC), June 2002.
- [216] M. Walfish, H. Balakrishnan, and S. Shenker, Untangling the web from DNS, Proc. First Symp. on Networked Systems Design and Implementation NSDI'04, March 29-31 2004, pp. 225-238.
- [217] B. Awerbuch and C. Scheideler, Robust distributed name service, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [218] A. Iamnitchi, Resource Discovery in Large Resource-Sharing Environments, Doctoral Dissertation 2003.
- [219] R. Cox, A. Muthitacharoen, and R. Morris, Serving DNS using a Peer-to-Peer Lookup Service, First Int'l Workshop on Peer-to-Peer Systems (IPTPS), March 2002.
- [220] A. Chander, S. Dawson, P. Lincoln, and D. Stringer-Calvert, NEVRLATE: scalable resource discovery, Second IEEE/ACM Int'l Symp. on Cluster Computing and the Grid CCGRID2002 2002, pp. 56-65.
- [221] M. Balazinska, H. Balakrishnan, and D. Karger, INS/Twine: A scalable Peer-to-Peer architecture for Intentional Resource Discovery, Proc. First Int'l Conf. on Pervasive Computing (IEEE) (2002)
- [222] J. Kangasharju, K. Ross, and D. Turner, Secure and resilient peer-to-peer E-mail: design and implementation, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, 1-3 Sept 2003.
- [223] V. Lo, D. Zappala, D. Zhou, Y. Liu, and S. Zhao, Cluster computing on the fly: P2P scheduling of idle cycles in the internet, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [224] A. Iamnitchi, I. Foster, and D. Nurmi, A peer-to-peer approach to resource discovery in grid environments, IEEE High Performance Distributed Computing 2002.
- [225] I. Foster and A. Iamnitchi, On Death, Taxes and the Convergence of Peer-to-Peer and Grid Computing, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
- [226] W. Hoschek, Peer-to-Peer Grid Databases for Web Service Discovery, Concurrency - Practice and Experience (2002) 1-7.
- [227] K. Aberer, A. Datta, and M. Hauswirth, A decentralized public key infrastructure for customer-to-customer e-commerce, Int'l Journal of Business Process Integration and Management (2004)
- [228] S. Ajmani, D. Clarke, C.-H. Moh, and S. Richman, ConChord: Cooperative SDSI Certificate Storage and Name Resolution, First Int'l Workshop on Peer-to-Peer Systems IPTPS, March 2002.
- [229] E. Sit, F. Dabek, and J. Robertson, UsenetDHT: a low overhead Usenet server, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [230] H.-Y. Hsieh and R. Sivakumar, On transport layer support for peer-to-peer networks, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [231] I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana, Internet indirection infrastructure, Proc. 2002 conference on applications, technologies, architectures and protocols for computer communications, August 19-23 2002, pp. 73-86.
- [232] E. Halepovic and R. Deters, Building a P2P forum system with JXTA, Proc. Second IEEE Int'l Conf. on Peer to Peer Computing P2P'02, September 5-7 2002.
- [233] M. Wawrzoniak, L. Peterson, and T. Roscoe, Sophia: an Information Plane for networked systems, ACM SIGCOMM Computer Communication Review 34 (1) (2004) 15-20.
- [234] D. Tran, K. Hua, and T. Do, A Peer-to-Peer Architecture for Media Streaming, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 121-133.
- [235] V. Padmanabhan, H. Wang, and P. Chou, Supporting heterogeneity and congestion control in peer-to-peer multicast streaming, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [236] A. Nicolosi and D. Mazieres, Secure acknowledgment of multicast messages in open peer-to-peer networks, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [237] R. Zhang and C. Hu, Borg: a hybrid protocol for scalable application-level multicast in peer-to-peer networks, Proc. 13th international workshop on network and operating systems for digital audio and video 2003, pp. 172-179.
- [238] M. Sasabe, N. Wakamiya, M. Murata, and H. Miyahara, Scalable and continuous media streaming on peer-to-peer networks, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, Sept 1-3 2003, pp. 92-99.
- [239] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava, PROMISE: peer-to-peer media streaming using CollectCast, Proc. eleventh ACM international conference on multimedia 2003, pp. 45-54.
- [240] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proc. 19th ACM symposium on operating systems principles 2003, pp. 298-313.
- [241] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, SCRIBE: a large-scale and decentralized application-level multicast infrastructure, IEEE Journal on Selected Areas in Communications 20 (8) (2002)
- [242] S. Zhuang, B. Zhao, A. Joseph, R. Katz, and J. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proc. 11th ACM international workshop on network and operating systems support for digital audio and video, Jan 2001.
- [243] R. Lienhart, M. Holliman, Y.-K. Chen, I. Kozintsev, and M. Yeung, Improving media services on P2P networks, IEEE Internet Computing 6 (1) (2002) 58-67.
- [244] S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu, Data Centric Storage in Sensornets with GHT, a geographic hash table, Mobile Networks and Applications 8 (4) (2003) 427-442.
- [245] M. Demirbas and H. Ferhatosmanoglu, Peer-to-peer spatial queries in sensor networks, Proc. Third Int'l IEEE Conf. on Peer-to-Peer Computing, 1-3 Sept 2003, pp. 32-39.
- [246] S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker, GHT: a geographic hash table for data-centric storage, Proc. First ACM Int'l Workshop on Wireless Sensor Networks and Applications (Mobicom) 2002, pp. 78-87.
- [247] J. Hellerstein and W. Wang, Optimization of In-Network Data Reduction, Proc. First Workshop on Data Management for Sensor Networks DMSN 2004, August 30th 2004.
- [248] J. Li, J. Stribling, T. Gil, R. Morris, and F. Kaashoek, Comparing the performance of distributed hash tables under churn, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
- [249] S. Shenker, The data-centric revolution in networking, Keynote Speech, 29th Int'l Conf. on Very Large Data Bases, September 9-12 2003.
- [250] S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu, What can databases do for P2P?, Proc. Fourth Int'l Workshop on Databases and the Web, WebDB2001, May 24-25 2001.
- [251] D. Clark, The design philosophy of the DARPA internet protocols, ACM SIGCOMM Computer Communication Review, Symp. proceedings on communications architectures and protocols 18 (4) (1988)
- [252] J.-C. Laprie, Dependable Computing and Fault Tolerance: Concepts and Terminology, Twenty-Fifth Int'l Symp. on Fault-Tolerant Computing, Highlights from Twenty-Five Years 1995, pp. 2-13.
- [253] D. Clark, J. Wroclawski, K. Sollins, and R. Braden, Tussle in cyberspace: defining tomorrow's internet, Conf. on Applications, Technologies, Architectures and Protocols for Computer Communications 2002, pp. 347-356.
- [254] L. O. Alima, A. Ghodsi, and S. Haridi, "A framework for structured peer-to-peer overlay networks," in Global computing, vol. 3267, Lecture Notes in Computer Science: Springer Berlin / Heidelberg, 2005, pp. 223-249.
- [255] Clip2, The Gnutella Protocol Specification, http://www.clip2.com (2000)
- [256] Napster, http://www.napster.com (1999)
- [257] J. Mishchke and B. Stiller, A methodology for the design of distributed search in P2P middleware, IEEE Network 18 (1) (2004) 30-37.
- [258] J. Li and K. Sollins, Implementing aggregation and broadcast over distributed hash tables. Full report, http://krs.lcs.mit.edu/regions/docs.html (November) (2003)
- [259] M. Castro, M. Costa, and A. Rowstron, Should we build Gnutella on a structured overlay?, ACM SIGCOMM Computer Communication Review 34 (1) (2004) 131-136.
- [260] A. Singla and C. Rohrs, Ultrapeers: Another Step Towards Gnutella Scalability, http://groups.yahoo.com/group/the_gdf/files/Proposals/Working%20Proposals/Ultrapeer/ Version 1.0, 26 November (2002)
- [261] B. Cooper and H. Garcia-Molina, Ad hoc, Self-Supervising Peer-to-Peer Search Networks, Technical Report, http://www.cc.gatech.edu/~cooperb/odin/ 2003.
- [262] R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval. Addison Wesley, Essex, England, 1999.
- [263] S. Sen and J. Wang, Analyzing peer-to-peer traffic across large networks, IEEE/ACM Trans. on Networking 12 (2) (2004) 219-232.
- [264] H. Balakrishnan, S. Shenker, and M. Walfish, Semantic-Free Referencing in Linked Distributed Systems, Second Int'l Workshop on Peer-to-Peer Systems IPTPS 03, 20-21 February 2003.
- [265] B. Yang, P. Vinograd, and H. Garcia-Molina, Evaluating GUESS and non-forwarding peer-to-peer search, The 24th Int'l Conf. on Distributed Computing Systems ICDCS'04, Mar 23-26 2004.
- [266] A. Gupta, B. Liskov, and R. Rodrigues, One Hop Lookups for Peer-to-Peer Overlays, 9th Workshop on Hot Topics in Operating Systems (HotOS), 18-21 May 2003.
[267] A. Gupta, B. Liskov, and R. Rodrigues, Efficient routing for peer-to-peer overlays, First symp. on Networked Systems Design and Implementation (NSDI), Mar 29-31 2004, pp. 113-126.
[268] A. Mizrak, Y. Cheng, V. Kumar, and S. Savage, Structured superpeers: leveraging heterogeneity to provide constant-time lookup, IEEE Workshop on Internet Applications, June 23-24 2003.
[269] L. Adamic, R. Lukose, A. Puniyani, and B. Huberman, Search in power-law networks, Physical review E, The American Physical Society 64 (046135) (2001)
[270] F. Banaei-Kashani and C. Shahabi, Criticality-based analysis and design of unstructured peer-to-peer networks as "complex systems", Proc. 3rd IEEE/ACM Int'l Symp. on Cluster Computing and the Grid 2003, pp. 351-358.
[271] KaZaa, KaZaa Media Desktop, www.kazaa.com (2001)
[272] S. Sen and J. Wang, Analyzing peer-to-peer traffic across large networks, Proc. second ACM SIGCOMM workshop on Internet measurement, November 06-08 2002, pp. 137-150.
[273] DirectConnect, http:www.neo-modus.com (2001)
[274] S. Saroiu, K. Gummadi, R. Dunn, S. Gribble, and H. Levy, An analysis of Internet content delivery systems, ACM SIGOPS Operating Systems Review 36 (2002) 315-327.
[275] A. Loo, The Future or Peer-to-Peer Computing, Communications of the ACM 46 (9) (2003) 56-61.
[276] B. Yang and H. Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems (extended), 27th Int'l Conf. on Very Large Data Bases, September 11-14 2001.
[277] D. Scholl, OpenNap Home Page, http://opennap.sourceforge.net/ (2001)
[278] S. Ghemawat, H. Gobioff, and S.-T. Leung, The Google file system, Proc. 19th ACM symposium on operating systems principles 2003, pp. 29-43.
[279] I. Clarke, S. Miller, T. Hong, O. Sandberg, and B. Wiley, Protecting Free Expression Online with Freenet, IEEE Internet Computing 6 (1) (2002)
[280] J. Mache, M. Gilbert, J. Guchereau, J. Lesh, F. Ramli, and M. Wilkinson, Request algorithms in Freenet-style peer-to-peer systems, Proc. Second IEEE Int'l Conf. on Peer to Peer Computing P2P'02, September 5-7 2002.
[281] C. Rohrs, Query Routing for the Gnutella Networks, http://www.limewire.com/developer/query_routing/keyword%20routing.htm Version 1.0 (2002)
[282] I. Clarke, Freenet's Next Generation Routing Protocol, http://freenetproject.org/index.php?page=ngrouting, 20th July 2003.
[283] A. Z. Kronfol, FASD: A fault-tolerant, adaptive scalable distributed search engine, Master's Thesis http://www.cs.princeton.edu/~akronfol/fasd/ 2002.
[284] S. Gribble, E. Brewer, J. M. Hellerstein, and D. Culler, Scalable, Distributed Data Structures for Internet Service Construction, Proc. 4th Symp. on Operating Systems Design and Implementation OSDI 2000, October 2000.
[285] K. Aberer, Efficient Search in Unbalanced, Randomized Peer-to-Peer Search Trees, EPFL Technical Report IC/2002/79 (2002)
[286] R. Honicky and E. Miller, A fast algorithm for online placement and reorganization of replicated data, Proc. 17th Int'l Parallel and Distributed Processing Symp., April 2003.
[287] G. S. Manku, Routing networks for distributed hash tables, Proc. 22nd annual ACM Symp. on Principles of Distributed Computing, PODC 2003, July 13-16 2003, pp. 133-142.
[288] D. Lewin, Consistent hashing and random trees: algorithms for caching in distributed networks, Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (1998)
[289] S. Lei and A. Grama, Extended consistent hashing: a framework for distributed servers, Proc. 24th Int'l Conf. on Distributed Computing Systems ICDCS 2004, March 23-26 2004.
[290] W. Litwin, Re: Chord & LH*, Email to Ion Stoica, March 23 2004a.
[291] J. Li, J. Stribling, R. Morris, F. Kaashoek, and T. Gil, A performance vs. cost framework for evaluating DHT design tradeoffs under churn, Proc. IEEE Infocom, Mar 13-17 2005.
[292] S. Zhuang, D. Geels, I. Stoica, and R. Katz, On failure detection algorithms in overlay networks, Proc. IEEE Infocomm, Mar 13-17 2005.
[293] X. Li, J. Misra, and C. G. Plaxton, Active and Concurrent Topology Maintenance, The 18th Annual Conf. on Distributed Computing (DISC 2004), Trippenhuis, Amsterdam, the Netherlands, October 4 - October 7 (2004)
[294] K. Aberer, L. O. Alima, A. Ghodsi, S. Girdzijauskas, M. Hauswirth, and S. Haridi, The essence of P2P: a reference architecture for overlay networks, Proc. of the 5th international conference on peer-to-peer computing, Aug 31-Sep 2 2005.
[295] C. Tang, M. Buco, R. Chang, S. Dwarkadas, L. Luan, E. So, and C. Ward, Low traffic overlay networks with large routing tables, Proc. of ACM Sigmetrics Int'l Conf. on Measurement and Modeling of Comp. Sys., Jun 6-10 2005, pp. 14-25.
[296] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, Handling churn in a DHT, Proc. of the USENIX Annual Technical Conference, June 2004.
[297] C. Blake and R. Rodrigues, High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two, 9th Workshop on Hot Topics in Operating Systems (HotOS), Lihue, Hawaii, 18-21 May (2003)
[298] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, and H. Yu, OpenDHT: a public DHT service and its uses, Proc. of the conf. on Applications, technologies, architectures and protocols for computer communications, Aug 22-26 2005, pp. 73-84.
[299] T. Gil, F. Kaashoek, J. Li, R. Morris, and J. Stribling, p2psim, a simulator for peer-to-peer protocols, http://www.pdos.lcs.mit.edu/p2psim/ (2003)
[300] K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, Distributed object location in a dynamic network, Theory of Computing Systems (2004)
[301] N. Lynch, D. Malkhi, and D. Ratajczak, Atomic data access in distributed hash tables, Proc. Int'l Peer-to-Peer Symp., March 7-8 2002.
[302] S. Gilbert, N. Lynch, and A. Shvartsman, RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks, Technical Report, MIT-CSAIL-TR-890 2004.
[303] N. Lynch and I. Stoica, MultiChord: A resilient namespace management algorithm, Technical Memo MIT-LCS-TR-936 2004.
[304] J. Risson, K. Robinson, and T. Moors, Fault tolerant active rings for structured peer-to-peer overlays, Proc. of the 30th Annual IEEE Conf. on Local Computer Networks, Nov 15-17 2005, pp. 18-25.
[305] B. Awerbuch and C. Scheideler, Peer-to-peer systems for prefix search, Proc. 22nd annual ACM Symp. on Principles of Distributed Computing 2003, pp. 123-132.
[306] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica, Towards a common API for structured P2P overlays, Proc. Second Int'l Workshop on Peer to Peer Systems IPTPS 2003, February 2003.
[307] N. Feamster and H. Balakrishnan, Towards a logic for wide-area Internet routing, Proc. ACM SIGCOMM workshop on Future Directions in Network Architecture, August 25-27 2003, pp. 289-300.
[308] B. Ahlgren, M. Brunner, L. Eggert, R. Hancock, and S. Schmid, Invariants: a new design methodology for network architectures, Proc. ACM SIGCOMM workshop on Future Direction in Network Architecture, August 30 2004, pp. 65-70.
[309] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition. MIT Press, McGraw-Hill, Cambridge, London, England, 2003.
[310] I. Abraham, D. Malkhi, and O. Dubzinski, LAND:Stretch (1+epsilon) Locality Aware Networks for DHTs, Proc. ACM-SIAM Symp. on Discrete Algorithms SODA-04 2004.
[311] S. Jain, R. Mahajan, and D. Wetherall, A study of the performance potential of DHT-based overlays, Proc. of the 4th Usenix symposium on internet technologies and systems (USITS), Mar 2003.
[312] J. Risson, A. Harwood, and T. Moors, Stable high-capacity one-hop distributed hash tables, Proc. of the IEEE Symposium on Computers and Communications (ISCC'06), Jun 26-29 2006.
[313] V. Ramasubramanian and E. Sirer, Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays, Proc. First Symp. on Networked Systems Design and Implementation (NSDI'04), San Francisco, California, March 29-31 (2004) 99-112.
[314] I. Abraham, A. Badola, D. Bickson, D. Malkhi, S. Maloo, and S. Ron, Practical locality-awareness for large scale information sharing, Proc. 4th International Workshop on Peer-to-Peer Systems, Feb 24-25 2005.
[315] B. Leong, B. Liskov, and E. Demaine, Epichord: parallelizing the Chord lookup algorithm with reactive routing state management, Proc. of the 12th International Conference on Networks, Nov 2004.
[316] J. Li, J. Stribling, R. Morris, and F. Kaashoek, Bandwidth-efficient management of DHT routing tables, Proc. 2nd Symposium on Networked Systems Design and Implementation, May 2-4 2005.
[317] S. Rhea, B.-G. Chun, J. Kubiatowicz, and S. Shenker, Fixing the embarrassing slowness of OpenDHT on PlanetLab, Proc. of the Second USENIX Workshop on Real, Large Distributed Systems, Dec 13 2005.
[318] M. Costa, M. Castro, A. Rowstron, and P. Key, PIC: Practical Internet coordinates for distance estimation, Proc. of the 24th international conference on distributed computing systems, Mar 2004.
[319] M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman, An evaluation of scalable application- level multicast built using peer-to-peer overlays, Proc. of the 22nd Annual Joint Conf. of the IEEE Comp. and Comm. Soc. (INFOCOM), 30 Mar - 3 Apr 2003, pp. 1510-1520.
[320] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, Application-level multicast using content-addressable networks, Proc. of the Third International Workshop on Networked Group Communication, Nov 7-9 2001.
[321] S. El-Ansary, L. Alima, P. Brand, and S. Haridi, Efficient broadcast in structured P2P networks, Second Int'l Workshop on Peer-to-Peer Systems (IPTPS 03), Berkeley, CA, USA, 20-21 February (2003)
[322] J. Li, K. Sollins, and D.-Y. Lim, Implementing aggregation and broadcast over Distributed Hash Tables, ACM Computer Communication Reviews 35 (1) (2005) 81-92.
[323] V. Pai, K. Tamilmani, V. Sambamurthy, K. Kumar, and A. Mohr, Chainsaw: eliminating trees from overlay multicast, Proc. 4th Int'l Workshop on Peer-to-Peer Systems, February 24-25 2005.
[324] K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, and M. Budiu, Bimodal Multicast, ACM Trans. on Computer Systems 17 (2) (1999) 41-88.
[325] Z. Zhang, S. Chen, Y. Ling, and R. Chow, Resilient capacity-aware multicasting based on overlay networks, Proc. of the 25th IEEE Int'l Conf. on Distributed Computing Systems, 6-10 June 2005, pp. 565-574.
[326] A. Bharambe, S. Rao, V. Padmanabhan, S. Seshan, and H. Zhang, The impact of heterogeneous bandwidth constraints on DHT-based multicast protocols, Proc. 4th Int'l Workshop on Peer-to-Peer Systems, February 24-25 2005.
[327] A. Ghodsi, L. O. Alima, S. El-Ansary, P. Brand, and S. Haridi, Self-correcting broadcast in distributed hash tables, Proc. of the 15th IASTED International Conf. on Parallel and Distributed Computing and Systems, Nov 2003.
[328] R. Mahajan, M. Castro, and A. Rowstron, Controlling the cost of reliability in peer-to-peer overlays, Second Int'l Workshop on Peer-to-Peer Systems IPTPS'03, February 20-21 2003.
[329] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, Handling churn in a DHT, Report No. UCB/CSD-03-1299, University of California, also Proc. USENIX Annual Technical Conference, June 2003.
[330] M. Castro, M. Costa, and A. Rowstron, Performance and dependability of structured peer-to-peer overlays, Microsoft Research Technical Report MSR-TR-2003-94, December. Also 2004 Int'l Conf. on Dependable Systems and Networks, June 28-July 1 2003.
[331] D. Liben-Nowell, H. Balakrishnan, and D. Karger, Analysis of the evolution of peer-to-peer systems, Annual ACM Symp. on Principles of Distributed Computing 2002, pp. 233-242.
[332] L. Alima, S. El-Ansary, P. Brand, and S. Haridi, DKS(N,k,f): a family of low communication, scalable and fault-tolerant infrastructures for P2P applications, Proc. 3rd IEEE/ACM Int'l Symp. on Cluster Computing and the Grid (2003) 344-350.
[333] D. Karger and M. Ruhl, Finding nearest neighbours in growth-restricted metrics, Proc. 34th annual ACM symposium on Theory of computing 2002, pp. 741-750.
[334] S. Ratnasamy, A Scalable Content-Addressable Network, Doctoral Dissertation 2002.
[335] S. McCanne and S. Floyd, The LBNL/UCB Network Simulator.
[336] M. Naor and U. Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proc. fifteenth annual ACM Symp. on Parallel Algorithms and Architectures, SPAA 2003, June 7-9 2003, pp. 50-59.
[337] N. D. de Bruijn, A combinatorial problem, Koninklijke Netherlands: Academe Van Wetenschappen 49 (1946) 758-764.
[338] J.-W. Mao, "The Coloring and Routing Problems on de Bruijn Interconnection Networks," in Doctoral Dissertation, National Sun Yat-sen University, 2003.
[339] M. L. Schlumberger, De Bruijn communication networks, Doctoral Dissertation 1974.
[340] M. Imase and M. Itoh, Design to minimize diameter on building-block network, IEEE Trans. on Computers C-30 (6) (1981) 439-442.
[341] S. M. Reddy, D. K. Pradhan, and J. G. Kuhl, Direct graphs with minimal and maximal connectivity, Technical Report, School of Engineering, Oakland University (1980)
[342] R. A. Rowley and B. Bose, Fault-tolerant ring embedding in de Bruijn networks, IEEE Trans. on Computers 42 (12) (1993) 1480-1486.
[343] K. Y. Lee, G. Liu, and H. F. Jordan, Hierarchical networks for optical communications, Journal of Parallel and Distributed Computing 60 (2000) 1-16.
[344] M. Naor and U. Wieder, Know thy neighbor's neighbor: better routing for skip-graphs and small worlds, The 3rd Int'l Workshop on Peer-to-Peer Systems, February 26-27 2004.
[345] P. Fraigniaud and P. Gauron, The content-addressable networks D2B, Technical Report 1349, Laboratoire de Recherche en Informatique, January 2003.
[346] A. Datta, S. Girdzijauskas, and K. Aberer, On de Bruijn routing in distributed hash tables: there and back again, Proc. Fourth IEEE Int'l Conf. on Peer-to-Peer Computing, , 25-27 August 2004.
[347] W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Proc. Workshop on Algorithms and Data Structures, August 17-19 1989, pp. 437-449.
[348] W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33 (6) (1990) 668-676.
[349] J. Gray, The transaction concept: Virtues and limitations, Proc. VLDB, September 1981.
[350] B. T. Loo, J. M. Hellerstein, R. Huebsch, S. Shenker, and I. Stoica, Enhancing P2P file-sharing with internet-scale query processor, Proc. 30th Int'l Conf. on Very Large Data Bases VLDB 2004, 29 August-3 September 2004.
[351] M. Stonebraker, P. Aoki, W. Litwin, A. Pfeffer, A. Sah, J. Sidell, C. Staelin, and A. Yu, Mariposa: a wide-area distributed database system, THE VLDB Journal - The Int'l Journal of Very Large Data Bases (5) (1996) 48-63.
[352] V. Cholvi, P. Felber, and E. Biersack, Efficient Search in Unstructured Peer-to-Peer Networks, Proc. Symp. on Parallel Algorithms and Architectures, July 2004.
[353] S. Daswani and A. Fisk, Gnutella UDP Extension for Scalable Searches (GUESS) v0.1, http://www.limewire.org/fisheye/viewrep/~raw,r=1.2/limecvs/core/guess_01.html (2002)
[354] A. Fisk, Gnutella Dynamic Query Protocol v0.1, Gnutella Developer Forum (2003)
[355] O. Gnawali, A Keyword Set Search System for Peer-to-Peer Networks, Master's Thesis 2002.
[356] Limewire, Limewire Host Count, http://www.limewire.com/english/content/netsize.shtml (2004)
[357] A. Fisk, Gnutella Ultrapeer Query Routing, http://groups.yahoo.com/group/the_gdf/files/Proposals/Working%20Proposals/search/Ultrapeer%20QRP/ v0.1 (2003)
[358] A. Fisk, Gnutella Dynamic Query Protocol, http://groups.yahoo.com/group/the_gdf/files/Proposals/Working%20Proposals/search/Dynamic%20Querying/ v0.1 (2003)
[359] S. Thadani, Meta Data searches on the Gnutella Network (addendum), http://www.limewire.com/developer/MetaProposal2.htm (2001)
[360] S. Thadani, Meta Information Searches on the Gnutella Networks, http://www.limewire.com/developer/metainfo_searches.html (2001)
[361] P. Reynolds and A. Vahdat, Efficient peer-to-peer keyword searching, ACM/IFP/USENIX Int'l Middleware Conference, Middleware 2003, June 16-20 2003.
[362] W. Terpstra, S. Behnel, L. Fiege, J. Kangasharju, and A. Buchmann, Bit Zipper Rendezvous, optimal data placement for general P2P queries, Proc. First Int'l Workshop on Peer-to-Peer Computing and Databases, March 14 2004.
[363] A. Singhal, Modern Information Retrieval: A Brief Overview, IEEE Data Engineering Bulletin 24 (4) (2001) 35-43.
[364] E. Cohen, A. Fiat, and H. Kaplan, Associative Search in Peer to Peer Networks: Harnessing Latent Semantics, IEEE Infocom 2003, The 22nd Annual Joint Conf. of the IEEE Computer and Communications Societies, March 30-April 3 2003.
[365] W. Muller and A. Henrich, Fast retrieval of high-dimensional feature vectors in P2P networks using compact peer data summaries, Proc. 5th ACM SIGMM international workshop on Multimedia Information Retrieval, November 7 2003, pp. 79-86.
[366] M. T. Ozsu and P. Valduriez, Principles of Distributed Database Systems, 2nd edition ed. Prentice Hall, 1999.
[367] G. Salton, A. Wong, and C. S. Yang, A vector space model for automatic indexing, Communications of the ACM 18 (11) (1975) 613- 620.
[368] S. E. Robertson, S. Walker, and M. Beaulieu, Okapi at TREC-7: automatic ad hoc, filtering, VLC and filtering tracks, Proc. Seventh Text REtrieval Conference, TREC-7, NIST Special Publication 500-242, July 1999, pp. 253-264.
[369] A. Singhal, J. Choi, D. Hindle, D. Lewis, and F. Pereira, AT&T at TREC-7, Proc. Seventh Text REtrieval Conf. TREC-7, July 1999, pp. 253-264.
[370] K. Sankaralingam, S. Sethumadhavan, and J. Browne, Distributed Pagerank for P2P Systems, Proc. 12th international symposium on High Performance Distributed Computing HPDC, June 22-24 2003.
[371] I. Klampanos and J. Jose, An architecture for information retrieval over semi-collaborated peer-to-peer networks, Proc. 2004 ACM symposium on applied computing 2004, pp. 1078-1083.
[372] C. Tang, Z. Xu, and S. Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proc. 2003 conference on Applications, Technologies, Architectures and Protocols for Computer Communications, August 25-29 2003, pp. 175-186.
[373] C. Tang and S. Dwarkadas, Hybrid global-local indexing for efficient peer-to-peer information retrieval, Proc. First Symp. on Networked Systems Design and Implementation NSDI'04, March 29-31 2004, pp. 211-224.
[374] G. W. Furnas, S. Deerwester, S. T. Dumais, T. K. Landauer, R. A. Harshman, L. A. Streeter, and K. E. Lochbaum, Information retrieval using a singular value decomposition model of latent semantic structure, Proc. 11th Annual Int'l ACM SIGIR Conf. on Research and Development in Information Retrieval 1988, pp. 465-480.
[375] C. Tang, S. Dwarkadas, and Z. Xu, On scaling latent semantic indexing for large peer-to-peer systems, The 27th Annual Int'l ACM SIGIR Conf. SIGIR'04, ACM Special Interest Group on Information Retrieval, July 2004.
[376] S. Milgram, The small world problem, Psychology Today 1 (61) (1967)
[377] J. Kleinberg, The small-world phenonemon: An algorithmic perspective, Proc. 32nd ACM Symp. on Theory of Computing (2000)
[378] Y. Petrakis and E. Pitoura, "On constructing small worlds in unstructured peer-to-peer systems," in Current trends in database technology (Proc. First Int'l Workshop on Peer-to-Peer Computing and Databases, Heraklion, Crete, Greece, March 14), vol. 3268, Lecture Notes in Computer Science: Springer, 2004, pp. 415-424.
[379] A. Iamnitchi, M. Ripeanu, and I. Foster, Locating Data in (Small World?) P2P Scientific Collaborations, First Int'l Workshop on Peer-to-Peer Systems (IPTPS), Cambridge, MA, March (2002)
[380] Y. Ren, C. Sha, W. Qian, A. Zhou, B. Ooi, and K. Tan, Explore the "small world phenomena" in pure P2P information sharing systems, Proc. 3rd IEEE/ACM Int'l Symp. on Cluster Computing and the Grid (2003) 232-239.
[381] G. S. Manku, M. Bawa, and P. Raghavan, Symphony: Distributed Hashing in a Small World, Proc. 4th USENIX Symp. on Internet Technologies and Systems, March 26-28 2003.
[382] W. Litwin and S. Sahri, Implementing SD-SQL Server: a Scalable Distributed Database System, CERIA Research Rerpot 2004-04-02, April 2004.
[383] M. Jarke and J. Koch, Query Optimization in Database Systems, ACM Computing Surveys 16 (2) (1984) 111-152.
[384] J. L. Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM 18 (9) (1975) 509-517.
[385] B. Chun, I. Stoica, J. Hellerstein, R. Huebsch, S. Jeffery, B. T. Loo, S. Mardanbeigi, T. Roscoe, S. Rhea, and S. Schenker, Querying at Internet Scale, Proc. 2004 ACM SIGMOD international conference on management of data, demonstration session 2004, pp. 935-936.
References 📚
[386] P. Cao and Z. Wang, Efficient top-K query calculation in distributed networks, Proc. 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing PODC 2004, July 25-28 2004, pp. 206-215.
[387] D. Psaltoulis, I. Kostoulas, I. Gupta, K. Birman, and A. Demers, Practical algorithms for size estimation in large and dynamic groups, Proc. Twenty-Third Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, PODC 2004, July 25-28 2004.
[388] R. van Renesse, The importance of aggregation, Springer-Verlag Lecture Notes in Computer Science "Future Directions in Distributed Computing". A. Schiper, A. A. Shvartsman, H. Weatherspoon, and B. Y. Zhao, editors. Springer-Verlag, Heidelberg volume 2584 (2003)
Author's Addresses 🎀
Okay, here's where you can find the authors, bestie! 💜
John Risson School of Elec Eng and Telecommunications University of New South Wales Sydney NSW 2052 Australia
EMail: jr@tuffit.com
Tim Moors School of Elec Eng and Telecommunications University of New South Wales Sydney NSW 2052 Australia
EMail: t.moors@unsw.edu.au
Full Copyright Statement 💖
Okay so the copyright is The IETF Trust (2007), and this document is subject to the rights, licenses and restrictions in BCP 78. Except for what BCP 78 says, the authors keep all their rights. 🫶
The legal disclaimer is kind of intense, so here it is word for word:
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property 🦋
The IETF doesn't take a side on whether any Intellectual Property Rights claimed for this technology are valid or how far they reach, and it doesn't say whether licenses are available. It also doesn't claim to have checked for those rights itself. 👀
If you want the details on how rights work for RFC documents, check out BCP 78 and BCP 79. 📖
Copies of IPR disclosures made to the IETF Secretariat, plus any assurances of licenses that are going to be available, live in the IETF online IPR repository at http://www.ietf.org/ipr. You can also find out what happens if someone tries to get a general license or permission to use those proprietary rights as an implementer or user of this specification. 🌸
The IETF really wants to hear about it if you know of any copyrights, patents, patent applications, or other proprietary rights that might cover technology needed to implement this standard. Send that info to ietf-ipr@ietf.org. 💅
📦 where this page comes from
- ietf: rfc4981 2007-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms