## RELATED WORK |

**Structured Peer to Peer Systems**

Beehive is based on a structured peer-to-peer infrastructure.
These systems provide automatic, self-managing overlay networks that can
heal around failures, though may incur high lookup latencies. Beehive
complements their self-organization with low-latency lookups.

**Polynomial Lookup Time Systems**

- CAN, O(d N^(1/d)) lookup, O(d) routing state.
- Plaxton Routing, O(log N) lookup, O(log N) routing state.
- Pastry, O(log N) lookup, O(log N) routing state.
- Chord, O(log N) lookup, O(log N) routing state.
- Tapestry, O(log N) lookup, O(log N) routing state.
- Kademlia, O(log N) lookup, O(log N) routing state.
- Skipnet, O(log N) lookup, O(log N) routing state.
- Viceroy, O(log N) lookup, O(1) routing state.
- Wieder and Naor, O(log N) lookup, O(1) routing state.
- Koorde, O(log N/log log N) lookup, O(log N) routing state.

These systems achieve constant hop lookups for any query distribution, though they may perform excessive replication. Beehive can achieve less than 1-hop performance with optimal replication.

- One-Hop, 1 hop lookup, O(N) routing state.
- Kelips, 1-2 hop lookup, O(sqrt N) routing state.
- Structured Super-peers, 2 hop lookups, O(sqrt N) routing state.
- SALAD, d hop lookup, O(d N^(1/d)) routing state.

We are grateful to the PlanetLab infrastructure for enabling us to deploy our initial prototype across the planet.

Cornell University