Browsing by Author "Spring, Neil"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Playing Vivaldi in Hyperbolic Space(2006-11-17) Lumezanu, Cristian; Spring, NeilInternet coordinate systems have emerged as an efficient method to estimate the latency between pairs of nodes without any communication between them. They avoid the cost of explicit measurements by placing each node in a finite coordinate space and estimating the latency between two nodes as the distance between their positions in the space. In this paper, we adapt the Vivaldi algorithm to use the Hyperbolic space for embedding. Researchers have found promise in Hyperbolic space due to its mathematical elegance and its ability to model the structure of the Internet. We attempt to combine the elegance of the Hyperbolic space with the practical, decentralized Vivaldi algorithm. We evaluate both Euclidean and Hyperbolic Vivaldi on three sets of real-world latencies. Contrary to what we expected, we find that the performance of the two versions of Vivaldi varies with each data set. Furthermore, we show that the Hyperbolic coordinates have the tendency to underestimate large latencies (> 100 ms) but behave better when estimating short distances. Finally, we propose two distributed heuristics that help nodes decide whether to choose Euclidean or Hyperbolic coordinates when estimating distances to their peers. This is the first comparison of Euclidean and Hyperbolic embeddings using the same distributed solver and using a data set with more than 200 nodes.Item A Secure DHT via the Pigeonhole Principle(2007-09-24) Baden, Randy; Bender, Adam; Levin, Dave; Sherwood, Rob; Spring, Neil; Bhattacharjee, BobbyThe standard Byzantine attack model assumes no more than some fixed fraction of the participants are faulty. This assumption does not accurately apply to peer-to-peer settings, where Sybil attacks and botnets are realistic threats. We propose an attack model that permits an arbitrary number of malicious nodes under the assumption that each node can be classified based on some of its attributes, such as autonomous system number or operating system, and that the number of classes with malicious nodes is bounded (e.g., an attacker may exploit at most a few operating systems at a time). In this model, we present a secure DHT, evilTwin, which replaces a single, large DHT with sufficiently many smaller instances such that it is impossible for an adversary to corrupt every instance. Our system ensures high availability and low-latency lookups, is easy to implement, does not require a complex Byzantine agreement protocol, and its proof of security is a straightforward application of the pigeonhole principle. The cost of security comes in the form of increased storage and bandwidth overhead; we show how to reduce these costs by replicating data and adaptively querying participants who historically perform well. We use implementation and simulation to show that evilTwin imposes a relatively small additional cost compared to conventional DHTs.