Files in this item



application/pdfPerturbation-Re ... ent Resource Discovery.pdf (111kB)
(no description provided)PDF


Title:Perturbation-Resistant and Overlay-Independent Resource Discovery
Author(s):Ko, Steven Y.; Gupta, Indranil
Subject(s):distributed systems
Abstract:This paper realizes techniques supporting the position that strategies for resource location and discovery in distributed systems should be both perturbation-resistant and overlay-independent. Perturbation-resistance means that inserts and lookups must be robust to ordinary stresses such as node perturbation, which may arise out of congestion, competing client applications, or user churn. Overlay-independence implies that the insert and lookup strategies, and to an extent their performance, should be independent of the actual structure of the underlying overlay. We first show how a well-known distributed hash table (Pastry) may degrade under perturbation. We then present a new resource location and discovery algorithm called MPIL (Multi-Path Insertion/Lookup) that is perturbation-resistant and overlay-independent. MPIL is overlay-independent in that it effectively provides to the distributed application an ability to insert and lookup Pastry objects in an overlay with Pastry IDs, but without the need to have Pastry-style overlay maintenance (i.e., the overlay underneath can be arbitrary). We quantify, through analysis and simulation results, the behavior of MPIL over complete, random, and power-law overlays. We also show how MPIL outperforms regular Pastry routing when there is perturbation.
Issue Date:2005-04
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2560
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-17

This item appears in the following Collection(s)

Item Statistics