2.11.2006

Algorytmy kompozycyjne w sieciach redukowalnych

W prezentowanej pracy przedstawione są i przedyskutowane trzy pojęcia związane z obliczeniami lokalnymi (rozproszonymi): sieci obliczeniowe, struktury kompozycyjne i algorytmy lokalne.
Pierwsze z nich, pojęcie grafów redukowalnych reprezentujących pewne sieci obliczeniowe, odnosi się do rodzin grafów dopuszczających lokalną ich redukcję do singletonów; decyzja o możliwości usunięcia wierzchołka jest zależna jedynie i wyłącznie od struktury jego sąsiedztwa. W realnych sieciach komputerowych taka decyzja nie musi oznaczać fizycznego usunięcia wierzchołka, a jedynie rezygnację z uczestnictwa wierzchołka w dalszych etapach wykonywania rozważanych algorytmów.
Drugie pojęcie, to struktura algebraiczna, utworzona z danych zapisanych w wierzchołkach sieci i pewnej operacji składania; dane wraz z tą operacją tworzą strukturę przypominającą niedeterministyczną półgrupę. Zadaniem sieci jest utworzenia złożenia z wszystkich danych zapisanych w sieci. Podane zostaną przykłady takich struktur, zwanych systemami kompozycyjnymi.
Praca kończy się podaniem algorytmu rozproszonego tworzącemu złożenie danych systemów kompozycyjnych drogą lokalnych obliczeń, stanowiącego trzecie pojecie dyskutowane w pracy. Jest to wspólny algorytm, którego konkretnymi instancjami mogą być: elekcja lidera w sieci, ustalenie wspólnego porządku liniowego wszystkich wierzchołków sieci, wyznaczenie drzewa rozpinającego sieci, ustalenie wspólnej permutacji nazw elementów sieci, wynegocjowanie maksymalnego zbioru niesprzecznych warunków, i inne tym podobne. Algorytm jest jednakowy dla wszystkich wierzchołków sieci, a dane do wykonania algorytmu zapisanego w wierzchołku są zapamiętane jedynie w jego sąsiedztwie (własność lokalności). Pokazana zostanie bezstronność rozwiązań, polegającą na możliwości uzyskania dowolnego rezultatu spełniającego zadane warunki.