Our Objectives
Fault tolerant protocols are essential for providing various
services. The traditional approach in
designing fault tolerant protocols assumes an upper bound on the number of faults
and involves a worst case design by fault masking. Self-stabilizing algorithms offer great
potential for distributed computing.
Our
objectives are:
- Create paradigms and guiding principles for
designing self-stabilizing distributed algorithms;
- Explore methodologies for translating a
conventional algorithm into a self-stabilizing analog;
- Utilize complexity theoretic concepts, such as
polynomial time transformations, to help reason about the intrinsic complexity
of such algorithms;
- Discover and analyze self-stabilizing protocols
for global communication primitives in a network;
- Explore fractional (rational) valued
self-stabilizing algorithms as a way to obtain improved approximate solutions
to otherwise NP-hard problems;
- Measure the degree to which self-stabilizing
algorithms can contain a single fault
Our research takes a combined theoretical and experimental
approach, and applies its results to emerging distributed applications for ad
hoc networks.