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

Accès au document

Texte intégral en lecture en ligne, réservé aux abonnés SPHAERO et aux membres de l'institution. Se connecter

Voir l'article sur le site de la revue

Auteur(s)

Statistiques

Consultations : 1

Téléchargements : 0