Show simple item record

dc.contributor.authorWong, Bernarden_US
dc.contributor.authorSlivkins, Aleksandrsen_US
dc.contributor.authorSirer, Emin Gunen_US
dc.description.abstractSelecting nodes based on their position in the network is a basic building block for many distributed systems. This paper describes a peer-to-peer overlay network for performing position-based node selection. Our system, Meridian, provides a lightweight, accurate and scalable framework for keeping track of location information for participating nodes. The framework consists of an overlay network structured around multi-resolution rings, query routing with direct measurements, and gossip protocols for dissemination. We show how this framework can be used to address three commonly encountered problems in large-scale distributed systems without having to compute absolute coordinates; namely, closest node discovery, central leader election, and locating nodes that satisfy target latency constraints. We show analytically that the framework is scalable with logarithmic convergence when Internet latencies are modeled as a growth-constrained metric, a low-dimensional Euclidian metric, or a metric of low doubling dimension. Large scale simulations, based on latency measurements from 6.25 million node-pairs, and an implementation deployed on PlanetLab both show that the framework is accurate and effectiveen_US
dc.format.extent620586 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleMeridian: A Lightweight Framework for Network Positioning without Virtual Coordinatesen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record