On the Subject of Non-Equivocation: Defining Non-Equivocation in Synchronous Agreement Systems

Mads Frederik Madsen, Søren Debois

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

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.
OriginalsprogEngelsk
TitelPODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
Antal sider10
Vol/bind39
ForlagAssociation for Computing Machinery
Publikationsdatojul. 2020
Sider159-168
ISBN (Elektronisk)978-1-4503-7582-5
DOI
StatusUdgivet - jul. 2020

Fingeraftryk

Dyk ned i forskningsemnerne om 'On the Subject of Non-Equivocation: Defining Non-Equivocation in Synchronous Agreement Systems'. Sammen danner de et unikt fingeraftryk.

Citationsformater