Idea algorytmów samostabilizujących została zapoczątkowana przez E. Dijkstrę artykułem pt. „Self-stabilizing systems in spite of distributed control” (Communications of the ACM, 1974). W rozprawie został położony nacisk na algorytmy samostabilizujące działające w sieciach o pewnych specyficznych topologiach, jak na przykład w grafach maksymalnych zewnętrznie planarnych, iloczynach kartezjańskich tych grafów ze ścieżkami i w drzewach. Wykorzystując powyższe własności sieci, pokazaliśmy algorytmy, które działają efektywniej w porównaniu ze znanymi obecnie algorytmami samostabilizującymi dla ogólnych topologii sieci. Ponadto pokazaliśmy algorytm wyznaczający zbiór cykli fundamentalnych grafu, należący do zaproponowanej przez nas klasy algorytmów quasi-samostabilizujących. Jest to rozszerzenie idei zaproponowanej przez Schneidera w artykule „Self-Stabilization” (ACM Computing Surveys, 1993). Dzięki temu nasz algorytm ma mniejszą złożoność w stosunku do klasycznego wyniku samostabilizującego.
Authors
- dr Michał Pańczyk
Additional information
- Category
- Doktoraty, rozprawy habilitacyjne, nostryfikacje
- Type
- praca doktorska pracowników zatrudnionych w PG oraz studentów studium doktoranckiego
- Language
- polski
- Publication year
- 2016
