Bounding the Impact of Unbounded Attacks in Stabilization
ABSTRACT:
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 permit 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. Our
property, called Strong Stabilization enables to contain the impact of
Byzantine nodes if they actually perform too many Byzantine actions. We derive
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.
INTRODUCTION
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.
EXITSING
SYSTEM
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.
PROPOSED
SYSTEM
§ 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.
§ Recall that strict stabilization requires
that processes beyond the containment radius eventually achieve their desired
behavior and are never disturbed by Byzantine processes afterwards.
§ 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.
§ To present new possibility results for
containing the influence of unbounded Byzantine behaviors.
MODULES:
v Network
Creation and Socket Connection module
v Link-Failure
Detection
v Byzantine
containment
MODULES
DESCRIPTION:
Network
Creation and Socket Connection
In this module, we first create the simulation
environment by creating the network as three entities viz: Source node, Router
Node and Destination Node. The source node is created with the properties of
sending the files using socket connection using IP Address provided by the
user. Then the router node and destination node is created with the socket
connection of using their properties.
Link-Failure Detection:
In
this module, in every node monitors the quality of its outgoing wireless links
at every tm (e.g., 10 sec) and reports the
results to a gateway via a management message. Second, once it detects a link
failure(s), in the detector node(s) triggers the formation of a group among
local mesh routers that use a faulty channel, and one of the group members is
elected as a leader and coordinating the reconfiguration.
Byzantine
containment:
In this paper, we investigate the possibility
of Byzantine containment in a self-stabilizing setting for tasks that are
global (i.e., for with there exists a causality chain of size r, where r
depends on n the size of the network), and focus on two global problems, namely
tree orientation and tree construction. As strict stabilization is impossible
with such global tasks, we weaken the containment constraint by limiting the
number of times that correct processes can be disturbed by Byzantine ones. Recall
that strict stabilization requires that processes beyond the containment radius
eventually achieve their desired behavior and are never disturbed by Byzantine processes
afterward. We relax this requirement in the following sense: we allow 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. The main contribution of this paper is to present new possibility
results for containing the influence of unbounded Byzantine behaviors.
SYSTEM
REQUIREMENTS:
HARDWARE
REQUIREMENTS:
•
System : Pentium IV 2.4 GHz.
•
Hard
Disk : 40 GB.
•
Floppy
Drive : 1.44 Mb.
•
Monitor : 15 VGA Colour.
•
Mouse : Logitech.
•
Ram : 512 Mb.
SOFTWARE
REQUIREMENTS:
•
Operating system : - Windows XP.
•
Coding Language : C#.Net.
•
TOOL USED : Visual Studio 2008
REFERENCE:
Swan
Dubois, Toshimitsu Masuzawa, Member, IEEE, and Se´ bastien Tixeuil, “Bounding
the Impact of Unbounded Attacks in Stabilization”, IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 23, NO. 3,
MARCH 2012.
