Keynote Talk: On the complexity of fault-tolerant consensus

Darek Kowalski2 Dariusz Kowalski

University of Liverpool (UK)

ABSTRACT. We consider the problem of reaching agreement in a distributed message-passing system prone to crash failures. Crashes are generated by constrained adversaries – a weakly-adaptive adversary, who has to fix, in advance, the set of f crash-prone processes, and a chain-adaptive adversary, who orders all the processes into k disjoint chains and has to follow this order when crashing them. Apart from these constraints, both of them may crash processes in an adaptive way at any time.

While commonly used strongly-adaptive adversaries model attacks and non-adaptive ones – pre-defined faults, the constrained adversaries model more realistic scenarios when there are fault-prone dependent processes, e.g., in hierarchical or dependable software/hardware systems. In this view, our approach helps to understand better the crash-tolerant consensus in more realistic executions.

We propose time-efficient consensus algorithms against such adversaries. We complement our algorithmic results with (almost) tight lower bounds, and extend the one for weakly-adaptive adversaries to hold also for (syntactically) weaker non-adaptive adversaries. Together with the consensus algorithm against weakly-adaptive adversaries (which automatically translates to the non-adaptive adversaries), these results extend  the state-of-the-art of the popular class of non-adaptive adversaries, in particular, the result of Chor, Meritt and Shmoys [JACM 1989], and prove separation gap between the constrained adversaries (including the non-adaptive ones) and the strongly-adaptive adversaries, analyzed by Bar-Joseph and Ben-Or [PODC 1998] and others.

BIOGRAPHY. Dariusz R. Kowalski is a professor in the School of Computer and Cyber Sciences at Augusta University, USA, and in the Department of Computer Science at the University of Liverpool, UK. He received his MSc in Mathematics in 1996 and PhD in Computer Science in 2001, both from Warsaw University, Poland. His research is in algorithm design and analysis, with particular interests in distributed and parallel algorithms, communication and mobility, fault tolerance, and applications in other sciences.



All deadlines are at 23:59 AoE

March 5th, 2021, March 19th, 2021

Abstract submission deadline

March 12th, 2021 March 26th, 2021

Paper submission deadline

April 26th, 2021 April 30th, 2021

Acceptance notification

May 10th, 2021

Camera ready

May 10th, 2021

Pre-recorded talk


Revised selected papers will be published as a post-proceedings in Springer's LNCS "Lecture Notes in Computer Science"

Partners & Sponsors