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

Title: An Algorithm for the asynchronous Write-All Problem

Abstract:
The problem of using P processes to write a given value to all positions of
a shared array of size N is called the Write-All problem. If the processes
are reliable and run equally fast it is easy to come up with
straightforward, optimal solutions for this problem. The situation is quite
different, however, if processes can be faulty or run at widely varying
speeds while at least one process remains active. The algorithm proposed in
the paper is a generalization of the naive two-processor algorithm where
the two processes each start at one side of the array and walk towards each
other until they collide. The generalized collision algorithm is wait-free,
which means that each non-faulty process will be able to finish the whole
task, within a predetermined amount of steps, independent of the actions
(or failures) of other processes.

Reference:
J.F. Goote, W.H. hesselink, S. Mauw, R. Vermeulen: An Algorithm for the
asynchronous Write-All problem based on process collision. Distributed
Computing Vol. 14, pp. 75-81, 2001.