-----------------------------------------------------------------------
TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar
-----------------------------------------------------------------------

Title:   Distributed Error Confinement
Speaker: Boaz Patt-Shamir

Place:   NE43-308
Time:    1-2:30pm
Date:    Sept. 20, 2002

We study error confinement in reactive distributed applications, where the
goal is that only nodes that were directly hit by a fault may deviate from
their correct external behavior, and only temporarily. The external behavior
of all other nodes must remain impeccable, even though their internal state
may be affected. Error confinement of reactive systems is impossible if an
adversary is allowed to inflict arbitrary transient faults on the system,
since the faults might completely wipe out input values. We define the
measure of \emph{agility}, which quantifies the strength of a reactive
algorithm against state corrupting faults. We study the basic problem of
broadcast, and propose algorithms that guarantee error confinement with
optimal agility to within a constant factor. The analysis of these
algorithms leads to a combinatorial optimization problem that may be of
independent interest.

Joint work with Yossi Azar and Shay Kutten.

------------------------------------------------------------------------