Skip to Main content Skip to Navigation
Conference papers

Time-Free Authenticated Byzantine Consensus

Abstract : This paper presents a simple protocol that solves the authenticated ByzantineConsensus problem in asynchronous distributed systems. To circumvent the FLP impossibility result in a deterministic way, synchrony assumptions should be added. In the context of Byzantine failures for systems where at most t processes may exhibit a Byzantine behavior and where not all the system is assumed eventually synchronous, Moumen et al. provide the main result. They assume at least one correct process, called 2t-bisource, connected with 2t privileged neighbors with eventually timely outgoing and incoming links. The present paper shows that a deterministic solution for the authenticated byzantine consensus problem is possible if the system model satisfies an additional assumption that does not rely on physical time but on the pattern of messages that are exchanged. The basic message exchange between processes is the query-response mechanism. To solve the Consensus problem, we assume a correct process p, called eventual 2t-winning process, and a set Q of 2t processes such that, eventually, for each query issued by p, any process q of Q receives a response from p among the (n-t) first responses to that query. The processes in the set Q can exhibit a Byzantine behavior and this set may change over time. Whereas many time-free solutions have been designed for the consensus problem in the crash model, this is, to our knowledge, the first time-free deterministic solution to the Byzantine consensus problem.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Achour Mostefaoui Connect in order to contact the contributor
Submitted on : Wednesday, December 8, 2010 - 12:20:46 PM
Last modification on : Thursday, January 20, 2022 - 4:20:36 PM
Long-term archiving on: : Thursday, March 10, 2011 - 11:48:39 AM


Publisher files allowed on an open archive


  • HAL Id : inria-00544518, version 1


Hamouma Moumen, Achour Mostefaoui. Time-Free Authenticated Byzantine Consensus. 10th IEEE International Symposium on Network Computing and Applications (NCA'11), IEEE, Jul 2010, Cambridge, MA, United States. pp.140-146. ⟨inria-00544518⟩



Record views


Files downloads