Campus Event Calendar
Event Entry
New for: D3
What and Who
Fast Distributed Replication in Modern Networks
Faraz Makari Manshadi
International Max Planck Research School for Computer Science - IMPRS
PhD Application Talk
IMPRS-CS Master student
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 16 February 2010
11:10
90 Minutes
E1 4
024
Saarbrücken
Abstract
In modern networks such as wireless and P2P networks and distributed search engines, replicating data is an important issue, which is often needed for availability, reliability and performance improvement. In
such distributed systems, often random walks are utilized for query routing and data replication can improve the probability of successfully finding requested items. In this respect, we investigate the problem of finding a replica allocation to peers such that at each peer some minimum threshold for the probability of successful search is satisfied while minimizing the total number of replicated data items in network. Obviously the number of replicated data items in the whole network is a global parameter. There exists a trade-off between the amount of local information and the quality of the solution for the global objective function and the challenging point is to optimize this global function only based on the local information. The literature contains huge amount of theoretical work; Most of the proposed algorithms are, due to their complexity, far from being practically applicable or based on some simplifying assumptions, e.g. unbounded message sizes.
In this thesis, we present a fast self-stabilizing distributed algorithm for replication based on the LP relaxation technique, which provides a nearoptimal solution and uses only small message. The algorithm can also be applied indynamic settings where nodes join and leave the system. These properties are very desirable in distributed systems with unreliable components. The most appealing features of our algorithm are its simplicity and polylogarithmic convergence. We also provide some experimental results of the performance of the algorithm on different network topologies such as random graphs and internet-style topologies, and introduce some application areas of our algorithm, while proving the theoretical guarantees.
such distributed systems, often random walks are utilized for query routing and data replication can improve the probability of successfully finding requested items. In this respect, we investigate the problem of finding a replica allocation to peers such that at each peer some minimum threshold for the probability of successful search is satisfied while minimizing the total number of replicated data items in network. Obviously the number of replicated data items in the whole network is a global parameter. There exists a trade-off between the amount of local information and the quality of the solution for the global objective function and the challenging point is to optimize this global function only based on the local information. The literature contains huge amount of theoretical work; Most of the proposed algorithms are, due to their complexity, far from being practically applicable or based on some simplifying assumptions, e.g. unbounded message sizes.
In this thesis, we present a fast self-stabilizing distributed algorithm for replication based on the LP relaxation technique, which provides a nearoptimal solution and uses only small message. The algorithm can also be applied indynamic settings where nodes join and leave the system. These properties are very desirable in distributed systems with unreliable components. The most appealing features of our algorithm are its simplicity and polylogarithmic convergence. We also provide some experimental results of the performance of the algorithm on different network topologies such as random graphs and internet-style topologies, and introduce some application areas of our algorithm, while proving the theoretical guarantees.
Contact
IMPRS-CS Office Team
0681 93 25 225
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Stephanie Jörg, 02/12/2010 11:05 -- Created document.