Bounding the Impact of Unbounded Attacks in Stabilization
ABSTRACT:Bounding the Impact of Unbounded Attacks in Stabilization- projects 2012
Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. Combining these two properties proved difficult: it is impossible to contain the spatial impact of Byzantine nodes in a self-stabilizing context for global tasks such as tree orientation and tree construction. We present and illustrate a new concept of Byzantine containment in stabilization. Strong Stabilization enables to contain the impact of Byzantine nodes if they actually perform too many Byzantine actions. Derived impossibility results for strong stabilization and present strongly stabilizing protocols for tree orientation and tree construction that are optimal with respect to the number of Byzantine nodes that can be tolerated in a self-stabilizing context.
The advent of ubiquitous large-scale distributed systems advocates that tolerance to various kinds of faults and hazards must be included from the very early design of such systems. Self-stabilization is a versatile technique that permits forward recovery from any kind of transient faults, while Byzantine Fault-tolerance is traditionally used to mask the effect of a limited number of malicious faults. Making distributed systems tolerant to both transient and malicious faults is appealing yet proved difficult as impossibility results are expected in many cases.
Two main paths have been followed to study the impact of Byzantine faults in the context of self- stabilization.
The first one is Byzantine fault masking. In completely connected synchronous systems, one of the most studied problems in the context of self-stabilization with Byzantine faults is that of clock synchronization. Probabilistic self stabilizing protocols were proposed for up to one third of Byzantine processors, while deterministic solutions tolerate up to one fourth and one third of Byzantine processors, respectively.
The second one is Byzantine containment. For local tasks (i.e. tasks whose correctness can be checked locally, such as vertex coloring, link coloring, or dining philosophers), the notion of strict stabilization was proposed. Strict stabilization guarantees that there exists a containment radius outside which the effect of permanent faults is masked. Authors show that this Byzantine containment scheme is possible only for local tasks. As many problems are not local, it turns out that it is impossible to provide strict stabilization for those.
v Investigate the possibility of Byzantine containment in a self stabilizing setting for tasks that are global, and focus on two global problems, namely tree orientation and tree construction.
v Recall that strict stabilization requires that processes beyond the containment radius eventually achieve their desired behavior and are never disturbed by Byzantine processes afterwards.
v Allowed these correct processes beyond the containment radius to be disturbed by Byzantine processes, but only a limited number of times, even if Byzantine nodes take an infinite number of actions.
v To present new possibility results for containing the influence of unbounded Byzantine behaviors.