Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, O(1) Time, and no Signature

摘要: This paper presents a new algorithm that reduces multivalued consensus to binary in an asynchronous message-passing system made up of n processes where t may commit Byzantine failures. has the following noteworthy properties: it assumes < n/3 (and is consequently optimal from resilience point view), uses O(n 2) messages, constant time complexity, and does not use signatures. The design this reduction relies on two all-to-all communication abstractions. first one allows non-faulty reduce number proposed values c, c small constant. second abstraction each process compute set (proposed) such that, if contains single value, then value belongs any process. Both abstractions have message complexity complexity. simple sequential these To best our knowledge, with messages (measured longest causal chain messages) presence processes, without using cryptography techniques. Moreover, tolerates re-ordering by processes. Une du multivalue au binaire en d'asynchronisme, de processus byzantins, avec un temps constant, et pas signatures Resume : Cet article presente algorithme reparti qui, dans systeme asynchrone qui communiquent par passage comprend jusqu'a ramene le probleme binaire. Cette est optimale rapport (t n/3), requiert n'utilise aucun element cryptographique (i.e., signatures). Elle considere donc adversaire la puissance calcul peut etre illimitee.