A Time-Free Assumption for Solving Signature-Free Asynchronous Multivalued Byzantine Consensus
Résumé
Abstract This paper tackles the asynchronous signature-free Byzantine consensus. One way to circumvent the FLP impossibility result consists in adding a Time-free assumption. This assumption is based on the pattern of messages that are exchanged. In the context of authenticated asynchronous Byzantine systems where at most t processes may exhibit a Byzantine behavior, Moumen and Mostéfaoui provide the main result. They assume at least one correct process $$p_i$$ p i , called $$\diamond \langle t+1\rangle \text {-winning}$$ ⋄ ⟨ t + 1 ⟩ -winning , and a set Q of t correct processes such that, eventually, for each query issued by $$p_i$$ p i , any process $$p_j$$ p j of Q receives a response from $$p_i$$ p i among the $$(n-t)$$ ( n - t ) first responses to that query. The main contribution of this paper is to show that a deterministic solution for the Signature-free Byzantine consensus problem is possible if the system model satisfies an additional assumption that relies on the pattern of exchanged messages. To solve the Consensus problem, we assume a correct process $$p_i$$ p i , called $$\diamond \langle 2t+1\rangle \text {-winning}$$ ⋄ ⟨ 2 t + 1 ⟩ -winning , and a set Q of $$(2t+1)$$ ( 2 t + 1 ) correct processes (including $$p_i$$ p i itself) such that, eventually, for each query issued by $$p_i$$ p i , any process $$p_j$$ p j of Q receives a response from $$p_i$$ p i among the $$(n - t)$$ ( n - t ) first responses to that query. The processes of the set Q may change over time. Based on this assumption, a Signature-free Multivalued Byzantine consensus protocol is proposed. Whereas many time-free protocols have been designed for the consensus problem in the crash model and in the Byzantine Authenticated model, this is, to our knowledge, the first time-free deterministic solution to the Signature-free Byzantine consensus Problem.
Citer ce document
Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)
Accès au document
Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter
Voir l'article sur le site de la revueLicence et provenance
Licence : CC BY
Notice moissonnée depuis OpenAlex le 26/09/2026. Le document reste hébergé par sa source.
Voir le document à la source →