Abstract

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.

Author (1)