Skip to Main content Skip to Navigation
Reports

A Timing Assumption and two $t$-Resilient Protocols for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems

Abstract : This paper considers the problem of electing an eventual leader in an asynchronous shared memory system. While this problem has received a lot of attention in message-passing systems, very few solutions have been proposed for shared memory systems. As an eventual leader cannot be elected in a pure asynchronous system prone to process crashes, the paper first proposes to enrich the asynchronous system model with an additional assumption. That assumption (denoted $\mathit{AWB}$) is particularly weak. It is made up of two complementary parts. More precisely, it requires that, after some time, (1) there is a process whose write accesses to some shared variables be timely, and (2) the timers of $(t-f)$ other processes be asymptotically well-behaved ($t$ denotes the maximal number of processes that may crash, and $f$ the actual number of process crashes in a run). The {\it asymptotically well-behaved} timer notion is a new notion that generalizes and weakens the traditional notion of timers whose durations are required to monotonically increase when the values they are set to increase (a timer works incorrectly when it expires at arbitrary times, i.e., independently of the value it has been set to). The paper then focuses on the design of $t$-resilient $\mathit{AWB}$-based eventual leader protocols. ``$t$-resilient'' means that each protocol can cope with up to $t$ process crashes (taking $t=n-1$ provides wait-free protocols, i.e., protocols that can cope with any number of process failures). Two protocols are presented. The first enjoys the following noteworthy properties: after some time only the elected leader has to write the shared memory, and all but one shared variables have a bounded domain, be the execution finite or infinite. This protocol is consequently optimal with respect to the number of processes that have to write the shared memory. The second protocol guarantees that all the shared variables have a bounded domain. This is obtained at the following additional price: all the processes are required to forever write the shared memory. A theorem is proved which states that this price has to be paid by any protocol that elects an eventual leader in a bounded shared memory model. This second protocol is consequently optimal with respect to the number of processes that have to write in such a constrained memory model. In a very interesting way, these protocols show an inherent tradeoff relating the number of processes that have to write the shared memory and the bounded/unbounded attribute of that memory.
Document type :
Reports
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00142865
Contributor : Anne Jaigu <>
Submitted on : Monday, April 23, 2007 - 2:08:19 PM
Last modification on : Thursday, January 7, 2021 - 4:18:20 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 1:13:10 AM

Files

PI-1842.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00142865, version 1

Citation

Antonio Fernández, Ernesto Jiménez, Michel Raynal, Gilles Trédan. A Timing Assumption and two $t$-Resilient Protocols for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems. [Research Report] PI 1842, 2007, pp.19. ⟨inria-00142865⟩

Share

Metrics

Record views

682

Files downloads

394