Speaker: Seda Davtyan
Day:  Wednesday, 12/05/2007
Room: ITEB 336
Time: 2:00-3:00pm

Title : Performing work Efficiently in the Presence of Faults

Abstract.
One of the fundamental problems in distributed computing is to  perform n
tasks in a distributed system prone to process failures.  When the tasks
are similar and independent from each other, and the  processors
communicate by sending messages, then this problem is called Do-All. The
algorithm for the Do-All problem need to be reliable, in that all the tasks
need to be performed as long as one of the processes remains operational.
We consider a system of t synchronous processes that communicate only by
sending messages to one another. We consider the following three parameters
for measuring the complexity of an algorithm: the number of messages sent,
the total number of units of work performed (including multiplicities), and
time. We will present three algorithms for solving the problem and will
discuss all pros and cons and the complexity of each algorithm in terms of
the aforementioned parameters.

Reading : 
Cynthia Dwork, Joseph Halpern and Orli Waarts "Performing work Efficiently
in the Presence of Faults", Proceedings of the eleventh annual ACM
symposium on Principles of distributed computing, PODC
Vancouver, British Columbia, Canada
Pages: 91 - 102