| 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.
|