2025/07/14 by Gabriel Kafure da Rocha, Rocha, Gabriel
Psychology · #Computational Complexity (cs.CC) #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Logic in Computer Science (cs.LO) #Parallel #Philosophy and Theoretical Science #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2507.10413
openalex publication_date 2025/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The consensus problem, briefly stated, consists of having processes in an asynchronous distributed system agree on a value. It is widely known that the consensus problem does not have a deterministic solution that ensures both termination and consistency, if there is at least one faulty process in the system. This result, known as the FLP impossibility theorem, led to several generalizations and developments in theoretical distributed computing. This paper argues that the FLP impossibility theorem holds even under a generalized definition of computation through oracles. Furthermore, using a theoretical machinery from complex systems, this paper also posits that inconsistency may be an emergent feature of consensus over distributed systems by examining how a system transitions phases. Under the same complex systems framework, this paper examines paraconsistent logics, arguing that while inconsistency is not an emergent feature for these logics, triviality may be. Lastly, some attention is given to the possibility of developing consensus algorithms capable of paraconsistent reasoning.