UTCS Colloquium/EDGE Seminar: Michel Raynal /IRISA-CNRS-INRIA-University Rennes France The Notion of a Timed Register and its Application to Indulgent Synchronization ACES 3.408 Wednesday June 6 2007 at 11:00 a.m.

Contact Name: 
Jenna Whitney
Date: 
Jun 6, 2007 11:00am - 12:30pm

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

ed algorithms and distributed computing. His
h-index is 31. Professor

Michel Raynal belongs to the editorial
board of several international

journals (including JPDC
and IEEE TPDS). He has published more than 100
papers in
journals has served in program committees for more than 70 international conferences chaired the program committee
of more

than 15 international conferences. Michel Raynal
received the IEEE ICDC

S best paper Award three times in
a row: 1999 2000 and 2001. He chair

edthe steering committee
leading the DISC symposium series in 2002-2004
and is
a member of the steering committees of the following confer

ences:
ACM PODC (ACM Symposium on the Principles of Distributed
Com

puting) SIROCCO (Colloquium on Structural Information and
Communicatio

n Complexity) and ICDCN (Int''l Conference on
Distributed Computing a

nd Networks).