Date of Award
Doctor of Philosophy (PhD)
James Wang, Committee Chair
Pradip Srimani, Committee Co-Chair
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 inﬂuence 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 diﬀerent models; they outperform the best possible solution existing in the literature. Recently, the concept of a positive inﬂuence dominating set has been used for the selection of inﬂuential users in the social network. However, this solution does not consider that (1) the mutual inﬂuence between two neighboring nodes is in general asymmetric; and (2) each node has diﬀerent tolerance level (sensitivity) towards neighbor’s inﬂuence. To overcome these drawbacks, I propose to select the users in the minimal weighted positive inﬂuence dominating set of a social network graph as the inﬂuential users, and then present the ﬁrst polynomial time self-stabilizing algorithm to compute a minimal weighted positive inﬂuence 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 ﬁrst 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 ﬁrst set of self-stabilizing algorithms with safe convergence property for packing and alliance problems in arbitrary network graphs.
Ding, Yihua, "Fault Tolerance in Distributed Systems Using Self-Stabilization" (2014). All Dissertations. 1861.