🚀 go-pugleaf

                                CATS Seminar

                        Capital Area Theory Seminar

             http://www.umiacs.umd.edu/users/liberato/cats/

			Static and Dynamic Fault Diagnosis

				Richard Beigel 
		University of Illinois at Chicago & DIMACS

                    Wednesday, September 1, 1999, 4 p.m.
                                  AVW 2120


                                  Abstract

Consider a set of processors that can communicate with each other.
Each processor is either ``good'' or ``faulty,'' and the processors
can be used to test each other.  (A good tester will tell whether the
testee is good or faulty.  A faulty tester may lie.)

Assuming that no processors fail during testing and that a strict
majority of the processors are good, we present a parallel algorithm
that determines which processors are good and which are faulty in 10
rounds of testing (independent of the number of processors).

The algorithm above requires that the status of each processor (good
or faulty) be static.  But, in a huge system, we may expect a few
processors to fail in each round.  Dynamic faults make diagnosis
substantially more difficult.  In our dynamic fault model all
processors are initially good, at most t fail per round, and s may be
repaired per round.  If s < t, then eventually almost all processors
may be faulty.  However, if s >= t, we give an algorithm that
guarantees that (at most) O(tlogt) processors are faulty at any one
time.

The work above is joint with Will Hurwood.  We will also sketch joint
work with Bin Fu on diagnosing intermittent faults.



Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)

The Capital Area Theory Symposia is an NSF sponsored series of symposia in 
theoretical computer science bringing computer scientists from around 
the world to the Capital area. The Symposia are given at the 
University of Maryland in cooperation with the Computer Science Department 
and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged