HTML reading edition · 82 source pages · Open the source PDF

Heterogeneous trust in reliable broadcast via modal logic and history structures

Murdoch J. Gabbay Isaac Sheff

We develop a novel modal logic and semantics for specifying and proving properties of distributed full-information-transfer protocols (protocols that broadcast state to all participants in a distributed system). We use this to present in declarative-programming style, three novel generalisations of Bracha’s ‘reliable broadcast’ algorithm to a heterogeneous trust setting (where distinct participants may have distinct trust assumptions), and state and prove their correctness properties. The maths in this paper has been mechanically formalised and checked, and a proof-of-concept model-checker is freely available.

Why does this matter?

Computer systems are often distributed, for resilience, speed, or scalability. A heterogeneous distributed system admits multiple sets of trust assumptions (quorums). Even if heterogeneous trust is not assumed, it arises anyway when homogeneous systems interact. Unfortunately, it is easy for heterogeneity to manifest as practical complexity for the user: without good support for heterogeneity, each (homogeneous) system becomes a “walled garden”, unable to interact flexibly with other systems because of differing trust assumptions.

There is no single world currency, but it is helpful if we can spend our local currency abroad as if there were (in the sense that we can think more about shopping than about currency exchange); there is no single world language, but it would be helpful if we could each speak our native language as if there were; there is no world register of medical doctors, but it would be helpful if we could safely consult with a foreign medical practitioner as if there were; there is no Single World Blockchain — but it would be helpful if we could transact across blockchains as if there were.

In abstract mathematical terms, the challenge is to liberate users (participants in a distributed environment) to reliably and easily transact across heterogeneous (i.e. different) trust models. Ideally, the user-facing outcome should be as smooth as transacting with some single centralised trusted party, in the sense that users do not have to worry about reasonable differences in trust models (for some suitable mathematically-stated notion of ‘reasonable’). This motivates mathematical support to help attain the diversity and resilience that heterogeneous distributed systems can offer, without the price imposed by the complexity of managing distributed heterogeneous trust.

This challenge invited us to fundamentally rethink how distributed algorithms are specified and their properties stated and proved. We adopt a declarative approach based on a novel modal logic whose modal operators are epistemic and quorum-based (rather than directly temporal), acting on a semantics in what we call history structures . In history structures, time is not clock-based, but instead is a history of what a participant knows when it performs the next event; and the logic provides explicit modalities for reasoning about knowledge, participants, and heterogeneous quorums (trust assumptions).

The advantage of being declarative, epistemic, and quorum-based over history structures is that this lets us write axioms that directly describe what the protocols do — since the protocols are typically based precisely on participants acting in the context of knowledge of past events, based on observations of quorum behaviour. This novel and (in our view) very natural semantic mapping between logic and protocol helps manage the complexity of the heterogeneous case.

We use this machinery to propose three heterogeneous generalisations of Bracha’s reliable broadcast protocol, each making different trade-offs between complexity and the strengths of their correctness properties. For each, we prove correctness properties: two liveness properties, and one agreement property. Individually, the protocols are new and interesting; and taken together, they illuminate a novel design space of heterogeneous distributed algorithms.

Our protocols are expressed compactly as logical theories (sets of logical axioms). A run of a protocol corresponds to a model of that protocol’s theory, and a correctness property is a property of the set of all models of the theory. Logic and model theory are powerful, precise, and flexible tools: once the machinery is set up, writing out a protocol just takes a modest table of axioms, and its correctness proofs are by a few lines of symbol-pushing from the axioms using some key lemmas.

Draft of 2026/11/14.

Additional Key Words and Phrases: Heterogeneous distributed systems, Distributed Broadcast, Bracha Broadcast, Modal Logic, Kripke semantics, History Structures

Contents

1 Introduction 3

1.1 The problem 3

1.2 A nontrivial test bench: Bracha Broadcast 6

1.2.1 Sketch of Bracha Broadcast 6

1.2.2 Heterogeneity 7

1.2.3 The fault model 7

1.3 Why broadcast? Why a new logic? Why heterogeneity? 9

1.4 Map of the paper 10

2 History structures and their logic 11

2.1 A brief discussion using programming terminology 11

2.2 Prehistories 12

2.2.1 Finite subsets and maybe-sets 12

2.2.2 Definition of prehistories 12

2.3 History structures 13

2.3.1 Definition 13

2.3.2 Discussion and examples 15

2.3.3 Design alternatives: element-transitivity and posets 17

2.3.4 Discussion of nothing: † 17

2.3.5 Further discussion of nothing 18

3 Logic over history structures 20

3.1 Syntax 20

3.2 Example predicates, and their intended meanings 22

3.3 Models 23

3.3.1 Semifilters 23

3.3.2 Definition of models 23

3.3.3 Discussion of models 25

3.4 The Kripke semantics associated to a model, and validity 26

3.4.1 Kripke (relational) semantics 26

3.4.2 Sequentiality 27

3.4.3 Validity 28

3.5 Active and inactive participants 30

3.6 Extending syntax with syntactic sugar 30

4 The modalities 37

4.1 Quorum intersection properties 37

4.2 Modal properties 38

5 Sequentiality and liveness 39

5.1 Properties of sequentiality 39

5.2 A logical theory of liveness 41

5.2.1 (Axiomatic) theories 41

5.2.2 Definition of ThyLive 42

5.2.3 More on the Knowledge axioms 43

5.2.4 More on (LiveAlways) 44

6 Theory ThyHBB1 45

6.1 What a theory is, and how is it executable 45

6.2 Definition of the theory 46

6.3 Further discussion of some ThyHBB1 axioms 49

6.4 Agreement 51

6.5 Cascade Termination 51

6.6 Happy Termination 53

6.7 Further discussion 54

7 Theory ThyHBB2 55

7.1 Definition of the theory 55

7.2 Discussion 56

7.3 Proofs of Agreement, Happy Termination, and Cascade Termination 58

8 Theory ThyHBB3 59

8.1 .=: the correlation relation 60

8.2 Definition of the theory 61

8.3 Agreement 63

8.4 Cascade Termination 63

8.5 Happy Termination 65

8.6 Discussion 66

9 Conclusions 67

9.1 Looking back on the results 67

9.2 Why heterogeneous protocols? 68

9.2.1 It’s about the ecosystem 68

9.2.2 Why this has not been done before 69

9.2.3 Embracing heterogeneity 70

9.3 Related work 70

9.3.1 Heterogeneous Paxos (2021) 70

9.3.2 XRP Ledger and Stellar (2014/15) 70

9.3.3 Epistemic logics 71

9.3.4 The ATL logic family 72

9.3.5 Event structures 72

9.3.6 Trace Diagrams 73

9.3.7 Temporal Logic 73

9.3.8 Cross-domain state updates 74

9.3.9 Interoperability of state for blockchain 74

9.4 Future work 74

A Reducing to the homogeneous case 80

A.1 Homogeneous ThyHBB1 and ThyHBB2 (Figures 8 and 10) 81

A.2 Homogeneous ThyHBB3 (Figure 12) 81

1. INTRODUCTION

1.1. The problem

In this paper, we develop a modal logic and associated denotation such that protocols for heterogeneous distributed protocols can be written concisely in declarative programming style, and their correctness properties stated and proved. Then, we use our framework to write down three novel heterogeneous generalisations of Bracha’s classic broadcast protocol, and we state and prove their correctness properties.

We will now unpack the jargon, starting with a sketch of what modal logic, distributed protocol, and heterogeneous mean, and why they matter.

Modal logic. A modal logic is a logic where the validity of its predicates may reference some notion of place or time. Instead of a judgement ⊨ϕ meaning ‘ϕ is valid’, we have a judgement of the form w ⊨ϕ meaning ‘ϕ is valid in some modal context w’ [BdRV01].1

Classic motivations for modalities include sentences like ‘it is raining’ (whose validity depends on where and when we are), or ‘I see rain’ (whose validity may additionally depend on who is making the claim), or ‘tomorrow, it will rain’, or ‘eventually, it will rain’ (which quantifies over future times), or ‘it rains everywhere sometime’ (which is ambiguous in English but can be disambiguated using the precision of ordering modal operators), and so on.2

In this paper, our modalities will refer to notions of place, time, and to quorums of participants (we explain quorums in a moment).

Distributed protocols. A distributed protocol, or synonymously a distributed algorithm, is a protocol/algorithm that runs over many participants [CGR11]. What makes the theory of distributed protocols different from that of parallel or concurrent ones is that in distributed protocols, some proportion of the participants may be faulty, by which we mean in this paper that they need not follow the protocol and may display arbitrary, possibly deliberately hostile, behaviour (the term Byzantine is also well-established in the literature [LSP82]; we may use this synonymously with ‘faulty’).

Distributed protocols gained their modern relevance when computers became networked in the 1980s (Ethernet was introduced in the mid-70s [MB76], and by the 80s it was in widespread use [SDRC82]). A machine on a network cannot necessarily vouch for the correctness of other machines on that network; the best it can do is proceed on a failure assumption that not too many of them are faulty (for some appropriate notion of ‘too many’) — and hope that this assumption is accurate. Subsequent developments, such as modern telephony, satellite systems, the internet, cloud computing, peer-to-peer protocols, and blockchains — all systems such that being distributed is part of the essential character of what that system is meant to accomplish — have made distributed systems an integral part of how modern computing works. Applied and theoretical research activity in distributed algorithms has grown accordingly.

The usual solution to the possibility of faulty participants, in general, is to treat a step in the protocol as completed only when some quorum of participants have attested to it. If we assume that quorums are large relative to the set of faulty participants then every quorum will contain a non-faulty (correct) participant3 — so that with this assumption, if we know that a quorum of participants agree on some output, then we can rely on the output being the result of a correct run of the protocol by some correct participant. It is simplistic but reasonably accurate to say that the typical distributed algorithm has the form ‘wait until we hear a quorum of participants return suitable messages, then proceed to our next relevant step on the assumption that at least one of them was an outcome of a correct run of the protocol thus far’.

Heterogeneity. A protocol is heterogeneous when different participants, or perhaps even the same participant at different times, might differ on what sets they recognise as quorums. In other words: in a heterogeneous protocol, the notion of ‘trust’ (as expressed by what quorums participants assume may be trustworthy) may vary with time and/or participant. For a simple example (we consider more below) consider an international bank transfer: two banks in different juristications using different servers — intuitively: having different trust models — must somehow agree that one has sent some cash to the other. This must be atomic: even if messages fail to arrive or sub-systems crash or become faulty, the system as a whole must not hang in a state in which one bank insists that it has sent the money and the other bank insists that it has not received it, or vice versa. As the reader may know, this is not trivial.

Remark 1.1.1

Heterogeneity matters for a certain kind of compositionality among distributed systems.

If a trust model must be homogeneously applied across the entire system, then two systems with different trust models cannot be called one (homogeneous) system — so if our philosophy and mathematics assume only homogeneous systems are of interest, it can say little about two of them interacting.4 In contrast, if the trust model is applied heterogeneously (e.g. by assigning each participant a possibly different trust model), then composition becomes natural.

Returning to our banking example, consider a multi-branch bank. This may have a separate distributed system (with a distinct trust model) for each branch (e.g. local servers to handle local affairs), and it may have yet another distributed system for cross-branch activity: each is fault-tolerant with its own set of quorums. However, if we want to reason about the bank’s systems as a whole, then these do not match a homogeneous model: the bank is a heterogeneous system, because it is made up of non-identical parts. Example properties we might want to prove about a heterogeneous bank include:

(1) Cross-branch transactions are atomic: either all branches update with their part of the transfer, or none update.

(2) No more money leaves the bank than came in: this should hold across the whole bank, not necessarily for any one branch.

(3) The sum of loans (across all branches) with a given piece of collateral should not exceed the value of that collateral.

Remark 1.1.2

Heterogeneity naturally arises across axes of both time and space:

(1) Multiple systems across space — bank branches, voting systems (national, local, or otherwise), businesses, and blockchains — use diverse trust models, and often have to work with other systems using different trust models. For example: blockchains have well-defined and often highly intersecting quorum systems, but applications built for homogeneous trust models may struggle to work with multiple blockchains simultaneously, which is a recognised impediment to getting anything done [Shi26]. The broadcast protocols later in this paper show precisely the kind of reasoning needed to atomically commit transactions (a key stumbling block for multi-blockchain systems) over blockchains with distinct, but overlapping trust models (such as most Cosmos chains [KB16]).

(2) One participant in a system might change trust models across times. For example, the quorums used to maintain a distributed database or blockchain update in response to changing infrastructure, participant behaviour or failures, and economic conditions. Many homogeneous system designs have explicit protocols for updating the trust assumptions of the system as a whole [CKV01; OO14; AGPPBTP19], but if we want to reason about operations that span such an update — then we’re reasoning about a heterogeneous system.

Homogeneity is simply a natural edge case: when all participants have the same assumptions throughout space and time. Reasoning about heterogeneous systems therefore generalises reasoning about homogeneous ones: every heterogeneous system becomes homogeneous when assumptions are uniform.

Remark 1.1.3

Practical examples of heterogeneity made explicit in blockchain include Cosmos blockchains (‘a network of distributed ledgers’) [KB16], which use different (but highly overlapping) quorum sets, or Ripple and Stellar (discussed in Subsection 9.3.2).

An under-appreciated fact is that similar ideas are being adopted and institutionalised in the central banking community. Central bankers use different language and publish in different venues5 but many of the problems are similar if not identical, and sometimes this is made explicit, see e.g. a recent BIS working report [Shi26] and accompanying Financial Times analysis [Nan26].

So heterogeneity is a real problem which arises naturally when homogeneous systems are composed, and compose they must. If this has flown under the radar, we would argue that this is because heterogeneity is extremely difficult to come to grips with.6 This paper is an attempt to do this for Bracha Broadcast, using tools from mathematical logic.

It is now time for some definitions:

Definition 1.1.4

Assume Pnt some set of participants in a distributed algorithm.7 A quorum system O ⊆ powerset(Pnt) is some set of sets of participants in a distributed algorithm. We call each O ∈O a quorum. We may also call O a trust assumption.

In the mathematics to come, quorum systems / trust assumptions will be refined to the notion of semifilter in Definition 3.3.2; see also the semifilter-valued learner interpretation in Definition 3.3.3(4) and the discussion of what that means in Remark 3.3.4(2).

Definition 1.1.5

A heterogeneous distributed algorithm is such that several trust assumptions are present, and which is used may potentially vary by time and participant. In other words, we have not one quorum system O, but some nonempty set of them: O = {O1, . . . , On, . . . } ⊆ powerset(powerset(Pnt)).8

Remark 1.1.6 (This paper in a nutshell).

(1) We develop a logic enriched with modalities for talking about participants (places), times, participants’ knowledge at each particular place and time, and rich modal properties having to do with heterogeneous quorums and quorum intersections.

(2) We apply our logic to invent and prove correctness properties of heterogeneous generalisations of Bracha’s reliable broadcast algorithm (see next Subsection): ThyHBB1, ThyHBB2, and ThyHBB3, each of which is interesting in its own right.

(3) The definitions and proofs in this paper have been formalised in the Lean 4 theorem prover, complete with clear instructions for use and with clear and precise linkages between the results in this paper and their formalised Lean code. The interested reader can download the files [Har25] and run the verification locally.

1.2. A nontrivial test bench: Bracha Broadcast

1.2.1. Sketch of Bracha Broadcast.

A seminal distributed algorithm is Bracha Broadcast (BB), introduced in a paper by Bracha [Bra87]. In the homogeneous case as considered by Bracha — so there is one, globally agreed, quorum system — this solves the problem of how a proposer can broadcast a value across the network, such that correct participants agree on the value proposed.9

The messaging pattern in BB is as follows: propose, echo, vote, and deliver. The initial propose message is just done by a designated initial proposer; then there are two rounds of messaging between participants (echo and vote); and a final deliver action where individual participants conclude which value they choose. Very briefly, the protocol runs as follows:

— participants echo only the first proposed value they see;

— they vote only upon observing a quorum of echoes with the same value, or a blocking set (a set intersecting all quorums) of votes for the same value; and

— they deliver upon observing a quorum of votes for the same value.

The interesting reader is referred to [Bra87] for more details, or to a declarative axiomatisation by the first author [Gab26a] (essentially: this paper, but for classic BB instead of HBB).

BB has three correctness properties, which we sketch as follows (these are not mathematical statements, yet):

— Happy Termination (a liveness property) If there is a quorum of correct participants (meaning: all participants in the quorum are live and correctly follow the protocol)10 and precisely one value v is proposed, then that correct quorum eventually concludes v. This is the ‘happy’ path which we would hope the system will follow most of the time: there are enough correct participants, the proposer is honest and proposes only one value, and things go smoothly and well.

— Cascade Termination (a liveness property) If one participant in a quorum of correct participants delivers v, then — even if the proposer incorrectly proposes multiple values — all participants in that quorum eventually deliver that same value v.

— Soundness / Agreement (a safety property) If two correct participants conclude v and v′ respectively, then v = v′.

1.2.2. Heterogeneity.

Note above that we write ‘there is a quorum’, without specifying who decides what a quorum is. This is because it is assumed that everyone agrees on this; Bracha’s trust assumptions were what we here call homogeneous. Heterogeneous Bracha Broadcast lives in the part of the design space where participants might not agree on what a quorum is.

As we argued in Remark 1.1.2, this is not an edge case. Heterogeneity naturally arises when distinct homogeneous systems seek to interact, e.g. when bank A (with its own servers and trust assumptions) wants to agree that it has paid a unit of currency to bank B (with its own, possibly different, servers and trust assumptions). It may be worth noting explicitly that a system is usually only as useful as its ability to interact with other systems. This naturally leads us to consider heterogeneous distributed systems, where participants do not necessarily have the same assumptions about who might fail and how, but nevertheless they must run protocols and interact.

It turns out that many heterogeneous generalisations of Bracha’s reliable broadcast exist, and we will introduce three of them, which between them triangulate in a rich design space. We will state precise analogues of the Happy Termination, Cascade Termination, and Soundness / Agreement properties later (see Figures 9, 11, and 13); the above is just to give the reader a flavour.

1.2.3. The fault model

Remark 1.2.1 (The fault model).

Bracha’s original paper had a threat model (which has become typical in distributed protocol theory) that strictly fewer than a third of participants should be faulty, where here faulty means does not follow the protocol, either through a crash or through deliberate misbehaviour. That is, if there are n = 3f + 1 participants, then at most f of them are faulty. We can rephrase this that the set of quorums in Bracha Broadcast is the set of sets of participants with at least 2f + 1 participants.

In this paper the fault model is slightly different, motivated by the systems which the second author has helped design:11 we will assume that the underlying message protocol is full information and cryptographically signed.

In the underlying implementation (warning: idealised description) this means every message sent by a participant p comes with a cryptographic hash which unforgeably identifies p as the sender

(e.g. using some private key known only to p), and which also unforgeably identifies the state of p, including all messages that p has received from other participants, at the moment of sending, along with a cryptographic proof that this state is legal and well-formed. How this cryptography works is out-of-scope, but it can be done.

Therefore p cannot ‘just invent messages’ from other participants (because p does not know their private keys) and p cannot ‘just invent state’ (because p would have to invent messages from other participants, and because ill-formed state cannot just be arbitrarily cryptographically signed as correct).

One might think that this would eliminate all possible incorrect behaviour (aside from crashing), but not so: p can equivocate, meaning that p omits incompatible fragments of state in incompatibly-historied messages it sends to other participants: it can leave out important facts.

To see how equivocation works, consider the classic example of a double-spend. Here, p sends a digital token to some q, and it also sends the same digital token to q′. p does not have to lie or invent state when it spends the digital token in a transaction with q′; it just has to not mention the part of its history where it had already spent that token in a transaction with q.12

The effect of this is that

the only admissible Byzantine behaviour in our fault model is non-sequential behaviour,

(i.e. the use of irreconcilable histories).

We illustrate this in Figure 1 with the exponential cake, a digital cake which a participant can have, and also eat (which is wrong, and that is the point). The cake that starts off with participant 1, is (sequentially) sent to participant 2, then nonsequentially sent to participants 1 (who eats the cake) and also to 3. This is nonsequential because our notion of history insists that digital cake should not be copied, reflecting the properties of real-life cake, so that according to our rules of what constitutes a valid history, 2 cannot include both sends on a single timeline — in our logic, this would be modelled by an axiom like the (EchoNE) or the (VoteNE) axioms which we will see later. Then 3 sends the cake back to 1, so that 1 has its cake, and eats it.

The double-spend by 2 creates a nonsequential branch in 2’s history; participant 2 equivocates about this. In our fault model, this diagram would not be admissible: participant 1 would detect that a nonsequential operation has taken place and be unable to accept the second piece of cake, because to do so would create an illegal history.

Our sequentiality-based fault model comes out of mathematics and theory, but it may be worth noting that other authors have come to a similar place from a different directions. For example (non-exhaustive list) [Hel07] written by a systems designer, takes an explicit position that serialisable systems like those admitted by our fault model are the ones that are most usefully implemented in practice,13 and a recent paper on distributed systems theory [?] proves that in certain circumstances one can without loss of generality assume a fault model as we do, even if the real-life fault model is more general.14

1 2 3a bcd efgh
Fig. 1: Nonsequential behaviour: the exponential cake (Remark 1.2.1)

1.3. Why broadcast? Why a new logic? Why heterogeneity?

Other distributed problems exist, including for example Consensus, yet we focus on Broadcast. Broadcast is arguably a canonical simplest nontrivial distributed algorithm, and research shows how Consensus can be built on top of it [Bra87, Section 4, “The Consensus Protocol”].15

Thus, Heterogeneous Bracha Broadcast (HBB) is a kind of universal building block, a useful test subject, and a convenient place to start. It is simple enough to be accessible, and expressive enough to be useful.16

Furthermore, it turns out that Bracha’s reliable broadcast algorithm is a useful and fruitful object of study because it admits multiple, and multiple interesting, generalisations to the heterogeneous case.

Other logics exist for specifying distributed algorithms. Why design a new one. Our logic will let us specify and reason about distributed algorithms declaratively: in our analysis an algorithm is an axiomatic theory, and a run of the algorithm is a model of that theory. We mean by declarative that we elide details of control flow and evaluation order — where we deem these inessential, which is surprisingly often — so we can focus on the essence of what the protocol is.

This method, which follows a thread of previous research [GZ26], yields simplifications that are analogous to what we see moving from programming in a low-level imperative language to a higher-level functional or logic programming language: more compact assertions, less control flow, less worrying about evaluation order, and more (and more clear) high-level specification of what the program does.

So one answer to the question above is: because it works well. But there are also two things going on in the logic we use in this paper, which are specific to this paper in particular.

(1) Its logical modalities are tailored to talk about heterogeneous quorums and quorum intersections; see the three modalities ↓,⤒→, and ♢ in Figure 4 and their semantics. This yields a compact but expressive logic with which we will be able to concisely and precisely express complex reasoning on our three algorithms.

This is so effective that once we have things set up, our correctness proofs can just proceed by symbolic manipulation (so-called ‘symbol pushing’). The proof of Proposition 6.5.5 is a case in point. The notation might take getting used to, but the proof is succinct and precise — and the other proofs are basically just minor variations of it. This is a feature, because it is good when correctness proofs are short, routine, and predictable.

(2) Second, and furthermore, we use a novel epsilon-inductive notion of time17 which we call History Structures. In a history structure, the time of an event is equal to the set of events that have happened before that event. We mean this literally. Time is not a number or a vector of numbers (cf. Lamport clocks [Lam78] or vector clocks [SM94; RS96]).18 For us, time is literally a set of past events, which themselves are indexed by times that are sets of past events, and so on. The slogan is that time is equal precisely to that which has happened before. It turns out that this interacts elegantly and naturally with our logical methodology and axiomatisation, as we shall see.

Why heterogeneous distributed algorithms matter. Heterogeneity reflects the following question:

how, and in what mathematical circumstances, can distinct communities collaborate, even if they have distinct trust assumptions?

Heterogeneity can provide diversity and resilience, in that different communities can make different choices and yet still interact, and the overall system can continue operating (in a suitable sense) even when some communities may fail.

In order for heterogeneous trust systems to compete on the basis of user-facing experience and simplicity with ones featuring a single homogeneous trust assumption, the system overall must be able to automate the accounting of managing multiple trust systems, such that two users with trust preferences compatible in the actual course of history can interact as if they were using a homogeneous system. In the ideal case, the system would be as easy to use as a centralised one that relies on a single trusted party who behaves as expected — even though it actually is composed of multiple communities with multiple trust assumptions, all stitched together in some mathematical way. So the challenge is how, and in what circumstances, we might reduce the differential user-facing complexity cost of a heterogeneous trust system to nearly zero.

Our three protocols give three preliminary, but precise and rigorous, answers to that question, and our logic gives a methodology for validating their correctness and, perhaps, for designing more protocols in future.

1.4. Map of the paper

(1) We begin in Section 1 with the Introduction. You Are Here.

(2) In Section 2 we introduce history structures. This inductive structure gives us our notion of time: a moment in time consists by definition of the collection of events that have happened before that time. The key definitions are Definitions 2.2.4 (prehistories) and 2.3.5 (history structures).

(3) In Section 3 we develop the syntax and semantics of a modal logic for specifying and reasoning about distributed algorithms. The key definitions are in Figures 3 (syntax) and 4 (validity).

(4) In Section 4 we explore the modal structure of our logic, which gives us a rich choice of modalities for talking about quorums and quorum intersections. This is not a long Section but it focusses on one of the most distinctive features of our logic, which is also key to its intended application of declaratively specifying and reasoning about heterogeneous distributed protocols.

(5) In Section 5 we discuss the two canonical correctness properties for participants: sequentiality and liveness. A participant is sequential when (intuitively) it experiences linear time. Recall that our model of time is that which has happened before, so sequentiality excludes equivocation; telling different and incompatible things to other participants.
In blockchain terminology, sequentiality corresponds roughly to not forking, which is arguably the canonical correctness property that a blockchain should preserve. Sequentiality is thus a form of non-forking consistency, for participants. A participant is live when it is correct (= follows the protocol) and always eventually progresses the protocol where possible (= does not crash). In a nutshell we can write:

Live = Correct/non-faulty + Non-crashing.

It turns out that we can express liveness formally as a logical theory (Figure 7).

(6) We now have enough to axiomatise and prove correctness properties of our three heterogeneous broadcast protocols, ThyHBB1, ThyHBB2, and ThyHBB3. We do this in Sections 6, 7, and 8.

(7) We then conclude with the Conclusions in Section 9.

List of Figures

We include a list of figures for convenient reference:

3Syntax of predicates (Definition 3.1.3 ) . . . . . . . . . . . . . . . . . . . . . . . .21
4Validity (Definition 3.4.10 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
5Extended (sugared) syntax (Definition 3.6.1 ) . . . . . . . . . . . . . . . . . . . . .31
6Denotation of sugar from Figure 5 (Definition 3.6.1 ) . . . . . . . . . . . . . . . . .31
7ThyLive : a theory of liveness (Definition 5.2.4 ). . . . . . . . . . . . . . . . . . .42
8Theory ThyHBB1 (Definition 6.2.2 ) . . . . . . . . . . . . . . . . . . . . . . . . .47
9Correctness properties for ThyHBB1 (Theorem 6.2.6 ) . . . . . . . . . . . . . . . .47
10Theory ThyHBB2 (Definition 7.1.1 ) . . . . . . . . . . . . . . . . . . . . . . . . .56
11Correctness properties for ThyHBB2 (Theorem 7.1.3 ) . . . . . . . . . . . . . . . .56
12Theory ThyHBB3 (Definition 8.2.1 ) . . . . . . . . . . . . . . . . . . . . . . . . .62
13Correctness properties for ThyHBB3 (Theorem 8.2.3 ) . . . . . . . . . . . . . . . .62

2. HISTORY STRUCTURES AND THEIR LOGIC

2.1. A brief discussion using programming terminology

This work is theoretical but we still want it to be accessible to programmers who might implement it, so before we define prehistories (Definition 2.2.4) and history structures (Definition 2.3.5), we will present the idea of history structures as an inductive datatype in the style of functional programming. Then, we will explain why we do not just take that inductive datatype as our definition.

Intuitively, a history structure is a polymorphic datatype of finitely-branching trees labelled with uninterpreted types of places and events, along with a ‘descendent of’ relation on these trees.

We define this in Haskell style as follows:

import Data.Set as S data History p e = History p (Maybe e) (S.Set (History p e)) deriving (Eq,Ord) isDesc h (History p e l) = (S.member h l) || or (S.map (isDesc h) l) :t isDesc isDesc :: (Ord p, Ord e) => History p e -> History p e -> Bool

Each node of the tree is labelled by a place and a maybe-event, and it may have finitely many children in a set. Being a descendent of is defined (as usual) as the transitive closure of child-of.

This definition is short and clear, and it may be especially palatable to readers with a coding background (though perhaps less so to set theorists). A problem with this datatype is that it is highly redundant: many distinct trees in History p e correspond to the same intended history structure. Consider for example:

h0 = History 0 Nothing (S.empty) h1 = History 0 Nothing (S.singleton h0) h2 = History 0 Nothing (S.singleton h1) h2b = History 0 Nothing (S.fromList [h1,h0])

Then h2 and h2b are extensionally equal — they have the same descendants — but they are not intensionally identical — they are different elements of the datatype.

If we are doing mathematics, we deprecate such redundancy: for each thing in our intended domain, we want our mathematical model to contain a single element that represents that thing.19 Therefore we will now repeat the definitions in mathematical style.

The resulting Definitions 2.2.4 and 2.3.5 are more verbose, but the set representation has no redundancies and will be mathematically easier to work with.

If the reader does not mind redundancy (and perhaps is fluent in Haskell) then they can take the code above as primitive and little harm will come of it.

2.2. Prehistories

2.2.1. Finite subsets and maybe-sets.

We start with some basic notation:

Notation 2.2.1

Suppose X and Y are sets. Define X ⊆fin Y , read X is a finite subset of Y , by

X ⊆fin Y when X ⊆Y and X is finite.

Note that X may be empty, so ∅⊆fin Y always.

Notation 2.2.2

Suppose X is a set. Define X⸸, read maybe-X, by

Native X with turned-dagger subscript equals X union the singleton turned dagger; exactly7 source spans. Preserve both dagger roles and source size/position.X⸸= X ∪{⸸}

where ⸸ is an uninterpreted disjoint element ⸸∉X.

Remark 2.2.3

In mathematics, X⸸ is traditionally written X⊥ and the adjoined element is written ⊥. In programming, the set is typically written Maybe(X) and the adjoined element is Nothing. The intuition is the same: to provide a default value that is not already in X — e.g. for when we have a function and want it to (mostly) return values from X, but occasionally to return some non-X return value.

We use the symbol ⸸ because upside-down-T-like symbols are already well-represented in our text: we use ⊥ for meta-level logical false, and ⊥ for the false symbol in our logic (see Figure 3).

2.2.2. Definition of prehistories

Definition 2.2.4 (Prehistories).

Assume Pnt a nonempty set of places — we may synonymously call these points or participants — and Event a disjoint set of events.20

Let PreHistory(Pnt, Event), the set of prehistories over Pnt and Event, be the least set closed under the following rule:

H ⊆fin Pnt × Event⸸× PreHistory(Pnt, Event) H ∈PreHistory(Pnt, Event)

In words:

Any finite (possibly empty) set of place-(maybe-event)-prehistory tuples, is a prehistory.

Example 2.2.5

Two prehistories are illustrated on the right-hand side of Figure 2. (These examples are also history structures, which we will define shortly.)

Definition 2.2.6

We need some definitions:

(1) Call a triple (p, x, H) ∈ Pnt × Event⸸× PreHistory(Pnt, Event), an event-tuple. Calling it a ‘maybe-event tuple’ would be more precise, but that is longer to say, so we may abbreviate it to just ‘event-tuple’.

(2) Given an event-tuple w = (p, x, H) ∈ Pnt × Event⸸× PreHistory(Pnt, Event), we define

place(w) = p event(w) = x and time(w) = H.

We call place(w) the place of w, event(w) its (maybe-)event, and time(w) its time.

(3) We may call a prehistory a time (as per the previous item).
For our purposes we will be most interested in histories, which are times that satisfy an additional well-formedness condition of being hereditarily transitive (Definition 2.3.5). However, we can already make a point here about prehistories, that if these are our notion of time then the only thing we will care about in that notion of time is that which has happened before.
This is so important that we will say it again: a prehistory is a set of events, so taking this as our notion of ‘time’ is to promise that all we care about of a time, is the set of events that happened before that time. See also Remark 2.3.7.

(4) If H and H′ are prehistories then write that H′ precedes H when H′ ⊆H. Note that this notion is non-strict, in the sense that H precedes itself.

(5) We may say that H knows of an event-tuple w = (p′, x′, H′) when w ∈H.

Remark 2.2.7

By the Kleene fixpoint theorem [Wik25] PreHistory(Pnt, Event) is characterised by

F(X) = fin(Pnt × Event⸸× X)PreHistory(Pnt, Event) = ⋃i∈N F i(∅),

and PreHistory(Pnt, Event) is the least set such that

PreHistory(Pnt, Event) = F(PreHistory(Pnt, Event)).

The restriction to finite powersets on the right-hand side is just to keep things simple; we plan to model finite runs of distributed algorithms, so finite subsets suffice. The mathematics would easily generalise: e.g. we would take countable or recursively enumerable subsets.

Prehistories are in some sense the fundamental structure of interest in this paper, but in this paper we will be interested in modelling full information protocols, which correspond to a structural restriction on prehistories which we discuss next (an explicit discussion of the correspondence is in Remark 2.3.4). If in future work we wish to generalise to partial-information protocols, it would suffice to just use prehistories.

2.3. History structures

2.3.1. Definition.

A history structure is just a hereditarily transitive prehistory. We give the relevant definitions:

Definition 2.3.1 (Element-of relation).

Suppose H, H′ ∈ PreHistory(Pnt, Event).

(1) Define H′ ≺−H by

H′ ≺−H when ∃p′ ∈Pnt, x′ ∈Event⸸.(p′, x′, H′) ∈H.

When H′ ≺−H we may call H′ an element of H. Intuitively, H′ ≺−H when H′ is the time of some event-tuple in H.

(2) Define H′ ⪯−H by

H′ ⪯−H when H′ ≺−H ∨H′ = H.

When H′ ⪯−H we may call H′ a non-strict element of H.

Definition 2.3.2

Call a prehistory H ∈ PreHistory(Pnt, Event) transitive when

H′ ≺−H =⇒H′ ⊊H or equivalently H′ ⪯−H =⇒H′ ⊆H.

In words: if H′ is a (strict/non-strict) element of H then H′ is a (strict/non-strict) subset of H.

Remark 2.3.3

Unpacking Definition 2.3.1(1), transitivity just means:

∀p′, x′, H′. ((p′, x′, H′) ∈H =⇒H′ ⊊H).

Strictness of the inclusion (i.e. that H′ ≠ H) follows from well-foundedness of the inductive definition of PreHistory in Definition 2.2.4, so that (p′, x′, H′) ∈H and H′ = H is impossible.21

We can sum this up in words with two equivalent slogans:

H is transitive when it is preceded (Definition 2.2.6(4)) by the time of every event-tuple that it contains.

Or, more compactly:

Transitive H is preceded by its elements.

Remark 2.3.4

Transitivity models an idea of full information: if H knows of an event (p′, x′, H′) in the sense of Definition 2.2.6(5) that (p′, x′, H′) ∈H, then H also knows of the full circumstances in which (p′, x′, H′) took place, namely H knows of every event-tuple in H′.

We do not expect a practical protocol to necessarily carry full information but mathematically, reasoning about a full information protocol lets us reason about what can be done. We can then reduce to exactly what things participants have to derive from their own memory and messages in order to make a given protocol work. Transitivity reflects this idealisation.22

Definition 2.3.5 (History structures).

Define History(Pnt, Event) the set of history structures

History(Pnt, Event) ⊆PreHistory(Pnt, Event)

to be the set of hereditarily transitive elements in PreHistory(Pnt, Event), by which we mean that this is the greatest set of prehistories such that

H ∈ History(Pnt, Event) implies H transitive ∧∀H′ ≺−H.(H′ ∈ History(Pnt, Event)).

Notation 2.3.6

Recall from Definition 2.2.6(3) that we call a prehistory a time. Henceforth, all times will be hereditarily transitive unless stated otherwise — i.e. all times are histories (Definition 2.3.5). Indeed, henceforth if the reader sees the symbol H then they can assume it is a history (not just a prehistory), unless stated otherwise.

This should always be clear from context.

Remark 2.3.7

The following observation might help the reader to parse the meaning of (pre)history structures from Definitions 2.2.4 and 2.3.5.

In an event-tuple p, x, H, the H is three things simultaneously:

— a full epsilon-structure of events preceding the event-tuple,

— now (i.e. the moment in time when the event ‘occurs’), and

— (for histories, by transitivity) a full record of what p knows at the time this event-tuple occurs.

These are all equated in the strong sense that they are literally equal. We can sum this up as follows:

H = the past (= a set of event-tuples) = now = what we know.

This ‘epistemic’ approach to time is novel, to the best of our knowledge.23 Clock-based notions of time represent time as a (possibly structured) timestamp [Lam78; SM94; RS96] (a number or a vector of numbers). Obviously, if time is a timestamp then we can talk about what has happened before that timestamp, or what an agent knows at that timestamp.

For our purposes this level of indirection is not needed. There are no timestamps. Time is simply that which has happened before.

p ⊢print(hello) p ⊢print(world) p ⊢exit(){(p, print(hello), ∅), (p, print(world), {(p, print(hello), ∅)}), (p, exit(), {(p, print(hello), ∅), (p, print(world), {(p, print(hello), ∅)})})}p ⊢print(hello) p ⊢print(world) p ⊢exit(){(p, print(hello), ∅), (p, print(world), ∅), (p, exit(), {(p, print(world), ∅), (p, print(hello), ∅)})} (a) Two history structuresPreH ={(p, print(hello), ∅), (p, print(world), {(p, print(hello), ∅)}), (p, print(!), {(p, print(world), {(p, print(hello), ∅)})}) (b) A prehistory that is transitive but not hereditarily so
Fig. 2: Illustrating (pre)history structures (Examples 2.2.5 and 2.3.8)

2.3.2. Discussion and examples

Example 2.3.8 (Illustrating history structures).

A history structure can be represented as a derivation tree, and we will use this representation because there are particularly convenient LaTeX packages for typesetting them.

Figure 2a presents two history structures. In the left column are derivation-tree style presentations, and in the right column are the corresponding history structures written out in full. We assume events print and exit and just one participant p. The two examples represent two sequencings of events print(hello), print(world), and exit().

In the first history:

— p sends hello to stdout (standard output) at time H0 = ∅,

— p sends world to stdout at time H1 = {(p, print(hello), H0)}, and then

— p stops at time H2 = {(p, print(hello), H0), (p, print(world), H1)}.

In the second history,

— p sends hello to stdout at time H0 = ∅,

— p sends world to stdout at the same time H0 = ∅, and then

— p stops at time H1 = {(p, print(hello), H0), (p, print(world), H0)}.

Obviously the derivation-tree presentation is more readable, but the sets definition is definitive and is what we use to do the mathematics.

Figure 2b presents a prehistory PreH (representing a printout of hello world!) which is transitive

— for every H ⪯− PreH we have H ⊆ PreH — but it is not hereditarily transitive, because it contains a prehistory that is non-transitive:

{(p, print(world), {(p, print(hello), ∅)})}

To see that this is not transitive, note that

{(p, print(hello), ∅)}≺−{(p, print(world), {(p, print(hello), ∅)})}

yet (p, print(hello), ∅) ∉{(p, print(world), {(p, print(hello), ∅)})}.
Example 2.3.9

Example 2.3.8 only involved one participant. What if we have more? We demonstrate this with a simple message-passing example. Assume two participants p and q, and two actions propose and accept which we will treat as 0-ary. Here are two example history structures in which p takes action propose() and q takes action accept(). We indicate participants with p ⊢ and q ⊢:

p ⊢propose() q ⊢accept()p ⊢propose(), q ⊢accept()

The difference is that in the left-hand history, q knows that p has proposed before it accepts; whereas in the right-hand history it does not. Here are the corresponding history structures in full: In the left-hand history:

— p proposes at time H0 = ∅.

— q accepts at time H1 = {(p, propose(), H0)}.

— The full history structure is H = {(q, accept(), H1), (p, propose(), H0)}.

In the right-hand history:

— p proposes at time H0 = ∅.

— q accepts at the same time H0.

— The full history structure is H = {(q, accept(), H0), (p, propose(), H0)}.

Finally, we illustrate a simple history where p proposes and then q learns that p has proposed:

p ⊢propose() q ⊢⸸

Here is the corresponding history structure written in full:

{(p, propose(), ∅), (q,⸸, {(p, propose(), ∅)})}

History structures are rich and complex, but structurally the examples above represent everything that can happen. The complexity just follows from scaling up.

2.3.3. Design alternatives: element-transitivity and posets.

2.3.3.1. Element-transitivity. An alternative notion of transitivity to Definition 2.3.2 is possible, but it is not to be mistaken for Definition 2.3.2 because it is strictly weaker (and will be too weak for our needs):

Definition 2.3.10

Call a prehistory H ∈ PreHistory(Pnt, Event) element-transitive when for every H′, H′′ ∈ History(Pnt, Event), H′′ ≺−H′ ∧H′ ≺−H implies H′′ ≺−H.

Lemma 2.3.11

Suppose H ∈ PreHistory(Pnt, Event). Then:

(1) If H is transitive (Definition 2.3.2) then it is element-transitive (Definition 2.3.10).

(2) The reverse implication need not hold: it is possible for H to be element-transitive but not transitive.

Proof

We consider each part in turn:

(1) Suppose H′′ ≺−H′ ≺−H. Then H′ ⊆H by Definition 2.3.2 (transitivity of H). The reader can check from Definition 2.3.1(1) that H′′ ≺−H′ ⊆H implies H′′ ≺−H, so we are done.

(2) It suffices to provide a counterexample. Take Pnt = {p, q} (so there are two participants) and Event = ∅ (so the only maybe-event is ⸸):

H1 and H2 counterexample, with native derivation treesH1 = {(p,⸸, ∅)}H2 = {(p,⸸, H1), (q,⸸, ∅)}or in derivation tree stylep ⊢⸸p ⊢⸸q ⊢⸸

Then H2 is trivially element-transitive and H1 ≺−H2, yet H1 ⊈H2.End of proof

2.3.3.2. Posets. The reader might look at history structures, defined as hereditarily transitive prehistories in Definition 2.3.5, and think that these are really just posets decorated with sets of place-maybe-event tuples, as follows: given H, consider the poset given by (Time(H), ⪯−) and a decoration function δ(H) = {(p, x) | (p, x, H) ∈H}.

Unfortunately, this translation is lossy and thus does not work. The poset presentation fails to distinguish between the following two history structures:

p ⊢E p ⊢E p ⊢Fandp ⊢F p ⊢E p ⊢E

end of time end of time These both correspond to a three-element linear decorated poset which we can write as follows:

{(p, E), (p, F)} ≤{(p, E)} ≤{}.

We can obtain a lossless poset presentation of a history structures H by considering its maybe-event-tuples partially ordered by the reflexive closure of (p′, x′, H′) < (p, x, H) when (p′, x′, H′) ∈H — this is essentially the accessibility relation ≪ from Definition 3.4.2(3).

2.3.4. Discussion of nothing: ⸸.

2.3.4.1. The end of time, and minimal and maximal event-tuples. Discussing nothing requires us to build a little bit of machinery:24

Definition 2.3.12

Fix H ∈ History(Pnt, Event). Then:

(1) We may call H the end of time in H, because every H ≺−H precedes it (Definition 2.2.6(4)) by transitivity (Definition 2.3.2).

(2) Call an event-tuple (p, x, H) ∈H minimal/p-minimal when H in H is ≺−-minimal / ≺−-minimal among tuples starting with p.

(3) Call an event-tuple (p, x, H) ∈H maximal/p-maximal when H in H is ≺−-maximal / ≺−-maximal among tuples starting with p.

Remark 2.3.13

Minimal and maximal event-tuples need not exist (the empty history H = ∅ has neither), and if they exist they need not be unique (the right-hand history in Example 2.3.9 has two of each).

Note that if (p, E, H) ∈H then H = H is impossible, so the end of time cannot be the time of an event-tuple in H, and in particular H is never the time of a final event-tuple.

2.3.4.2. The problem: final event-tuples. Why do we use Event⸸ to build (pre)history structures in Definitions 2.2.4 and 2.3.5, instead of just Event? This is motivated by the design of the Knowledge axiom-schemes (Knowledge♢↓) and (Knowledge□↓) in the theory of liveness ThyLive in Figure 7.

We will discuss these axioms in detail in Subsection 5.2. What matters here is that they express that live participants communicate information to one another: if a live participant p performs some event E, then eventually every other live participant p′ will know that E occurred (the precise statement is in Figure 7; here we are speaking intuitively).

The technical difficulty is how we record that p′ learns about E having happened. If our notion of history is only mapped out in terms of event-tuples — i.e. if H consists only of triples (p, E, H) where E ∈ Event — then p′ learning that E has taken place is itself an event, which (between live participants) itself must be communicated. This seems unintuitive, and it may lead to an infinite regress.

2.3.4.3. ⸸: the solution. Broadly speaking we have the following options:

(1) We can accept this: I did E; you learned that I did E (itself an event); I learned that you learned that I did E (itself another event), ... We have nothing against infinities but here this feels like a hack, because it does not correspond to how we think of distributed algorithms actually behaving.

(2) We can tweak the meaning of our temporal modalities, or perhaps tweak ThyLive.

(3) We can introduce ⸸ and maybe-events Event⸸ as defined above. This is what we do.

Thus we permit a triple (p,⸸, H) in a participant’s history. This ⸸-event-tuple does not record an event — in the technical sense that the event-tuple has ⸸ in its second entry, which is not in the set of events Event — but it does represent an H-update to the view that p has of history.

We can think of this as corresponding roughly to p receiving a message, e.g. as per a Lamport diagram [Lam78, Figure 1].25

Now suppose (p, E, H) is a final event-tuple in H. If we have ⸸, then the model can continue to evolve such that this event-tuple becomes known to another participant q, by adding a tuple (q,⸸, H ∪{(p, E, H)}). This use of a maybe-event can be read as representing q becoming aware of (p, E, H).

2.3.5. Further discussion of nothing

Remark 2.3.14 (⸸ viewed as a receive action).

We can think of ⸸ as a generalisation of the notion of a ‘receive’ action, as follows:

Let us view E ∈ Event as a broadcast event, so that (p, E, H) means ‘p broadcasts E at time H’. Then we can view ⸸ as a receive action, where (p′,⸸, H ∪{(p, E, H)}) is the event-tuple that records the time at which information arrives at p′ that (p, E, H) happened.

Note that, following this analogy, not every ‘receive’ action needs to be via ⸸. For instance, we can have (p, E, H) ∈H and also (p′, E′, H ∪{(p, E, H)}) ∈H. By our analogy, this corresponds to p broadcasting E and then p′ broadcasting E′ at the same time as it receives the broadcast from p.26

Nevertheless, ⸸ gives participants the option of updating their local history without making an event of this.

Note that this Remark is just an analogy: history structures, events, and ⸸ are their own thing.

Remark 2.3.15 (⸸ viewed as an ϵ transition).

Automata theory has a notion of an automaton making silent or internal transitions. Traditionally these are called ϵ-transitions [HMU07, Subsection 2.5, “Finite Automata With Epsilon-Transitions”].

The traditional reading of this is an internal state change that does not involve interaction with the environment.

A difficulty with interpreting ⸸ as a receive action, as we do in Remark 2.3.14, is that there is no restriction on an event-tuple (p,⸸, H) that H should contain information that is somewhere in the rest of some larger history for p to ‘receive’. H could be arbitrary.

In this sense, it also makes sense to think of ⸸ simply as an internal transition of p, more akin to the automata-theoretic ϵ action.

Yet ⸸ is not just a silent internal action without interaction with the environment, because H could also contain information that is in the rest of some larger history, e.g. when we interpret it as a receive action. So we repeat the final line of Remark 2.3.14: history structures, events, and ⸸ are their own thing.

Remark 2.3.16 (⸸ viewed as an attestation).

Perhaps a better way to think of ⸸ is as marking a pure attestation: when (p,⸸, H) ∈H this means that p attests to knowing of time H and the information encoded therein.

Of course (p, E, H) ∈H also means that p attests to knowing of H, but that happens in the sense that an event E occurs at p at time H. In contrast, (p,⸸, H) is a pure attestation; p might have received the information that the time H exists from the environment, or p might have computed the time H internally. In this sense, ⸸ generalises both receive and ϵ: it represents the act of attesting to some internal state change of knowledge, and in our model, knowledge and time are the same thing.

Remark 2.3.17

It is perfectly feasible to have

(p, E, H) ∈H and also (p,⸸, H ∪{(p, E, H)}) ∈H.

For instance, this is a valid history structure:27

H = {(p, E, ∅), (p,⸸, {(p, E, ∅)})}.

In derivation tree style (and bearing in mind that there is only one participant) we can illustrate it as follows:

Native E-over-turned-dagger derivation tree with one native horizontal rule; separate from following prose.E⸸

We could even replace E with ⸸ above, to obtain this:

Native turned-dagger-over-turned-dagger tree with one native horizontal rule; separate from preceding/following prose.⸸⸸

With respect to the encoding of natural numbers in Remark 2.3.18 below, this is the natural encoding of the number 2.

It is surprisingly interesting to look at a history structure with no events. Thus, the only maybe-event possible is ⸸ itself:

Remark 2.3.18

Consider history structures with no events and only one participant, so that

Native three-part display Event=emptyset and Event with turned-dagger subscript=singleton turned dagger and Pnt={p}; preserve shared horizontal baseline and both dagger roles.Event = ∅ and Event⸸= {⸸} and Pnt = {p}.

Then the definitions simplify up to isomorphism as follows:

— PreHistory is a least fixedpoint under the rule

H ⊆fin PreHistory H ∈PreHistory

— History is the set of hereditarily transitive prehistories.

This simplifies to:

∅∈History H ∈History =⇒H ∪{(p,⸸, H)} ∈History.

The reader might recognise this as essentially identical to the construction of finite von Neumann ordinals:

0 = ∅ n + 1 = n ∪{n}.

This is the standard von Neumann construction of the natural numbers in set theory, which has the nice property that a number n is represented as the set of representations of numbers less than n [Dev93, Figure 7.2].

We can take this coincidence seriously and view history structures as a generalisation of the finite von Neumann ordinals, extending them with concurrency (given by letting Pnt contain multiple participants) and with events (given by letting Event be nonempty). Thus we can view histories as concurrent numbers, where the mapping

(p, x, H)↦ −→ (p,⸸, H ∪{(p, x, H)})

corresponds to the mapping n↦ →n ∪{n} used above to define n+1. In this sense, we can loosely identify ⸸ with the successor operation.

Conversely, von Neumann ordinals are obtained from History structures as the special case where there is just one participant, and only the one maybe-event ⸸.28

Remark 2.3.19 (Taking stock).

We will use the following mathematical machinery:

— History structures from Section 2 give us a notion of events happening in time and at places, where (p, E, H) ∈H is interpreted as ‘event E happens at place p at time H’.

— Semifilters from Subsection 3.3.1 will give us the notion of quorum which is fundamental to many distributed algorithms, including broadcast algorithms of the type we will study here.

Mathematically, this is all the machinery we need. In Section 3 we will combine history structures with semifilters to define the syntax and semantics of a logic for reasoning about heterogeneous broadcast algorithms.

3. LOGIC OVER HISTORY STRUCTURES

3.1. Syntax

Definition 3.1.1

(1) A signature Σ is a tuple

Σ = (VSym, ESym, PSym, Value)

of disjoint sets of variable symbols, event symbols, predicate symbols, and values. We assume that VSym is countably infinite and that Value is nonempty (so there are many variable symbols and at least one value). For reasons discussed in Remark 3.3.8, we may write Value synonymously as Learner. These are different concepts but we use a single set to represent both.29

(2) We define sets of events and atomic predicates over Σ by:

Event(Σ) = {E(v1, . . . , vn) | E ∈ESym, n ≥0, v1, . . . , vn ∈Value} AtmPred(Σ) = {P(v1, . . . , vn) | P ∈PSym, n ≥0, v1, . . . , vn ∈Value}
t ::= (a ∈VSym) | (v ∈Value) ϕ ::= ⊥| ϕ ⇒ϕ | t=t | ∀a.ϕ | E(t, . . . , t) | P(t, . . . , t) | ↓ϕ |⤒→ϕ | ♢t...tϕ | seq Above: E ∈ESym and P ∈PSym; and n ≥0 is any nonnegative integer; and the multiple ‘t’ in t=t and P(t, . . . , t) and ♢t...tϕ represent multiple (possibly distinct) terms; and the two ‘ϕ’ in ϕ ⇒ϕ represent two (possibly distinct) predicates.
Fig. 3: Syntax of predicates (Definition 3.1.3)
Notation 3.1.2

We do not impose an arity or sort system on our syntax, so if P ∈ PSym then P(), P(v), and P(v1, v2), are all valid syntax, and similarly for E ∈ ESym.

In practice we will use each event and predicate symbol with a consistent arity (= number of arguments). In the 0-ary case we may elide the empty brackets, writing P() just as P. For instance, we do this with live in our theory of liveness in Figure 7.

Definition 3.1.3

Suppose Σ is a signature.

(1) We define the syntax of terms t and predicates ϕ over Σ by the grammar in Figure 3.

(2) By convention the modal operators ↓ϕ,⤒→ϕ, and ♢t1...tn ϕ have higher precedence than ⇒, so that for example ↓ϕ ⇒ψ brackets as (↓ϕ) ⇒ψ. Also by convention the quantifier ∀a.ϕ binds as far to the right as possible, so that for example ∀a.↓ϕ ⇒ψ brackets as ∀a.((↓ϕ) ⇒ψ). That said, we may use whitespace rather than brackets for clarity, so that for example ∀a.ϕ ⇒ψ brackets as (∀a.ϕ) ⇒ψ. Meaning will always be clear, and where there is any danger of confusion we may insert brackets, even if this is not required according to our conventions.

(3) A closed predicate is one with no free variable symbols. It can still mention values; so if a ∈ VSym and v ∈ Value then a=v is not closed, and ∃a.a=v is closed.

Remark 3.1.4

We read the predicates in Figure 3 as follows:

— ⊥ is false, ⇒ is implies, and ∀ is for all, as usual.

— t=t′ is equality; the equality holds when t and t′ denote equal values.

— E(t1, . . . , tn) is an event and P(t1, . . . , tn) is an atomic predicate. Both events and atomic predicates are predicates in our logical syntax (but an event is not an atomic predicate, nor vice-versa). This is intuitively justified because E(t1, . . . , tn)-the-predicate will assert that E(t1, . . . , tn) happens.30 Events and atomic predicates are syntactically similar, but they have different meanings in the denotation. Events are handled by a history structure, whereas predicates are handled by an interpretation. See the rules for interpreting w ⊨E and w ⊨P in Figure 4.

— We read ↓ as at the time of some strictly preceding event or just in the past; and

— We read⤒→ϕ as ϕ at the end of time.

— We read ♢l1...ln ϕ as someone in every l1. . . ln-quorum intersection has ϕ or l1. . . ln-quorum intersections admit ϕ (cf. Remark 3.6.3(7)); and

— seq as sequential (we define and study what this means in Definition 3.4.9 and Subsection 5.1). The above are intuitions; they will be made formal in the denotation in Figure 4.

3.2. Example predicates, and their intended meanings

In Figure 4 we will build a notion (in fact, three notions) of logical validity; and in Figures 5 and 6 we will extend our syntax with useful macros (syntactic sugar).

However, even before we do that, we can use the syntax from Figure 3 to show how some properties of interest to distributed systems can be expressed. We assume an event symbol echo ∈ ESym and an atomic predicate symbol live ∈ PSym:

(1) echo(hello world). We echo ‘hello world’. Note that the logic does not know what ‘echo’ means; this is just an abstract event.

(2) live(). Here and now, we are live. We abbreviate empty brackets to nothing, so a 0-ary use of a predicate symbol may be written just as live in the maths that follows. Note that the logic does not know what ‘live’ means; but we will develop an axiomatisation of liveness in Figure 7.

(3) seq. Up until now, we have been sequential (performed actions in linear order).

(4) ⤒→seq. At the end of time we have been sequential. In plain English: we are sequential forever.

(5) ↓echo(hello world). We have echoed ‘hello world’ in the past.

(6) ⤒→↓echo(hello world). By the end of time in the past we will have echoed ‘hello world’. Or in more colloquial English: we echo ‘hello world’ sometime.

(7) ♢⤒→↓echo(hello world) and⤒→♢↓echo(hello world) These mean: somewhere sometime a participant echoes ‘hello world’; and at the end of time somewhere a participant has echoed ‘hello world’. As it happens, one is valid in a model if and only if the other is, so these are equivalent in that sense. (More generally, ♢ and⤒→commute in the sense that ♢⤒→ϕ and⤒→♢ϕ will always be assigned the same truth-value.)

(8) ♢ll′ ⊤. Every l-quorum intersects every l′-quorum. What l- and l′-quorums are will be explained in Subsection 3.3.1; think of them as trust assumptions, and see Lemma 4.1.1.

(9) ♢ll′ seq. Every l-quorum intersects every l′-quorum at a sequential participant (again, see Lemma 4.1.1).

(10) ♢ll seq. We take l = l′ in the previous example, so: every pair of l-quorums intersects at a sequential participant.

(11) ♢live, and ¬♢¬live. Some participant is live, and every participant is live, respectively.

(12) ⤒→∀v.♢↓echo(v). By the end of time, for every value there is a participant who echoed v in the past. Or in plain English: every value is eventually echoed by some participant.

(13) echo(world) ⇒↓echo(hello). If we echo ‘world’, then we must have echoed ‘hello’ in the past.

(14) echo(hello) ⇒⤒→↓echo(world). If we echo ‘hello’, then we must echo ‘world’ at some time (though we do not say precisely when).

(15) ♢seq, ♢l seq, ♢ll′ seq, and ♢lll seq.

Respectively these mean: some participant is sequential; every l-quorum contains a sequential participant; the intersection of every pair of l- and l′-quorums contains a sequential participant; and any three l-quorums intersect at a sequential participant. Sequentiality is from Definition 3.4.9. Intuitively, a participant is sequential when it does not equivocate (= report incompatible histories to different participants). This will be an important well-behavedness property for our proofs.

We hope this gives the reader some initial feeling for how the syntax in Figure 3 can be used. We are now ready to build models and use these to give the logic a formal notion of validity.

3.3. Models

3.3.1. Semifilters.

We need a technical notion to build our models: semitopologies are a mathematical generalisation of the notion of quorum system typically used in distributed systems [Gab24; Gab25]. We do not need the full machinery of semitopologies in this paper but it is convenient to import a useful notation ≬, and the notion of a semifilter.

Notation 3.3.1

Suppose O and O′ are sets. Define O ≬O′ [Gab24; Gab25, Notation 3.1.1] by

O ≬O′when O ∩O′ ≠ ∅.

In this case we say that O intersects O′.

Definition 3.3.2

Suppose Pnt is a set of points. A semifilter L on Pnt [Gab24, Definition 13.1.1(5)] is a nonempty up-closed set of pairwise intersecting nonempty subsets of Pnt. Spelling this out:

(1) Nonempty subsets ∅≠ L ⊆ pow(Pnt).

(2) Up-closed If O ∈L and O ⊆O′ ⊆ Pnt, then O′ ∈L.

(3) Pairwise intersecting If O, O′ ∈L then O ≬O′. Nonemptiness of the subsets follows as the special case that O ∈L must intersect itself.

Semifilters are essentially just the notion of quorum system from [Mal99; MR97]. Page 1 of [Mal99] says (in edited form) that: a quorum system is a set of pairwise intersecting subsets of some universe of servers. The essential difference between this and [Gab24, Definition 13.1.1(5)] is just that the latter identifies the former as a topological concept corresponding to the notion of abstract point in topology.31

This logic-and-topology view of quorum systems helped us to design our logic here — but if every time we write semifilter, the reader reads quorum system, then no harm will come of it.

Write SemiFilter(Pnt) for the set of semifilters on Pnt. Thus:

SemiFilter(Pnt) = {L ⊆ pow(Pnt) | L is a semifilter}.

If L is a semifilter then we might call O ∈L an open set or a quorum.

3.3.2. Definition of models

Definition 3.3.3

Suppose Σ = (VSym, ESym, PSym, Value) is a signature. Then a model M for Σ is a tuple

M = (Pnt, H, ϱ, ς)

where:

(1) Pnt is a nonempty set of participants; we may also call these points or places.

(2) H ∈ History(Pnt, Event(Σ)) is a history structure (Definition 2.3.5). Following Definition 2.3.12, we may call H the end of time in M, because it represents a time at which all events in the model are in the past.

(3) ϱ is a (predicate) interpretation, such that

ϱ(p, H) ⊆AtmPred(Σ)

for every p ∈ Pnt and H ⪯−H. Intuitively, ϱ(p, H) decides which atomic predicates are true at place p and at time H (we make this formal in the clause for w ⊨ P(v1, . . . , vn) in Figure 4).

(4) ς is a learner interpretation which assigns a semifilter to each value, so it is such that

ς(v) ∈SemiFilter(Pnt)

for every v ∈ Value. We might write l for values when we intend that they be interpreted using ς. Intuitively, ς assigns a semifilter (Definition 3.3.2; a set of quorums) to each value. We use this in the clause for ♢l1...ln in Figure 4.

Remark 3.3.4 (Comments on Definition 3.3.3).

(1) How is an atomic predicate different from an event? Syntactically, an atomic predicate P(v1, . . . , vn) looks very much like an event E(v1, . . . , vn). A difference is that events happen at times H ≺−H, whereas atomic predicates are assigned truth-values at times that are not necessarily times of events. This difference is real, e.g. by construction no event can happen at the end of time H, but it is important that predicates can be true or false there, e.g. so that we can state correctness properties which may regard all events and so naturally exist at the end of time.
The flexibility here is deliberate — e.g. our judgement form ⊨ϕ in Figure 4 explicitly uses the end of time H, which intuitively is a time when all events have already happened, so no events should occur at H, but we will still make logical assertions.

(2) What is a learner? Technically we identify learners with values, but this is just a convenience. The definition to look at to understand what ‘learner’ means is Definition 3.3.3(4), which indicates that ‘learner’ = ‘semifilter on participants’, where (as per Definition 3.3.2) a semifilter is a set of quorums. A quorum is a specific notion in distributed systems. We will not go into an abstract discussion of what that is here — for that, the interested reader is referred to [Gab24; Gab25]) — but some examples will give the idea:

— In a voting system, a quorum is a proportion of votes sufficient to carry a motion (e.g. ‘more than half’, ‘more than two thirds’, or some more complex system e.g. involving weights). So the ‘learner’ in a voting system is the set of all sets of participants with enough voting power to win the vote.

— In a ‘Proof-of-Stake’ blockchain like Ethereum, a quorum is any majority proportion of the current tokens, so the ‘learner’ is the set of all sets of participants such that if they agree on a transaction, then that transaction is final (i.e. committed irreversibly to the blockchain).

— In a Maekawa-style grid protocol for a database, participants are arranged on a grid, and a quorum is any set that includes a full row and a full column (because any two quorums must intersect), so the ‘learner’ is the set of subsets of the grid that included a full row and a full column.

— In Ethereum and Tezos (two proof-of-stake blockchains) bridged by a bridging node , a quorum consists of any set that includes a quorum of Ethereum, a quorum of Tezos, and the bridging node, so intuitively the ‘learner’ is the set of all pairs of quorums from the respective systems plus the bridging node — a set of nodes is in the learner when it represents an Ethereum quorum that could agree with a bridging node that they have sent some tokens to Tezos, and a Tezos quorum that could agree with the bridging node that they have received it.

Here a bridging node is a machine that, as a service and for a fee, will organise token transfers across blockchains by creating agreement across a pair of quorums as described above — a middleman, in other words, who transacts with party A and party C to attain the effect of some trade between them. Intuitively, a ‘learner’ is not a participant in the system, it is in some sense an observer, making decisions based on observing sets of participants in that system, as in our voting example above: we observe a vote and when we observe a quorum of votes for a motion, we learn that this motion has been passed. Moving back from intuitions to mathematical definitions, mathematically, a learner is just a semifilter. We will use these semifilters in our logical theories, to represent within our declarative axiomatic framework a powerful abstraction of the examples given above.

Example 3.3.5 (Empty model).

Arguably the simplest possible model takes H = ∅. So we have sets of participants and events and all the structure of a model, but there are no events; nothing happens.

We call ∅ the empty history and a model with the empty history an empty model.

If H ≠ ∅ then we call the history structure nonempty. If a model has a nonempty history structure then we call it a nonempty model.

Looking forward to Definition 3.5.1 ((in)active participants) a model is nonempty precisely when it contains some active participant, and empty when all of its participants are inactive.

Example 3.3.6 (The minimal nonempty model).

Following on from the empty model in Example 3.3.5, what is the smallest model in which all participants do something, i.e. in which at least one event-tuple is associated to each participant? Perhaps surprisingly, there is a canonical such. Define:

(1) Pnt = {p} (there is precisely one participant).

(2) Event = ∅.

(3) H = {(p,⸸, ∅)}.

(4) ϱ(p, ∅) = ∅ and ϱ(p, H) = ∅ and ς(v) = {Pnt} for every value.

Although this example looks simple, it captures much of the essential structure of a model. Other complexity is just a matter of extending this core.32

3.3.3. Discussion of models

Notation 3.3.7

A model will always be written M and the history structure of that model will always be written H, so we might not always spell out that H belongs to M.

If the reader does not like this, they can read ‘HM’ every time they see ‘H’, and their understanding will be precisely correct.

Remark 3.3.8 (Values as learners).

ς maps values to semifilters. In effect, this allows us to use elements v ∈ Value to represent value and learners. In places where we intend a value to denote a learner, we may write that value as l (rather than as v); see for example ♢l1...ln ϕ in Figure 4. We may abuse notation and write

Learner = Value.

So l ∈ Learner has the same semantic meaning as v ∈ Value; the difference is just how we intend this value to be used.

If the reader does not like this, the reader is welcome to mentally distinguish the two sets as disjoint sets of learners and values. The price we would then pay is just notational: we need two kinds of variable (one to range over learners, one to range over values), and two kinds of quantification (one for each kind of variable).

Indeed, we could introduce a sort system, and give event symbols and atomic predicate symbols arities, and maybe then extend to a full typing system. For a practical implementation we might require this apparatus, but it would not change the essential character of the mathematics. For an initial syntax in this paper, it suffices to take a single set and use it to denote values or learners as convenient.

Remark 3.3.9

As we have set things up, learners are represented in the model via the learner interpretation ς in Definition 3.3.3(4), which maps values (thought of as learners) to semifilters.

This is arguably counterintuitive: surely learners should be participants in the model? In practice, the only thing we care about of a learner is its semifilter of quorums. We could certainly include learners as participants, but for our axioms and our correctness properties, this is not required.33 So we do not bother.

3.4. The Kripke semantics associated to a model, and validity

Remark 3.4.1 (Kripke structures).

Our logical syntax from Figure 3 is overtly modal, in the sense of modal logic [BdRV01; Gar24]: we have symbols ↓,⤒→, and ♢ which look like modalities, and we have even called them ‘modalities’. Modal logic has a standard semantics in terms of Kripke structures (also called relational semantics). A typical Kripke structure consists of a set of possible worlds and an accessibility relation on worlds.

Modal validity is per-world, by which we mean that each predicate is valid or invalid at a possible world. The intuition is that the validity of some assertions naturally depends on where and/or when we make them, e.g. ‘it is raining’ may be valid in some places and times and not in others, so this is best understood as a modal judgement, as in e.g. ‘here ⊨ it is raining’.

Definition 3.3.3 gives us a notion of what we call a model M. We called M ‘a model’ but really it is just a tuple; for it to behave like a model, we need to use it to build a notion of logical validity. In this Subsection we will do that. We will extract from M:

— a Kripke-style semantics (possible worlds World(M) and an accessibility relation ≪), in Definition 3.4.2; and

— three modal notions of validity with respect to that semantics, in Definition 3.4.10 and Figure 4 (why we need three notions of validity will become clear).

3.4.1. Kripke (relational) semantics

Definition 3.4.2 (Kripke-style semantics).

Suppose M = (Pnt, H, ϱ, ς) is a model.

(1) Define Time(M) the set of possible times by

Time(M) = {H | H ⪯−H}.

(⪯− is from Definition 2.3.1(2); H ⪯−H means either H = H or (p, x, H) ∈H for some p and x.) Intuitively, the set of possible times of a model is: the set of all the times of events that occur in the model, plus H the end of time itself.

(2) Define World(M) the set of possible worlds by

World(M) = Pnt × Event⸸× Time(M).

We will write w, w′ ∈ World(M); so w and w′ will range over possible worlds.

(3) Define an accessibility relation ≪ on possible worlds such that for (p, x, H), (p′, x′, H′) ∈ World(M),

(p′, x′, H′) ≪(p, x, H) when (p′, x′, H′) ∈H.

Equivalently writing w′ = (p′, x′, H′) and w = (p, x, H) and using time(w) from Definition 2.2.6(2),

w′ ≪w when w′ ∈time(w).

For convenient reference, we mention here that ≪ will be transitive and irreflexive: see Proposition 3.4.5.

(4) Define an in-place accessibility relation ≪− such that for (p, x, H), (p′, x′, H′) ∈ World(M),

(p′, x′, H′) ≪−(p, x, H) when (p′, x′, H′) ∈H ∧p′ = p.

Equivalently using Definition 2.2.6(2),

w′ ≪−w when w′ ∈time(w) ∧place(w′) = place(w).
Lemma 3.4.3

Suppose M is a model and w′, w ∈ World(M). Then

w′ ≪w implies time(w′) ≺−time(w) ∧time(w′) ⊊time(w).
Proof

Suppose w′ ≪w. By Definition 3.4.2(3) w′ ∈ time(w). By assumption time(w) ≺−H or time(w) = H; in either case, time(w) is a history structure. By Definition 2.3.1(1) (since w′ ∈ time(w)) time(w′) ≺− time(w), and by Definition 2.3.2 and Remark 2.3.3 time(w′) ⊊ time(w).End of proof

Lemma 3.4.4 is a correctness check that we can set Time(M) = {H | H⪯−H} in Definition 3.4.2(1), rather than {H | H ⪯−∗H}, where ⪯−∗ denotes the transitive closure of ⪯−:

Lemma 3.4.4

Suppose M is a model and w, w′ ∈ World(M). Then

w′ ≪w implies time(w′) ≺−H.
Proof

By Definition 3.4.2(2) time(w)⪯−H, so by transitivity of histories (Definitions 2.3.2 and 2.3.5) time(w) ⊆H. By Definition 3.4.2(3) w′ ∈ time(w), thus w′ ∈H. By Definitions 2.3.1(1) and 2.2.6(2) time(w′) ≺−H as required.End of proof

Proposition 3.4.5 (Transitivity and irreflexivity of accessibility).

Suppose M = (Pnt, H, ϱ, ς) is a model. Then the accessibility relation ≪ from Definition 3.4.2(3) is transitive and irreflexive. That is:

∀w, w′, w′′ ∈World(M). w′′ ≪w′ =⇒w′ ≪w =⇒w′′ ≪w

and

∀w ∈World(M). ¬(w ≪w).
Proof

Suppose w′′ ≪w′ and w′ ≪w. By Definition 3.4.2(3) w′′ ∈ time(w′) and by Lemma 3.4.3 time(w′) ⊊ time(w), so w′′ ∈ time(w). By Definition 3.4.2(3) again w′′ ≪w as required.

Irreflexivity is a simple corollary of Lemma 3.4.3, since time(w) ⊊ time(w) is impossible.End of proof

3.4.2. Sequentiality

Remark 3.4.6

We need the notion of sequentiality for Figure 4, to interpret the proposition seq. Intuitively, p is sequential in H when p performs its actions in sequence, according to H. Sequentiality will be important to our later mathematics because, for our needs, sequential participants will be the ‘good’ ones. In Remark 5.1.6 we will note a more abstract but more permissive orderability condition that would also suffice for our needs.

A technical definition will help us define sequentiality in Definition 3.4.9:

Definition 3.4.7

Suppose p ∈ Pnt and H ∈ Time(M). Define H@p the history H at p or set of event-tuples at p by

H@p = {w ∈H | place(w) = p}.
Remark 3.4.8

Note that:

(1) H@p is a prehistory but it need not be a history, because it might not be transitive (Definition 2.3.2) (this will not be a problem; we will only ever use it as a set).

(2) Recalling from Definition 3.4.2(3) that

w′ ≪w when w′ ∈time(w),

a nice characterisation of w′ ≪−w from Definition 3.4.2(4) is

w′ ≪−w if and only if w′ ∈time(w)@place(w).
false w ⊨⊥ ⇐⇒⊥implies w ⊨ϕ ⇒ϕ′⇐⇒(w ⊨ϕ ⟹⇒w ⊨ϕ′)equality w ⊨v=v ⇐⇒⊤inequality w ⊨v=v′⇐⇒⊥ (v′ not equal to v)forall w ⊨∀a.ϕ ⇐⇒∀v∈Value.(w ⊨ϕ[a:=v])event p, x, H ⊨E ⇐⇒(x = E ∧(p, E, H) ∈H)atomic predicate p, x, H ⊨P ⇐⇒P ∈ϱ(p, H)in the past w ⊨↓ϕ ⇐⇒∃w′ ≪−w. (w′ ⊨ϕ)end of time p, x, H ⊨⤒→ϕ ⇐⇒p,⸸, H ⊨ϕadmission p, x, H ⊨♢l1...ln ϕ ⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃p′ ∈O1 ∩· · · ∩On. (p′,⸸, H ⊨ϕ)sequentiality p, x, H ⊨seq ⇐⇒p sequential at Hvalidity (end-of-time) ⊨ϕ ⇐⇒∀p ∈Pnt. (p,⸸, H ⊨ϕ)validity (all-world) □W ⊨ϕ ⇐⇒∀w ∈World(M). (w ⊨ϕ)Above: — We assume a fixed signature Σ = (VSym, ESym, PSym, Value) (Definition 3.1.1) and model M = (Pnt, H, ϱ, ς) (Definition 3.3.3) for that signature. — w ∈World(M) is a world (Definition 3.4.2(2)). — p ∈Pnt is a participant, and E / P is an event / atomic predicate in the sense of Definition 3.1.1(2), i.e. E = E(v1, . . . , vn) / P = P(v1, . . . , vn) for some v1, . . . , vn ∈Value (and for some n). — w′ ≪−w is from Definition 3.4.2(4) and means w′ ∈time(w) ∧place(w′) = place(w). — p being sequential at H is from Definition 3.4.9 (see also Lemma 5.1.2). — The italic text in the leftmost column (‘false’, ‘implies’, etc) is just a reminder of how to read the connective. It has no formal meaning; it is just a useful hint. The terminology ‘admission’ for ♢is put in context in Remark 3.6.3. — In the first line, ⊥on the left represents the formal symbol from our predicate syntax in Figure 3 (object-level), and ⊥on the right represents logical false (meta-level). In the next line, ⇒is an object-level symbol and ⟹⇒is meta-level implication. Similarly for = and =, for ∀and ∀, and so on.
Fig. 4: Validity (Definition 3.4.10)
Definition 3.4.9 (Sequentiality).

Suppose p ∈ Pnt and H ∈ Time(M).

(1) Call p sequential at H when

∀w, w′ ∈H@p.(w ≪w′ ∨w′ ≪w ∨w = w′).

In words: p is sequential in H when event-tuples at p occur in sequence in H.

(2) Call H sequential when

∀w, w′ ∈H.(w ≪w′ ∨w′ ≪w ∨w = w′)

In words: H is sequential when event-tuples in H occur in sequence.

3.4.3. Validity

Definition 3.4.10 (Validity).

Suppose M is a model and w ∈ World(M) D3.4.2(2)= Pnt × Event⸸× Time(M) and ϕ is a closed predicate. Then we define three validity judgements as follows:

(1) Define possible world validity

w ⊨ϕ

inductively by the rules in Figure 4. Write w = (p, x, H). In the judgement “p, x, H ⊨ϕ”, we may follow Definition 2.2.6(2) and call p the place, x the (maybe-)event, and H the time of the judgement.

(2) Define omniscient or end-of-time validity by

⊨ϕ when p,⸸, H ⊨ϕ for every p ∈ Pnt.

(3) Define all-world validity by

□W ⊨ϕ when w ⊨ϕ for every w ∈ World(M).

Where we write just ‘validity’, it will always be clear which kind of validity we refer to. When we write w ⊨ϕ, ⊨ϕ, or □W ⊨ϕ, it will always be clear (or unimportant) with respect to which model we intend this.

Remark 3.4.11 (Validity and time).

The treatments of validity and time in the judgement w ⊨ϕ from Definition 3.4.10 and Figure 4 are subtle. We make some observations:

(1) Possible world validity w ⊨ϕ is a standard-looking modal validity judgement that ϕ is valid (or is not valid) at the possible world w ∈ World(M). However, Figure 4 defines two more validity judgements: end-of-time validity ⊨ϕ and all-world validity □W ⊨ϕ. We discuss and contrast these in Subsection 5.2. Briefly: we use □W ⊨ϕ to impose axioms on a model, and ⊨ϕ to assert correctness properties that look retrospectively back on the model as viewed from the end of time.

(2) In w ⊨ϕ, note that:

— w has the form (p, x, H) for any p ∈ Pnt and x ∈ Event⸸ and H ≺−H ∨H = H.

— We do not make the stricter requirement that w ∈H. That is, w does not have to be an event-tuple that actually occurs in H: this could be because H = H, or because x is a maybe-event such that (p, x, H) ∉H (even though perhaps (p, x′, H) ∈H for some other choice of x′ ∈ Event⸸).34

This is deliberate: the⤒→modality takes us to the end of time, where by definition no events occur, so for the validity judgement ⊨ϕ (meaning p,⸸, H ⊨ϕ for every p) to make sense, we need to consider possible worlds other than just those in H. Similarly when we interpret w ⊨♢l1...ln ϕ we consider a possible world (p′,⸸, time(w)), and there is no guarantee that (p′,⸸, time(w)) ∈H. This is why we define World(M) = Pnt × Event⸸× Time(M) in Definition 3.4.2(2). This is inherent and a feature of our design. Conversely, defining World(M) to be just equal to H would be too weakly-structured for what Figure 4 requires.

(3) Continuing the previous point and contrasting with it — the in the past modality ↓ looks specifically for a possible world in H. We unpack the clause for w ⊨↓ϕ in Figure 4:

w ⊨↓ϕ ⇐⇒∃w′ ≪−w. (w′ ⊨ϕ) Figure 4⇐⇒∃w′ ≪w. (place(w′) = place(w) ∧w′ ⊨ϕ) Definition 3.4.2(4)⇐⇒∃w′ ∈time(w). (place(w′) = place(w) ∧w′ ⊨ϕ) Definition 3.4.2(3)

It follows from the above and from Lemma 3.4.3 that time(w′) ≺−H. Note also that the interpretation of w ⊨E (for E an event) also appeals to whether a possible world is in H. So two notions of possible world coexist in Figure 4, in a kind of creative tension:

— There are w ∈ World(M), which we call possible worlds in Definition 3.4.2(2).

— There are w ∈H, which we call event-tuples in Definition 2.2.6(1).

We require the former to interpret □W ⊨ϕ and⤒→and ♢ in Figure 4, and we require the latter to interpret ↓ and E.

3.5. Active and inactive participants

It will be helpful later if we make a short technical detour and introduce the notion of (in)active participants:

Definition 3.5.1 ((In)active participants).

Call p active in H when H@p ≠ ∅. Unpacking Definition 3.4.7 this means that there exists some w ∈H with place(w) = p. If p is not active (so H contains no event-tuple starting with p) then call it inactive in H.

Usually H will be fixed or understood, so we will just call p (in)active, without mentioning H explicitly. Intuitively, a participant is active when it is the location of at least one event.

Remark 3.5.2

The empty model from Example 3.3.5 is characterised precisely by being such that all of its participants are inactive. The minimal model from Example 3.3.6 is the simplest such that all of its participants are active.

Lemma 3.5.3

Suppose M is a model with history structure H and suppose p ∈ Pnt. Then the following are equivalent:

(1) p,⸸, H ⊨↓⊤.

(2) p is active (there is an event-tuple in H starting with p; Definition 3.5.1).

As a corollary, ⊨↓⊤ if and only if all participants are active.

Proof

We just unpack the definitions in Figure 4.End of proof

3.6. Extending syntax with syntactic sugar

The core syntax from Figure 3 is expressive, and it will be convenient to use sugar as follows:

Definition 3.6.1 (Syntactic sugar).

We define syntactic sugar as described in Figure 5, and we unpack the corresponding denotation in Figure 6.

Remark 3.6.2 (de Morgan dualities).

We recall some standard background on logic and negation.35

Logical connectives — quantifiers, modalities, and propositional connectives — tend to come in pairs, which are dual to one another by negation in a standard way. Standard dualities include:

(1) forall/exist duality ∀a.ϕ = ¬∃a.¬ϕ and ∃a.ϕ = ¬∀a.¬ϕ.

(2) and/or duality ϕ ∧ψ = ¬(¬ϕ ∨¬ψ) and ϕ ∨ψ = ¬(¬ϕ ∧¬ψ).

(3) every/some duality In modal logic, we have □ϕ = ¬♢¬ϕ and ♢ϕ = ¬□¬ϕ.

All definitions will be written out in full, but the reader should just note that usually these connectives come in pairs and we will structure our definitions accordingly.

Sugar for basic propositions & predicates ¬ϕ = (ϕ ⇒⊥) ⊤= ¬⊥ϕ ∨ϕ′ = ((¬ϕ) ⇒ϕ′) ϕ ∧ϕ′ = ¬((¬ϕ) ∨(¬ϕ′))ϕ ⇔ϕ′ = (ϕ ⇒ϕ′) ∧(ϕ′ ⇒ϕ) ∃a.ϕ = ¬∀a.¬ϕ ∃01a.ϕ = ∀a, b.ϕ ⇒ϕ[a:=b] ⇒a=b ∃1a.ϕ = (∃01a.ϕ) ∧∃a.ϕSugar for time ⇓ϕ = ¬↓¬ϕ ↕ϕ =⤒→↓ϕ ⇕ϕ = ¬↕¬ϕ =⤒→⇓ϕSugar for the modality ♢↓□l1...ln ϕ = ¬♢l1...ln ¬ϕ □↓l1...ln ϕ = □l1...ln ↓ϕ♢↓l1...ln ϕ = ♢l1...ln ↓ϕ□⇓l1...ln ϕ = □l1...ln ⇓ϕ♢⇓l1...ln ϕ = ♢l1...ln ⇓ϕ□ϕ = □∅ϕ♢ϕ = ♢∅ϕIn the clause for ∃01a.ϕ (which introduces a variable symbol b), ϕ[a:=b] denotes the usual capture- avoiding substitution of b for a, and (also as usual) we assume that b is fresh for ϕ.
Fig. 5: Extended (sugared) syntax (Definition 3.6.1)
w ⊨⊤ ⇐⇒⊤w ⊨¬ϕ ⇐⇒w ⊭ϕw ⊨ϕ ∨ϕ′⇐⇒(w ⊨ϕ) ∨(w ⊨ϕ′)w ⊨ϕ ∧ϕ′⇐⇒(w ⊨ϕ) ∧(w ⊨ϕ′)w ⊨ϕ ⇔ϕ′⇐⇒((w ⊨ϕ) ⇐⇒(w ⊨ϕ′))w ⊨∃a.ϕ ⇐⇒∃v ∈Value.(w ⊨ϕ[a:=v])

w ⊨∃01a.ϕ and w ⊨∃1a.ϕ are as expected

w ⊨⇓ϕ ⇐⇒∀w′ ≪−w. (w′ ⊨ϕ)w ⊨↕ϕ ⇐⇒∃w′ ∈H@place(w). (w′ ⊨ϕ)w ⊨⇕ϕ ⇐⇒∀w′ ∈H@place(w). (w′ ⊨ϕ) w ⊨□l1...ln ϕ ⇐⇒∃(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∀p′ ∈O1 ∩· · · ∩On.(p′,⸸, time(w) ⊨ϕ)w ⊨♢↓l1...ln ϕ ⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃w′ ≪w. (place(w′) ∈O1 ∩· · · ∩On ∧w′ ⊨ϕ)w ⊨□↓l1...ln ϕ ⇐⇒∃(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∀p′ ∈O1 ∩· · · ∩On.∃w′ ≪w. (place(w′) = p′ ∧w′ ⊨ϕ)w ⊨♢⇓l1...ln ϕ ⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃p′ ∈O1 ∩· · · ∩On.∀w′ ≪w. (place(w′) = p′ =⇒w′ ⊨ϕ)w ⊨□⇓l1...ln ϕ ⇐⇒∃(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∀p′ ∈O1 ∩· · · ∩On.∀w′ ≪w. (place(w′) = p′ =⇒w′ ⊨ϕ) p, x, H ⊨♢ϕ ⇐⇒∃p′ ∈Pnt.p′,⸸, H ⊨ϕp, x, H ⊨□ϕ ⇐⇒∀p′ ∈Pnt.p′,⸸, H ⊨ϕ

Above, w′ ≪w is from Definition 3.4.2(3) and means w′ ∈ time(w). Note that Figure 5 defines syntactic sugar — like ⇓ϕ = ¬↓¬ϕ — and this Figure unpacks the denotation of that sugar as per Figure 4. It is not the case that there are (for example) two ⇓ symbols — indeed, formally there is no symbol ⇓ at all, since it is a macro for ¬↓¬.

Fig. 6: Denotation of sugar from Figure 5 (Definition 3.6.1)
Remark 3.6.3

We briefly discuss the sugar in Figure 5, with more details to follow in the Remarks and Lemmas that follow:

(1) ¬, ∧, and ∨ are defined from ⊥ and ⇒ using standard encodings.

(2) ∃a.ϕ = ¬∀a.¬ϕ is also standard: it is the usual de Morgan dual definition of ∃ in terms of ∀.

(3) ⇓ is the de Morgan dual to ↓. ↓ϕ means that ϕ holds at the time of some past event at the current place, so its de Morgan dual ⇓ϕ means that ϕ holds at the time of every past event at the current place.

(4) ↕ϕ and ⇕ϕ are temporal modal operators (see Subsection 1.3 of [GHR94] for an old but very approachable survey of the genre):

— ↕ϕ — read sometime ϕ — means that ϕ holds at the time of some maybe-event at the current place.

— ⇕ϕ — read everytime ϕ — means that ϕ holds at the time of every maybe-event at the current place.

These are de Morgan duals: ↕ϕ is equivalent to ¬⇕¬ϕ and ⇕ϕ is equivalent to ¬↕¬ϕ.

(5) □l1...ln ϕ = ¬♢l1...ln ¬ϕ. This defines □l1...ln ϕ as the de Morgan dual to ♢l1...ln ϕ.

(6) The ∅ in ♢ϕ = ♢∅ϕ and □ϕ = □∅ϕ denotes the empty list (of learners).

(7) Eight modalities are definable and will be of interest. We list them:

(a) ♢l1...ln ϕ means ‘ϕ holds somewhere in every l1. . . ln-quorum intersection’. We may read this as all l1. . . ln-quorum intersections admit ϕ.

(b) □l1...ln ϕ means ‘ϕ holds everywhere in some l1. . . ln-quorum intersection’. We may read this as some l1. . . ln-quorum intersection agrees on ϕ.

(c) ♢↓l1...ln ϕ means ‘ϕ held in the past somewhere in every quorum intersection’. We may read this as all l1. . . ln-quorum intersections admit past ϕ.

(d) □↓l1...ln ϕ means ‘ϕ held in the past everywhere in some quorum intersection’. We may read this as some l1. . . ln-quorum intersection agrees on past ϕ.

(e) ♢⇓l1...ln ϕ means ‘ϕ held up to (not including) now somewhere in every quorum intersection’. We may read this as all l1. . . ln-quorum intersections admit ϕ up to (but not necessarily including) now.

(f) □⇓l1...ln ϕ means ‘ϕ held up to (not including) now everywhere in some quorum intersection’. We may read this as some l1. . . ln-quorum intersection agrees on ϕ up to (but not necessarily including) now.

(g) We may read ♢ϕ as ϕ holds somewhere (now), and □ϕ as ϕ holds everywhere (now).

We will justify the terminology above, with the results that follow below. In our usage, ‘admit’ is the de Morgan dual to ‘agree’, because ♢ is the de Morgan dual to □. That is: we admit ϕ if we do not agree on not-ϕ.

We check correctness of some parts of Figure 6:

Lemma 3.6.4

Suppose M is a model and w ∈ World(M). Then as per Figure 6:

(1) The following are equivalent:

— w ⊨↕ϕ

— ∃w′ ∈H. (place(w′) = place(w) ∧w′ ⊨ϕ)

— ∃w′ ∈H@place(w). w′ ⊨ϕ.

(2) The following are equivalent:

— w ⊨⇕ϕ

— ∀w′ ∈H. (place(w′) = place(w) =⇒w′ ⊨ϕ)

— ∀w′ ∈H@place(w). w′ ⊨ϕ.

(3) The following are equivalent:

— w ⊨♢↓l1...ln ϕ

— ∀(O1, . . . , On) ∈ ς(l1) × · · · × ς(ln).∃w′ ≪w.(place(w′) ∈O1 ∩· · · ∩On ∧w′ ⊨ϕ)

Proof

Part 2 follows from part 1 by de Morgan duality, so we focus on part 1. We reason as follows, where we take w = (p, x, H):

w ⊨↕ϕ ⇐⇒w ⊨⤒→↓ϕ Figure 5⇐⇒p,⸸, H ⊨↓ϕ Figure 4⇐⇒∃w′ ≪−(p,⸸, H). w′ ⊨ϕ Figure 4⇐⇒∃H′, x′. (p, x′, H′) ∈H ∧p, x′, H′ ⊨ϕ Definition 3.4.2(4)

The equivalences then follow from the definitions (H@place(w) is from Definition 3.4.7).

For part 3 we unpack ♢↓ as ♢ and ↓ and use Figure 4 as follows:

p, x, H ⊨♢↓l1...ln ϕ ⇐⇒p, x, H ⊨♢l1...ln ↓ϕ Figure 5⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃p′ ∈O1 ∩· · · ∩On. p′,⸸, H ⊨↓ϕ Figure 4⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃p′ ∈O1 ∩· · · ∩On.∃w′ ≪(p′,⸸, H). Figure 4 &(place(w′) = p′ ∧w′ ⊨ϕ) Def 3.4.2(3&4)⇐⇒∀(O1, . . . , On) ∈ς(l1) × · · · × ς(ln). ∃w′ ≪w. (place(w′) ∈O1 ∩· · · ∩On ∧w′ ⊨ϕ) FactEnd of proof
Remark 3.6.5

We unpack the modalities ♢, □, ♢↓, □↓, ♢⇓, and □⇓. We consider each modality in turn.

(1) Modality ♢ϕ: “Somewhere, with ⸸, ϕ holds at the current time.”

p, x, H ⊨♢ϕ ⇐⇒∀()∈∗.∃p′ ∈⋂ ∅. p′,⸸, H ⊨ϕ⇐⇒∃p′ ∈Pnt. p′,⸸, H ⊨ϕ.

∀()∈∗ denotes a choice of elements from the empty product ∗. This has one element: the 0-tuple (). Then ⋂ ∅ denotes taking the intersection of no subsets of Pnt, which by convention is Pnt. So p, x, H ⊨♢ϕ just looks for some p′ such that p′,⸸, H ⊨ϕ. Subtlety alert: because of how ♢ ‘resets’ the current maybe-event from x ∈ Event⸸ to ⸸, it is not necessarily the case that w ⊨E ⇒♢E. For a counterexample, take Pnt = {p} and E ∈ Event and H = {(p, E, ∅)} and w = (p, E, ∅). The reader can check that w ⊨E but w ⊭♢E. We will never notice this edge case because we will only ever use ♢ (and indeed □; see next point) in situations where the current maybe-event is of no interest.

(2) Modality □ϕ: “Everywhere, with ⸸, ϕ holds at the current time.” This is just dual to ♢ϕ:

p, x, H ⊨□ϕ ⇐⇒∃()∈∗.∀p′ ∈⋂ ∅. p′,⸸, H ⊨ϕ⇐⇒∀p′ ∈Pnt. p′,⸸, H ⊨ϕ.

Note again a subtlety that it is not necessarily the case that w ⊨□ϕ ⇒ϕ. For a counterexample, take Pnt = {p} and E ∈ Event and H = {(p, E, ∅)} and w = (p, E, ∅). Then w ⊨□¬E but w ⊭¬E.

(3) Modality ♢↓ϕ: “I have evidence / I know that someone satisfied ϕ at some past event-tuple.” This is a particularly important case. Recall that ♢↓ is sugar for ♢↓. The denotation is:

w ⊨♢↓ϕL3.6.4(3)⇐⇒ ∀()∈∗. ∃w′ ≪w.(place(w′) ∈⋂ ∅∧w′ ⊨ϕ) ⇐⇒∃w′ ≪w.(place(w′) ∈Pnt ∧w′ ⊨ϕ) ⇐⇒∃w′ ≪w. w′ ⊨ϕ.(1)

We unpack how this works. First, we use Lemma 3.6.4(3). Then we simplify. ∀()∈∗ denotes a choice of elements from the empty product ∗; this has one element the 0-tuple (). Then ⋂ ∅ denotes taking the intersection of no subsets of Pnt, which by convention is Pnt. The idea of equation (1) is straightforward: w ⊨♢↓ϕ means that ϕ holds at a world accessible from w. The traditional meaning of the modal diamond operator in Kripke semantics is precisely that ⋄ϕ holds when ϕ holds at some accessible world. In this sense, ♢↓ (not ♢) is the natural modal diamond of our logic.

(4) Modality □↓ϕ: “I have evidence / I know that everyone satisfied ϕ at some past event-tuple (not necessarily the same tuple).” w ⊨□↓ϕ means that for every p′ ∈ Pnt, some w′ ≪w exists with place(w′) = p′ and w′ ⊨ϕ holds. We may call □↓ the knowledge modality, because it is a modality in the logic that corresponds to the idea of ‘knows of’ from Definition 2.2.6(5).

(5) Modality ♢⇓: “I know of someone who satisfied ϕ at every past event-tuple located at them that I know of.” w ⊨♢⇓ϕ means that for some p′ ∈ Pnt, every event-tuple w′ ≪w such that w′ ∈H@p′ is such that w′ ⊨ϕ. In symbols:

w ⊨♢⇓ϕ ⇐⇒∃p′ ∈Pnt.∀w′ ≪w.(place(w′) = p′ =⇒w′ ⊨ϕ).

(6) Modality □⇓ϕ: “ϕ holds every past event-tuple that I know of (including event-tuples not located at me).” The reader can check that w ⊨□⇓ϕ if and only if w ⊨¬♢↓¬ϕ, so this is the de Morgan dual of ♢↓. It is the modal ‘box’ operator to ♢↓’s modal ‘diamond’: it means that ϕ holds at every accessible world, i.e.

w ⊨□⇓ϕ ⇐⇒∀w′ ≪w. w′ ⊨ϕ.
Remark 3.6.6

Remark 3.6.5 describes six modalities: ♢, □, ♢↓, □↓, ♢⇓, and □⇓. These are all derived by suitable combinations of core modalities ♢, ¬, and ↓, but our six modalities have a life of their own in the mathematics to follow, so (even if they can be decomposed) we can treat them as independent conceptual entities.36

Conceptually, it may be more relevant to say that there are three dual pairs of modalities — to have one element of the pair is also, in some sense, to have the other:

— ♢= ¬□¬ and □= ¬♢¬.

— ♢↓= ¬□⇓¬ and □⇓= ¬♢↓¬.

— ♢⇓= ¬□↓¬ and □↓= ¬♢⇓¬.

Do we need all of them?

Yes. The reader can find them all mentioned in our axioms and correctness properties: see for example Figure 7 (theory of liveness), Figure 8 (axioms of theory ThyHBB1), and Figure 9 (correctness properties of ThyHBB1).

Remark 3.6.7

We unpack some common special cases of Figures 5 and 6:

(1) p, x, H ⊨□l ϕ means that there exists an l-quorum O such that p′,⸸, H ⊨ϕ for every p′ ∈O. In words we say: an l-quorum agrees that ϕ (at ⸸ at the current time).

(2) p, x, H ⊨□↓l ϕ means that there exists an l-quorum O such that for every p′ ∈O, some (p′, x′, H′) ∈H exists such that p′, x′, H′ ⊨ϕ. In words we say: an l-quorum agrees that ϕ in the past (meaning: at some past event-tuple).

(3) p, x, H ⊨□⇓l ϕ means that there exists an l-quorum O such that for every w′ ∈H, if place(w′) ∈ O then w′ ⊨ϕ.

(4) We leave it to the reader to unpack □l1...ln ϕ, □↓l1...ln ϕ, and □⇓l1...ln ϕ. We may read □↓l1...ln ϕ as a(n l1. . . ln-)quorum intersection agrees that ϕ in the past.

(5) Matters simplify further when H = H: Thus:

— ⊨♢ll′ ϕ and p,⸸, H ⊨♢ll′ ϕ mean that for every l-quorum and l′-quorum, there exists a p′ in their intersection such that p′,⸸, H ⊨ϕ.

— ⊨♢↓ll′ ϕ and p,⸸, H ⊨♢↓ll′ ϕ mean that for every l-quorum and l′-quorum, there exists a p′ in their intersection and some w′ ∈H such that place(w′) = p′ and w′ ⊨ϕ.

— We leave it to the reader to unpack □ll′ ϕ, □↓ll′ ϕ, ♢⇓ll′ ϕ, and □⇓ll′ ϕ.

Remark 3.6.8

Figures 5 and 6 do not exhaust the design space of modalities. We take a moment to mention other possible modalities (for simplicity we may omit l1. . . ln subscripts):

(1) An at some non-strictly preceding event modality ↓′ϕ such that

w ⊨↓′ϕ ⇐⇒(w ⊨ϕ ∨∃w′ ≪−w.w′ ⊨ϕ).

This looks like ↓ from Figure 4, but it uses a non-strict notion of ‘in the past’ which might include the present. ↓′ϕ can easily be expressed in our syntax just as ϕ ∨↓ϕ.

(2) An at some future modality ↑ϕ such that

w ⊨↑ϕ ⇐⇒∃w′ ∈H.(w ≪w′ ∧w′ ⊨ϕ).

We do not need this for our axioms or correctness properties so far, so we omit it from the main development, but it is a perfectly reasonable definition. ↑ϕ cannot be expressed in the predicate syntax in Figure 3, so if we wanted this modality then we would need to extend the syntax.

(3) An at every possible world modality

□W ϕ meaning ∀w ∈World(M).w ⊨ϕ,

and its dual at some possible world ♢W ϕ meaning ∃w ∈ World(M).w ⊨ϕ. These modalities cannot be expressed in the predicate syntax in Figure 3, and we do not add them (we could; we just do not need to for now) — however, we will see □W in our notion of validity in equation (3) in Definition 5.2.1.

(4) We can express an at every event in history modality as⤒→□⇓ϕ meaning ∀w ∈H.w ⊨ϕ, and its dual at some event in history⤒→♢↓ϕ meaning ∃w ∈H.(w ⊨ϕ). Note that □W ϕ is not the same thing as⤒→□⇓ϕ (at every possible world in H), nor is it the same thing as⤒→(□⇓ϕ ∧□ϕ) (at every possible world in H or at the end of time), and ♢W is not the same thing as⤒→♢↓ϕ or⤒→(♢↓ϕ ∨♢ϕ). There may exist event-tuples in World(M) that are not in H and are not of the form (p,⸸, H). This is deliberate, and motivated by the semantics for ♢ in Figure 4 (cf. footnote 34, which is based on a similar observation).

These and other modalities exist in a rich design space supported by our models.

Remark 3.6.9

Definition 3.4.2 (possible worlds and the accessibility relation) and Definition 3.4.10 (validity) define a Kripke structure and a modal logic over it. Let us just spell this out explicitly. Given a model M = (Pnt, H, ϱ, ς), the corresponding Kripke structure K(M) is as follows:

— The set of possible worlds is World(M) from Definition 3.4.2(2).

— The accessibility relation w′ ≪w is as per Definition 3.4.2(3) (namely: w′ ∈ time(w)).

— We deem an E to hold at w = (p, x, H) when E = x and w ∈H, and we deem an atomic predicate P to hold at w when P ∈ϱ(p, H) (see the predicate interpretation of M; Definition 3.3.3(3)).

So far, so straightforward. But there are some subtleties to this:

(1) Not every possible world in World(M) is an element of H. On the contrary, there are many possible worlds that are not of this form, because of how⤒→and ♢ are interpreted (see the discussion in Remark 3.4.11(2)).

(2) The modalities — in-the-past ↓, end-of-time⤒→, and the diamond modality ♢l1...ln — are specific, in the sense that they reflect structure that cannot be understood purely in terms of the accessibility relation on worlds. ♢↓ and □⇓ are not specific in this sense: we can understand them purely in terms of ≪: they are just the standard diamond (‘for some accessible world’) and box (‘for all accessible worlds’) modalities in the usual modal sense (see Remark 3.6.5(3&6)). But other modalities are not standard at all: to interpret ↓ we require ≪−which is a specific structure that enriches ≪ with a notion of ‘same participant’; and⤒→requires a notion of ‘end-of-time’. Then, and most strikingly, ♢l1...ln does its own idiosyncratic thing having to do with the existence of participants in quorum intersections.37 So K(M) is ‘a Kripke structure’ similarly to how a lion is ‘a cat’: the generic description is true but elides specific characteristics that can matter a lot when we interact with the specific beast in question. Working out what abstract properties K(M) has, above and beyond being a Kripke model, that give it its own particular and specific character, is future work.

(3) We have not one, but three relevant notions of validity (and we will use all three).

All the above is to say to the reader who is expert in modal logic that: yes, this is a modal logic, and it does modal-flavoured things with things that look like modalities, but that is not the end of it. The choice of definitions, modalities, and the design of their semantics, is specific and crafted to satisfy specific constraints and expressivity requirements as imposed by the axiomatic theories and correctness proofs which we will see later.

Empirically, those design constraints are surprisingly stringent, in the sense that deviation from the design presented here seems to be punished by messy and/or incorrect proofs. This design did not write itself: we had to work to find it.38

4. THE MODALITIES

Remarks 3.6.7 and 3.6.5 might give an impression that the modalities created from the combination of ♢, ↓, and ¬ — namely ♢, □, ♢↓, □↓, ♢⇓, and □⇓ — will play an important role in what will follow. This impression is correct: we now develop more of the relevant theory.

4.1. Quorum intersection properties

A common theme in distributed systems is quorum intersection properties. A typical assumption has the form ‘any n quorums intersect’, for a value of n that may depend on the protocol under consideration. Common values are n = 2 or n = 3; see e.g. the Q2 property from [DDFN07, Theorem 1], and the Q3 property of [ACTZ24, Definition 2] or [HM00, page 4]. In the classical synchronous Byzantine model, consensus with n processors and up to f faulty processors requires n > 3f [AW04, Theorem 5.8]. Going further back, Bracha’s original papers assumed the same thing, though for him quorum intersection was a corollary of a stronger cardinality assumption. See “In this section we show that the protocol in Fig. 1 achieves Asynchronous Byzantine agreement for 0 ≤t < n/3” [Bra84, Subsection 3.2] and “[we present] a randomized consensus protocol that tolerates up to t < n/3 Byzantine processes” [Bra87, Page 133]. In the semitopological literature, these ideas appear as topological notions. An intertwined space from [Gab24; Gab25] corresponds to any two quorums intersecting; and n-way intersection properties are considered in generality in a section on n-twined semitopologies in [GZ26].

Here, we will exploit an elegant way to express quorum intersection properties logically, using the ♢ modality:

Lemma 4.1.1

Suppose l1, . . . , ln ∈ Learner and suppose ϕ is a closed predicate. Then:

(1) ⊨♢l1...ln ϕ if and only if every n-way quorum intersection between an n-tuple of l1, . . . , ln-quorums, contains some p such that p,⸸, H ⊨ϕ.

(2) ⊨♢l1...ln ⊤ if and only if every n-way quorum intersection between an n-tuple of l1, . . . , ln-quorums is nonempty.

(3) ⊨♢l1...ln ϕ implies ⊨♢l1...ln ⊤.

Proof

We consider each part in turn:

(1) Routine from the clause for ♢ in Figure 4.

(2) p,⸸, H ⊨⊤ always by Figure 6. We use part 1 of this result.

(3) Using the fact that ϕ ⇒⊤.End of proof

Some notation will be useful.

Notation 4.1.2

Suppose l1, . . . , ln ∈ Learner and suppose M = (Pnt, H, ϱ, ς) is a model (Definition 3.3.3). Then consider the following validity judgements:

⊨♢l1...ln ⊤ ⊨♢l1...ln seq ⊨♢l1...ln live

(seq is from Figure 3. The symbol live will become important later on in Definition 5.2.4, when we discuss a theory of liveness. For convenience we collate it here; the reader can treat live for now as just a predicate-symbol which happens to have a suggestive name and some associated intuition, which will be fleshed out more formally later.)

— When ⊨♢l1...ln ⊤, say that l1. . . ln have nonempty quorum intersections, or just that they have intersecting quorums, By Lemma 4.1.1(1) this means that for every n-tuple of quorums O1 ∈ ς(l1), ..., On ∈ ς(ln) the intersection O1 ∩· · · ∩On is nonempty.

— When ⊨♢l1...ln seq, say that l1. . . ln have sequential quorum intersections. By Lemma 4.1.1(1) this means that for every n-tuple of quorums O1 ∈ ς(l1), ..., On ∈ ς(ln) the intersection O1 ∩· · · ∩On contains a sequential participant.

— When ⊨♢l1...ln live, say that l1. . . ln have live quorum intersections. By Lemma 4.1.1(1) this means that for every n-tuple of quorums O1 ∈ ς(l1), ..., On ∈ ς(ln) the intersection O1 ∩· · · ∩On contains a live participant.

4.2. Modal properties

Modal logics are a rich field. The traditional study of modal logics has done a particularly nice job of building up a library of named axiomatic properties. To take one example, the reader might have seen the axiom “□A =⇒ □□A” — traditionally this is called (4) in the literature. Accessible surveys are in [Gar24; GKWZ03].39

Our set of modalities has a rich yet specific texture, since it includes ↓ (in the past),⤒→(end of time), and modality-schemes parameterised over lists of learners ♢l1...ln , ♢↓l1...ln , ♢⇓l1...ln , and their □-duals. Many interactions are possible; here we will study what is relevant to and/or required for our proofs.

Lemma 4.2.1

Suppose w ∈ World(M) and l, l1, . . . , ln ∈ Learner, and suppose ϕ is a closed predicate. Then:

(1) w ⊨□↓l ϕ ⇒♢↓ϕ.

This is reminiscent of the traditional (D) axiom from modal logic, which is usually written “□A =⇒♢A”. In the standard Kripke semantics for (standard) modal logic, it corresponds to the accessibility relation being serial (there is always an accessible world).

(2) ⊨□ϕ ⇒♢ϕ and ⊨□l ϕ ⇒♢ϕ.

(3) w ⊨□l1...ln ϕ does not necessarily imply w ⊨♢ϕ.

(4) w ⊨ϕ does not necessarily imply w ⊨♢l1...ln ϕ.

Proof

We consider each part in turn:

(1) By Remark 3.6.7(2) w ⊨□↓l ϕ when there exists O ∈ ς(l) such that for every p′ ∈O there exists w′ ≪w such that place(w′) = p′ and w′ ⊨ϕ. Now O ⊆ Pnt is assumed nonempty by Definition 3.3.2(3), so by assumption there exists some p′ ∈O and w′ ≪w such that place(w′) = p′ and w′ ⊨ϕ. Thus there exists w′ ≪w such that w′ ⊨ϕ, and by Remark 3.6.5(3) w ⊨♢↓ϕ.

(2) ⊨□l ϕ ⇒♢ϕ follows by similar arguments to part 1. ⊨□ϕ ⇒♢ϕ also follows by similar arguments to part 1, using the fact in Definition 3.3.3 that we assumed Pnt ≠ ∅.

(3) The intersection O1 ∩· · · ∩On might be empty.

(4) p need not be in every quorum intersection (indeed, as just observed, the intersection might be empty).End of proof

Lemma 4.2.2

Suppose w ∈ World(M) and ϕ is a closed predicate. Then

w ⊨♢↓♢↓ϕ ⇒♢↓ϕ.

This corresponds to the traditional (4) axiom from modal logic, which is usually written dually as “□A =⇒□□A” and is one of the signature axioms of the modal logic S4. In the standard Kripke semantics for (standard) modal logic, it corresponds to the accessibility relation being transitive.

Proof

We reason using equation (1) in Remark 3.6.5 and Proposition 3.4.5 (transitivity of the accessibility relation), as follows:

w ⊨♢↓♢↓ϕ ⇐⇒∃w′′ ≪w′ ≪w. w′′ ⊨ϕ Equation (1)=⇒∃w′′ ≪w. w′′ ⊨ϕ Proposition 3.4.5⇐⇒w ⊨♢↓ϕ Equation (1)End of proof
Lemma 4.2.3

Suppose w ∈ World(M) and l ∈ Learner and ϕ is a closed predicate. Then:

(1) w ⊨♢↓□↓l ϕ ⇒□↓l ϕ.

This axiom seems analogous to the traditional (5) axiom, usually written dually as “♢A =⇒ □♢A”. In the standard Kripke semantics for (standard) modal logic, it corresponds to the accessibility relation being Euclidian (x R y and x R z implies y R z).

(2) w ⊨↓□↓l ϕ ⇒□↓l ϕ.

(3) The reverse implications need not hold.

Proof

We consider each part in turn:

(1) By Figure 6, if w ⊨♢↓□↓l ϕ then there exists w′ ≪w (Definition 3.4.2(3)) such that w′ ⊨□↓l ϕ. By Remark 3.6.7(2) there exists an l-quorum O ∈ ς(l) of participants such that for every p′ ∈O there exists w′′ p′ ≪w′ such that place(w′′ p′) = p′ and w′′ p′ ⊨ϕ. Using Proposition 3.4.5 (transitivity of the accessibility relation; since w′ ≪−w) also w′′ p′ ≪w for every p′ ∈O, and by Remark 3.6.7(2) again, w ⊨□↓l ϕ as required.

(2) From part 1, noting (from Figures 4 and 6) that ↓ implies ♢↓.

(3) It suffices to provide a counterexample. Consider E ∈ Event and Pnt = {p} (one participant) and one learner l with one quorum equal to Pnt. Define

H = {(p, E, ∅)}.

We illustrate H in derivation tree style:

p ⊢E

end of time Then the reader can check that p,⸸, H ⊨□↓l E but p,⸸, H ⊨¬↓□↓l E and p,⸸, H ⊨¬♢↓□↓l E.End of proof

5. SEQUENTIALITY AND LIVENESS

5.1. Properties of sequentiality

As per Definition 3.4.9, p is sequential at H when event-tuples in H starting with p are linearly ordered. Our logic in Figures 3 and 4 internalises sequentiality via a predicate seq. In this Subsection, we study sequentiality in more detail.

Example 5.1.1

We start with a simple example to illustrate sequentiality. Consider

H = {(p,⸸, ∅), (p, E, ∅)} or in tree formp ⊢⸸p ⊢E

Note that p,⸸, ∅⊨ seq and p, E, ∅⊨ seq (trivially so), but p,⸸, H ⊭ seq.

With the machinery we have built so far, we can give an attractive characterisation of the clause for w ⊨ seq in Figure 4:

Lemma 5.1.2

Suppose M is a model and w ∈ World(M). Then the following are equivalent:

(1) w ⊨ seq.

(2) {w′ ∈ World(M) | w′ ≪−w} is linearly ordered by ≪.

Proof

By Figure 4 w ⊨ seq holds when place(w) is sequential in time(w). We check the equivalence by unpacking the definition of sequentiality (Definition 3.4.9(1)) and of the in-place accessibility relation (Definition 3.4.2(4)) and seeing that it is so.End of proof

Lemma 5.1.3

Suppose M is a model and w, w′ ∈ World(M). Then

w′ ≪−w implies {w′′ ∈World(M) | w′′ ≪−w′} ⊆{w′′ ∈World(M) | w′′ ≪−w}.
Proof

By routine reasoning from the definition of ≪− (Definition 3.4.2(4)) and transitivity of ≪ on history structures (Proposition 3.4.5).End of proof

Proposition 5.1.4 (Sequentiality monotone).

Suppose M is a model and w′, w ∈ World(M). Then:

(1) If w′ ≪−w then w ⊨ seq implies w′ ⊨ seq.

(2) w ⊨ seq ⇒⇓seq.

Proof

We consider each part in turn:

(1) By Lemma 5.1.2 w ⊨ seq when {w′ ∈ World(M) | w′ ≪−w} is linearly ordered by ≪. We use Lemma 5.1.3.

(2) By Figure 6 w ⊨⇓seq when ∀w′ ≪−w.w′ ⊨ seq, but this just re-states part 1 of this result.End of proof

Proposition 5.1.5 is fundamental to our treatment of sequentiality:

Proposition 5.1.5

Suppose that:

— M is a model and w = (p, x, H) ∈ World(M).

— l, l′ ∈ Learner.

— ϕ and ϕ′ are closed predicates and E, E′ are distinct events (meaning E ≠ E′).

Then:

(1) w ⊨♢ll′ seq ∧□↓l ϕ ∧□↓l′ ϕ′ implies w ⊨♢(seq ∧↓ϕ ∧↓ϕ′).

(2) w ⊨ seq ∧↓E ∧↓E′ implies w ⊨♢↓(E ∧↓E′) ∨♢↓(E′ ∧↓E).

(3) w ⊨♢ll′ seq ∧□↓l E ∧□↓l′ E′ implies w ⊨♢↓(E ∧↓E′) ∨♢↓(E′ ∧↓E).

Proof

We consider each part in turn. We may write w as (p, x, H) without comment:

(1) Assume w ⊨♢ll′ seq ∧□↓l ϕ ∧□↓l′ ϕ′.

— Following the clause for ♢ in Figure 4, w ⊨♢ll′ seq means that any l-quorum intersects any l′-quorum at some p′ ∈ Pnt such that p′,⸸, H ⊨ seq.

— By Figure 5 □↓l = □l ↓, and it follows that w ⊨□↓l ϕ and w ⊨□↓l′ ϕ′ mean that there exist an l-quorum of participants p′ satisfying p′,⸸, H ⊨↓ϕ and an l′-quorum of participants p′ satisfying p′,⸸, H ⊨↓ϕ′.

Therefore, there exists p′ ∈ Pnt such that p′,⸸, H ⊨ seq∧↓ϕ∧↓ϕ′, and so w ⊨♢(seq∧↓ϕ∧↓ϕ′) as required.

(2) Suppose w ⊨ seq ∧↓E ∧↓E′. Since w ⊨ seq, by Lemma 5.1.2 events in H@p are linearly ordered. We assumed that E ≠ E′, and so E happens before E′ or vice versa. The result follows.

(3) We combine parts 1 and 2 of this result.End of proof

Remark 5.1.6 (Design alternative: Sequentiality vs. orderability).

Sequentiality is a maximalist condition: intuitively, it is the strongest well-behavedness property we could require on a participant, short of allowing it to control other participants or to see the future.

We can look at how our sequentiality property is actually used in the proofs — and we see that its full power is not required. For example, it would suffice to replace seq in Figure 4 with a weaker (and thus more general) orderability predicate ord, with the following theory of orderability ThyOrd:

(Order) ord ⇒(↓E ∧↓E′) ⇒(↓(E ∧↓E′) ∨↓(E′ ∧↓E))(E ≠ E′)(OrdPast) ord ⇒⇓ord(OrdPast♢↓) (∀l′.♢ll′ ord) ⇒⇓∀l′.♢ll′ ord(2)

We obtained this theory by looking at what the proofs require: morally, (Order) corresponds to Proposition 5.1.5(2); (OrdPast) corresponds to Proposition 5.1.4(2); and (OrdPast♢↓) corresponds to Lemma 6.5.1 (it is the key technical property required to preserve the ∀l′.♢ll′ seq in axiom (Safe) from Figure 8, under taking ⇓).40

It is straightforward to see that sequentiality implies orderability; however, the reverse implication does not hold. For a minimal counterexample, take Pnt = {p} with {p} being the only quorum, and E ∈ Event, and consider the same history structure from Example 5.1.1:

H = {(p,⸸, ∅), (p, E, ∅)} or in tree formp ⊢⸸p ⊢E

We can interpret ord as true at every possible world, so we see that p is orderable in H (there is only one event E), but it is not sequential (E does not occur before or after the ⸸).

Weak assumptions are generally preferable if they lead to the same results. Thus, we could remove seq from Figures 3 and 4 and instead use a predicate ord with a ‘theory of orderability’ ThyOrd — much as we will define a ‘theory of liveness’ ThyLive in Figure 7. This would be morally satisfying (a smaller core logic with more heavy lifting done by axioms is generally good practice) and more general.

Nevertheless, for now we use sequentiality: it is easier to think about, has a clear linear visual interpretation, and it is pragmatically justified as corresponding to what we think of as a participant following a protocol step-by-step.

5.2. A logical theory of liveness

5.2.1. (Axiomatic) theories.

We have built a notion of model (Definition 3.3.3), and notions of logical validity over a model given by w ⊨, ⊨, and □W ⊨ from Figure 4. We are nearly ready to put this together to develop an axiomatic theory of what it means to be live, which we will do in Definition 5.2.4 and Figure 7.

First, we need to state what an axiomatic theory is, and what it means for such a theory to be valid in a model. Recall from Figure 4, that

— ⊨ϕ means p,⸸, H ⊨ϕ for every p ∈ Pnt, and

— □W ⊨ϕ means w ⊨ϕ for every w ∈ World(M).

Our notion of validity of a theory in a model is based on □W ⊨ϕ, as follows:

Definition 5.2.1

Suppose Σ is a signature (Definition 3.1.1).

(1) An axiom (over Σ) is a closed predicate ϕ in the syntax of Figure 3.

(2) Suppose M is a model for Σ (Definition 3.3.3) and suppose ϕ is an axiom (over Σ). Call ϕ valid of M when

□W ⊨ϕ meaning ∀w ∈World(M). w ⊨ϕ. (3)

(3) A theory is a (possibly infinite) set of axioms.41 In Figures 7, 8, 10, and 12 we illustrate theories using predicates that appear to be open (i.e. have free variables). Consistent with a common shorthand for writing axioms in logic, we assume that a top-level closing universal quantification is present but elided (as in “commutativity: x∗y = y∗x” instead of “the commutativity axiom is ∀x.∀y.(x ∗y = y ∗x)”).

(4) Suppose M is a model for Σ (Definition 3.3.3) and suppose Thy is a theory over Σ. We define □W ⊨ Thy by

□W ⊨Thy when ∀ϕ ∈Thy.(□W ⊨ϕ).

In words, a theory is valid when each of its axioms is valid. In this case we may say that M satisfies or is a model of Thy.

Remark 5.2.2

Note that an axiom ϕ being valid in a model M is based on □W ⊨ϕ, as per equation 3 in Definition 5.2.1 above. That is, on its validity at the time and place of every possible world.

Note that this definition is not based on ⊨ϕ (validity at every possible world at the end of time, i.e. having the form (p,⸸, H)).42

In fact this is a matter of emphasis: we can derive the effect of ⊨ϕ using the validity judgement □W ⊨, just by writing □W ⊨⤒→ϕ. And indeed we do just this, in the two Knowledge axioms in Figure 7.

(LiveAlways) live ⇔⤒→live(LiveSeq) live ⇒seq(Knowledge♢↓) (⤒→♢↓(live ∧E)) ⇒live ⇒↕♢↓E(Knowledge□↓) (⤒→□↓l1...ln (live ∧E)) ⇒live ⇒↕□↓l1...ln EAbove: E ∈Event is an event and the⤒→modality takes us to the end of time in the model (which we typically write as H). live is a predicate symbol and we shorten live() to live, as per Notation 3.1.2.
Fig. 7: ThyLive: a theory of liveness (Definition 5.2.4)
Remark 5.2.3 (Design choice).

An interesting design tension exists between two notions of everywhere:

— we have ‘at all events in history’, as in □⇓, and

— we have ‘at all possible worlds’, as in □W.

We use both notions, implicitly or explicitly, in our proofs.

There are deep reasons for this: it comes from the fact that our syntax in Figure 3 contains events and predicates. Events and predicates coexist in our syntax and our axioms, by design. For example, axiom (Safe) in Figure 8 mentions both a predicate safe and an event propose.

Events interact most naturally with □⇓ (because the history of a model is fundamentally a set of event-tuples); whereas predicates interact most naturally with □W (because predicates are true or false at a possible world regardless of whether anything happens there). Our proofs will flow naturally, but under the surface there is this subtle design tension between predicates whose design shape suits □W, and events whose design shape suits □⇓. We accommodate this design tension as follows:

— The predicate syntax in Figure 3 includes event-based modalities like ↓, ♢↓, and □⇓. There is no □W modality in the syntax.

— Our notion of axiomatic validity in Definition 3.4.10 uses an ‘at all possible-worlds’ based modality □W.

This is a design choice: it seems to work well, but please just note that this was not a priori obvious, and other design choices might be possible and in other circumstances other choices might even be preferable. There is a design space here and we are free to use it as most convenient.

5.2.2. Definition of ThyLive.

Intuitively, we call a participant p live when:

(1) p does not crash, and

(2) p correctly follows the algorithm.

Perhaps surprisingly, it is possible to render this intuition as an axiomatic theory ThyLive. Recall from Definition 5.2.1 that a theory is a set of closed predicates, which in this context we call axioms:

Definition 5.2.4

Assume a signature with a predicate-symbol live. Let the theory of liveness ThyLive be as defined in Figure 7.

Remark 5.2.5

We discuss the axioms of ThyLive in Figure 7:

— (LiveAlways): being live is a property of place, not of time. (LiveAlways) expresses that p being live does not depend on the time H. This makes sense, because liveness is a property of a participant, not of the time of any event. During a run of an algorithm we cannot predict whether p will crash, because that would involve seeing the future. What ‘p remains live during the run of the algorithm’ refers to is a property of p that only makes sense after the run of the algorithm is complete.
Note a subtlety that there is another important component to being live, that a live participant should progress according to the protocol. However, what ‘progress according to the protocol’

means is protocol-dependent. This part of liveness can be and is expressed on a per-protocol basis as so-called forward rules in Figures 8, 10, and 12.

— (LiveSeq): live participants are sequential. This is definitional. We define live to mean ‘does not crash and is sequential’. Being sequential, along with obeying the forward rules, captures the notion of ‘following the protocol’.

— (Knowledge♢↓): live participants communicate events. If some live participant carries out an event E ∈ Event, then eventually (there is no guarantee how long it will take, but eventually) every live participant will know that an event E has occurred

— in the sense that for every p, there exists some maybe-event-tuple (p, x, H) ∈H such that H contains an E-event tuple.

We call this a knowledge axiom because it governs what live participants eventually know, in the sense of Definition 2.2.6(5).

— (Knowledge□↓): live participants communicate quorum-intersections of events. This is a slightly different property which neither implies nor is implied by the previous one. If some l-quorum of live participants do some E, then (eventually) every live participant will know that an l-quorum of participants have done E — in the sense that for every participant p there exists some event-tuple (p, x, H) ∈H such that the time H includes E-event-tuples for an l-quorum of participants.

5.2.3. More on the Knowledge axioms

Remark 5.2.6

(Knowledge♢↓) and (Knowledge□↓) are axiom-schemes in Figure 7. Axiom-schemes are a standard device in logic.43

We will invoke the Knowledge axioms directly in what follows, but importantly, we also use them via Proposition 5.2.8. We need a technical observation for Proposition 5.2.8:

Lemma 5.2.7

Suppose M is a model and p ∈ Pnt and ϕ is a closed predicate. Then

p,⸸, H ⊨⤒→↓ϕ if and only if p,⸸, H ⊨↓ϕ.

In words: at the end of time, what happens sometime at p happens in the past at p.

Proof

By routine calculations from Figure 4.End of proof

Proposition 5.2.8

Suppose M is a model and □W ⊨ ThyLive (Figure 7) and suppose E ∈ Event is an event. Then

⊨□l live and ⊨♢↓(live ∧E) implies ⊨□↓l (live ∧♢↓E).

In words: if there is an l-quorum of live participants, and some live participant has an event-tuple at which E holds, then eventually there is an l-quorum of live participants who know that an event-tuple occurred at which E held.

Proof

Suppose

⊨♢↓(live ∧E).

In words: there is an event-tuple in H at which a live participant satisfies E.

We assumed □W ⊨ ThyLive so we have

□W ⊨⤒→♢↓(live ∧E) ⇒live ⇒↕♢↓E.

So consider some live p ∈ Pnt. We have that p,⸸, H ⊨♢↓(live ∧E) implies p,⸸, H ⊨ live implies p,⸸, H ⊨↕♢↓E. It follows that p,⸸, H ⊨↕♢↓E and so using (LiveAlways) and Lemma 5.2.7 we have p,⸸, H ⊨↓(live ∧♢↓E).

Since we assume that an l-quorum of live participants p exists, we have ⊨□↓l (live ∧♢↓E) as required.End of proof

5.2.4. More on (LiveAlways)

Lemma 5.2.9

Suppose M is a model and satisfies ThyLive from Figure 7,44 and suppose w, w′ ∈H and place(w) = place(w′). Then:

(1) w ⊨ live if and only if place(w),⸸, H ⊨ live.

(2) w ⊨ live if and only if w′ ⊨ live.

(3) ⊨ live ⇒⇓live.

Proof

Part 1 just restates (LiveAlways), unpacking the meaning of⤒→in Figure 4.45 Part 2 follows by two uses of part 1. Part 3 follows by one use of part 1.End of proof

Proposition 5.2.10 is conceptually simple, and it turns out to be a key property for our Cascade Termination results (Propositions 6.5.5, 7.3.2, and 8.4.5):

Proposition 5.2.10

Suppose M is a model and □W ⊨ ThyLive (Figure 7). Suppose ϕ is a closed predicate and l1, l2 ∈ Learner. Suppose further that

⊨♢l1l2 ⊤ and ⊨□l2 live.

Then

⊨□↓l1 ϕ implies ⊨♢↓(live ∧ϕ).

In words: if l1 and l2 have nonempty quorum intersections46 and l2 has a quorum of live participants, then any l1-quorum of ϕ contains at least one live participant.

Proof

Suppose ⊨□↓l1 ϕ. By Lemma 4.1.1(2) (since ⊨♢l1l2 ⊤) every l1-quorum intersects every l2-quorum. Using Lemma 5.2.9(1) ⊨♢↓(live ∧ϕ) as required.End of proof

Lemma 5.2.11 has in common with Lemma 4.2.2 that it expresses in our logic a(nother) version of the (4) axiom from the modal logic S4. It is nice how the same basic axiomatic property arises in different ways, here for □↓l +live:

Lemma 5.2.11

Suppose M is a model and □W ⊨ ThyLive (Figure 7). Suppose E ∈ Event is an event and l ∈ Learner. Then

⊨□↓l (live ∧E) implies ⊨□↓l (live ∧□↓l E).

In words: if an l-quorum of live participants perform E, then eventually an l-quorum of live participants knows that an l-quorum of participants performed E.

Proof

Suppose ⊨□↓l (live ∧E). Unpacking Remark 3.6.7(2) there exists an l-quorum O ∈ ς(l) such that p,⸸, H ⊨ live ∧↓E for every p ∈O. Using (Knowledge□↓) at each p ∈O we get p,⸸, H ⊨ live ∧↓□↓l E (we have ↓ instead of ↕ on the right because this is at the end of time, so the two are equivalent by Lemma 5.2.7). It follows using Lemma 5.2.9(3) that ⊨□↓l (live ∧□↓l E) as required.End of proof

Remark 5.2.12 (Design choice).

Our theory of liveness in Figure 7 does not exclude an empty model as per Example 3.3.5. This is a model with H = ∅, in which there are no event-tuples in history and, intuitively, nothing happens.

Arguably this is pathological — in what sense is a participant who does nothing ‘live’ – and if the reader agrees then it is easy to add an axiom stating that every live participant performs some action. Using Lemma 3.5.3 we can concisely capture this idea as the following rather elegant axiom:

(LiveActive) ⤒→□(live ⇒↓⊤) or equivalently □(live ⇒↕⊤).

We omit this from Figure 7 just because we do not need it for any of our correctness proofs. But it would cost nothing to add this axiom, if required.

6. THEORY ThyHBB1

6.1. What a theory is, and how is it executable

Remark 6.1.1

Depending on the point of view, a theory in our logic is either:

(1) an algorithm written in declarative programming style — if the point of view is that declarative programming comes first, and an embedding in step-by-step execution comes after — or

(2) a description of a concrete algorithm in a declarative programming style — this is equivalent to the previous point of view, but it puts step-by-step execution first and considers declarative code to be a description of what the real implementation actually does,47 or

(3) an abstract specification of a protocol — if the point of view is that formal specification is a thing in its own right, which may be satisfied by many possible implementations, declarative or otherwise.

In the case of ThyHBB1, ThyHBB2, and ThyHBB3 of this paper, step-by-step executables can be quite directly extracted from the theories as written, as per Remark 6.1.2; thus, the use our logic the theories is according to the “algorithm written in declarative programming style” philosophy enumerated above.

But also, we use the logic to write correctness properties, and these are are more akin to the ‘abstract specification’ philosophy.

Thus, our framework is flexible and by design it can accommodate multiple levels of abstraction, depending on what detail we want to include in our predicates. In whichever case, what matters is that the logical theory should cleanly capture whatever essential detail matters to us for a given use-case at a given moment.

Remark 6.1.2

The theories ThyHBB1, ThyHBB2, and ThyHBB3 might look abstract at first glance, but this is somewhat deceptive. They are also surprisingly concrete, and can be compiled to a step-by-step executable without too much difficulty. We just have to look at the axioms in a particular way.

For example, axioms (Echo?), (EchoNE), and (Echo!) correspond to an execution rule like one of the following:

— Echo the first proposal you hear of, and then don’t echo any more, or

— Echo precisely one of the proposals that you hear about — and don’t wait forever to do so, or

— Listen to the network for 10 seconds and then either echo a value you see most other participants echoing (bearing in mind that an echo implies a proposal), and after that just echo the first proposed value you hear of ,

— ...and so on.

All of the above satisfy axioms (Echo?), (EchoNE), and (Echo!) and are therefore valid implementations of the Echo part of the theory.

This is no different from any other high-level language, e.g. in Python we might write mylist.sort() and not worry at all by which specific algorithm the list gets sorted; we just know that it gets sorted. “.sort()” is a logical specification, masquerading as imperative programming!

Axioms for the other message-types differ only in their complexity. E.g. for (Deliver?) and (Deliver!), the natural rule is to deliver the moment we observe a quorum of votes. We will return to this in a bit more detail in Remark 6.2.7.

6.2. Definition of the theory

Remark 6.2.1

Sections 6, 7, and 8 share a common structure. We take a moment to spell it out:

— Define a logical theory — ThyHBB1, ThyHBB2, and ThyHBB3 respectively — which we can view as algorithms written directly in declarative programming style as per the discussion in Subsection 6.1, and from which concrete step-by-step executable protocols can be extracted.

— Fix a model M of that theory for the rest of the Section. Perhaps discuss the axioms.

— Prove Soundness/Agreement, then a Cascade Termination property, and then a Happy Termination property. We gather the result for Theorems 6.2.6 (for ThyHBB1), 7.1.3 (for ThyHBB2), and 8.2.3 (for ThyHBB3).

— Discuss, and compare and contrast where appropriate with the other theories.

Our treatment of ThyHBB1 will be most detailed. Then, as we get used to the mathematics, we may elide routine details.

Definition 6.2.2 (Theory ThyHBB1).

(1) Assume a signature (Definition 3.1.1) with event-symbols propose, echo, vote, and deliver, and with predicate-symbols live and safe.48

(2) Define ThyHBB1 in this signature to be the theory with axioms as per Figure 8.

(3) For the rest of this Section, we fix a model M of ThyHBB1, meaning that □W ⊨ ThyHBB1 as per Definition 5.2.1.

Notation 6.2.3

Here and in ThyHBB2, we will read w ⊨ deliver(l′, l, v) as place(w) delivers v for (l′, l). We will call l the source learner and l′ the reporting learner.49

Remark 6.2.4

We make some general observations about how ThyHBB1 generalises Bracha Broadcast. All three of our heterogeneous protocols generalise Bracha Broadcast’s quorums, such that there are multiple learners and each learner has its own quorum system — i.e. one set of trust assumptions

— that may be different from that of a distinct learner. This is by design: it is what makes our setting ‘heterogeneous’. Therefore, deliveries of values at the end of the protocol must be relative to a specific learner and its quorum system. Several generalisations are possible here. In ThyHBB1 from Figure 8 we have a notion of delivering a value for a pair of learners: as per Notation 6.2.3 deliver(l′, l, v) is read ‘deliver v for (l′, l)’.

Intuitively this means that

the delivering participant has observed an l′-quorum of participants who have observed an l-quorum of participants who have observed propose(v).50

This makes the two-round structure from Bracha’s original protocol explicit, in that delivery identifies which set of trust assumptions is used in each round.

We call l the source learner because its trust assumptions are used to determine when we have observed a quorum of echo (and thus propose) messages; we call l′ the reporting learner because its trust assumptions are used to determine when we have observed a quorum of vote messages.

Backward rules (HBB) (Echo?) echo(v) ⇒♢↓propose(v)(Vote?) vote(l, v) ⇒(safe(l) ∧□↓l echo(v))(Deliver?) deliver(l′, l, v) ⇒□↓l′ vote(l, v)Other rules Include axioms of ThyLive from Figure 7 (EchoNE) echo(v) ⇒↓echo(v′) ⇒v=v′(Safe) safe(l) ⇔((∃01v.♢↓propose(v)) ∨∀l′.♢ll′ seq)Forward rules (Echo!) (live ∧♢↓propose(v)) ⇒∃v′.↕echo(v′)(Vote!) ⇕safe(l) ⇒(live ∧□↓l echo(v)) ⇒↕vote(l, v)(Deliver!) (live ∧□↓l′ vote(l, v)) ⇒↕deliver(l′, l, v) Recall that ↕(sometime) and ⇕(everytime) are from Figures 5 and 6.
Fig. 8: Theory ThyHBB1 (Definition 6.2.2)

(1) Happy Termination

If l ∈Learner and ⊨□l live and ⊨∃1v.♢↓propose(v) then⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, l, v).

In words: suppose there is a live l-quorum and suppose precisely one value is proposed. Then if some live participant finds out about that proposed value, then every live participant eventually delivers.

(2) Cascade Termination If l′ 1, l′ 2, l ∈ Learner and v ∈ Value and ⊨♢l′ 1l′ 2 ⊤ and ⊨ safe(l) and ⊨□l′ 2 live then

⊨♢↓deliver(l′ 1, l, v) ⇒live ⇒↕deliver(l′ 2, l, v).

In words: suppose l′ 1 and l′ 2 have nonempty quorum intersections and l is safe and there is a live l′ 2-quorum. Then if some participant delivers v for (l′ 1, l) then every live participant delivers v for (l′ 2, l).

(3) Soundness / Agreement If l1, l2, l′ 1, l′ 2 ∈ Learner and v1, v2 ∈ Value and ⊨♢l′ 1l′ 2 seq then

⊨♢↓deliver(l′ 1, l1, v1) ⇒♢↓deliver(l′ 2, l2, v2) ⇒v1=v2.

In words: suppose l′ 1 and l′ 2 have sequential quorum intersections. Then if some participant delivers v1 for (l′ 1, l1) and another delivers v2 for (l′ 2, l2), then v1 = v2.

Fig. 9: Correctness properties for ThyHBB1 (Theorem 6.2.6)
Remark 6.2.5

The axioms from Figures 8, 10, and 12 fall into three groups:

— backward rules have names ending in ?,

— forward rules have names ending in !, and

— other rules.

We briefly explain this design (without going into details of specific rules; that discussion comes later):

— Backward rules: ‘if we observe X, then we must have observed Y ’. (Echo?) is a typical backward rule. It says that if a participant does echo(v) then it must know of a participant that did propose(v).51 (Vote?) and (Deliver?) follow a similar pattern.

— Forward rules: ‘if X happens, then Y happens’.
These are not just the backward rules in reverse, because participants might fail or have choices in how to proceed, so forward rules tend to be a bit more complex than backward rules. A case in point is (Echo!), which has liveness conditions and also a choice ∃v′; if a participant observes several propose messages, it is supposed to pick one to eventually echo.
An intriguing subtlety to the forward rules is that they are not really forward, at least not in the sense of time. For, consider that (Echo!) has a ↕ modality on its conclusion. Axiomatic validity is evaluated using the □W ⊨ validity judgement from Figure 4, meaning that for every w ∈ World(M) if w ⊨ (live ∧♢↓propose(v)) then there exists a v′ such that for some w′ ∈H with place(w′) = place(w) we have w′ ⊨ echo(v′). However, there is no condition on how time(w) and time(w′) relate; for example it could even be that time(w′) ⊊ time(w). This might seem odd, but remember that the backward rule (Echo?) still gives some guarantees. In particular, by (Echo?) there exists a w′′ ∈ World(M) such that w′′ ⊨ propose(v′).
It is nevertheless remarkable that even with these somewhat weak conditions, we obtain a full suite of correctness results.

— Other rules These represent assorted definitions, structural requirements on the model, or requirements on the protocol. In the case of ThyHBB1 these consist of:

— ThyLive, a structural requirement on the model (see Subsection 5.2),

— (EchoNE), a specific restriction on the protocol (see Remark 6.3.1), and

— (Safe), which defines the behaviour of a predicate safe (see Remark 6.3.2).

Theorem 6.2.6

In Figure 9 we collect the correctness properties we will require of our model M such that □W ⊨ ThyHBB1, for ease of reference.

Proof

The relevant results are Propositions 6.6.3, 6.5.5, and 6.4.1 respectively. Proofs and discussion will follow.End of proof

Remark 6.2.7

Continuing Remark 6.1.2, we can extract a more traditionally-presented protocol from the axioms as follows, where we interpret events as messages:

(1) A proposer broadcasts propose(v) for some value v.52

(2) p broadcasts echo(v) for precisely one proposed value, provided it observes any proposals at all.

(3) If p receives an l-quorum of echo(v) messages and l is safe, then it broadcasts vote(l, v). p considers l to be safe when at least one of the following conditions holds:

— p only knows of at most one value that has been proposed.

— For every learner l′ and every l-quorum and l′-quorum, there is a participant in their intersection whom p has observed to be sequential.

This verbal description just spells out the content of axiom (Safe) in Figure 8.

(4) If p receives an l′-quorum of vote(l, v) messages then it broadcasts deliver(l′, l, v).

It might help to spell out the intuitive logical content of each broadcast. We can write:

— propose(v) means I propose v.

— echo(v) means I saw someone propose v.

— vote(l, v) means I saw an l-quorum of participants who saw someone propose v, and l is a safe learner so far as I know.

— deliver(l′, l, v) means I saw an l′-quorum of participants who each believed l is a safe learner at a time when they saw an l-quorum of participants who saw someone propose v.

6.3. Further discussion of some ThyHBB1 axioms

Remark 6.3.1 (The (EchoNE) rule).

ThyHBB1 from Figure 8 includes axiom (EchoNE), that

echo(v) ⇒↓echo(v′) ⇒v=v′.

Intuitively, this expresses that a sequential participant only ever echoes at most one value. (EchoNE) does permit a sequential participant to echo the same value multiple times, but it will not echo two distinct values one after the other.

This does not exclude hostile behaviour: a nonsequential participant can echo distinct values, just so long as the relevant event-tuples are not related by ≪. This corresponds to p broadcasting echo(v) to one group of participants, and echo(v′) to another group of participants, without telling one group about the value that it broadcast to the other. In the literature this is called equivocation, defined informally as to make “conflicting statements to different processes” [CJKR12] or to “lie in different ways to different clients or servers” [CMSK07].53

‘NE’ is short for ‘non-equivocation’, and non-equivocation axioms will be ubiquitous in our theories: ThyHBB2 from Figure 10 and ThyHBB3 from Figure 12 have the identical axiom (EchoNE), and ThyHBB3 includes a (VoteNE) axiom.

One thing to note is that our axioms are quite precise about what cannot be equivocated: just echo messages for ThyHBB1 and ThyHBB2, and both echo and vote messages in ThyHBB3. We impose no further non-equivocation conditions, and this is a feature, because it means that our correctness results are robust against any other equivocation.

Remark 6.3.2 (Axiom (Safe)).

As touched on in Remark 6.2.7, (Safe) characterises p, x, H ⊨ safe(l) as holding when (as viewed from p, x, H)

— if two or more values have been proposed,

— then l has sequential quorum intersections with all other learners (Notation 4.1.2), meaning that for every l-quorum O and every learner l′ (including l) and every l′-quorum O′, there exists q ∈O∩O′ such that q,⸸, H ⊨ seq.

The disjunct in (Safe) is there to give us the Happy Termination property in Proposition 6.6.3, and specifically to give us Lemma 6.6.2: that if at most one value is proposed then every learner is safe.

Note from Figure 8 that being safe depends on quorum intersections being sequential. But the sequentiality condition is overspecified: sequentiality applies to all maybe-events, but in this protocol we only care about nonsequential echo events for distinct values.54 If only one value is proposed then that is impossible.

Remark 6.3.3

We study the fine structure of the (Echo!) axiom.

This expresses that if a live participant knows of a propose(v) then at some time that participant will perform echo(v′) for some v′ (which need not be equal to v). We mention a few subtleties to how this is constructed:

(1) In full, (Echo!) is as follows — we just write out the implicit universal quantification over the v:

∀v.(live ⇒♢↓propose(v) ⇒∃v′.↕echo(v′)).

(2) This axiom is wrong:

(live ∧♢↓propose(v)) ⇒↕echo(v′)

This is wrong because by (EchoNE) a participant should echo at most one value. If a proposer proposes two values, each other participant is supposed to pick one value and echo at most that value (and no other).

(3) This axiom is correct and equivalent to what is written:

(live ∧♢↓propose(v)) ⇒↕∃v′.echo(v′).

(We flip the existential quantifier ∃v′ and the sometime modality ↕.) While both forms are correct, as a matter of style and convenience here and elsewhere, we will follow a policy of putting quantifiers outside modalities where possible. This means that (working top-down through the predicate) we get to a proposition sooner rather than later.

Remark 6.3.4 (A design alternative).

We note in passing that (EchoNE) from Figure 8 — we recall it here for convenient reference

echo(v) ⇒↓echo(v′) ⇒v=v′

— is not the only possible non-equivocation axiom. We could impose a stronger condition:

(EchoNE’) echo(v) ⇒♢↓echo(v′) ⇒v=v′.

All of our correctness properties would work just as well. To see the difference between (EchoNE’) and (EchoNE), consider the following history structure, which we present informally in derivation tree style, where ς(p) = ς(q) = {{p, q}} (so there is in effect only one learner). This satisfies (EchoNE) but not (EchoNE’):

p ⊢propose(0) p ⊢echo(0) q ⊢propose(1) q ⊢echo(1)

We prefer (EchoNE) precisely because it is a weaker assumption; the weaker assumption means that our correctness results are stronger.

Morally (this is not a precise mathematical statement) (EchoNE’) corresponds to an algorithm where we echo at most one of any of the values that have been proposed.55 (EchoNE) corresponds to an algorithm where we echo at most one of the values that we hear proposed, but it need not necessarily be the first one that we hear about.

6.4. Agreement

Proposition 6.4.1 (Soundness / Agreement).

Suppose l1, l2, l′ 1, l′ 2 ∈ Learner and v1, v2 ∈ Value and

⊨♢l′ 1l′ 2 seq.

Then

⊨♢↓deliver(l′ 1, l1, v1) ⇒♢↓deliver(l′ 2, l2, v2) ⇒v1=v2.
Proof

If v1 = v2 then there is nothing to prove, so it will be convenient (for the step marked (∗∗) below) to assume v1 ≠ v2 and derive a contradiction. We reason as follows:

Agreement derivation⊨♢↓deliver(l′ 1, l1, v1) ∧♢↓deliver(l′ 2, l2, v2)=⇒⊨□↓l′ 1 vote(l1, v1) ∧□↓l′ 2 vote(l2, v2) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓(vote(l1, v1) ∧↓vote(l2, v2))∨⊨♢↓(vote(l2, v2) ∧↓vote(l1, v1))Prop 5.1.5(3), v1≠v2, ⊨♢l′ 1l′ 2 seq=⇒w ⊨vote(l2, v2) ∧↓vote(l1, v1) 2nd disjunct(∗), some w ∈H by Remark 3.6.5(3)=⇒w ⊨safe(l2) ∧□↓l2 echo(v2) ∧□↓l1 echo(v1) (Vote?), Lemma 4.2.3(2)=⇒w ⊨♢l2l1 seq ∧□↓l2 echo(v2) ∧□↓l1 echo(v1) (Safe)(∗∗), v1≠v2=⇒v1 = v2Prop 5.1.5(3), v1≠v2, (EchoNE)=⇒⊥ v1≠v2

We expand on two steps in the derivation above:

(∗) Just above the step marked (∗), we have a disjunction between ⊨♢↓(vote(l1, v1) ∧↓vote(l2, v2)) or ⊨♢↓(vote(l2, v2) ∧↓vote(l1, v1)). The first possibility is precisely symmetric with the second, so we just consider the second disjunct. (∗∗) At the step marked (∗∗) we go from safe(l2) to ♢l2l1 seq.

The behaviour of safe is determined by (Safe) in Figure 8. This characterises safe using two disjuncts ∃01v.♢↓propose(v) or ∀l′.♢ll′ seq. The former disjunct is not valid because we are at a world at which we know of (quorums of, and thus) some past echo(v2) and echo(v1), and using (Echo?) we know of some past propose(v2) and propose(v1) — and we assumed v1 ≠ v2. Thus, the latter disjunct must be valid.

We note v1 ≠ v2 using Proposition 5.1.5(3) above because the result requires distinct events.End of proof

6.5. Cascade Termination

Lemma 6.5.1

Suppose w′ ≪−w ∈ World(M) and l ∈ Learner. Then:

(1) w ⊨ safe(l) implies w′ ⊨ safe(l).

(2) w ⊨ safe(l) ⇒⇓safe(l).

Proof

From the definition of safe in Figure 8, using Proposition 5.1.4 (seq monotone).End of proof

Lemma 6.5.2

Suppose ϕ and ψ are closed predicates and l ∈ Learner. Then:

(1) ⊨□↓l ϕ and □W ⊨ϕ ⇒↕ψ implies ⊨□↓l ψ.

(2) If □W ⊨ ThyLive then

⊨□↓l (live ∧ϕ) and □W ⊨(live ∧ϕ) ⇒↕ψ implies ⊨□↓l (live ∧ψ).
Proof

We consider each part in turn:

(1) Suppose ⊨□↓l ϕ. By Remark 3.6.7(2) this means that there is an l-quorum O such that for each p ∈O there exists wp ∈H@p such that wp ⊨ϕ. By our assumptions wp ⊨ϕ ⇒↕ψ for each

p ∈O, and so by Lemma 3.6.4(1) there exists some w′ p ∈H@p such that w′ p ⊨ψ. This is true of every p ∈O, and ⊨□↓l ψ follows.

(2) First, note from Lemma 5.2.9(2) that

□W ⊨(live ∧ϕ) ⇒↕ψ implies □W ⊨(live ∧ϕ) ⇒↕(live ∧ψ).

We can now just use part 1 of this result.End of proof

Lemma 6.5.3

Suppose ϕ and ψ are closed predicates and □W ⊨ ThyLive. Then

⊨live ⇒↕ϕ and □W ⊨(live ∧ϕ) ⇒↕ψ implies ⊨live ⇒↕ψ.
Proof

We unpack definitions using Figures 4 (validity), 5 (syntactic sugar) and 6 (its denotation):

— By Figure 4 and Lemma 3.6.4(1), ⊨ live ⇒↕ϕ means that for every live participant56 p ∈ Pnt there exists some wp ∈H@p (Definition 3.4.7) such that wp ⊨ϕ.

— By Figure 4, □W ⊨ (live ∧ϕ) ⇒↕ψ means that for every w ∈ World(M), and thus in particular for every w ∈H, if place(w) is live (by (LiveAlways) the time does not matter) then w ⊨ϕ implies that there exists some event-tuple w′ ∈H such that place(w) = place(w′) and w′ ⊨ψ.

— ⊨ live ⇒↕ψ holds when for every live participant p ∈ Pnt there exists some wp ∈H@p such that wp ⊨ψ.

Putting the first two assumptions together we obtain the required conclusion.End of proof

Lemma 6.5.4

Suppose ϕ is a closed predicate and l ∈ Learner. Then

⊨□l ↕ϕ if and only if ⊨□↓l ϕ.
Proof

By Figure 4, ⊨□l ↕ϕ means p,⸸, H ⊨↕ϕ for every p ∈O for O some l-quorum. Using Lemma 5.2.7 we can simplify this to ⊨□l ↓ϕ, and by Figure 5 this is just ⊨□↓l ϕ as required.End of proof

Proposition 6.5.5 (Cascade Termination).

Suppose l′ 1, l, l′ 2 ∈ Learner and v ∈ Value. Suppose further that

⊨♢l′ 1l′ 2 ⊤ and ⊨safe(l) and ⊨□l′ 2 live.

In words: l′ 1 and l′ 2 have nonempty quorum intersections (Notation 4.1.2) and l′ 2 has a live quorum. Then

⊨♢↓deliver(l′ 1, l, v) ⇒live ⇒↕deliver(l′ 2, l, v).

As corollaries,

⊨♢↓deliver(l′ 1, l, v) ⇒□↓l′ 2 deliver(l′ 2, l, v) and⊨♢↓deliver(l′ 1, l, v) ⇒♢↓deliver(l′ 2, l, v).
Proof

We reason as follows:

⊨♢↓deliver(l′ 1, l, v) =⇒⊨□↓l′ 1 vote(l, v) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓(live ∧vote(l, v)) Prop 5.2.10, ⊨♢l′ 1l′ 2 ⊤∧□l′ 2 live=⇒⊨□↓l′ 2 (live ∧♢↓vote(l, v)) Prop 5.2.8, ⊨□l′ 2 live=⇒⊨□↓l′ 2 (live ∧□↓l echo(v)) (Vote?), Lemma 4.2.3(1)=⇒⊨□↓l′ 2 (live ∧safe(l) ∧□↓l echo(v)) Lemma 6.5.1, ⊨safe(l)=⇒⊨□↓l′ 2 (live ∧vote(l, v)) Lemma 6.5.2(2), (Vote!)=⇒⊨live ⇒↕□↓l′ 2 vote(l, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l′ 2, l, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l′ 2 ↕deliver(l′ 2, l, v) ⊨□l′ 2 live=⇒⊨□↓l′ 2 deliver(l′ 2, l, v) Lemma 6.5.4=⇒⊨♢↓deliver(l′ 2, l, v) Lemma 4.2.1(1)End of proof

6.6. Happy Termination

Lemmas 6.6.1 and 6.6.2 will help us prove Proposition 6.6.3.

Lemma 6.6.1

⊨∃1v.♢↓propose(v) implies □W ⊨ (live ∧♢↓propose(v)) ⇒↕echo(v).

Proof

Suppose ⊨∃1v.♢↓propose(v) (i.e. precisely one value is proposed). To prove □W ⊨ (live ∧ ♢↓propose(v)) ⇒↕echo(v) it suffices by Figure 4 to show for every w ∈ World(M) that w ⊨ live ∧♢↓propose(v) implies w ⊨↕echo(v).

So suppose

w ⊨live ∧♢↓propose(v).

Using (Echo!)

w ⊨↕echo(v′) for some v′ ∈ Value.

It follows using (Echo?) that ⊨♢↓propose(v′), but we assumed ⊨∃1v.♢↓propose(v), so v = v′ and we are done.End of proof

Lemma 6.6.2

Suppose l ∈ Learner. Then

⊨∃01v.♢↓propose(v) ⇒⇕safe(l).

In words: if there exists at most one proposed value, then every learner is safe.

(⇕ is from Figures 5 and 6 and we check its denotation in Lemma 3.6.4(2).)

Proof

By the construction of safe in Figure 8.End of proof

Proposition 6.6.3 (Happy Termination).

Suppose l ∈ Learner and

⊨□l live and ⊨∃1v.♢↓propose(v).

Then

⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, l, v).

As corollaries,

⊨♢↓(live ∧♢↓propose(v)) ⇒□↓l deliver(l, l, v) and⊨♢↓(live ∧♢↓propose(v)) ⇒♢↓deliver(l, l, v).
Proof

We reason as follows:

⊨♢↓(live ∧♢↓propose(v)) =⇒⊨♢↓(live ∧echo(v)) Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧♢↓echo(v)) Proposition 5.2.8, ⊨□l live=⇒⊨□↓l (live ∧♢↓propose(v)) (Echo?), Lemma 4.2.2=⇒⊨□↓l (live ∧echo(v)) Lemma 6.5.2(2) & Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧□↓l echo(v)) Lemma 5.2.11=⇒⊨□↓l (live ∧□↓l echo(v)) ∧⇕safe(l) Lemma 6.6.2, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧vote(l, v)) Lemma 6.5.2(2), (Vote!)=⇒⊨live ⇒↕□↓l vote(l, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l, l, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l ↕deliver(l, l, v) ⊨□l live=⇒⊨□↓l deliver(l, l, v) Lemma 6.5.4=⇒⊨♢↓deliver(l, l, v) Lemma 4.2.1(1)End of proof
Remark 6.6.4

The statement of Proposition 6.6.3 contains a nested pair of knowledge modalities ♢↓: ⊨♢↓(live ∧♢↓propose(v)). The outermost one is omniscient and the inner one is relative to a place and a (non-end-of-time) time. It might be helpful to unpack this.

The outer ♢↓ is omniscient, in the sense that it is evaluated at the end of time, so it has the value of

there exists some w ∈H at some live participant p, and ...

Note the use of ‘there exists’ above. The inner ♢↓ takes the local view and has the value of

at w, p knows of a propose(v) event.

Note the use of ‘at w, p knows’ above. This is non-omniscient because we evaluate at w ∈H. Putting this together, we arrive at the full meaning of ⊨♢↓(live ∧♢↓propose(v)):

There exists some event by a live participant such that at the time of that event the live participant knows of a past propose(v) message.

That is a bit of a mouthful, and we can shorten it (with some mild loss of precision) to:

Some live participant learns of a propose(v).

6.7. Further discussion

Remark 6.7.1

Recall from Notation 6.2.3 and Remark 6.2.4 that we read p, x, H ⊨ deliver(l′, l, v) as ‘p delivers v for (l′, l)’, and this implies that the delivering participant p has observed an l′-quorum of participants who observed an l-quorum of participants who observed propose(v).

Let us reflect on the correctness properties from Figure 9:

— The Agreement property (Proposition 6.4.1) is strong: provided l′ 1 and l′ 2 have sequential quorum intersections (Notation 4.1.2), we have a guarantee that any p and p′ that deliver values for (l′ 1, l1) and (l′ 2, l2) respectively, will agree on the value that they deliver.

— The Cascade Termination guarantee (Proposition 6.5.5) is weak in the following sense: In a situation where two values v and v′ have been proposed, an adversary could wait for some p to deliver v for (l′ 1, l), for some l. Then the adversary creates a nonsequential quorum intersection for that l, and advertises it to all other participants. This would prevent Proposition 6.5.5 from making any useful predictions about deliveries for (l′ 2, l) for any l′ 2, because the condition ⊨ safe(l) would no longer hold.

— The Happy Termination guarantee (Proposition 6.6.3) is as one would expect; no weaker or stronger than what makes sense.

Protocols ThyHBB2 and ThyHBB3 will go some way to correcting the weak Cascade Termination guarantee of ThyHBB1, or rather, they will make different trade-offs. See a comparative discussion of ThyHBB1 and ThyHBB2 in Remark 7.2.1.

Remark 6.7.2

A few words on how the predicate symbols live and safe are used in ThyHBB1.

(1) Both live() (we drop the empty brackets and write this just as ‘live’) and safe(l) are atomic predicates (Definition 3.1.1(2)) in the signature of ThyHBB1 (Definition 6.2.2(1)).
We have not imposed an arity system on our syntax, but we use live as a 0-ary proposition which is true at a live participant. The property of being live is a property of a place/participant, but not a time, in a sense made formal by axiom (LiveAlways).
In contrast, the property of a learner l being safe is a property of time, as per axiom (Safe). A learner l is only safe at a participant p and at a time H and it might become not-safe at p at a later H′ — unless H = H in which case the system is omniscient and l is indeed safe until the end of time because, well, we are at the end of time and l is safe. Regardless, the content of the assertion safe(l) is that l is safe here and until now, i.e. it is a local assertion, whereas the content of the assertion live is that here is live, forever, i.e. it is an omniscient assertion about behaviour now and into the future.

(2) Note that propose, echo, vote, and deliver are event-symbols, not predicate symbols. Events are very similar to atomic predicates but they are handled differently in the denotation; see the discussion in Remark 3.1.4.

Remark 6.7.3

Sequentiality is central to our arguments. We assume that all messages are cryptographically signed, so forging messages is impossible, so what gives our mathematics its flavour is (mis)behaviour through (non)sequentiality. Thus in our proofs of correctness, there is a focus on intersection properties of quorums, and on sequentiality properties of participants within those quorums.

7. THEORY ThyHBB2

ThyHBB1 is not the only way to generalise Bracha’s reliable broadcast. Here we present ThyHBB2, a slightly simpler theory that makes different trade-offs between liveness and agreement.

7.1. Definition of the theory

Definition 7.1.1 (Theory ThyHBB2).

(1) Assume a signature with event-symbols propose, echo, vote, and deliver, and with a predicate-symbol live.

(2) Define ThyHBB2 to be the theory with axioms as per Figure 10.

(3) For the rest of this Section, we fix a model M of ThyHBB2, meaning that □W ⊨ ThyHBB2 as per Definition 5.2.1.

Remark 7.1.2

As we did in Remark 6.2.7 for ThyHBB1, we can extract an abstract protocol from the axioms as follows, where we interpret events as messages:

(1) A proposer broadcasts propose(v) for some value v.

(2) p broadcasts echo(v) for precisely one proposed value, provided it observes any proposals at all.

(3) If p receives an l-quorum of echo(v) messages, then it broadcasts vote(l, v).

(4) If p receives an l′-quorum of vote(l, v) messages then it broadcasts deliver(l′, l, v).

We spell out the intuitive logical content of each broadcast:

— propose(v) means I propose v.

— echo(v) means I saw propose v.

— vote(l, v) means I saw an l-quorum of participants who each saw someone propose v.

— deliver(l′, l, v) means I saw an l′-quorum of participants who each saw an l-quorum of participants who each saw someone propose v.

Backward rules (HBB) (Echo?) echo(v) ⇒♢↓propose(v)(Vote?) vote(l, v) ⇒□↓l echo(v)(Deliver?) deliver(l′, l, v) ⇒□↓l′ vote(l, v)Other rules Include axioms of ThyLive from Figure 7 (EchoNE) echo(v) ⇒↓echo(v′) ⇒v=v′Forward rules (Echo!) (live ∧♢↓propose(v)) ⇒∃v′.↕echo(v′)(Vote!) (live ∧□↓l echo(v)) ⇒↕vote(l, v)(Deliver!) (live ∧□↓l′ vote(l, v)) ⇒↕deliver(l′, l, v)
Fig. 10: Theory ThyHBB2 (Definition 7.1.1)

(1) Happy Termination

If l ∈Learner and ⊨□l live and ⊨∃1v.♢↓propose(v) then⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, l, v).

In words: suppose there is a live l-quorum and suppose precisely one value is proposed. Then if some live participant finds out about that proposed value, then every live participant eventually delivers.

(2) Cascade Termination If l′ 1, l′ 2, l ∈ Learner and v ∈ Value and ⊨♢l′ 1l′ 2 ⊤ and ⊨□l′ 2 live then

⊨♢↓deliver(l′ 1, l, v) ⇒live ⇒↕deliver(l′ 2, l, v).

In words: suppose l′ 1 and l′ 2 have nonempty quorum intersections and there is a live l′ 2-quorum. Then if some participant delivers v for (l′ 1, l) then every live participant delivers v for (l′ 2, l).

(3) Soundness / Agreement

If l1, l2, l′ 1, l′ 2 ∈Learner and v1, v2 ∈Value and ⊨♢l1l2 seq then ⊨♢↓deliver(l′ 1, l1, v1) ⇒♢↓deliver(l′ 2, l2, v2) ⇒v1=v2.

In words: suppose l1 and l2 have sequential quorum intersections. Then if some participant delivers v1 for (l′ 1, l1) and another delivers v2 for (l′ 2, l2), then v1 = v2.

Fig. 11: Correctness properties for ThyHBB2 (Theorem 7.1.3)
Theorem 7.1.3

We collect the correctness properties for ThyHBB2 in Figure 11, for ease of reference.

Proof

The relevant results are Propositions 7.3.3, 7.3.2, and 7.3.1 respectively.End of proof

7.2. Discussion

Before we come to the proofs in Subsection 7.3, we take some time to compare and contrast ThyHBB1 and ThyHBB2. The differences are real, but not necessarily easy to spot.

Remark 7.2.1

ThyHBB1 and ThyHBB2 have similarities, but also significant differences:

— ThyHBB1 and ThyHBB2 are similar in that they have the same event symbols: propose, echo, vote, and deliver. In both theories, the delivery assertion deliver(l′, l, v) can be read as

‘an l′-quorum of participants believe that an l-quorum of participants echoed v’,

and we say (as per Remark 6.2.4) that we deliver v for (l′, l). This makes explicit which learner’s trust assumptions (quorums) are used in the echo and vote stages, reflecting the fact that our protocol is heterogeneous and may involve multiple trust assumptions.

— ThyHBB2 is simpler in the sense that it does not use (or need) the predicate safe. As a result, the axiomatisation in ThyHBB2 is slightly smaller.

— The Agreement property for ThyHBB2 (Proposition 7.3.1) differs significantly from that for ThyHBB1 (Proposition 6.4.1). We compare the two Agreement properties in sketch form:

ThyHBB1♢l′ 1l′ 2 seq =⇒♢↓deliver(l′ 1, l1, v1) =⇒♢↓deliver(l′ 2, l2, v2) =⇒v1 = v2ThyHBB2♢l1l2 seq =⇒♢↓deliver(l′ 1, l1, v1) =⇒♢↓deliver(l′ 2, l2, v2) =⇒v1 = v2.

The difference above is highlighted:

— the precondition ♢l′ 1l′ 2 seq in ThyHBB1 assumes sequential quorum intersections between l′ 1 and l′ 2, which are the learners who we want to agree; whereas

— the precondition ♢l1l2 seq in ThyHBB2 assumes sequential quorum intersections between the learners for whom we have the original quorums of echoes.

Arguably ♢l1l2 seq is a stronger condition than ♢l′ 1l′ 2 seq — making the Agreement property of ThyHBB2 in some sense weaker than that of ThyHBB1 — because:

— in ThyHBB2, if an attacker creates a nonsequential quorum intersection between l1 and l2 (e.g. by causing some participant pl1,l2 in that quorum intersection to reveal nonsequential behaviour and ensuring that this nonsequential behaviour is known to all participants)57 then no l′ 1 and l′ 2 are guaranteed to agree in delivering values based on l1 and l2; whereas

— in ThyHBB1, an attacker wishing to destroy agreement would have to attack the quorum intersections between l′ 1 and l′ 2 directly, for each l′ 1 and l′ 2. This is arguably harder because it may requires an attacker to control more participants: one pl′ 1,l′ 2 for each each pair l′ 1 and l′ 2, versus just controlling one single pl1,l2.

— The Cascade Termination guarantee in Proposition 7.3.2 for ThyHBB2 is stronger than that for ThyHBB1 in Proposition 6.5.5. We just need the two learners to have nonempty quorum intersections. There is no safety restriction, as we needed for Proposition 6.5.5 for ThyHBB1. So ThyHBB2 is intuitively ‘more live 2’ than ThyHBB1.

So intuitively ThyHBB1 and ThyHBB2 are cut from similar cloth but they make different trade-offs:

(1) In ThyHBB1 it is relatively hard for an attacker to break agreement properties, but relatively easy for it to break the liveness 2 property, whereas

(2) in ThyHBB2 it is relatively easier for an attacker to break agreement properties, but relatively harder for it to break the liveness 2 property.

(3) The statements of the Happy Termination properties are identical, but arguably ThyHBB2 is also ‘more live 1’ than ThyHBB1, just because the (Vote!) drops the safety precondition. We compare the two (Vote!) rules for the reader’s convenience:

ThyHBB1 ⇕safe(l) ⇒(live ∧□↓l echo(v)) ⇒↕vote(l, v)ThyHBB2 (live ∧□↓l echo(v)) ⇒↕vote(l, v)

It seems likely to be easier to make progress with the second rule, because we do not require l to be safe (ThyHBB2 does not even use this concept).

So to sum this up, ThyHBB1 is less live but tends to agree where the protocol succeeds; whereas ThyHBB2 is more live but may agree less. As always, which trade-offs we prefer will depend on the use-case, our trust assumptions, and our attacker model.

7.3. Proofs of Agreement, Happy Termination, and Cascade Termination

Proposition 7.3.1 (Agreement).

Suppose l1, l2, l′ 1, l′ 2 ∈ Learner and

⊨♢l1l2 seq. Then for every v1, v2 ∈ Value,

⊨♢↓deliver(l′ 1, l1, v1) ∧♢↓deliver(l′ 2, l2, v2) implies v1 = v2.
Proof

If v1 = v2 then we are done, so suppose v1 ≠ v2. We reason as follows:

⊨♢↓deliver(l′ 1, l1, v1) ∧♢↓deliver(l′ 2, l2, v2)=⇒⊨□↓l′ 1 vote(l1, v1) ∧□↓l′ 2 vote(l2, v2) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓vote(l1, v1) ∧♢↓vote(l2, v2) Lemma 4.2.1(1)=⇒⊨□↓l1 echo(v1) ∧□↓l2 echo(v2) (Vote?)=⇒v1 = v2Prop 5.1.5(3), v1≠v2, ⊨♢l1l2 seq, (EchoNE)

We note v1 ≠ v2 using Proposition 5.1.5(3) above because the result requires distinct events.End of proof

Proposition 7.3.2 (Cascade Termination).

Suppose l′ 1, l′ 2, l ∈ Learner and

⊨♢l′ 1l′ 2 ⊤ and ⊨□l′ 2 live.

Then for every v ∈ Value,

⊨♢↓deliver(l′ 1, l, v) ⇒live ⇒↕deliver(l′ 2, l, v).

As corollaries,

⊨♢↓deliver(l′ 1, l, v) ⇒□↓l′ 2 deliver(l′ 2, l, v) and⊨♢↓deliver(l′ 1, l, v) ⇒♢↓deliver(l′ 2, l, v).
Proof

We reason as follows:

⊨♢↓deliver(l′ 1, l, v) =⇒⊨□↓l′ 1 vote(l, v) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓(live ∧vote(l, v)) Prop 5.2.10, ⊨♢l′ 1l′ 2 ⊤∧□l′ 2 live=⇒⊨□↓l′ 2 (live ∧♢↓vote(l, v)) Prop 5.2.8, ⊨□l′ 2 live=⇒⊨□↓l′ 2 (live ∧□↓l echo(v)) (Vote?), Lemma 4.2.3(1)=⇒⊨□↓l′ 2 (live ∧vote(l, v)) Lemma 6.5.2(2), (Vote!)=⇒⊨live ⇒↕□↓l′ 2 vote(l, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l′ 2, l, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l′ 2 ↕deliver(l′ 2, l, v) ⊨□l′ 2 live=⇒⊨□↓l′ 2 deliver(l′ 2, l, v) Lemma 6.5.4=⇒⊨♢↓deliver(l′ 2, l, v) Lemma 4.2.1(1)End of proof
Proposition 7.3.3 (Happy Termination).

Suppose l ∈ Learner and

⊨□l live and ⊨∃1v.♢↓propose(v).

Then for every v ∈ Value,

⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, l, v).

As corollaries,

⊨♢↓(live ∧♢↓propose(v)) ⇒□↓l deliver(l, l, v) and⊨♢↓(live ∧♢↓propose(v)) ⇒♢↓deliver(l, l, v).
Proof

We reason as follows:

⊨♢↓(live ∧♢↓propose(v)) =⇒⊨♢↓(live ∧echo(v)) Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧♢↓echo(v)) Proposition 5.2.8, ⊨□l live=⇒⊨□↓l (live ∧♢↓propose(v)) (Echo?), Lemma 4.2.2=⇒⊨□↓l (live ∧echo(v)) Lemma 6.5.2(2) & Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧□↓l echo(v)) Lemma 5.2.11=⇒⊨□↓l (live ∧vote(l, v)) Lemma 6.5.2(2), (Vote!)=⇒⊨live ⇒↕□↓l vote(l, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l, l, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l ↕deliver(l, l, v) ⊨□l live=⇒⊨□↓l deliver(l, l, v) Lemma 6.5.4=⇒⊨♢↓deliver(l, l, v) Lemma 4.2.1(1)End of proof
Remark 7.3.4

We use Lemma 6.6.1 in the proof of Proposition 7.3.3 (Happy Termination for ThyHBB2) just as we used it in Proposition 6.6.3 (Happy Termination) for ThyHBB1).

However, Lemma 6.6.1 was proved for theory ThyHBB1, whereas now we are working in theory ThyHBB2. We examine the proof of that Lemma and see that it depends only on axioms and properties that the two theories have in common, and it is entirely clear that it works equally well here, so we reuse it.

8. THEORY ThyHBB3

A quick recap is in order. Recall from Notation 6.2.3 and Remark 6.2.4 that in ThyHBB1 and ThyHBB2, the deliver event has the form deliver(l′, l, v), where we call l the source learner and l′ the reporting learner. The trust assumptions (= quorums) of the source learner are used to determine when we have observed a quorum of echo messages, and the trust assumptions of the reporting learner are used to determine when we have observed a quorum of vote messages.

This reflects and makes explicit the two-round structure from Bracha’s original protocol, and this is reasonable because in a heterogeneous setting we have design freedom in whose trust assumptions to use in each of the two rounds.

For ThyHBB3 we do things slightly differently.

The deliver event is simplified to be relative to a single learner: deliver(l, v). Structurally, this gives us liveness and agreement properties that more closely resemble those of Bracha’s original (homogeneous) broadcast algorithm. However, our setting is still heterogeneous and we are still dealing with a choice of trust assumptions; the complexity of managing that choice does not just go away.

ThyHBB3 deals with this by introducing a correlation relation .=, which expresses when learners might need to agree, and then — intuitively — we existentially quantify over an l-quorum of votes by .=-correlated chains of learners, where each chain of votes leads to a quorum of echo messages from some (existentially quantified) source learner.

We use logic to make the intuition precise. The key axioms to look at are (Vote?) and (Deliver?) in Figure 12. In particular, (Vote?) has a disjunction, between

— an l-quorum of echoes (□↓l echo(v)), and

— another vote, by an existentially-quantified .=-connected learner (∃l′ .=l.♢↓vote(l′, v)).

The right-hand disjunct lets us build an existentially quantified chain of .=-correlated learners,58 and the left-hand disjunct lets us terminate it with a quorum of echoes. Then (Deliver?) just expresses that if we deliver then we observed an l-quorum of votes, and we are done.

Of course there are many details to get just right, but we have the framework of our logic to help us and we can now proceed:

8.1. .=: the correlation relation

We give some intuition for how ThyHBB3 works. The discussion is informal and our logic will make it precise starting with Subsection 8.2.

Remark 8.1.1

We introduce the notion of a binary relation l .=l′ between learners, which we read as l correlates with l′. We may write ¬(l .=l′) as l .≠l′ and say that l does not correlate with l′.

The correlation relation .= has two properties:

(1) .= is a partial equivalence relation (transitive, symmetric, but not necessarily reflexive).

(2) If p believes that l correlates with l′, then p should know that they should have sequential quorum intersections. In symbols:

( .=seq) l .=l′ ⇒♢ll′ seq.

The contrapositive is clearer: if p knows of an intersection between an l-quorum and an l′-quorum that is not sequential (i.e. every element is nonsequential), then p believes l .≠l′ and thus that l and l′ do not correlate.59

Note that the ( .=seq) implication does not run in the other direction: just because p knows that l and l′ have sequential quorum intersections does not mean that p believes l .=l′.

To see the motivation for this, consider two points:

(1) If l and l′ do not have sequential quorum intersections then there is some pair of quorums whose intersection is entirely composed of nonsequential participants, i.e. faulty ones. That faulty intersection could be reporting one version of history to an l-quorum of participants, and another version of history to an l′-quorum of participants. Thus (intuitively) p cannot necessarily expect behaviours regarding l and l′ to correlate. This motivates ( .=seq).

(2) Now imagine we have three learners l1, l2, and l3, and suppose p believes l1.=l2 and l2.=l3. By transitivity p also believes l1.=l3. Now suppose p learns of a nonsequential quorum intersection between l1 and l3, so that p believes l1 .≠l3. By transitivity, p has to give up on at least one of l1.=l2 or l2.=l3. There is no canonical way in general to do this.60 So p just has to choose; thus even if (for example) l1 and l2 may have sequential quorum intersections, p may still need to give up on believing them to be correlated, because of nonsequential behaviour elsewhere. This is all just a mathematical way of saying that opinions can diverge, and if they do, p may have to pick a side.

The benefit of introducing .= is that we can devise a simple protocol that, in some sense, uses .= to marry the strong Agreement properties of ThyHBB1 with the strong Liveness properties of ThyHBB2. That said, our third protocol has its own distinct identity.

Remark 8.1.2

Our protocol will also include a strong assumption on quorums, namely (3twined) in Figure 12

(3twined)♢ll′l′′ ⊤

asserts that any three quorums have nonempty intersection, as per Lemma 4.1.1(2).

The terminology ‘3-twined’ follows the semitopological terminology from [GZ26], where an n-twined semitopology is one such that any n nonempty open sets (= quorums) intersect (though here, of course, the situation is slightly different because the three quorums may come from three different learners’ trust assumptions).

The 3-twined assumption does not appear in ThyHBB1 or ThyHBB2. However, assumptions of this form are extremely common — arguably they are almost universal — in the literature on (homogeneous) distributed algorithms with byzantine behaviour. Quorum intersection properties may appear explicitly with names like ‘the Q3 condition’ or ‘the B3 condition’, or they may be arithmetically implicit: e.g. authors assume some f ≥ 0 and that Pnt has size 3f + 1 and that quorums have size at least 2f + 1, which by simple arithmetic guarantees that any three quorums intersect. A discussion with references is at the start of Subsection 4.1.

Here, we have (3twined), which makes a beautiful and compact use of our logic to express precisely what is required.

8.2. Definition of the theory

Definition 8.2.1 (Theory ThyHBB3).

(1) Assume a signature with event-symbols propose, echo, vote, and deliver, and with predicate symbols live and .= (which we will write as a binary infix; thus t .=t′ is actually sugar for .=(t, t′)).

(2) Define ThyHBB3 to be the theory with axioms as per Figure 12.

(3) For the rest of this Section, we fix a model M of ThyHBB3, meaning that □W ⊨ ThyHBB3 as per Definition 5.2.1.

Remark 8.2.2

As in Remarks 6.2.7 and 7.1.2, we extract an abstract protocol from the axioms as follows, where we interpret events as messages:

(1) A proposer broadcasts propose(v) for some value v.

(2) p broadcasts echo(v) for precisely one proposed value, provided it observes any proposals at all.

(3) If p receives an l-quorum of echo(v) messages, then it broadcasts vote(l, v).

(4) If p receives a vote(l′, v) message for some l′ that correlates with l at the time, then p broadcasts vote(l, v).61

(5) If p receives an l-quorum of vote(l, v) messages then it broadcasts deliver(l, v).

We spell out the intuitive logical content of each broadcast, bearing in mind that signatures cannot be forged:

— propose(v) means I propose v.

— echo(v) means I saw propose v.

— vote(l, v) means I saw an l-quorum of participants who saw propose v, or vote(l′, v) for an l′ that correlated with l at the time.

— deliver(l, v) means I saw an l-quorum of participants, each of whom saw a correlated chain of votes leading to some l′-quorum of participants who saw propose v.

Backward rules (Echo?) echo(v) ⇒♢↓propose(v)(Vote?) vote(l, v) ⇒(□↓l echo(v) ∨∃l′ .=l.♢↓vote(l′, v))(Deliver?) deliver(l, v) ⇒□↓l vote(l, v)Other rules Include axioms of ThyLive from Figure 7 (EchoNE) echo(v) ⇒↓echo(v′) ⇒v=v′(VoteNE) vote(l, v) ⇒↓vote(l′, v′) ⇒l .=l′ ⇒v=v′(3twined)♢ll′l′′ ⊤( .=seq) l .=l′ ⇒♢ll′ seq( .=⇓) l .=l′ ⇒⇓(l .=l′)( .=symm) l .=l′ ⇒l′ .=l( .=tran) l .=l′ ⇒l′ .=l′′ ⇒l .=l′′Forward rules (Echo!) (live ∧♢↓propose(v)) ⇒∃v′.↕echo(v′)(Vote!) (live ∧□↓l echo(v)) ⇒∃v′.↕vote(l, v′)(Vote’!) (live ∧⇕(l .=l′) ∧♢↓vote(l′, v)) ⇒∃v′.↕vote(l, v′)(Deliver!) (live ∧□↓l vote(l, v)) ⇒↕deliver(l, v) Above, ⇕, ↕, and ⇓are from Figure 6 and mean ‘at every event at p’, ‘at some event at p’, and ‘at every past event at p’ respectively..= is the correlation relation from Subsection 8.1.
Fig. 12: Theory ThyHBB3 (Definition 8.2.1)

(1) Happy Termination

If l ∈Learner and ⊨□l live and ⊨∃1v.♢↓propose(v) then⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, v).

In words: suppose there is a live l-quorum and suppose precisely one value is proposed. Then if some live participant finds out about that proposed value, then every live participant eventually delivers.

(2) Cascade Termination

If l1, l2 ∈Learner and v ∈Value and ⊨□(l1.=l2) and ⊨□l2 live then⊨♢↓deliver(l1, v) ⇒live ⇒↕deliver(l2, v).

In words: suppose l1 and l2 are always and everywhere correlated and there is a live l2-quorum. Then if some participant delivers v for l1 then every live participant delivers v for l2.

(3) Soundness / Agreement

If l1, l2 ∈Learner and v1, v2 ∈Value and ⊨□(l1.=l2) then⊨♢↓deliver(l1, v1) ⇒♢↓deliver(l2, v2) ⇒v1=v2.

In words: suppose l1 and l2 are always everywhere correlated. Then if some participant delivers v1 for l1 and another delivers v2 for l2, then v1 = v2.

Fig. 13: Correctness properties for ThyHBB3 (Theorem 8.2.3)
Theorem 8.2.3

We collect the correctness properties for ThyHBB3 in Figure 13, for convenient reference.

Proof

The relevant results are Propositions 8.5.1, 8.4.5, and 8.3.1 respectively.End of proof

8.3. Agreement

Proposition 8.3.1 (Soundness / Agreement).

Suppose l1, l2 ∈ Learner. Suppose further that

⊨□(l1.=l2).

Then for every v1, v2 ∈ Value,

⊨♢↓deliver(l1, v1) ⇒♢↓deliver(l2, v2) ⇒v1=v2.
Proof

Note from ⊨□(l1.=l2) that:

— Using ( .=seq) we have ⊨♢l1l2 seq.

— Using ( .=⇓) we have ⊨□⇓(l1.=l2), i.e. by Remark 3.6.5(6) w ⊨l1.=l2 for every w ∈H.

— By ( .=symm) we also have ⊨□⇓(l2.=l1).

If v1 = v2 then we are done, so suppose v1 ≠ v2. We reason as follows:

⊨♢↓deliver(l1, v1) ∧♢↓deliver(l2, v2)=⇒⊨□↓l1 vote(l1, v1) ∧□↓l2 vote(l2, v2) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓(vote(l1, v1) ∧↓vote(l2, v2))∨⊨♢↓(vote(l2, v2) ∧↓vote(l1, v1))Prop 5.1.5(3), v1≠v2, ⊨♢l1l2 seq=⇒v1 = v2(VoteNE), ⊨□⇓(l1.=l2), ⊨□⇓(l2.=l1)

We note v1 ≠ v2 using Proposition 5.1.5(3) above because the result requires distinct events.End of proof

Remark 8.3.2 (Design alternative).

There is a wrinkle in axiom ( .=⇓) in Figure 12, that the modality ⇓ only quantifies over worlds w ∈H, not over all possible worlds w ∈ World(M). An alternative axiom⤒→(l1.=l2) ⇒l1.=l2 eliminates that possibility. This is weaker in the sense that the left-hand side of the implication goes to the end of time (the left-hand side of the implication in ( .=⇓) as written does not do that), but it is stronger in the sense that the right-hand side works at all possible worlds. Perhaps surprisingly, either axiom will work in our proofs.62

8.4. Cascade Termination

Lemma 8.4.1 is an elegant result in its own right, and it will help us prove Lemma 8.4.3(1):

Lemma 8.4.1

Suppose l1, l2, l3 ∈ Learner and suppose ϕ1, ϕ2, and ϕ3 are three closed predicates. Then

⊨♢l1l2l3 ⊤⇒(□l1 ϕ1 ∧□l2 ϕ2 ∧□l3 ϕ3) ⇒♢(ϕ1 ∧ϕ2 ∧ϕ3).
Proof

Suppose ⊨♢l1l2l3 ⊤. By Lemma 4.1.1(2),

(1) an l1-quorum of p ∈ Pnt that satisfies p,⸸, H ⊨ϕ1, and

(2) an l2-quorum of p ∈ Pnt that satisfies p,⸸, H ⊨ϕ2, and

(3) an l3-quorum of p ∈ Pnt that satisfies p,⸸, H ⊨ϕ3,

must intersect at some p, which will satisfy p,⸸, H ⊨ϕ1 ∧ϕ2 ∧ϕ3. The result follows.End of proof

Lemma 8.4.2 will help us prove Lemma 8.4.3(2):

Lemma 8.4.2

Suppose l ∈ Learner and v ∈ Value and w ∈H. Then:

(1) w ⊨ vote(l, v) implies ⊨□↓l′ echo(v) for some l′ ∈ Learner.

(2) ⊨♢↓vote(l, v) implies ⊨□↓l′ echo(v) for some l′ ∈ Learner.

Proof

Part 1 is by a simple inductive argument on time(w), using (Vote?) from Figure 12. Part 2 follows since by Remark 3.6.5(3) ⊨♢↓vote(l, v) just means w ⊨ vote(l, v) for some w ∈H.End of proof

Lemma 8.4.3

Suppose l, l1, l2 ∈ Learner — we do not assume l .=l1 or l1.=l2; these are just any three learners — and

⊨□l seq.

Then for any v, v1, v2 ∈ Value:

(1) ⊨□↓l1 echo(v1) ∧□↓l2 echo(v2) implies v1 = v2.

(2) ⊨♢↓vote(l1, v1) ∧♢↓vote(l2, v2) implies v1 = v2.63

(3) □W ⊨ (live ∧⇕l1.=l2 ∧♢↓vote(l1, v)) =⇒↕vote(l2, v).

(4) □W ⊨ (live ∧□↓l echo(v)) ⇒↕vote(l, v).

Proof

We consider each part in turn:

(1) Using Lemma 8.4.1 (since we assume (3twined) in Figure 12) we have

⊨♢(seq ∧↓echo(v1) ∧↓echo(v2)).

The result now follows using Proposition 5.1.5(2) and (EchoNE).

(2) From part 1 of this result, using Lemma 8.4.2.

(3) From (Vote’!), noting that by part 2 of this result, only v can ever be voted for.

(4) From (Vote!), noting that by Lemma 8.4.2 and by part 1 of this result, only v can ever be voted for.End of proof

Lemma 8.4.4

Suppose l1, l2 ∈ Learner. Then:

(1) ⊨♢(l1.=l2) implies ⊨♢l1l2 ⊤.

(2) ⊨□(l1.=l2) implies ⊨♢l1l2 ⊤.

Proof

Part 2 follows from part 1 using Lemma 4.2.1(2) (that □ implies ♢).

For part 1, suppose ⊨♢(l1.=l2). Unpacking what this means using Remark 3.6.5(1), there exists p ∈ Pnt such that p,⸸, H ⊨l1.=l2. Using ( .=seq) p,⸸, H ⊨♢l1l2 seq and (since seq ⇒⊤) also p,⸸, H ⊨♢l1l2 ⊤.End of proof

Proposition 8.4.5 (Cascade Termination).

Suppose l1, l2 ∈ Learner, and

⊨□(l1.=l2) and ⊨□l2 live.

Then for every v ∈ Value,

⊨♢↓deliver(l1, v) ⇒live ⇒↕deliver(l2, v).

As corollaries,

⊨♢↓deliver(l1, v) ⇒□↓l2 deliver(l2, v) and⊨♢↓deliver(l1, v) ⇒♢↓deliver(l2, v).
Proof

Note that:

— ⊨♢l1l2 ⊤ by Lemma 8.4.4 (since ⊨□(l1.=l2)).64

— □W ⊨⇕(l1.=l2) because we assume ⊨□(l1.=l2) and ( .=⇓).

We reason as follows:

⊨♢↓deliver(l1, v) =⇒⊨□↓l1 vote(l1, v) (Deliver?), Lemma 4.2.3(1)=⇒⊨♢↓(live ∧vote(l1, v)) Prop 5.2.10 ⊨♢l1l2 ⊤∧□l2 live=⇒⊨□↓l2 (live ∧♢↓vote(l1, v)) Proposition 5.2.8, ⊨□l2 live=⇒⊨□↓l2 (live ∧vote(l2, v)) Lemma 8.4.3(3), □W ⊨⇕(l1.=l2)=⇒⊨live ⇒↕□↓l2 vote(l2, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l2, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l2 ↕deliver(l2, v) ⊨□l2 live=⇒⊨□↓l2 deliver(l2, v) Lemma 6.5.4=⇒⊨♢↓deliver(l2, v) Lemma 4.2.1(1)End of proof

8.5. Happy Termination

Proposition 8.5.1 (Happy Termination).

Suppose l ∈ Learner and

⊨□l live and ⊨∃1v.♢↓propose(v).

Then

⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(l, v).

As corollaries,

⊨♢↓(live ∧♢↓propose(v)) ⇒□↓l deliver(l, v) and⊨♢↓(live ∧♢↓propose(v)) ⇒♢↓deliver(l, v).
Proof

Note that because ⊨□l live, by (LiveSeq) from Figure 7 also ⊨□l seq. We reason as follows:

⊨♢↓(live ∧♢↓propose(v)) =⇒⊨♢↓(live ∧echo(v)) Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧♢↓echo(v)) Proposition 5.2.8, ⊨□l live=⇒⊨□↓l (live ∧♢↓propose(v)) (Echo?), Lemma 4.2.2=⇒⊨□↓l (live ∧echo(v)) Lemma 6.5.2(2) & Lemma 6.6.1, ⊨∃1v.♢↓propose(v)=⇒⊨□↓l (live ∧□↓l echo(v)) Lemma 5.2.11=⇒⊨□↓l (live ∧vote(l, v)) Lemmas 6.5.2(2) & 8.4.3(4), ⊨□l seq=⇒⊨live ⇒↕□↓l vote(l, v) (Knowledge□↓)=⇒⊨live ⇒↕deliver(l, v) Lemma 6.5.3, (Deliver!)=⇒⊨□l ↕deliver(l, v) ⊨□l live=⇒⊨□↓l deliver(l, v) Lemma 6.5.4=⇒⊨♢↓deliver(l, v) Lemma 4.2.1(1)End of proof
Remark 8.5.2

We use Lemma 6.6.1 in the proof of Proposition 8.5.1 above, although that Lemma concerns echo in ThyHBB1, and here we are working with echo in ThyHBB3. However, the (Echo?) and (Echo!) (and indeed also the (EchoNE)) rules of ThyHBB1 are identical to those of ThyHBB3, and it is clear that the result transfers.

8.6. Discussion

Remark 8.6.1

ThyHBB3 assumes a correlation relation .=. We make minimal assumptions on .= such that our proofs work. These are:

— Symmetry ( .=symm) and transitivity ( .=tran); at every w ∈ World(M), the relation {(l, l′) | w ⊨ l .=l′} is a partial equivalence relation.

— Monotonicity ( .=⇓); if l and l′ stop correlating then they cannot ≪−-(re)correlate later.

— Sequentiality ( .=seq): correlated learners must have sequential quorum intersections (and conversely, if they do not, they do not correlate).

Other properties for .= are possible. We do not need any to prove our correctness properties, but it is interesting to mention a few here:

(1) ∀l, l′.(¬↓⊤) ⇒l .=l′ All learners correlate at first. The intuition is that learners with no behaviour should correlate, and only when they start to display behaviour might we decide that these behaviours do not correlate.

(2) □(l .=l′) ⇔♢(l .=l′) Correlation is a property of time, but not of place. The intuition is that before the protocol is run a scheme is broadcast whereby, for the same information, participants know what the correlation relation should be.65

(3) ∀l, l′.⤒→♢↓l .=l′ All learners correlate somewhere, sometime. This is perhaps the most interesting property. Algorithmically, this reflects an intuition (which we do not prove here) that if l never correlates with l′ anywhere, at any time, then their .=-equivalence partitions are in some sense running two concurrent algorithms. Even if they use the same messages, these two partitions cannot block one another so they can be thought of logically as two distinct runs of the algorithm, which happen to be run on the same network, but which are logically distinct nonetheless.

Remark 8.6.2 (Discussion of (3twined)).

Recall the (3twined) axiom from Figure 12. We invoke (3twined) once, in Lemma 8.4.3(1), whose proof requires a nonempty intersection between an l-quorum of sequential participants, and l1- and l2-quorums of echo messages. Both Liveness properties depend on this result.66

This is the only place in which we invoke (3twined), so we should examine the proof to see precisely how this property is used — and whether something weaker might suffice.

It is not hard to see that weaker versions are indeed possible, for example this:

□l seq =⇒♢l1l2 seq (4)

(As standard in writing axioms, we elide top-level universal quantifiers.)

We could assume property (4) in ThyHBB3 instead of (3twined) and the proofs would work just as well. We prefer (3twined) because:

— It is a purely structural restriction on quorums whose validity does not depend on behaviour during a run of the protocol.

— It is very simple.

— It corresponds nicely to the standard ‘2f+1’-style assumption on quorum sizes that appears frequently in the literature (e.g. [HM00, page 4, Q(3) property] or [ACTZ24, Definition 2]).

Nevertheless, we note that a design space exists here, which could be explored in future work.

Remark 8.6.3 (Alternative vote axioms).

Arguably the following backward and forward rules for vote are more elegant than what is in Figure 12 (the other rules, including (VoteNE), are unchanged):

(AltVote?) vote(l, v) ⇒∃l′ .=l.□↓l′ echo(v)(AltVote!) (live ∧⇕(l′ .=l) ∧□↓l′ echo(v)) ⇒∃v′.↕vote(l, v′)

This gives vote(l, v) an intuition of I saw an l′-quorum of participants who saw someone propose v for an l′ that correlates with l — note that it may be that l′ = l.

This treatment of vote is simpler and cleaner than the one in Figure 12, but it is also weaker. We see this clearly when we contrast the alternate forward rule (AltVote!), which only guarantees progress for l that correlate with themselves, with (Vote!) in Figure 12, which has no such restriction.

In practice we are most interested in learners that do indeed correlate with themselves, so this restriction is not critical. Nevertheless, we prefer to state the stronger (more live) theory.

Remark 8.6.4 (Wrong treatment of seq).

In view of Proposition 5.1.4 (seq monotone) it might be tempting to unify axioms ( .=seq) and ( .=⇓) in Figure 12 into a single axiom as follows:

( .=wrong) l .=l′ ⇔♢ll′ seq.

But this would be wrong. As outlined in Remark 8.1.1(2), a participant might need to pick a side in some dispute between two other learners, and as a result decide to break l .=l′ — even though ♢ll′ seq still holds.

Remark 8.6.5 (Concluding remarks on ThyHBB3).

ThyHBB3 succeeds on its own terms: it is a short and simple protocol that naturally generalises homogeneous Bracha Broadcast, with correctness properties that resemble those for Bracha Broadcast.

If there is a defect it is that the 3-twined quorum intersection property that any three quorums intersect (needed for the Cascade Termination property; see Remark 8.6.2) might be too strong an assumption for some use-cases. That said, and to be fair, assuming nonempty triple quorum intersections (e.g. as in “assume 3f + 1 participants of which at most f are faulty”) is a standard assumption in the literature, including for broadcast and consensus protocols.

9. CONCLUSIONS

9.1. Looking back on the results

Let us summarise our ideas at a high level:

(1) Prehistories equate time with an epsilon-structure of past events: a point in time is a set of place-event-time tuples, the time of each is itself a set of tuples, and so on.
History structures are just hereditarily transitive prehistories. Intuitively, transitivity means that knowledge of time is transitive: if we know of an event from a participant that knew of some other event, then we know of that other event. This corresponds to modelling full information protocols.

(2) We use (pre)histories to design a modal logic, tailored to specifying and reasoning about distributed protocols. We include built-in modalities for specifying things like occurrence of events in the past, quorums of present and past events, quorum intersections, and sequentiality / non-equivocation. Using this, we can write clean and compact formal axiomatisations of relevant properties (see next point).

(3) We use our modal logic to specify distributed protocols symbolically as axiomatic theories. A model of the axioms corresponds to a concrete run of the protocol; the class of all models corresponds to the set of all possible runs of the protocol. Essentially, phrasing things in this way turns distributed protocol design and verification into axiomatic logic and model theory. Verification of a correctness property ϕ is just a proof that ϕ is valid in every model of the axioms: if a structure validates the axioms, then it satisfies ϕ.

(4) We use this machinery to design three protocols for Heterogeneous Bracha Broadcast (HBB) — ThyHBB1, ThyHBB2, and ThyHBB3 — each of which is a generalisation of broadcast to the case with multiple learners, and the three of which taken together give an idea of the design space involved. We formally state and prove their correctness properties.67

We can shorten this to three slogans and a claim:

(1) Slogan 1: Times are sets.

(2) Slogan 2: Protocols are theories.

(3) Slogan 3: Protocol verification is proof and model-checking.

(4) Claim: Heterogeneous broadcast can be studied as the above.

We do not mean these slogans reductively, rather: set theory, modal logic, and model-theory are well-developed fields and we can usefully import their ideas to represent and prove things about distributed protocols.

The development in this paper has been formalised in Lean 4. The relevant files are easily available [Har25], along with (clear and straightforward) usage instructions.68

The logic-and-models approach offers precision: English is good for exposition and for giving context, but logic has a way of distilling complex ideas into short predicates with precise meanings. Informal arguments reduce to precise and concise formal reasoning. In the ideal case, verification of correctness properties reduces to symbol-pushing. Furthermore, we would argue that the understanding of the protocol is deeper for a logic formalisation, for the same reason that logic helps deepen understanding in other fields: this encourages (and forces) us to state assumptions, to identify key lemmas, and to phrase assumptions in abstract yet precise form.

The reader can find this exhibited in, for example, the specification of ThyHBB3 in Figure 12, its correctness properties in Figure 13, and in their proofs.

Remark 9.1.1

Our modal logic is specific, in the sense that the maths is shaped by and optimised for the requirements of specific algorithms. Conversely, our three algorithms only exist because we designed them using this logic. We might not have found them otherwise.

The logic and its semantics, and the protocols, came into existence by a constructive symbiosis. There is a real and useful sense in which the logic, semantics, and protocols have constrained, motivated, guided, and validated the design of each other.

9.2. Why heterogeneous protocols?

9.2.1. It’s about the ecosystem.

Why should we consider heterogeneous distributed protocols? The short answer is: because they are ubiquitous. The longer answer is as follows:

Any distributed protocol must include some form of trust model. In this paper, we represent the trust model as a semifilter (a.k.a. a quorum system) as per Definition 3.3.2. But let us step back from the mathematics and its definitions and note that:

— if you use Ethereum, you trust Ethereum (to some extent);

— if you use a bank, you trust that bank (to some extent);

— if you live in a country, you trust that country’s society and governance (to some extent);

— if you eat a pre-made sandwich, you trust the industrial complex that manufactured it to (probably) not give you food poisoning;

— if you go to a nightclub, you trust the staff to keep you safe;

and so on. So the world is naturally an ecosystem of distributed systems, each one based on and requiring some kind of trust assumption. That is: the world is distributed and heterogeneous.

There is a tendency within a system to use that system, and to pretend that the rest of the world is somehow out-of-scope. Indeed, some trust models have been very successful: Ethereum, the US dollar, large sandwich brands. This may generate an illusion of homogeneity, but this is an illusion — and this illusion can become expensive, and even self-defeating. At best, a very popular, trusted system can lead to high prices as the system is oversubscribed. At worst, a homogeneous, dominant trust model can lead to monopolistic and rent-seeking behaviour [Doc25].69

There will always be a bottleneck. There will always be someone who wants a different service. There will always be someone who will not (or cannot, e.g. for regulatory reasons) submit to your trust model.70

As helpful as it is to optimise individual distributed systems to be faster and more reliable, this will just result in improved individual distributed systems, and to the extent that these might gain users, these improvements will only make more pressing the bottlenecking question of how to make multiple distributed systems interact well, as a healthy ecosystem. There can never be One Final Trusted Party.

Therefore, and inevitably, we must ask ourselves: how can we approach heterogeneous distributed systems? How can distributed systems collaborate gracefully, reliably, and at low cost? What is the mathematics of an ecosystem with heterogeneous trust?

History structures, our modal logic, and our three heterogeneous trust broadcast protocols are this paper’s preliminary, theoretical, provisional answer.

9.2.2. Why this has not been done before.

We see two reasons that protocols like ThyHBB1, ThyHBB2, and ThyHBB3 have not been studied before:

(1) Distributed systems in the modern sense are relatively new. The founding papers are from the late 1970s and early 1980s (e.g. [Lam78] and [LSP82]). However, it has only been with the rise of the internet and its integration into modern systems, including but not limited to blockchains, that distributed systems have assumed the modern reach and relevance that we now associate to them. In a nutshell, these issues have only become pressing in the last ten years or so, and the mathematics is very much still catching up.

(2) Distributed systems are hard, and heterogeneous distributed systems are even harder, because of how the trust model may vary by participant and by time. A goal of this paper is to establish heterogeneous distributed systems as a field of study and to show how they can be accurately and conveniently approached via modal logic over (pre)histories. These ideas are new — though we would argue that they are also necessary and inevitable.

In short, as we see it, heterogeneous broadcast is at the cutting edge both of practical necessity and of what modern mathematics can deliver. This paper is intended to improve the state of the art in both dimensions: it makes new things possible, and it opens up new mathematical ways of making further progress.71

So: if heterogeneity is unavoidable, then how do existing systems deal with it? With difficulty, and sometimes at considerable expense.

Mostly, existing systems deal with heterogeneous trust by reducing the system to its worst common denominator. Because this denominator may be very low (i.e. participants do not trust one another) this often means in effect inventing more trusted parties, at great expense. To caricature the situation: if two parties that do not trust one another want to transact, it is necessary for them to find or create, and pay for, a third neutral trusted party to mediate between them. While possible, this is expensive and it does not scale — not least because it just pushes the problem down a level. What happens if the transaction above is successful and now a fourth party wants to interact? Should they invent a fifth neutral trusted party (more expense), or should they accept a single shared trusted arbiter of all truth (brings its own challenges)? Where does this end, if not in centralising all trust?

9.2.3. Embracing heterogeneity.

The mathematics in this paper — preliminary, theoretical, and provisional as it may be — is of a different colour, in that it embraces heterogeneity in existing trust assumptions as a central technical challenge and tries to exploit it and make it mathematical and efficient. This is an interesting, relevant, and useful research direction which we hope will grow and be fruitful.

9.3. Related work

9.3.1. Heterogeneous Paxos (2021).

The second author has been working on heterogeneous protocols since inventing Heterogeneous Paxos (HP) [SWvRM21].

An early success of the logic used in this work was to help us find an error in the HP correctness proofs. The HP liveness property in [SWvRM21] uses an unstated assumption (which the authors had not realised) buried in its proofs [SWvRM20, §6.4, p.19]: it assumes crashes occur at the beginning of time (this is generally not a realistic assumption for distributed protocols!). In particular, the statement “all 2as generated by acceptors in qa with values ≠ V(y) will be buried” [SWvRM20, §6.4, p.19] fails, because it requires that the learners specified in those 2as (which may not be learner a) still have a live quorum. Since they formed a 2a previously, we know that they used to have a live quorum, so the proof works if crashes occur only at the beginning of time. We were able to discover this thanks to creating a compact formalised presentation using the logic in this paper. A revision of Heterogeneous Paxos (formalised concurrently in a different system by a different team) [SK26] fixes this issue: the protocol is redesigned so it terminates regardless of when crashes occur.

Empirically, our logic decreased the textual volume of the second author’s proofs dramatically: five pages of verbal argument [SWvRM20, §6, p.16-20] or hundreds of TLAPS lemmas [SK26] reduced to one page of logical symbol-pushing (similar to the core proofs of ThyHBB1, 2, or 3). In this precise modal logic, the gap in the proof for the original HP system became evident.

9.3.2. XRP Ledger and Stellar (2014/15).

The XRP Ledger [SYB14] and Stellar [Maz15] payment protocols are two commercially successful systems offering global payment services.72 They are blockchains, but this is almost incidental: what sets them apart is that they acknowledge the problem of heterogeneity directly in their design (incompatible bank transfer systems are a big practical problem), and they use heterogeneous consensus algorithms as a basis for practical infrastructure offering reliable, fast, low-cost bank transfers.73

This work has in common with XRP Ledger and Stellar that we embrace heterogeneity. However, the scenario in this work is substantively different in its emphasis. XRP Ledger and Stellar are about participant-learners coming to a global agreement on a single network. This gives XRP Ledger and Stellar a flavour of each creating a trusted third party, whom we may trust (and pay!) for global payments services. Here, we are interested in collaboration between existing systems, whose trust assumptions may be distinct. We consider learners (representing trust assumptions of existing systems) separately from participants (trust domains drawn from one or more collaborating systems). This gives our work a flavour of promoting emergent collaborations between existing chains; not creating a whole new one. If this seems like semantic hair-splitting, it is not: it makes a substantive difference both to the mathematics and the use-cases. Both are legitimate, distinct — dare we say heterogeneous — answers to the question ‘How heterogeneity?’.

In distributed systems terms, there are two key distinctions in our approach to heterogeneity:

— We consider a closed world: participants know all the learners and all their trust assumptions in advance. XRP Ledger and Stellar use open world systems: participants learn trust assumptions as part of the protocol. Open world protocols are more general, but more things are possible in a closed world.

— We specify the safety and liveness guarantees of our protocols fully in terms of facts known to participants in advance. XRP Ledger and Stellar learners cannot know (in advance) the conditions which guarantee a decision. Indeed, this is likely impossible in an open system.

9.3.3. Epistemic logics.

Epistemic logics are logics for reasoning about knowledge. This is a well-researched field; an excellent and comprehensive survey is in [BvdH14].

Our logic is a modal temporal logic with an epistemic flavour, in that the notion of possible world w = (p, x, H) ∈ World(M) from Definition 3.4.2(2) includes a history structure H which is the knowledge that p has of past events — as well as being a moment in time, since as per Remark 2.3.7 our notion of time equates time with knowledge of past events as being literally equal and encoded in H as an epsilon-structure.

This appears to be new: to the best of our knowledge, this approach to time in general, and in particular history structures as defined in Definitions 2.2.4 and 2.3.5, are novel in the field of epistemic temporal logic. In the epistemic logic literature, if a notion of ‘history’ is relevant it is in the first instance modelled as a linear trace of events, and ‘knowledge’ is thought of denotationally as an equivalence class of traces. More sophisticated approaches include using simplicial complexes (where knowledge is modelled as a simplex) and even as an elegant denotation using chromatic hypergraphs [GKL24]. To that canon, this paper adds history structures.

There is another more subtle difference between what we do in this paper and the epistemic logic literature: the latter is historically about studying ...logic, whereas for us the focus is on specific theories: ThyLive, ThyHBB1, ThyHBB2, and ThyHBB3. These use specific axioms in a specific modal logic to embed specific mechanisms of interaction which we care about for specific protocols. Epistemic logic as traditionally pursued is more about the general theory. This matters, and it gives the mathematics a different flavour and momentum.

We should perhaps also note that even if all the reader cares about is general theory, what we do here matters because it is a new example: the use-cases lead us to study new modalities and semantics; namely, ↓,⤒→, and the ♢ family of modalities for learners over semifilters. Thus, this work certainly fits into a rich literature on using logic for epistemology, but it would appear that logic for decentralised heterogeneous computation is its own thing. We hope that this observation will motivate and enrich new research directions in epistemic modal logics.

Remark 9.3.1

We commented that our logic has an ‘epistemic flavour’. We will unpack what this means concretely, because the connection is quite interesting.

Let M be a model with history structure H, and consider a possible world w = (p, x, H) ∈ World(M) as per Definition 3.4.2(2). This includes a participant p ∈ Pnt, a maybe-event x ∈ Event⸸, and a time H ∈ History(Pnt, Event). The time H is a set of past events and (because we model full information protocols in this paper) H is also what p knows at the possible world w.

This epistemic flavour becomes even more explicit when we give meaning to ♢ in Figure 4. We repeat the clause here, for clarity:

p, x, H ⊨♢l1...ln ϕ ⇐⇒∀(O1, . . . , On) ∈ ς(l1)×· · ·×ς(ln).∃p′ ∈O1∩· · ·∩On. (p′,⸸, H ⊨ϕ).

There are a lot of symbols here, but note that

— we start with p, x, H on the left and

— we end up with p′,⸸, H ⊨ϕ on the right.

This structure matters, because even if some event (p′, E′, H) is in H, the predicate ϕ does not a priori get access to that information when we evaluate p′,⸸, H ⊨ϕ.74

So, there is implicitly a local view of H here, in that we change the place of our context from p to p′, but do not update the time to include any events that p′ might perform. Indeed, it may even be that (p′,⸸, H) ∉H! That is: the possible world (p′,⸸, H) is potentially ‘virtual’, in the sense that it does not actually happen within H. The tuple (p′,⸸, H) represents a state of p′ as p might imagine it when p is at time H. That is epistemic: it is not necessarily a real state of p′ as per H; it is a state that p constructs at time H in order to understand (to the best of its H-knowledge) what p′ has done.

In this sense, we can view ♢ as logically representing an act of imagination based on current knowledge, and the ‘sideways, imaginary’ step to a (p′,⸸, H) that need not be in H, has an explicit epistemic flavour.

Arguably also the end-of-time modality⤒→does something similar, in the sense that it takes us from (p, x, H) to (p,⸸, H), and (p,⸸, H) ∉H. This is a possible world at the end of time, when all events are known.

9.3.4. The ATL logic family.

A thread of research is based on branching-time temporal logic to describe concurrent games between agents. This starts with ATL (alternating-time temporal logic) [AHK97] and has been extended in various ways including with epistemic aspects [vdHW03].

We note three things about the relation with this work.

(1) ATL is a logic for talking about agents and their (possibly cooperative) strategies. In contrast the logic in this paper is all about expressing particular protocols. If we think of a protocol as a kind of strategy, then this logic is good for specifying and reasoning about the strategies that ATL-like logics might then reason about.

(2) Our logic puts the idea of possibly faulty participants front and centre, reflecting the fact that this is a central concern of designing distributed protocols. ATL-style logics are designed for reasoning about games; a faulty participant could in principle be modelled as a player with extra moves, but for our purposes that is somewhat less natural.

(3) Our logic puts quorums and quorum intersection properties, and also temporal properties like ‘the end of time’, front and centre. We are not aware of such an emphasis in the ATL family of logics.

In short, the ATL family of logics are different and designed for different purposes, though these purposes are complementary to the extent that our protocols can correspond to ATL’s strategies.

9.3.5. Event structures.

Event Structures are a model of concurrency, where we assume a set of events, a so-called causal relation on events, and consistency and inconsistency relations between events. An overview is in [WN95].

This looks like it should be related to our notion of history structure from Definition 2.3.5, but in fact they turn out to be quite different.

We have a set Event that we call a set of events, but our events are abstract actions; an event in Event Structures corresponds more closely to our notion of an event tuple or possible world. However, events in the Event Structure sense are unlike event tuples in that they are uninterpreted — all their structure comes from their causal, compatibility, or incompatibility relations — whereas our event-tuples carry a place and a time, which we use to give meaning to a rich modal logic for reasoning about events at a place, at a time in the past or the future, and about quorums of events and their quorum intersections.

Our modal logic can use implication to express ‘backward rules’ (if X happens then Y must have happened). This looks like it should be related to the causal relation of event structures, but implication is weaker than causation; there may be many Y in the past relative to X and there is no a priori sense within the logic that one of them in particular caused X. On the other hand, our modal logic can express ‘forward rules’ (having to do with liveness), and of course because of our focus on distributed systems, our logic includes rich modal structure for reasoning about quorums and quorum intersections.

In short: History Structures and their modal logic share with Event Structures that they talk about ‘events’, and they abstract away from linear / numerical notions of time, but they seem to be different tools created for different purposes.

9.3.6. Trace Diagrams.

Our derivation-tree style presentation of history structures (see for example Figure 2) follows a tradition of diagrammatic illustration of runs of distributed systems. Lamport’s diagrams [Lam78, Figure 1] are foundational in this area (and the pedigree extends further; Lamport was following Minkowski spacetime diagrams [TW92]). More recent diagram systems for traces include Message Sequence Charts [Int11] and Communication Diagrams in UML [Obj17]. These diagrams feature events, happens-before arrows, and instances or processes which correspond to our places.

Unlike our history structures, Message Sequence Charts and Communication Diagrams admit messages as first-class entities in the diagram — as arrows between instances/processes — and they treat receiving a message as an event. Our setup is equivalent in expressivity, but it arranges the ideas differently. Messages are implicit in the history structure itself: when one place knows about events at another place, this represents a message carrying information about those events having been transmitted. When necessary, we can model times and places where messages were received but nothing else happened using the ⸸ maybe-event, but ⸸ has its own (in our opinion very interesting!) mathematical identity: interpretations of our ⸸ maybe-event are discussed in Subsection 2.3.5, starting with Remark 2.3.14.

Some trace diagrams try to totally order events: for our needs, the additional liberty to let history structures be partially, but not necessarily totally, ordered is extremely useful. This saves us having to reason about trivially equivalent traces differing only in how they interleave events whose order we do not care about, and furthermore, it allows us to avoid modelling processes that act on information that would be unknowable, such as the relative order of unrelated events.

9.3.7. Temporal Logic.

Temporal Logic is a well-studied field with a long and distinguished theoretical pedigree and many practical applications. A body of prior work applies Temporal Logic to specify and prove properties of concurrent systems, including distributed systems. In this area, Lamport’s TLA+ [Lam02] and its automated proof system [CDL+12] have been extremely influential.

Like the modal logic used in this paper, Temporal Logic features always and eventually modalities, so we can reason about time. Unlike the models used in this paper, TLA+ models (and models of related logics) consist of sets of totally ordered traces of events, and possible worlds are just times (more-or-less in the sense of clock-ticks). There is no notion of place nor epsilon-inductive notion of history-structure-as-time.

For our needs, our modal logic’s ability to reason about time and place, and in particular what information is available at each time and place, is extremely useful for the distributed systems we wish to axiomatise and reason about.

9.3.8. Cross-domain state updates.

Bracha’s reliable broadcast provides agreement on delivered messages: if one correct participant delivers an update, then all correct participants eventually deliver that same update. Unlike consensus, this can deadlock under contention: multiple proposals for the same broadcast might result in no update ever happening [CGK+20]. Yet broadcast is useful and sufficiently powerful for a variety of applications, including payment systems [CGK+20; AFRT20] and cryptocurrencies [GKM+19; SW20], where a proposer is well-defined, and a double-proposer deadlocking itself is not a problem. It can be used to implement a single-writer read-write register [MPRJ17], or more generally a log with order chosen by a unique proposer [CGK+20]. Such a log may stop advancing if the proposer proposes conflicting updates [CGK+20], or if there are multiple concurrent proposers [SW20]. Sui generalises this register to a notion of owned objects, which can update more quickly and easily (using broadcast) than the rest of Sui’s state (which uses consensus), but which can get stuck if the object’s owner misbehaves [BCD+24].

As we discussed in the Introduction, a motivation for heterogeneous protocols is to enable interoperability between distributed systems with different trust models. The Heterogeneous Paxos paper [SWvRM21] — which as mentioned in Subsection 9.3.1 we found an error in using the logic in this paper — envisioned atomic transactions across multiple consensus-based distributed systems. In principle, the Heterogeneous Broadcast(s) in this paper could be part of a solution to update Sui-style owned objects across multiple domains.

9.3.9. Interoperability of state for blockchain.

Interoperability has been something of a challenge for blockchains. IBC [Goe20] allows compatible chains to send messages to one another (from one chain’s replicated state machine to the other’s), something most blockchains cannot do by default. Protocols like ICS20 [GS24] use IBC to transfer wrapped tokens to other chains, while keeping track of relevant trust assumptions [Cos]. So-called blockchain bridges take a similar approach, with different details when chains are not compatible with IBC. Such protocols are extremely useful, but they are fundamentally asynchronous point-to-point communication, so they do not and cannot carry the guarantees that broadcast can.

In contrast, Heterogeneous Broadcast ensures that multiple chains eventually receive the same message (subject to suitable liveness conditions) as made formal in this paper by Cascade Termination. It might be possible to use this for cross-chain atomic transactions with Sui-style owned objects [BCD+24], reducing or eliminating reliance on multi-phase commit [Her18] using cross-chain messaging protocols. Perhaps broadcast-based cross-chain transactions might be faster than multi-phase commits. Note also that in a multi-phase commit, each chain locks state until the other chains respond. If another (involved) chain never responds, everyone else’s state remains locked: liveness of all involved state is bounded by the least live chain, which is not ideal. Perhaps protocols that directly address heterogeneity could be usefully less susceptible to this issue. Investigating this is future work.

9.4. Future work

Several future directions are clear:

(1) Model checking. A model-checker for our logic would be helpful. This would accelerate the development loop for candidate protocols, because we could write down axioms and some desired correctness properties and ask the machine to find a refuting counterexample if it can, i.e. a model that satisfies the axioms but does not satisfy the correctness properties. This would help with triage of protocols. We would still want formal proofs of correctness for the final, successful, axiomatisation.

(2) Theorem-proving. A dedicated ‘domain-specific’ theorem-prover based on our logic, for fast prototyping and construction of formal proofs of correctness for protocols expressed in our logic, would likewise be useful. The Lean formalisation of this paper [Har25] technically fulfils this requirement, but a domain-specific prover using our logic and tailored to our models, might be a useful complement, especially for iterating and fast prototyping protocol designs.

(3) n-round HBB. We have given three HBB protocols in this paper, but the design space is large and we have by no means exhausted it. In particular, preliminary investigation suggests that an n-round protocol (where n is the number of learners) would provide stronger agreement guarantees. The intuition is that after n rounds, any hostile behaviour that does exist will become known to all n learners, thus in some sense reducing the n-learner heterogeneous case to something closer to the simpler homogeneous case. The relevant protocols remain to be developed and checked.

(4) Heterogeneous Paxos. Continuing the previous point, broadcast is useful for many kinds of algorithms (e.g. payment algorithms, where all we want to do is reliably broadcast actions by individual participants), but consensus would be a step up in power. Consensus can be expressed using broadcast [Bra87, Section 4, “The Consensus Protocol”], but a Heterogeneous Paxos algorithm would be useful.
As noted in Subsection 9.3.1 the logic of this paper was used to formalise and find a bug in the correctness proofs of the heterogeneous paxos algorithm from [SWvRM21]. Its replacement remains to be designed and checked, and if we do then we will use this logic to do so.

(5) Implementation. It remains to implement a prototype system based on the heterogeneous protocols in this paper or evolved from these (e.g. see previous point). Subsections 9.3.8 (cross-domain state updates) and 9.3.9 (interoperability) outline some concrete use-cases (these examples are not exhaustive).

(6) Other protocols. Protocol design is an active area of research. It remains to use the declarative methodology of this paper to study further protocols, and to design new ones. One particular interest is heterogeneous protocols, but the design space of distributed protocols, heterogeneous or not, is vast. We would put to the reader that each protocol family has its own distinct character, each of which may correspond to a distinct family of logics which remains to be discovered and studied. A lot of interesting theoretical work, with useful practical outcomes, may be possible here, giving declarative formalisations of distributed protocols.

(7) Methodology. Having now analysed a number of protocols in declarative logical style, including Paxos [GZ26] and both homogeneous and heterogeneous broadcast, the first author puts to the reader that we do not really understand a protocol until we have declaratively axiomatised it. We may think that we do, but the declarative axiomatic method is as much of a step up in clarity and precision applied to distributed protocols, as it was when Euclid invented and applied it to geometry [Euc08]. The first author would argue that our understanding of every protocol could be deepened and enriched by a declarative axiomatisation in the general spirit of this paper, and that we should be applying the techniques in this paper and its companion papers (e.g. [GZ26]) more widely to protocols both large and small.

(8) Morphisms. An interesting question is what an appropriate notion of morphism of models would be (Definition 3.3.3). Since morphisms are structure-preserving maps, to answer this question is to decide on the essential structure of a model. This is similar to the question we posed in Remark 3.6.9(2), as to what abstractly the structure of one of our Kripke models is. One likely answer, given that our modalities refer to quorums and quorums are semitopological (cf. Subsection 3.3.1 and footnote 33), is to decide that we have been studying semitopological Kripke structures (i.e. Kripke structures where possible worlds are enriched with notions of points and semitopological structure). This seems natural. A notion of ‘topological Kripke structure’ has been created [Pym02], though we do not believe they would necessarily be closely related to what we do here. This is future research.

(9) Time-heterogeneity; more heterogeneity. In Remark 1.1.2 we discussed how in the real world quorums (trust assumptions) vary both by space and by time. In this paper we use a notion of learner, each of which identifies a different set of trust assumptions, but this is not the only way to set things up. Notably, we could extend our framework and logic such that trust assumptions can evolve, e.g. they could evolve over time. In fact our protocol ThyHBB3 already includes some element of this, by using logic to express a correlation relation .= between learners. Nevertheless, there is clear scope for more exploration of a design space where trust assumptions are allowed to vary even more.

On a related note, this paper is about heterogeneous distributed systems, but (as noted in the previous paragraph) it is not the most heterogeneous situation imaginable. So we can ask: what is the most heterogeneous possible mathematically interesting notion of trust? Right now we are clearly nowhere near that limit. We see this because our definitions are full of mathematical structure: semifilters; modal logics; history structures. To be clear: this paper is designed to have structure in search of specific broadcast protocols, not remove it in search of generality for its own sake (though even if all we care about is generality for its own sake, studying specific protocols still informs the shape of the interesting design space). In future work we could go the other way and generalise, generalise, generalise, trying to distil most general possible accounts (there may be more than one) of what heterogeneous trust can mean.

REFERENCES

[ACTZ24]Orestis Alpos, Christian Cachin, Björn Tackmann, and Luca Zanolini, Asymmetric distributed trust, Distributed Computing 37 (2024), no. 3, 247–277. doi:10.1007/s00446-024-00469-1

[AFRT20]Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani, Money transfer made simple: A specification, a generic algorithm, and its proof, Bulletin of the EATCS (2020), no. 132, Extended version: arXiv:2006.12276.

[AGPPBTP19] Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni, Correctness of Tendermint-core blockchains, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) (Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 125, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, pp. 16:1– 16:16. doi:10.4230/LIPIcs.OPODIS.2018.16

[AHK97]Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman, Alternating-time temporal logic, Proceedings 38th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1997, pp. 100–109. doi:10.1109/SFCS.1997.646098

[AW04]Hagit Attiya and Jennifer Welch, Fault-tolerant consensus, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, Ltd, 2 ed., 2004, pp. 91–124. doi:10.1002/0471478210.ch5

[BCD+24]Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang, Sui Lutris: A blockchain combining broadcast and consensus, 2024. doi:10.48550/arXiv.2310.18042

[BdRV01]Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, 2001. doi:10.1017/CBO9781107050884

[Bra84]Gabriel Bracha, An asynchronous [(n − 1)/3]-resilient consensus protocol, Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (New York, NY, USA), PODC ’84, Association for Computing Machinery, 1984, pp. 154–162. doi:10.1145/800222.806743

[Bra87]—, Asynchronous Byzantine agreement protocols, Information and Computation 75 (1987), no. 2, 130–143. doi:10.1016/0890-5401(87)90054-X

[BT83]Gabriel Bracha and Sam Toueg, Asynchronous consensus and byzantine protocols in faulty environments, June 1983. https://hdl.handle.net/1813/6399

[BvdH14]Nick Bezhanishvili and Wiebe van der Hoek, Structures for epistemic logic, Johan van Benthem on Logic and Information Dynamics (Alexandru Baltag and Sonja Smets, eds.), Outstanding Contributions to Logic, vol. 5, Springer International Publishing, Cham, 2014, pp. 339–380. doi:10.1007/978-3-319-06025-5_12

[CDL+12]Denis Cousineau, Damien Doligez, Leslie Lamport, Stephan Merz, Daniel Ricketts, and Hernán Vanzetto, TLA+ proofs, FM 2012: Formal Methods (Berlin, Heidelberg) (Dimitra Giannakopoulou and Dominique Méry, eds.), Lecture Notes in Computer Science, vol. 7436, Springer Berlin Heidelberg, 2012, Extended version: https://proofs.tlapl.us/doc/web/content/Documentation/Publications/fm-long.pdf, pp. 147–154. doi:10.1007/978-3-642-32759-9_14

[CGK+20]Daniel Collins, Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh, and Athanasios Xygkis, Online payments by merely broadcasting messages, 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), IEEE, 2020, pp. 26–38. doi:10.1109/DSN48063.2020.00023

[CGR11]Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues, Introduction to reliable and secure distributed programming, 2 ed., Springer, 2011. doi:10.1007/978-3-642-15260-3

[CJKR12]Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues, On the (limited) power of non-equivocation, Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (New York, NY, USA), PODC ’12, Association for Computing Machinery, 2012, pp. 301–308. doi:10.1145/2332432.2332490

[CKV01]Gregory V. Chockler, Idit Keidar, and Roman Vitenberg, Group communication specifications: A comprehensive study, ACM Computing Surveys 33 (2001), no. 4, 427–469. doi:10.1145/503112.503113

[CMSK07]Byung-Gon Chun, Petros Maniatis, Scott Shenker, and John Kubiatowicz, Attested append-only memory: making adversaries stick to their word, SIGOPS Operating Systems Review 41 (2007), no. 6, 189–204. doi:10.1145/1323293.1294280

[Cos]Cosmos Developer Portal, IBC token transfer, Originally accessed at the Cosmos Developer Portal on 2025-10-29. https://ida.interchain.io/academy/3-ibc/7-token-transfer

[DDFN07]Ivan Damgård, Yvo Desmedt, Matthias Fitzi, and Jesper Buus Nielsen, Secure protocols with asymmetric trust, Advances in Cryptology - ASIACRYPT 2007, 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007, Proceedings (Kaoru Kurosawa, ed.), Lecture Notes in Computer Science, vol. 4833, Springer, 2007, pp. 357–375. doi:10.1007/978-3-540-76900-2_22

[Dev93]Keith Devlin, The joy of sets: Fundamentals of contemporary set theory, 2 ed., Undergraduate Texts in Mathematics, Springer, New York, August 1993. doi:10.1007/978-1-4612-0903-4

[Doc25]Cory Doctorow, Enshittification: Why everything suddenly got worse and what to do about it, Verso Books, October 2025. https://www.versobooks.com/en-gb/products/3341-enshittification

[Dol82]Danny Dolev, The Byzantine generals strike again, Journal of Algorithms 3 (1982), no. 1, 14–30, Author’s copy: https://www.cs.huji.ac.il/˜dolev/pubs/byz-strike-again.pdf. doi:10.1016/0196-6774(82)90004-9

[Dru67]Peter F. Drucker, The effective executive, 1 ed., Harper & Row, New York, 1967. https://briscoe.uthscsa.edu/cgi-bin/koha/opac-detail.pl?biblionumber=16172

[Euc08]Euclid, Euclid’s elements of geometry, 2008, Revised and corrected edition. Greek text of J. L. Heiberg (1883–1885), edited and translated into English by Richard Fitzpatrick. https://farside.ph.utexas.edu/Books/Euclid/Elements.pdf

[Gab24]Murdoch J. Gabbay, Semitopology: decentralised collaborative action via topology, algebra, and logic, Studies in Logic, vol. 108, College Publications, London, UK, August 2024. https://www.collegepublications.co.uk/logic/?00056=

[Gab25]—, Semitopology: a topological approach to decentralized collaborative action, Journal of Logic and Computation 35 (2025), no. 5, exae050. doi:10.1093/logcom/exae050

[Gab26a]—, Declarative distributed algorithms as axiomatic theories in three-valued modal logic over semitopologies, Logic journal of the IGPL (2026), In press. doi:10.1093/jigpal/jzag015

[Gab26b]—, Semiframes: the algebra of semitopologies and actionable coalitions, Mathematical Structures in Computer Science 36 (2026), e3, Originally circulated as arXiv:2310.00956. doi:10.1017/S096012952510042X

[Gar24]James Garson, Modal Logic, The Stanford Encyclopedia of Philosophy (Edward N. Zalta and Uri Nodelman, eds.), Metaphysics Research Lab, Stanford University, Spring 2024 ed., 2024. https://plato.stanford.edu/archives/spr2024/entries/logic-modal/

[GHR94]Dov M. Gabbay, Ian Hodkinson, and Mark Reynolds, Temporal logic: Mathematical foundations and computational aspects, vol. 1, Oxford University Press, July 1994. doi:10.1093/oso/9780198537694.001.0001

[GKL24]Éric Goubault, Roman Kniazev, and Jérémy Ledent, A Many-Sorted Epistemic Logic for Chromatic Hypergraphs, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) (Dagstuhl, Germany) (Aniello Murano and Alexandra Silva, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 30:1–30:18. doi:10.4230/LIPIcs.CSL.2024.30

[GKM+19]Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi, The consensus number of a cryptocurrency, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (New York, NY, USA), PODC ’19, Association for Computing Machinery, 2019, Extended version: https://arxiv.org/abs/1906.05574, pp. 307–316. doi:10.1145/3293611.3331589

[GKWZ03]Dov M. Gabbay, Agnes Kurucz, Frank Wolter, and Michael Zakharyaschev, Many-dimensional modal logics: theory and applications, 1 ed., Studies in Logic and the Foundations of Mathematics, vol. 148, Elsevier, 2003. https://shop.elsevier.com/books/many-dimensional-modal-logics-theory-and-applications/kurucz/978-0-444-50826-3

[Goe20]Christopher Goes, The Interblockchain Communication Protocol: An Overview, June 2020, Earlier source snapshot: https://github.com/cosmos/ibc/blob/8d9d3b6fe7309b034df8457760b3bbd11d24b8e1/archive/papers/2020-05/build/paper.pdf. doi:10.48550/arXiv.2006.15918

[GS24]Christopher Goes and Aditya Sripal, Fungible token transfer (ICS-20, version 2), 2024, Draft specification, version 2; now retained in the deprecated specifications directory. https://github.com/cosmos/ibc/blob/main/spec/app/ics-020-fungible-token-transfer/deprecated/README.md

[GZ26]Murdoch J. Gabbay and Luca Zanolini, A declarative approach to specifying Paxos using three-valued modal fixpoint logic, 2026, arXiv:2502.00892v2; originally submitted in 2025, revised 22 October 2026. doi:10.48550/arXiv.2502.00892

[Har25]Anthony Hart, Heterogeneous Broadcast in Lean 4, Anoma Research Topics; Zenodo software archive, November 2025, Direct download of zip archive: https://zenodo.org/api/records/17611735/files-archive. doi:10.5281/zenodo.17611735

[Hel07]Pat Helland, Life beyond distributed transactions: an apostate’s opinion, Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research (CIDR) (Asilomar, California, USA), 2007, pp. 132–141. http://www-db.cs.wisc.edu/cidr/cidr2007/papers/cidr07p15.pdf

[Her18]Maurice Herlihy, Atomic cross-chain swaps, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (New York, NY, USA), PODC ’18, Association for Computing Machinery, 2018, pp. 245–254. doi:10.1145/3212734.3212736

[HM00]Martin Hirt and Ueli Maurer, Player simulation and general adversary structures in perfect multiparty computation, Journal of Cryptology 13 (2000), no. 1, 31–60. doi:10.1007/s001459910003

[HMU07]John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, 3 ed., Pearson/Addison-Wesley, Boston, 2007, Available online (permalink). https://www.pearson.com/en-us/subject-catalog/p/introduction-to-automata-theory-languages-and-computation/P200000003517/9780321455369

[Int11]International Telecommunication Union, Message sequence chart (MSC), ITU-T Recommendation Z.120 (02/2011), International Telecommunication Union, February 2011. https://handle.itu.int/11.1002/1000/11063

[KB16]Jae Kwon and Ethan Buchman, Cosmos: A network of distributed ledgers, Whitepaper, August 2016. https://v1.cosmos.network/resources/whitepaper

[Lam78]Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM 21 (1978), no. 7, 558–565. doi:10.1145/359545.359563

[Lam02]—, Specifying systems: The TLA+ language and tools for hardware and software engineers, Addison-Wesley, USA, 2002. https://lamport.azurewebsites.net/tla/book.html

[LSP82]Leslie Lamport, Robert Shostak, and Marshall Pease, The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4 (1982), no. 3, 382–401. doi:10.1145/357172.357176

[Mal99]Dahlia Malkhi, Quorum systems, Encyclopedia of distributed computing (Joseph Urban and Partha Dasgupta, eds.), Kluwer, March 1999, Manuscript dated 23 March 1999; identifies itself as a chapter in The Encyclopedia of Distributed Computing. https://malkhi.com/files/Quorums1999.pdf

[Maz15]David Mazières, The Stellar consensus protocol: a federated model for Internet-level consensus, White paper, Stellar Development Foundation, 2015. https://www.stellar.org/papers/stellar-consensus-protocol.pdf

[MB76]Robert M. Metcalfe and David R. Boggs, Ethernet: Distributed packet switching for local computer networks, Communications of the ACM 19 (1976), no. 7, 395–404. doi:10.1145/360248.360253

[MPRJ17]Achour Mostéfaoui, Matoula Petrolia, Michel Raynal, and Claude Jard, Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems, Theory of Computing Systems 60 (2017), no. 4, 677–694. doi:10.1007/s00224-016-9699-8

[MR97]Dahlia Malkhi and Michael Reiter, Byzantine quorum systems, Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’97, Association for Computing Machinery, 1997, pp. 569–578. doi:10.1145/258533.258650

[Nan26]Toby Nangle, Stablecoin = fracturedcoin, Financial Times Alphaville (2026). https://www.ft.com/content/4724ae3f-04a7-4ca3-8221-2244c7644faa

[Obj17]Object Management Group, OMG unified modeling language (OMG UML), version 2.5.1, Specification formal/2017-12-05, Object Management Group, December 2017. https://www.omg.org/spec/UML/2.5.1/

[OO14]Diego Ongaro and John Ousterhout, In search of an understandable consensus algorithm, 2014 USENIX Annual Technical Conference (USENIX ATC 14) (Philadelphia, PA), USENIX Association, June 2014, pp. 305–319. http://web/conference/atc14/technical-sessions/presentation/ongaro

[Pym02]David J. Pym, Topological Kripke semantics, The Semantics and Proof Theory of the Logic of Bunched Implications, Applied Logic Series, vol. 26, Springer Netherlands, Dordrecht, 2002, pp. 67–87. doi:10.1007/978-94-017-0091-7_5

[RS96]Michel Raynal and Mukesh Singhal, Logical time: capturing causality in distributed systems, Computer 29 (1996), no. 2, 49–56, Available online at https://decomposition.al/CSE232-2021-09/readings/extra/raynal-singhal-logical-time-survey.pdf (permalink). doi:10.1109/2.485846

[SDRC82]John F. Shoch, Yogen K. Dalal, David D. Redell, and Ronald C. Crane, Evolution of the Ethernet local computer network, Computer 15 (1982), no. 8, 10–27. doi:10.1109/MC.1982.1654107

[Shi26]Hyun Song Shin, Tokenomics and blockchain fragmentation, BIS Working Papers 1335, Bank for International Settlements, March 2026, Full text: https://www.bis.org/publ/work1335.pdf. Archived copy: https://web.archive.org/web/20260420081702/https://www.bis.org/publ/work1335.pdf. https://www.bis.org/publications/working-paper-1335-tokenomics-and-blockchain-fragmentation

[SK26]Isaac Sheff and Aleksandr Karbyshev, Hpaxos-nrounds-public, 2026. https://github.com/isheff/HPaxos-NRounds-Public

[SM94]Reinhard Schwarz and Friedemann Mattern, Detecting causal relationships in distributed computations: In search of the holy grail, Distributed Computing 7 (1994), no. 3, 149– 174, Available online at https://vs.inf.ethz.ch/publ/papers/holygrail.pdf (permalink). doi:10.1007/BF02277859

[SW20]Jakub Sliwinski and Roger Wattenhofer, ABC: Proof-of-stake without consensus, arXiv:1909.10926v3, 2020, Versions 1 and 2 are titled “ABC: Asynchronous Blockchain without Consensus”. https://arxiv.org/abs/1909.10926

[SWvRM20] Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers, Heterogeneous paxos: Technical report, December 2020. doi:10.48550/arXiv.2011.08253

[SWvRM21] Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers, Heterogeneous Paxos, 24th International Conference on Principles of Distributed Systems (OPODIS 2020) (Dagstuhl, Germany) (Quentin Bramas, Rotem Oshman, and Paolo Romano, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 184, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021, pp. 5:1–5:17. doi:10.4230/LIPIcs.OPODIS.2020.5

[SYB14]David Schwartz, Noah Youngs, and Arthur Britto, The Ripple Protocol Consensus Algorithm, White paper, Ripple Labs Inc., 2014. https://ripple.com/files/ripple_consensus_whitepaper.pdf

[TW92]Edwin F. Taylor and John Archibald Wheeler, Spacetime physics: Introduction to special relativity, 2 ed., W. H. Freeman and Co., New York, USA, 1992. https://eftaylor.com/spacetimephysics/

[vdHW03]Wiebe van der Hoek and Michael Wooldridge, Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications, Studia Logica 75 (2003), no. 1, 125– 157. doi:10.1023/A:1026185103185

[Wik25]Wikipedia, Kleene fixed-point theorem — Wikipedia, the free encyclopedia, 2025. https://en.wikipedia.org/w/index.php?title=Kleene_fixed-point_theorem&oldid=1289692885

[WN95]Glynn Winskel and Mogens Nielsen, Models for Concurrency, Handbook of Logic in Computer Science (S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum, eds.), vol. 4, Oxford University Press, May 1995, pp. 1–148. doi:10.1093/oso/9780198537809.003.0001

A. REDUCING TO THE HOMOGENEOUS CASE

We consider what happens to our axiomatisations and correctness properties when we assume there is just one learner.75 We further assume that any three quorums intersect at a sequential participant (in our logic: ♢lll seq).76

Given one learner l and sequential triple quorum intersections, it is easy to check that:

(1) ⊨♢ll⊤ and ⊨♢lll⊤ and ⊨♢ll seq always.

(2) In ThyHBB1, the unique learner l is always safe.

(3) In ThyHBB3, we have (3twined) and ( .=seq). We will also assume that every learner is correlated. Since there is only one learner, and all quorum intersections contain a sequential participant, this is reasonable.

We obtain axiomatisations and correctness properties as below. We sum up the outcome:

(1) ThyHBB1 and ThyHBB2 become textually identical to one another and to the idea of Bracha Broadcast.

(2) ThyHBB3 is textually slightly different because of the disjunct in its (Vote?) rule and because of (Vote’!), but a very small amount of proof shows that this is only apparent: the disjunct and (Vote’!) are logically redundant and can be removed. There is also the (VoteNE) rule, but with our assumptions this is also redundant because it can be derived from (EchoNE) and the other axioms. So ThyHBB3 simplifies to the same thing as ThyHBB1 and ThyHBB2.

In conclusion: in the homogeneous case, our three protocols — boringly and reassuringly — reduce to the same core.

A.1. Homogeneous ThyHBB1 and ThyHBB2 (Figures 8 and 10)

Backward rules (HBB)(Echo?) echo(v) ⇒♢↓propose(v)(Vote?) vote(v) ⇒□↓l echo(v)(Deliver?) deliver(v) ⇒□↓l vote(v)Other rules Include axioms of ThyLive from Figure 7(EchoNE) echo(v) ⇒↓echo(v′) ⇒v=v′Forward rules(Echo!) (live ∧♢↓propose(v)) ⇒∃v′.↕echo(v′)(Vote!) (live ∧□↓l echo(v)) ⇒↕vote(v)(Deliver!) (live ∧□↓l vote(v)) ⇒↕deliver(v)

(1) Happy Termination If ⊨□l live and ⊨∃1v.♢↓propose(v) then

⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(v).

(2) Cascade Termination If v ∈ Value and ⊨□l live then

⊨♢↓deliver(v) ⇒live ⇒↕deliver(v).

(3) Soundness / Agreement If v1, v2 ∈ Value then

⊨♢↓deliver(v1) ⇒♢↓deliver(v2) ⇒v1=v2.

A.2. Homogeneous ThyHBB3 (Figure 12)

Backward rules(Echo?) echo(v) ⇒♢↓propose(v)(Vote?) vote(v) ⇒(□↓l echo(v) ∨♢↓vote(v))(Deliver?) deliver(v) ⇒□↓l vote(v)Other rules Include axioms of ThyLive from Figure 7(EchoNE) echo(v) ⇒↓echo(v′) ⇒v=v′(VoteNE) vote(v) ⇒↓vote(v′) ⇒v=v′Forward rules(Echo!) (live ∧♢↓propose(v)) ⇒∃v′.↕echo(v′)(Vote!) (live ∧□↓l echo(v)) ⇒∃v′.↕vote(v′)(Vote’!) (live ∧♢↓vote(v)) ⇒∃v′.↕vote(v′)(Deliver!) (live ∧□↓l vote(v)) ⇒↕deliver(v)

(1) Happy Termination If ⊨□l live and ⊨∃1v.♢↓propose(v) then

⊨♢↓(live ∧♢↓propose(v)) ⇒live ⇒↕deliver(v).

(2) Cascade Termination If v ∈ Value and ⊨□l live then

⊨♢↓deliver(v) ⇒live ⇒↕deliver(v).

(3) Soundness / Agreement If v1, v2 ∈ Value then

⊨♢↓deliver(v1) ⇒♢↓deliver(v2) ⇒v1=v2.

Notes

1If the reader is familiar with typing contexts and wonders how these differ from modal contexts, these are indeed both contexts, and an argument (out of scope for this paper) can be made that there is some technical overlap. But we hope the following intuitive rule might help: if your w helps you to type x, y, and z then it is probably a typing context; if your w tells you who you are, where you are, and/or what time it is, then this is probably a modal context. ↩

2How? ♢time □place (it rains) means ‘there is a time when it rains at all places’ and □place ♢time (it rains) means ‘at all places there exists a time where it rains’. Traditionally, the box symbol carries some meaning of all/everywhere/always and the diamond symbol carries some meaning of exists/somewhere/sometime. ↩

3We have to make a trust assumption here; e.g. “up to a third of participants may be faulty, but no more”. If our trust assumptions are inaccurate, then behaviour can no longer be guaranteed. Such is life. ↩

4...unless they have exactly the same trust model, which is quite a strong condition which in a certain deep sense insists that this is really one system, interacting with itself. ↩

5Arguably they are not eager to shout out that they are ‘re-doing blockchain’ — and to be fair, central bankers are culturally a quieter and more academic community than blockchain enthusiasts. ↩

6The BIS working report (written by a central banker) concludes, to simplify greatly but not entirely unfairly, that ‘heterogeneity is so hard that it should only be entrusted to central banks’. We beg to differ only on one small detail: it should be entrusted to central banks and to logicians. ↩

7Pnt can stand for ‘ParticipaNT’ or ‘PoiNT’. ↩

8In a real-world system, all these sets are finite, but unless stated otherwise, our discussion will not depend on this. ↩

9In jargon: it solves the reliable broadcast problem in an asynchronous network with Byzantine failures [BT83]. ↩

10The pedantic reader (including the first author, when he was first introduced to these concepts) might now ask: but what do ‘live’ and ‘correctly follow the protocol’ mean precisely? Intuitively these concepts are clear enough for this introductory exposition, but what do they actually mean? Such a reader is in luck, because logic excels at giving precise mathematical form(s) to compelling but informal concepts. See Subsection 5.2. ↩

11We have ideas and computational power now that did not exist in their modern form in Bracha’s time. ↩

12The classic movie The Producers is based on this idea: the producers sell the same shares of a play to multiple investors. Each sale on its own is legitimate, it is the totality of the sales in context that creates the fraud. ↩

13“Personally, I have invested a non-trivial portion of my career as a strong advocate for the implementation and use of platforms providing guarantees of global serializability ... application developers simply do not implement large scalable applications assuming distributed transactions. When they [try to,] the performance costs and fragility make them impractical. Natural selection kicks in [and] applications are built using different techniques”. In other words: the author argues that serialisable systems are a natural Darwinian optimum in the real-life design space. ↩

14“Our main result shows that for systems of validators, the effect that Byzantine components can have on honest validators is precisely identical to the effect that equivocating components can have on non-equivocating validators. Therefore, for distributed systems of potentially faulty validators, replacing Byzantine components with equivocating components has no material analytical consequences” ↩

15For the interested reader, section 3 of [CGR11] contains an exhaustive survey of broadcast algorithms, all making different safety assumptions and delivering different correctness guarantees. In particular crusader agreement [Dol82] stands out as arguably simpler than Bracha Broadcast, and it has a termination property which our algorithms will not have — but only because it makes a strong assumption which we do not wish to make, of assuming a globally synchronous network (messages arrive reliably and on time). Arguably, a globally synchronous network makes less sense in a heterogeneous setting, because this is a global trust assumption on the network, and we do not want a crash in one trust system to prevent progress of another. So perhaps we should say that Bracha Broadcast is a simplest nontrivial useful distributed algorithm that makes sense (to us) in a heterogeneous setting. See Footnote 16. ↩

16Bracha’s reliable broadcast may be simple (at least in the tautological sense that it is simpler than more complex protocols) but this belies its considerable expressive power. It suffices to update state in several types of distributed systems, including cryptocurrencies (although many of them unnecessarily use Consensus, which is stronger) [GKM+19]. It can be used to implement a single-writer read-write register [MPRJ17], a single-appender log [CGK+20], or even arbitrary objects identified with a single owner [BCD+24]. ↩ ↩

17‘Epsilon-inductive’ is fancy set-theorist jargon for saying that something is built from sets, or sets of sets, or sets of sets of sets, and so on. See Definition 2.2.4, which is visibly epsilon-inductive because it builds a prehistory as a set of things that themselves contain prehistories. ↩

18Vector clocks seem to have been independently invented by several people during the 1980s. The surveys [SM94; RS96] include historical comments in footnote 3 on page 6, and on page 4, respectively. ↩

19The first author has a motto: Quotient sets are a sign of failure. ↩

20For this definition, we do not care about the internal structure of places and events. If we have in mind to implement them then we might want them to be recursively enumerable, but the definition and mathematics do not require that. ↩

21In Definition 2.2.4 we define a prehistory as an inductive datatype built up using set membership. The set theorists’ term for that is inductively defined epsilon-structure. This is almost exactly the same thing as what a programmer would call an inductively defined data structure, the only difference being that sets come natively with some algebraic identities, for example X ∪X = X and X ∪Y = Y ∪X. A coinductive, non-wellfounded notion of PreHistory would also be possible but is not required here. ↩

22In other applications we might want the precise opposite, i.e. information hiding. That is a topic in itself, which is out of scope here. This could be accommodated in our framework; impose suitable axioms that precisely contradict transitivity (we control the definition; we can impose whatever axioms we like). Thus, whether we insist on transitivity or perhaps insist on properties that contradict it, either way, this property is an important reference point. ↩

23Epistemic: relating to knowledge. We discuss the relation of our logic to purpose-built epistemic logics, i.e. ones with modalities for reasoning directly about knowledge, in Subsection 9.3. ↩

24We are mathematicians, so we appreciate that careers — good ones — have been made from studying nothing. ↩

25Though Lamport considers receiving a message to be an event, and we do not. Just under Figure 1, Lamport writes “We assume that sending or receiving a message is an event in a process”. Indeed, traditionally in distributed systems receiving a message is considered an event. ↩

26Think of this in the style of Mealy machines, in which every step has to receive a message, update state, and send a message. ↩

27It is a sequential one, in the sense of Definition 3.4.9(2). ↩

28It might be interesting to take this seriously and replay the evolution of set-theoretic semantics for numbers. We list some questions in increasing order of speculativeness: What are the arithmetic properties of ‘concurrent naturals’? What are the arithmetic and topological properties of the spaces of ‘concurrent rationals’ and ‘concurrent reals’? What might ‘concurrent surreal numbers’ mean? And even: is the natural notion of ‘concurrent sets’ substantively different from its encoding in normal set theory as per the definition of prehistories above? Such ideas are out of scope for this paper, but they might be a starting point for a nice research programme in mathematical foundations. ↩

29It is standard to use a single set to represent multiple domains. Set theory takes this to its extreme, where sets represent everything (e.g. ∅ can represent both the empty set and the number zero), and in computing, it is fundamental that all data can be serialised to binary bitstrings. ↩

30This is just as in natural language. The English predicate ‘The cat sits on the mat’ asserts that the cat sits on the mat. That is, the sentence ‘The cat sits on the mat’ is true when the cat does sit on the mat, i.e. when the event “the cat sits on the mat” is actually happening, and it is false when the cat does not sit on the mat, i.e. when that event is not happening. Thus observe in English that the predicate ‘The cat sits on the mat’ and the event “the cat sits on the mat” are written identically (here we use single quote marks around the predicate and double quote marks around the (linguistic representation of) the event). ↩

31Definition 3.3.2(2) also requires up-closure, to be consistent with standard notions of filter coming from order-theory. This is convenient, but not essential. There is a claim here: that the notion of learner used in this paper is morally identical to the notion of abstract point in the sense of point-free topology. The technical work to make this intuition precise is out of scope for this paper; but the reader can find more about abstract points in a semitopological context in [Gab24, Part II, semiframes] or [Gab26b]. ↩

32To be fair, that other complexity is considerable. See the construction of the finite von Neumann numbers in Remark 2.3.18. ↩

33 A comment on design. Initial drafts of this material included learners as participants. We imposed a full semitopology Open on the set of participants and the role of the semifilter ς(l) was filled by just taking the set of open neighbourhoods of l; Opn(l) = {O ∈ Open | l ∈O}. This is elegant, topological, and arguably intuitive (learners are participants and their quorums are their open neighbourhoods) — but it created an annoying notational problem that we needed our logic to have quantification over learners (and participants), and also quantification over values, and also variable symbols for both kinds of quantifier, and it all got a bit long to write out. The nice feature of identifying learners with values, using a learner interpretation ς, and having just one quantification symbol, is that it gives a minimal and slick presentation of the logic and axioms. And it is enough to give us all the expressivity that we actually need. So we do that. ↩ ↩

34 This comes from the fact that we define World(M) = Pnt × Event⸸× Time(M) in Definition 3.4.2(2). Design alternative: We could refine Definition 3.4.2(2) such that World(M) = H ∪{(p,⸸, H) | p ∈ Pnt, H ⪯−H}, where ⪯− is the notion of ‘non-strict element of’ from Definition 2.3.1(2). It turns out (this is not obvious) that with this definition our results would work just as well. The key observation is that if we start from w in the refined set then every operation on possible worlds in Figure 4 keeps us within it. For computational purposes (e.g. model-checking) the refined set may be helpful, because it is smaller; but for our purposes Definition 3.4.2(2) suffices, and it is conceptually simple, so we use that. ↩ ↩

35The reader who is already familiar with de Morgan dualities should please be patient: de Morgan duality is surprising and not necessarily intuitive to the uninitiated reader. ↩

36Analogy: every number can be derived by combining 0 with a suitable number of applications of the successor function. But this does not make number theory trivial, nor can we understand ‘three’ just by saying “it’s just some combination of 0 and successor”. 3 is its own thing relative to 0, just as ♢↓ is its own thing relative to ♢ and ↓. ↩

37Idiosyncratic: belonging to one’s peculiar and individual character. ♢l1...l2 is undeniably a modality, but from the point of view of Kripke semantics there is nothing generic about it. It is motivated by specific notions of quorum intersections from distributed systems. Arguably, this modality is what imports the essence of distributed systems into a Kripke-logic style framework. ↩

38It remains to study classes of logics based on protocols other than Bracha Broadcast, to see how robust this logical design is. Perhaps it will turn out that each family of protocols has its own characteristic logic; or perhaps the logics will all be fundamentally similar, and all we need to do is perhaps tweak the modalities as per Remark 3.6.8. Most likely it will be some mixture of both. Finding this out will make for interesting future research, for new logics, and hopefully it will lead us to improved protocols and improved confidence in existing ones. Some readers — perhaps if they are used to logical frameworks like Isabelle/HOL or Lean — might find it odd that a logic might be tailored to a protocol or family of protocols. Should we really need to tweak our logic every time we want to model a new protocol-family? Surely a logic is a specification language, which ideally should be protocol-agnostic. Yes, but not only that. Another very important use of logic is to pick a minimally expressive language to express one particular thing. This can be a fruitful way to abstract what that thing is, and thus to contrast it (via the logics generated) with what another thing is. Classic examples of this philosophy include: descriptive complexity theory (where logics characterise complexity classes), reverse mathematics, and also the zoo of logic-programming clause formats (like DNF, CNF, Horn clause, Harrop clauses, hereditarily Harrop formulae, and so on). In fact there is never just one logic: there are and will always be multiples, and this is a feature, not a bug. ↩

39A short but useful map, with names, can be found at https://plato.stanford.edu/entries/logic-modal/#MapRelBetModLog. ↩

40Technically, (Order) is an axiom-scheme, with an axiom (Order)E,E′ for each pair of distinct events. ↩

41Infinite theories naturally exist. For instance, if the set of events Event is infinite then we might want an axiom-scheme parametric over infinitely many events. Technically, ThyLive in Figure 7 is infinite provided there is at least one event and one learner, because it contains the Knowledge axiom-schemes. See the discussion in Remark 5.2.6. ↩

42...It is also not based on ⊨⤒→□⇓ϕ (validity at every possible world in H). ↩

43In contrast, if an axiom mentions v or l — like the ones in Figure 8 — then this does not necessarily mean that they are axiom-schemes. As per standard notation in logic, an axiom is considered to be universally quantified over any free variables. Our logic has quantification over values, so an axiom that mentions values just has invisible ∀ quantifiers quantifying those values at top level. We do not have an explicit quantification over events in the logic, so we use axiom-schemes. ↩

44We only actually need axiom (LiveAlways). ↩

45Note that w ∈H here, instead of w ∈ World(M). A stronger version of the Lemma is possible but for our purposes, the Lemma as stated is enough. See also Remark 5.2.3. ↩

46This terminology is from Notation 4.1.2; it means that every intersection between an l1-quorum and an l2-quorum, is nonempty. ↩

47It is important to appreciate that one person’s ‘implementation’ is another person’s ‘abstraction’. For example: someone used to Java might look at Haskell and see an abstraction, and at C, with its explicit memory management, and see an implementation layer; whereas someone used to thinking in Lean or Agda might look at Haskell and see an implementation layer. And of course, it was not so long ago that many people looked at C and saw an abstraction of machine code. ↩

48There are allowed to be other event-symbols and predicate-symbols, but we will not use them. ↩

49ThyHBB3 also has a notion of source and reporting learner, but the source learner is existentially quantified. See the discussion opening Section 8. ↩

50This is a simplification; we have elided the role of safe learners. See Remark 6.2.7 for a more detailed exposition. ↩

51We can put this strong condition even on byzantine participants because (for the protocols that interest us) we assume that messages are cryptographically signed, so no participant (not even a byzantine one) can forge a propose message. The first author’s study of (homogeneous) Paxos did not assume such cryptographic guarantees, instead using a three-valued logic to represent byzantine behaviour, while retaining structurally similar axioms [GZ26]. ↩

52Our axiomatisation does not explicitly assume that a unique participant proposes, nor that precisely one value is proposed. In an implementation, we would probably expect the proposer to be unique and to propose precisely one value. But we get our correctness properties without requiring this. In part, this is because the Happy Termination correctness property in Figure 9 is explicitly conditioned on assuming that precisely one value is proposed. Thus we can say that the practical assumption ‘assume one proposer who broadcasts a unique value’ is encoded precisely in that condition. ↩

53But surely a hostile participant could violate (EchoNE); just sequentially echo v and then echo v′? Yes, a hostile participant can do what it wants. But, if it broadcasts a history that violates (EchoNE) to an honest participant then that honest participant will refuse to accept that history as a well-formed message. So the force of (EchoNE) is not that it constrains hostile participants’ real-world behaviour; it is that it constrains hostile participants’ ability to influence the behaviour of honest ones. This is a subtle difference between actual behaviour and a logical model of behaviour: our logical models can afford to be more abstract, even where they model hostile participants, essentially because we only care about hostile behaviour that might influence honest behaviour. This is a feature. ↩

54Likewise for ThyHBB2. In ThyHBB3 we care about nonsequential echo and also nonsequential vote events. A rule of thumb is: nonsequentiality matters where it might break a non-equivocation axiom like (EchoNE) or (VoteNE). ↩

55By axiom (Echo?), if we know of an echo(v) then we also know of a propose(v). ↩

56Recall from Lemma 5.2.9(2) that by (LiveAlways) in Figure 7, it does not matter when p is live; p is either live or not live, at all w ∈H@p. ↩

57Concretely, it would suffice for an attacker to hack into pl1,l2’s account one morning to make it perform nonsequential behaviour, then pay influencers to chatter about it online so it gets into the news, and by that same evening, nobody trusts p. Any similarity to any real life events is entirely coincidental. ↩

58Subtlety alert: the correlations are measured at the times of the votes, not necessarily at the time of the final delivery. ↩

59One particular special case is when there exist disjoint l- and l′-quorums. Then l and l′ can never correlate. This recovers the spirit of the kind of quorum intersection property that is very commonly seen in the theory of distributed algorithms. ↩

60This assertion can be made precise. A set union of two partial equivalence relations is not necessarily a partial equivalence relation. It follows that if S is a symmetric relation, then the ⊆-poset of partial equivalence relations contained in S does not necessarily have a greatest element. It will have at least one maximal element, but there is in general no single canonical greatest one. ↩

61This is a nice opportunity to illustrate the difference between an operational rule in a protocol, and an axiom in a theory representing that protocol: axiom (Vote’!) in Figure 12 assumes l .=l′ at every time. This is a stronger condition, and thus a weaker guarantee, than the operational rule’s requirement that l .=l′ at the time of execution. Thus, the protocol might carry out some execution steps that are not required by the (Vote’!) axiom (but also are not forbidden by it). This is a feature, not a bug: logic can look at all of time whereas a protocol cannot; and if we can derive correctness properties from the relatively weaker axioms, then these properties will hold of any protocol that satisfies those axioms, including the one described here. ↩

62The dedicated reader might look at this design space and conclude that ↓ and ⇓ should quantify over all preceding possible worlds, rather than just those preceding worlds that are event-tuples in H. Unfortunately, that does not work! We need ↓ as written in order to express the Knowledge axioms in Figure 7. The design tension here is real. We could have two ‘in-the-past’ modalities (one for event-tuples in history and one for all possible worlds), or we can do as we have done and live with the wrinkle in ( .=⇓). Since this wrinkle is harmless in our current proofs, this seems a valid tradeoff. ↩

63This result might seem to imply (VoteNE), because if vote(l, v) and ↓vote(l′, v′) hold at some world, then certainly ♢↓vote(l, v) and ♢↓vote(l′, v′) at the end of time, and then by this result v = v′. However, this result assumes the existence of a quorum of sequential participants, whereas (VoteNE) does not. ↩

64We can also get this property as a special case of (3twined), but that is an axiomatic constraint on the entire model whereas ⊨□(l1.=l2) is a specific assumption in this particular result. It is better to use the assumption and to avoid invoking the axiomatic constraint, where we can — it means that later on it is easier to see where the axioms are really needed, and so how we might tweak them; see Remark 8.6.2. ↩

65This does not constrain the behaviour of faulty participants. They can deviate from the protocol so they can deviate from its assumptions. ↩

66We could also use (3twined) to deduce ♢l1l2 ⊤, but we have that from l1.=l2. ↩

67Other protocols are possible, but HBB is an excellent start: a simple but nontrivial and useful protocol which occupies a (for us) helpful spot in the design space. ↩

68We emphasise the ‘clear and straightforward’. Anybody who can get this far in the paper can certainly follow the formalised development. ↩

69Enshittification or platform decay [Doc25]: the tendency of a useful platform (‘trust model’, in our terms) to create value, succeed, dominate — then extract rent from each of the parties who trusted it until the original value proposition is completely undermined. Enshittification seems more accurate than ‘platform decay’, because ‘decay’ suggests a natural process that happens through neglect, whereas ‘enshittification’ more accurately suggests the outcome of active choices made by participants in an economic framework. A classic 1960s text on business management [Dru67, page 14] comes at a related point, when it writes of a tendency of executives in an organisation to make poor decisions because they simply forget that the outside world exists: “The executive is within an organisation [but] there are no results within an organisation. All the results ...are produced by a customer who converts the ...efforts of the business into ...profits through his willingness to exchange his purchasing power for ...products and services”. The underlying common theme here is that it’s never just about the system; it’s always about how that system interacts with the rest of the world. Where we forget that, things go wrong. ↩

70It may help to put numbers to this. The market capitalisation of Ethereum at time of writing is (according to an internet search) roughly 0.5 trillion USD. This is a lot of money. However, it is less than the total assets of the House of Saud at 1.4 trillion USD, or of J.P. Morgan’s assets under management at 3.4 trillion USD. The numbers are subject to change but what will not change is that J.P. Morgan, House of Saud, and Ethereum will never merge. They will never fully trust each other. The real world is inherently heterogeneous. ↩

71There is an irony to our solution, in that the techniques we import are from modal logic and model theory, which are old fields (older than distributed systems). But then again perhaps we should not be surprised: modal logic and model theory were designed to handle complexity, so perhaps (heterogeneous) distributed algorithms are just another thing they are good at. ↩

72The XRP Ledger protocol is sometimes colloquially called Ripple. This is not quite correct. XRP Ledger is a protocol; Ripple is a company (which administers a blockchain running the XRP Ledger protocol). ↩

73The first author has studied them theoretically and proposed that mathematically, they correspond to distributed logic programming computing open sets in a semitopology. More details are in [Gab24; Gab25]. In XRP Ledger and Stellar each participant heterogeneously picks their preferred trust assumptions. Semitopologically, the trust assumptions of a participant p correspond to what topologists call the open neighbourhood system of p, which is just the set of open neighbourhoods that contain p. We mention this because it pinpoints a precise technical connection to this work: these open neighbourhood systems correspond to the semifilters from Definition 3.3.2 (modulo a nonessential but simplifying up-closedness assumption used here).↩

74ϕ can always gain omniscient access by being⤒→ϕ′, but that is a different story. ↩

75In Definition 3.1.1 we identified the set of learners with the set of values: Value = Learner. That did no harm in context because in Definition 3.3.3(4) we interpret elements v ∈ Value = Learner via a learner interpretation (an assignment of a semifilter to each v ∈ Value); Value was just a convenient carrier set which we had anyway. Here, we insist there is literally precisely one learner, but we do not not necessarily insist on there being one value, so technically we need to distinguish the (singleton) set of learners from the (possibly non-singleton) set of values. This distinction is an accounting detail, which changes nothing substantive. ↩

76In fact, our proofs will only require ♢ll seq and ♢lll ⊤; pairwise sequential intersections and nonempty (but not necessarily sequential) triple intersections. This is interesting, because quorum intersection properties correspond to safety assumptions, so that weaker intersection properties yield stronger correctness results. ↩