## Synchronous Condition-based Consensus Adapting to Input-vector Legality

### Authors

- Taisuke Izumi, Osaka University
- Toshimitsu Masuzawa, Osaka University

### Abstract

This paper proposes a novel condition-based algorithm for the uniform
consensus in synchronous systems. The proposed algorithm is adaptive
in the sense that its execution time depends on actual difficulty of
input vectors, legality level, which is newly formalized in this
paper. On the assumption that majority of processes are correct, the
algorithm terminates within min{f + 2 - l, t + 1} rounds if l < f,
where f and t is the actual and the maximum numbers of faults
respectively, and l is the legality level of input vectors. Moreover,
the algorithm terminates in 1 round if l >= t and f=0, and terminates
within 2 rounds if l >= f holds. Compared with previous algorithms,
the algorithm achieves the best time complexity in almost all
situations.