Date of Award
12-2014
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Computer Science
Committee Member
James Wang, Committee Chair
Committee Member
Pradip Srimani, Committee Co-Chair
Committee Member
Jason Hallstrom
Committee Member
Feng Luo
Abstract
Self-stabilization is an optimistic paradigm to provide autonomous resilience against an un-limited number of transient faults in distributed systems. A self-stabilizing system guarantees an eventual return to a legitimate operating state beginning with an unknown initial state, including a state that arises as the result of an unanticipated transient fault (e.g., node failure, state corruption, or node mobility in mobile systems). This thesis focuses on the fault tolerance in distributed sys-tems using self-stabilization, and presents a collection of self-stabilizing algorithms for well-known problems in distributed systems.
Two variants of dominating set (i.e., weakly connected dominating set and positive influence dominating set) have been widely used in distributed system applications, such as network security, facility location, message routing and others. In this thesis, three new self-stabilizing algorithms are proposed to compute a minimal weakly connected dominating set in the arbitrary network graph under different models; they outperform the best possible solution existing in the literature. Recently, the concept of a positive influence dominating set has been used for the selection of influential users in the social network. However, this solution does not consider that (1) the mutual influence between two neighboring nodes is in general asymmetric; and (2) each node has different tolerance level (sensitivity) towards neighbor’s influence. To overcome these drawbacks, I propose to select the users in the minimal weighted positive influence dominating set of a social network graph as the influential users, and then present the first polynomial time self-stabilizing algorithm to compute a minimal weighted positive influence dominating set in an arbitrary social network.
In a traditional self-stabilizing algorithm, the desired global property (the relevant service in the system) is not guaranteed during the convergence interval; thus the concept of safe convergence was introduced to minimize possible inconvenience. A self-stabilizing algorithm has the safe conver-gence property if it first converges to a safe (sub-optimal) state in constant time, and then converges to a legitimate (optimal) state without breaking safety in the process. Safe convergence property is especially attractive as it provides a measure of safety (desired service at a sub-optimal level) during the convergence interval until the optimal legitimate state is reached. This thesis presents the first set of self-stabilizing algorithms with safe convergence property for packing and alliance problems in arbitrary network graphs.
Recommended Citation
Ding, Yihua, "Fault Tolerance in Distributed Systems Using Self-Stabilization" (2014). All Dissertations. 1861.
https://open.clemson.edu/all_dissertations/1861