Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 43 von 53
Zurück zur Trefferliste

Approximate Algorithms for Distributed Systems

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-42370
  • Peer-to-peer (P2P) systems form a special class of distributed systems. Typically, nodes in a P2P system are flat and share the same responsabilities. In this thesis we focus on three problems that occur in P2P systems: the storage of data replicates, quantile computation on distributed data streams, and churn rate estimation. Data replication is one of the oldest techniques to maintain stored data in a P2P system and to reply to read requests. Applications, which use data replication are distributed databases. They are part of an abstract overlay network and do not see the underlying network topology. The question is how to place a set of data replicates in a distributed system such that response times and failure probabilities become minimal without a priori knowledge of the topology of the underlying hardware nodes? We show how to utilize an agglomerative clustering procedure to reach this goal. State-of-the-art algorithms for aggregation of distributed data or data streams require at some point synchronization, or merge data aggregates hierarchically, which does not accompany the basic principle of P2P systems. We test whether randomized communication and merging of data aggregates are able to produce the same results. These data aggregates serve for quantile queries. Constituting and maintaining a P2P overlay network requires frequent message passing. It is a goal to minimize the number of maintenance messages since they consume bandwidth which might be missing for other applications. The lower bound of the frequency for mainte- nance messages is highly dependent on the churn rate of peers. We show how to estimate the mean lifetime of peers and to reduce the frequency for maintenance messages without destabilizing the infrastructure of the constituting overlay.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Marie Hoffmann
Dokumentart:Masterarbeit
Freies Schlagwort / Tag:peer-to-peer, machine learning, approximate, clustering, quantile, linear regression
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
CCS-Klassifikation:I. Computing Methodologies
Titel verleihende Institution:Freie Universität Berlin
Betreuer:Thorsten Schütt, Katinka Wolter
Datum der Abschlussprüfung:04.02.2013
Veröffentlichende Institution:Zuse Institute Berlin (ZIB)
Datum der Erstveröffentlichung:07.09.2013
Seitenzahl:75
Lizenz (Deutsch):License LogoCreative Commons - Namensnennung-Nicht kommerziell
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.