A number of Distributed Hash Table (DHT)-based protocols
have been proposed to address the issue of scalability in peer-topeer
networks. However, it remains an open question whether
there exists a DHT scheme that can achieve the theoretical lower
bound of log n / (log log n).
on network diameter when the average routing
table size at nodes is no more than log n. In this paper, we
present Ulysses, a peer-to-peer network based on the butterfly
topology that matches this theoretical lower bound. Compared
to existing DHT-based schemes with similar routing table size,
Ulysses reduces the network diameter by a factor of log log n,
which is 2-4 for typical configurations. This translates into the
same amount of reduction on query latency and average traffic
per link/node. In addition, Ulysses maintains the same level of
robustness in terms of routing in the face of faults and recovering
from graceful/ungraceful joins/departures, as provided by existing
DHT-based schemes. The protocol is formally verified for
its correctness and robustness using techniques from distributed
computing. The performance of the protocol has been evaluated
using both analysis and simulation.