loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'07)
A Timing Assumption and a t-Resilient Protocol for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems
Santorini Island, Greece
May 07-May 09
ISBN: 0-7695-2765-5
Antonio Fernandez, Universidad Rey Juan Carlos, Spain
Ernesto Jimenez, Universidad Politecnica de Madrid, Spain
Michel Raynal, IRISA, Universite de Rennes, France
Gilles Tredan, IRISA, Universite de Rennes, France
While electing an eventual common leader, despite process crashes, in a shared memory system where the processes communicate only by reading and writing shared registers is possible when the processes progress synchronously, this problem becomes impossible to solve as soon as the processes can progress in a fully asynchronous way. So, an important problem consists in finding additional behavioral assumptions that are, at the same time, "as weak as possible" (in order they are practically always satisfied), and "strong enough" in order to allow implementing an eventual leader service despite the net effect of asynchrony and failures. This paper focuses on this dilemma. More explicitly, it investigates a timing assumption that allows implementing an eventual leader in presence of partial asynchrony and process crashes. The proposed timing assumptions are particularly weak. They are the following: after some time (i) there is a process that behaves synchronously, and (ii) (t - f) other processes have timers that work correctly (t is the maximal number of processes that may crash, and f the actual number of process crashes; a timer works incorrectly when it expires too early with respect to the value it has been set). Then, the paper proposes a t-resilient protocol that elects an eventual common leader in any shared memory system that satisfies the previous assumption. Interestingly, this protocol is based on simple design principles.
Index Terms:
Asynchronous system, Atomic register, Eventual leader, Fault-tolerance, Omega, Process crash, Shared memory, System model, Timer property, Timing assumptions.
Citation:
Antonio Fernandez, Ernesto Jimenez, Michel Raynal, Gilles Tredan, "A Timing Assumption and a t-Resilient Protocol for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems," isorc, pp.71-78, 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.