A Time-Free Assumption for Solving Signature-Free Asynchronous Multivalued Byzantine Consensus

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.