MatchTree: Flexible, scalable, and fault-tolerant wide-area resource discovery with distributed matchmaking and aggregation

TitleMatchTree: Flexible, scalable, and fault-tolerant wide-area resource discovery with distributed matchmaking and aggregation
Publication TypeJournal Article
Year of Publication2012
AuthorsLee, K, Choi, TW, Boykin, PO, Figueiredo, RJ
JournalFuture Generation Computer Systems
ISSN0167-739X
KeywordsDecentralized resource discovery, Distributed information aggregation, Fault-tolerant self-organizing tree
AbstractThis paper proposes a novel wide-area resource discovery method, MatchTree, that is built upon a Peer-to-Peer (P2P) framework to deliver scalable and fault-tolerant resource discovery supporting distributed query processing and aggregation of results. MatchTree leverages a self-organizing tree for query distribution and result aggregation with the asymptotic latency increase pattern of O ( log N ) , where N is the number of queried nodes. MatchTree distinguishes itself from related resource discovery systems based on structured P2P overlays by supporting complex queries (such as regular expressions in match-making), and from related unstructured P2P discovery systems by guaranteeing query completeness. This paper presents the overall architecture of MatchTree, proposes heuristics to improve fault-tolerance and reduce query response times through redundant query topologies, dynamic timeout policies, and sub-region queries. The paper evaluates the system quantitatively through large scale simulations, as well as through experiments with a prototype implementation deployed on a wide-area infrastructure (PlanetLab). The experiment results with proposed heuristics show that the maximum query latency of MatchTree decreases from 154 seconds to 12 seconds, and the maximum query missing region decreases from 13.4% to 2.3% in the wide-area real world testbed.
URLhttp://www.sciencedirect.com/science/article/pii/S0167739X12001653?v=s5
DOI10.1016/j.future.2012.08.009