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

Prelegent(ci)

Krzysztof Rządca

Afiliacja

Uniwersytet Warszawski

Termin

1 grudnia 2011 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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)

---