Speaker: Nicolas Nicolaou
Day:  Wednesday, 11/9/2005
Room: ITEB 201
Time: 3:30pm
Title: Time-efficient implementations of atomic read/write registers

Abstract:
This paper investigates time-efficient implementations of atomic read/write 
registers in message passing systems where the number of readers can be 
arbitrarily large. In particular we study the case of the single writer, 
multiple reader and S servers, such that the writer any subset of readers and 
up to t servers may crash.  A recent result shows how to obtain 
\emph{fast implementations} under a constraint on the number of 
concurrent readers in the system.  However they pose a question 
of whether it is possible to relax the bound on readers, and at what 
cost, if {\em semifast} implementations are considered, i.e., 
implementations that have fast reads or fast writes. This paper provides an 
answer to this question.  It is shown that one can obtain implementations 
where all writes are fast, i.e., involving a single round-trip 
communication, and where reads complete in one to two communication round 
trips under the assumption that no more than t<S/2 servers crash. Simulated 
scenarios presented in this paper indicate that a small fraction of 
reads require a second communication round.  Interestingly the correctness 
of the implementation does not depend on the number of concurrent 
readers in the system.  The solution is obtained with the help of a
 (non-unique) {\em virtual id} assigned to each node. Several readers 
can share a virtual id, with readers sharing the same virtual id forming 
a group. A notion of \emph{non-trivial} semifast implementations is 
introduced and it is shown that such implementations are possible if 
and only if the number of virtual ids is less than S/t-2.  
The result is proved to be tight in terms of the required communication
.It is shown that only a {\em single} two round-trip read operation 
may be necessary for each write operation, and it is proved 
that no semifast implementation can achieve better.  It is furthermore shown 
that no semifast implementation exists for the multi-read/multi-write model.