Teoriogrowe mechanizmy zwiększania dostępności danych w rozproszonych systemach replikacyjnych

Speaker(s)

Krzysztof Rządca

Affiliation

Uniwersytet Warszawski

Date

Dec. 1, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

W systemach przechowywania danych w architekturze peer-to-peer, użytkownicy zwiększają dostępność danych przez wzajemne ich replikowanie. Centralny system pośredniczący w zawieraniu umów replikacyjnych może zoptymalizować dostępność danych tak, by wszyscy użytkownicy mieli podobny poziom dostępności. Jeśli jednak umowy zawierane są w sposób zdecentralizowany przez samych użytkowników, ich egoizm prowadzi do nierówności, skutkujących ograniczeniem niezawodności danych nowych użytkowników, a więc i zmniejszeniu popularności całego systemu.

Podczas seminarium pokażę teoriogrowy mechanizm ograniczający cenę anarchii w systemie zdecentralizowanym. Mechanizm "opodatkowuje" wysoko dostępnych użytkowników: część z ich slotów replikacyjnych używana jest do replikacji danych nisko dostępnych użytkowników. Opiszę warunki przy których mechanizm zachęca wszystkich użytkowników - zarówno opodatkowanych jak i wspieranych - do zwiększenia dostępności (truthful). Zaprezentuję również wyniki symulacji pokazujące że mechanizm ten zwiększa dostępność danych nisko dostępnych użytkowników o dwa rzędy wielkości. Mechanizm ten jest wystarczający do osiągnięcia zadowalającego poziomu dostępności danych wszystkich użytkowników.

Praca wspólnie z Anwitamanem Datta (NTU, Singapur) i Sonją Buchegger (KTH, Szwecja)

---