 |  |
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.
Constant Lookup Time Systems
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.
PlanetLab
We are grateful to the PlanetLab infrastructure for enabling us to deploy our initial prototype across the planet.
