Seminarium: Systemy Rozproszone
19 maja 2014, godzina 12:15, sala 4070
Piotr Jaszkowski

Rozproszony slicing i zliczanie probabilistyczne

Coraz bardziej popularne stają się systemy rozproszone złożone z małych i tanich urządzeń. Od takich urządzeń często oczekuje się silnej autonomii i długiego życia bez żadnej obsługi z zewnątrz. Oczywiście ze względu na oszczędności takie urządzenia mają bardzo ograniczoną pamięć, moc procesora i pojemność baterii. Mając to na uwadze wiele obecnie stosowanych algorytmów na urządzeniach stale podłączonych do zasilania nie przekłada się te tanie sensory. Jednym z takich problemów jest rozproszony slicing, którego efektywne rozwiązanie jest tematem mojej pracy magisterskiej. Na seminarium przybliżę ten problem oraz nasze dotychczasowe próby rozwiązania go.

Dodatkowo omówię jedną z wykorzystywanych przez nas technik jaką jest zliczanie probabilistyczne, które pozwala między innymi na policzenie liczby unikatowych elementów w mutlizbiorze o mocy 10^9 z dokładnością 2% i użyciu 1.5kB pamięci.

Zapraszam serdecznie!
Piotr Jaszkowski

Bibliografia:

• Antonio Fernandez, Vincent Gramoli, Ernesto Jimenez, Anne-Marie Kermarrec, Michel Raynal, Distributed Slicing in Dynamic Systems
• Stefan Heule, Marc Nunkesser, Alex Hall, HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm