Next: Literatura
Wybrane problemy komunikacyjne
w sieciach z usterkami
Adam Malinowski
Praca dotyczy tematyki obliczeń równoległych i rozproszonych odpornych na błędy. Szereg przedstawionych w niej rozwiązań problemów komunikacyjnych w sieciach z usterkami demonstruje wachlarz algorytmicznych metod stosowanych do eliminacji skutków błędów transmisji i uszkodzeń elementów składowych sieci komputerowych.
Pierwszy rozdział zawiera krótkie omówienie modeli komunikacji i atrybutów usterek rozważanych w literaturze przedmiotu oraz niezbędnego aparatu matematycznego. Struktura dalszej części pracy jest oparta na gradacji modelu rozmieszczenia usterek w prezentowanych przykładach: od losowego przez liniowo ograniczone do dowolnego.
W rozdziałach 2 i 3 omawiane są dwa dość zbliżone problemy przesyłania bez kopiowania i przesyłania z kopiowaniem przez źródło (ang. token transfer, token dispersal), stanowiące warianty podstawowego problemu komunikacyjnego -- rozgłaszania (ang. broadcasting). W obydwu rozdziałach przyjęty został model losowych usterek węzłów i/lub łączy w sieci. W pierwszym problemie celem jest odwiedzenie przez jeden żeton wszystkich sprawnych węzłów w sieci. Rozważanych jest kilka wersji modelu różniących się dopuszczalnym stopniem adaptatywności algorytmów. Ważnym założeniem odnośnie do modelu komunikacji jest jednokierunkowość łączy -- łącze od węzła u do v może być sprawne, ale łącze od v do u -- uszkodzone. Powoduje to konieczność stworzenia mechanizmu, który nie dopuszcza do utraty kontroli nad żetonem. Najbardziej pomysłowe rozwiązania tej kwestii zawierają asymptotycznie optymalne algorytmy dla uszkodzonych węzłów i łączy w przypadku nieadaptatywnym i w pełni adaptatywnym. Wyniki przedstawione w rozdziale 2 zostały opublikowane w pracy [3].
Drugi problem różni się od poprzedniego tym, że teraz źródło, czyli węzeł, który posiadał żeton na początku algorytmu, może tworzyć i rozsyłać jego kopie. Przedstawione są asymptotycznie optymalne algorytmy dla uszkodzonych łączy i/lub węzłów. Na uwagę zasługuje nietypowe zastosowanie sieci sortujących -- do zapełnienia żetonami ustalonego zbioru węzłów. Wyniki przedstawione w rozdziale 3 zostały opublikowane w pracy [2].
W rozdziale 4 omawiany jest problem bizantyjskiej zgody (ang. Byzantine Agreement) w sieci z losowymi usterkami. W artykule [7] zostało postawione pytanie, czy istnieje liniowy algorytm plotkowania (ang. gossiping) odporny na błędy typu bizantyjskiego (przekłamania) w tym modelu błędów przy jednobitowym rozmiarze komunikatu. Przedstawiony tu algorytm, rozwiązujący nawet nieco trudniejszy problem (wśród sprawnych węzłów uzgadniane są również wartości węzłów uszkodzonych), wykorzystuje efektywne asymptotycznie dobre kody korygujące błędy. Wyniki przedstawione w tym rozdziale zostały opublikowane w pracy [6].
W rozdziale 5 rozważany jest model liniowo ograniczonego rozmieszczenia usterek, w którym liczba dowolnie rozmieszczonych błędów może być proporcjonalna do czasu działania algorytmu. Przedstawiony tu algorytm rozgłaszania w sieci stałego stopnia stanowi rozwiązanie problemu postawionego w pracy [5], oparte na teoriografowych własnościach sieci (odpowiednio duża liczba rozłącznych wierzchołkowo ścieżek). Wyniki przedstawione w tym rozdziale zostały opublikowane w pracy [1].
W ostatnim rozdziale przedstawiony jest parametryzowany rozmiarem komunikatu algorytm probabilistyczny dla problemu plotkowania przy niemal dowolnym rozmieszczeniu usterek (z pewnym dodatkowym technicznym założeniem, zapewniającym skomunikowanie się każdych dwóch sprawnych węzłów w stałym czasie ze stałym prawdopodobieństwem). Główny pomysł polega na wykorzystaniu rodziny k-uniwersalnych funkcji haszujących do dokonania podziału zbioru węzłów na grupy w sposób wystarczająco zbliżony do losowego przy użyciu niewielkiej liczby komunikatów. Wyniki przedstawione w rozdziale 6 ukażą się w [4].
Przedstawione w pracy algorytmy wykorzystujące różnorodne techniki, głównie natury probabilistycznej, ukazują siłę i ograniczenia metod stosowanych w teorii protokołów komunikacyjnych odpornych na błędy.
Next: Literatura Adam Malinowski 2000-03-30