03/08/2020

On the subject of non-equivocation: Defining non-equivocation in synchronous agreement systems

Mads Frederik Madsen, Søren Debois

Keywords: synchronous systems, agreement, non-equivocation, fault tolerance

Abstract: We study non-equivocation in synchronous agreement protocols: the restriction on faulty processes that they cannot act differently towards distinct non-faulty processes. Guarantees of non-equivocation have been used to provide improved fault tolerance in agreement protocols, and various mechanisms for achieving it have been proposed. However, the exact meaning of non-equivocation varies subtly in the literature. In this paper, we propose two different formal notions of non-equivocation: strong and weak. We define both as fault models for synchronous agreement protocols with reliable channels, and we show how the two models yield distinct bounds for the minimal number of communication rounds required and the maximum number of faulty processes tolerable to achieve agreement: 1 round, n > t for strong non-equivocation; and t + 1 rounds, n > 2t for weak non-equivocation. This makes weak non-equivocation the only fault model with a lower bound on fault tolerance of n > 2t for broadcast agreement and interactive consistency, confirming the folklore knowledge that equivocation is, in a sense, the most critical of the Byzantine faults. Finally, we show how the weak and strong non-equivocation fault models relate to well-known agreement problems: strong non-equivocation corresponds to Byzantine broadcast and weak non-equivocation to crusader agreement.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers