Evènement pour le groupe Algorithmique Distribuée


Date 2008-12-08  14:00-15:00
TitreFault-tolerant implementations of regular register by safe register 
RésuméLamport defined three classes of communication registers: safe, regular. and atomic, in his seminal paper ("On Interprocess Communication", dc, 1986). The class of a register R depends on the returned values by a read operation of R overlapped by write operations on R. Register R is safe if a read operation that does overlap write operation returns any value. Register R is regular if any read operation that overlaps a write returns the value of either the latest write that happens-before it, or the value of some overlapping write. In any register R, a read operation that does not overlap any write, returns the value of the latest write on R that happens-before it. Lamports gives a wait-free implementation of a single-writer/single-reader regular binary register from only one single-writer/single-reader binary safe register. One extension to the research initiated by Lamport arises from asking whether wait-free and self-stabilizing constructions of regular registers from weak one can be made. Wait-freedom, captures tolerance of stopping failures of components of the network; and self-stabilization, captures recovery of the network from transient errors of its components. Lamport transformation is not self-stabilizing. In fact, as established by Hoepman, Papatrianfafiou and Tsigas ("Self-stabilization of wait-free shared memory objects",jpdc, 2002) there is no wait-free and self-stabilizing implementation of a single-writer/single-reader regular binary register with only one single-writer/single-reader safe binary register. In this talk we present a wait-free and self-stabilizing implementation of a single-writer/single-reader regular register by several single-writer/single-reader safe registers. This is joint work with Lisa Higham.  
LieuSalle 178 
OrateurColette Johnen 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index