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

Title:   Towards Byzantine ABD

Speaker: Gregory Chockler

Place:   NE43-308
Time:    1:00pm - 2:30pm
Date:    Oct. 24, 2003

Abstract:

The famous ABD simulation protocol implements a fault-tolerant atomic
register on top of a message-passing system. The simulation is resilient
to up to n/2 process crash failures which is optimal. In this talk we
consider fault-tolerant object emulations in an asynchronous shared memory
model with failure-prone objects.  The ABD results can be easily applied
in this model as long as the objects are benign faulty. However, it turns
out that achieving optimal resilience to Byzantine object failures (t<n/3)
incurs a high cost in terms of the communication complexity. To this end,
I will show how to emulate a wait-free shared register in this model using
a collection of 3t+1 fault-prone base objects. I will also show that
emulations with this level of resilience require invoking substantially
more operations onb the base objects than constructions that have lower
resilience level.

If time permits, I will discuss the ongoing and future work concerned with
emulating stronger object types (regular and safe) and their cost, ways to
circumvent the emulation cost by relaxing the termination condition, and
approaches to solving Consensus in this model (Byzantine Disk Paxos).

This is a joint work with Idit Keidar (Technion) and Dahlia Malkhi (HUJI).