Self-stabilizing multivalued consensus in the presence of Byzantine faults and asynchrony

Consensus, abstracting myriad problems in which processes must agree on a single value, is one of the most celebrated problems of fault-tolerant distributed computing. Consensus applications include fundamental services for the Cloud and Blockchain environments, and in such challenging environments, malicious behaviors are often modeled as adversarial Byzantine faults. At OPODIS 2010, Mostéfaoui and Raynal (in short, MR) presented a Byzantine-tolerant solution to consensus in which the decided value cannot be proposed only by Byzantine processes. MR has optimal resilience coping with up to t < n / 3 Byzantine nodes over n processes. MR provides this multivalued consensus object (which accepts proposals taken from a finite set of values), assuming the availability of a single binary consensus object (which accepts proposals taken from the set { 0 , 1 } ). This work, which focuses on multivalued consensus, aims to design an even more robust solution than MR. Our proposal expands MR's fault-model with self-stabilization, a vigorous notion of fault-tolerance. In addition to tolerating Byzantine, self-stabilizing systems can automatically recover after arbitrary transient-faults occur. These faults represent any violation of the assumptions according to which the system was designed to operate (provided that the algorithm code remains intact). To the best of our knowledge, we propose the first self-stabilizing solution for multivalued consensus for asynchronous message-passing systems prone to Byzantine failures. Our solution has an O ( t ) stabilization time from arbitrary transient faults.