Jovan Komatovic

Jovan Komatovic is a first year PhD student in Distributed Computing Laboratory (DCL) at School of Computer and Communication Sciences at EPFL.He obtained Bachelor's and Master's degree in computer science at School of Electrical Engineering, University of Belgrade.His research interests centre around theory and practice of highly secure distributed protocols.The current project Jovan is working on investigates the problem of accountable consensus algorithms.

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed t0) and allowing correct processes to obtain proof of culpability of (at least) t0+1 faulty processes whenever correct processes disagree. We present four complementary contributions: 1) We introduce ABC: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. ABC introduces an overhead of only two all-to-all communication rounds and O(n2) additional bits in executions with up to t0 faults (i.e., in the common case). 2) We define the accountability complexity, a complex-ity metric representing the number of accountability-specific messages that correct processes must send. Fur-thermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus protocol incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the ABC transformation to any Byzantine consensus protocol. 3) We demonstrate that, when applied to an optimal Byzan-tine consensus protocol, ABC constructs an accountable Byzantine consensus protocol that is (1) optimal with respect to the communication complexity in solving consensus whenever consensus is solvable, and (2) op-timal with respect to the accountability complexity in obtaining accountability whenever disagreement occurs. 4) We generalize ABC to other distributed computing prob-lems besides the classic consensus problem. We charac-terize a class of agreement tasks, including reliable and consistent broadcast [5], that ABC renders accountable.

IEEE2022

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.

Dagstuhl Publishing2022

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic

IEEE2022

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Crime and Punishment in Distributed Byzantine Decision Tasks

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Crime and Punishment in Distributed Byzantine Decision Tasks