Issues with Protocols and Dependent Failures

26.03.2004

Foredragsholdere
Keith Marzullo

Tid: Fredag 10:15 til 12:00
Sted: Lille auditorium Realfagsbygget

Title: The mechanics of paper submission and review.

Speaker: Keith Marzullo, UC San Diego, USA and Department of Computer Science, UiTø.

Abstract:
Often, lower bounds are specified using what has been called a threshold model: out of n components, no more than t of them are assumed to be faulty. Protocols that are optimal with respect to such a model, however, tacitly assume that failures are independent and identically distributed (IID) since any set of t or fewer components can be faulty.

We have developed a model for representing non-IID failures of processes and explored the design of protocols using our model. I will present our model and give some examples of how it can be used to represent non-IID failures. I will then give some bounds, expressed in our model, that state when there is sufficient process replication to support a protocol that requires in the threshold model n > kt for some integer k > 1. I will also show what replication bounds mean in our model where, in the threshold model, the bound is expressed as n > at/b for integer a > b > 0 and illustrate them with a novel leader election protocol (first posed but not generally solved by Navin Budhiraja). I will finally consider the following problem: what if one has a protocol P that requires n > kt, and a set of processors that has enough replication to solve the same problem that P solves, but not sufficient replication to run protocol P? I show how to transform P into a protocol that can be run on the existing system.

The work in this talk is joint work with Flavio Junqueira.


Eventuelle spørsmål i tilknytting til Marzullos forelesning kan rettes til professor Dag Johansen, tlf 7764 4047.

Vel møtt!