Autonomic Computing Tutorial

Squid: Flexible Information Discovery in Decentralized Distributed SystemsCristina Schmidt and Manish ParasharThe Applied Software Systems LaboratoryRutgers, The State University of New JerseyHPDC, June 2003„„„„„OutlineIntroductionRelated WorkDesignEvaluationOngoing workHPDC, June 2003‰„‰‰„MotivationThe need for information discovery in large, decentralized, distributed resource sharing environments, in the absence of global knowledge of naming conventionsExamples:P2P Document Sharing SystemsGrid Resource DiscoveryWeb Service DiscoveryHPDC, June 2003„„„OverviewSquid is a Peer-to-Peer (P2P) indexing and information discovery systemSupports complex queries containing partial keywords, wildcards and range queriesGuarantees that all existing data elements matching a query will be found with bounded cost in terms of number of messages and nodes involvedHPDC, June 2003‰‰„„„„„„‰‰‰Related WorkUnstructured (Gnutella-like)Unstructured overlay network, use floodingHybrid (Napster)Unstructured overlay network, use centralized directories for searchData-lookup (CAN, Chord, Pastry, etc)Structured overlay, Internet-scale DHTStructured keyword searchStructured overlay, extend data-lookup protocolsExamples:Distributed Inverted IndicesSpace Filling CurveHPDC, June 2003‰‰‰‰„Design - OverviewSystem components:Locality preserving mapping that maps documents to indices – using Space Filling Curves (SFC)Overlay ...