Author name cluster

Achour Mostéfaoui

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

TCS Journal 2021 Journal Article

Set-constrained delivery broadcast: A communication abstraction for read/write implementable distributed objects

Damien Imbs
Achour Mostéfaoui
Matthieu Perrin
Michel Raynal

This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ′, no process delivers first a set of messages including m ′ and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the “power” side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the “computability limits” side it shows that SCD-broadcast and read/write registers are computationally equivalent.

Details DOI

TCS Journal 2018 Journal Article

Randomized k-set agreement in crash-prone and Byzantine asynchronous systems

Achour Mostéfaoui
Hamouma Moumen
Michel Raynal

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. Algorithms solving k-set agreement in synchronous message-passing systems have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t ≥ k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t ≥ k, this paper presents two distributed algorithms that solve k-set agreement in asynchronous message-passing systems where up to t processes may commit crash failures (first algorithm) or more severe Byzantine failures (second algorithm). To circumvent k-set agreement impossibility, this article considers that the underlying system is enriched with the computability power provided by randomization. Interestingly, the algorithm that copes with Byzantine failures is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Both algorithms share basic design principles.

Details DOI

TCS Journal 2010 Journal Article

Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound

Achour Mostéfaoui
Michel Raynal
Corentin Travers

The k -set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k -set agreement problem in synchronous systems that can suffer up to t crash failures requires ⌊ t k ⌋ + 1 rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after min ( ⌊ f k ⌋ + 2, ⌊ t k ⌋ + 1 ) rounds, where f is the number of actual crashes in a run ( 0 ≤ f ≤ t ). This paper explores a new direction to solve the k -set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted has [ m, ℓ ] _SA objects) that allow solving the ℓ -set agreement problem in a set of m processes ( m < n ). The paper makes several contributions. It first proposes a synchronous k -set agreement algorithm that benefits from such underlying base objects. This algorithm requires O ( t ℓ m k ) rounds, more precisely, ⌊ t Δ ⌋ + 1 rounds, where Δ = m ⌊ k ℓ ⌋ + ( k mod ℓ ). The paper then shows that this bound, that involves all the parameters that characterize both the problem ( k ) and its environment ( t, m and ℓ ), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous computability. Finally, the paper extends its investigation to the early deciding case. It presents a k -set agreement algorithm that directs the processes to decide and stop by round min ( ⌊ f Δ ⌋ + 2, ⌊ t Δ ⌋ + 1 ). These bounds generalize the bounds previously established for solving the k -set agreement problem in pure synchronous systems.

Details DOI

TCS Journal 2009 Journal Article

From adaptive renaming to set agreement

Eli Gafni
Achour Mostéfaoui
Michel Raynal
Corentin Travers

The adaptive M -renaming problem consists of providing processes with a new name taken from a name space whose size M depends only on the number p of processes that participate in the renaming (and not on the total number n of processes that could ask for a new name). The k -set agreement problem allows each process that proposes a value to decide a proposed value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M = p + t. In the same setting, the k -set agreement problem cannot be solved when t ≥ k. This paper focuses on the way a solution to the adaptive renaming problem can help in solving the k -set agreement problem when t ≥ k. It has two contributions. Considering the case k = t ( 1 ≤ t < n ), the first contribution is a t -resilient algorithm that solves the k -set agreement problem from any adaptive ( p + k − 1 ) -renaming algorithm. The second contribution considers the case k < t. It shows that there is no such wait-free algorithm when k < n / 2 (wait-free means t = n − 1 ). So, while a solution to the adaptive ( p + k − 1 ) -renaming problem allows t -resiliently solving the k -set agreement problem despite t = k failures, when k < t such an additional power becomes useless for the values of n > 2 k (i. e. adaptive ( p + k − 1 ) -renaming allows progressing from k > t to k = t, but does not allow bypassing the “ k = t ” frontier when n > 2 k ).

Details DOI

STOC Conference 2001 Conference Paper

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Achour Mostéfaoui
Sergio Rajsbaum
Michel Raynal

This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions , for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes.

Details