1 Komunikacja w systemach rozproszonychMichał Strojnowski

2 Ekspandery - przykład Stopień każdego wierzchołka ≤dKażdy podzbiór k Graf ma średnicę O(log n), i liniową liczbę krawędzi Losowe grafy są zwykle ekspanderami, ale deterministyczne konstrukcje są trudne.

3 Zastosowania Dowody teorio-obliczeniowe Kody korekcji błędówGeneratory pseudolosowe (ekstraktory) Sieci sortujące Algorytmy routowania Zarządzanie pamięcią dzieloną Rozproszone algorytmy odporne na błędy

4 Przydatne własności Po usunięciu f Te wierzchołki mogą wykonać zadanie, nie przejmując się resztą

5 Przykładowe problemy 1. Zebranie informacji od wszystkich procesorów2. Wykonanie zbioru prostych zadań (zależnych lub niezależnych)

6 Manipulowanie własnościamiStopień każdego wierzchołka ≤ dnε Każdy podzbiór k Średnica grafu jest stała, a liczba krawędzi O(n1+ε)

7 Manipulowanie własnościami c.d.Graf dwudzielny (A,P,E): |P|=n, |A|=n1-ε Stopień wierzchołków P jest stały Dla każdego f Jeśli wiemy że błędów jest niewiele, to możemy komunikować się przez liderów.