Speaker Name/Affiliation: Michel Raynal/IRISA-CNR

S-INRIA-University
Rennes France

Date/Time: Wednesday June 6
2007 at 11:00 a.m. - 12:30 p.m.

Location: ACES 3.408

Host:
Prof. Vijay Garg

Talk Title: The Notion of a Timed Register and it

s Application to
Indulgent Synchronization

Talk Abstract:
A n

ew type of shared object called timed register is
proposed and used

for the design of indulgent timing-based
algorithms. A timed register g

eneralizes the notion of an
atomic register as follows: if a process in

vokes two consecutive
operations on the same timed register which are a
read followed
by a write then the write operation is executed only if

it is invoked at most d time units after the read operation
where

d is defined as part of the read operation. In this
context a timing-b

ased algorithm is an algorithm whose
correctness relies on the existenc

e of a bound Delta such
that any pair of consecutive constrained read a

nd write
operations issued by the same process on the same timed
re

gister are separated by at most Delta time units. An indulgent
algorith

m is an algorithm that always guarantees the safety
properties and ens

ures the liveness property as soon as
the timing assumptions are satisf

ied. The usefulness of
this new type of shared object is demonstrated b

y presenting
simple and elegant indulgent timing-based algorithms that

solve the mutual exclusion L-exclusion adaptive renaming
test&se

t and consensus problems. Interestingly timed registers
are universal
objects in systems with process crashes and
transient timing failures (

i.e. they allow building any
concurrent object with a sequential speci

fication).

Speaker Bio:
Michel Raynal (http://www.irisa.fr/miche

l.raynal/)has been
a professor of computer science since 1981. At IRISA

(CNRS-INRIA-University joint computing research laboratory
located
in Rennes) he founded a research group on Distributed
Algorithms in 1

983. His research interests include distributed
algorithms distributed
computing systems networks and
dependability. His main interest lies

in the fundamental principles
that underly the design and the construct

ion of distributed computing
systems. He has been Principal Investigator
of a number
of research grants in these areas and has been invited by many universities all over the world to give lectures
on distribut

nd Networks).