A study on self-stabilizing dominating set algorithms

Distributed systems are widely used in many information systems, and spreading even more with the increasing number of IoT systems. They are formed by autonomous devices that are connected to each other. In distributed system applications, self-stabilizing algorithms are being widely used in order to keep the system stable in case of failing nodes, either by a software or hardware failure. To test the self-stabilizing algorithms a special simulator is required. As there is not any known distributed selfstabilizing simulator which is up-to-date with technology of today, we have designed and implemented SELFSIM in this thesis. SELFSIM, while giving ease to algorithm developers and instructors with its user-friendly user/programming interface, can compare performance values of different algorithms in different graphs with its internal performance analyzer. Moreover, as SELFSIM can run with much more nodes then its likes it would give much more accurate results. Dominating Set is a significant concept that is used widely in in distributed systems. In this thesis, using SELFSIM, 3 known Self-Stabilizing Dominating Set algorithms are compared by their energy consumption, stabilization duration, move count, and detected dominant node count by taking different node counts and graph densities into consideration. According to the results, while Goddard's algorithm outperforms Chiu's and Turau's, Turau's algorithm was found to be the least performing among the three.