Consistent histories: enforcing linearity and excluding double-spending amongst collaborating controllers
Abstract
We address the consistent histories problem: how to ensure that linear digital resources (such as tokens of fiat currency, of cryptocurrency, records of title, exclusive locks, and so on) remain linear across execution traces that span multiple independent collaborating controllers (state machines), without a single trusted global authority. This problem underlies a wide range of practical challenges, including atomic swaps, cross-chain bridges, interchain messaging, and tokenised settlement. A solution to this problem would address an important outstanding theoretical issue in the mathematics of banking and cryptocurrency. We propose a mathematical framework based on a novel notion of sequential located semilattices with Cut. In this model, each controller (communicating state machine) maintains a bounded semilattice of times (= some abstraction of controller state), such that incomparable elements join to a distinguished top element representing inconsistency. Controllers attest to each other’s times via an attestation operation that is controller-preserving, expansive, and contradiction-preserving. A carefully designed family of flags on times enables us to introduce a Cut operation, which prunes history, thus reducing storage cost. Our main result states that any inconsistent execution trace contains an active inconsistent index (an inconsistency that has not been cut away). We further provide an even stronger absolute consistency criterion, which has the advantage of being independent of trust assumptions, at the expense of being a little harder to prove. In particular, Cut is safe: the only way to remove byzantine behaviour from history is to introduce new byzantine behaviour into the history, so that if a pruned history is safe, then the original history must have been safe. Our framework is constructive in the sense that we exhibit explicit models, including one which is close to a realistic implementation, such that times are tuples carrying cryptographic digests of attested controller states. The mathematics in this paper has been formalised in Lean 4 and the formalisation is available online.
Keywords: Consistent history ; controllers ; distributed systems ; decentralised computation
References 84
1. Introduction
1.1. Setting the scene
The reader has probably lain awake at night worrying how we can solve the consistent histories problem: how multiple independent state machines (‘controllers’) can collaborate on linear resources without a single trusted authority, while excluding double-spends.
If the reader has not worried about this, then they probably should, because this is arguably the fundamental problem of digital assets, and digital assets run (large parts of) the world, and the world has multiple controllers.
It is the recurring safety problem behind atomic swaps [Tyg96][BHG87, §7.3], cross-domain asset transfers [Com92] and cross-chain bridges [Her18, Goe24], interchain messaging [Goe20], and tokenised asset settlement [Ban23, Ban25, BB23, BBE25]: excluding double-spends and ensuring consistent spend histories. To this difficult and vital problem, we offer the following response:
Use sequential located semilattices with Cut, as per the mathematics in this paper.
The definitions and proofs in this paper have been formalised in the Lean 4 theorem prover, complete with instructions for use and linkages between the results in this paper and their formalised Lean code. The interested reader can download the files [Har26] and run the verification locally.
We will now explain the issue and unpack the jargon.
1.2. The exponential cake
Figure 1 illustrates the problem of non-linearity with a cake that you can have, and also eat. This is of course ridiculous, which is our point. We spell out the sequence of events:
• Controller 1 sends a cake to Controller 2.
• Controller 2 illegally copies the cake. This is a non-linear operation:
– It is non-linear in the ‘linear logic’ sense that the cake is ‘spent’ more than once, thus treated as an exponential resource [Gir87].1
– It is non-linear in the geometric sense that the two spends cannot legally exist on a single, sequential (thus linear), timeline.
Accordingly, Controller 2 creates two distinct timelines, one for each of the two copies of the cake, as illustrated.2
• From the first timeline, Controller 2 sends the cake back to Controller 1.
• From the second timeline, Controller 2 sends the cake to Controller 3.
• Controller 3 passes the cake back on to Controller 1.
Note here that:
1. Controller 1 never directly interacts with the second timeline of Controller 2. As far as Controller 1 is concerned, it has simply received two cakes: one from Controller 2 and another from Controller 3. How nice!
The only way for Controller 1 to detect that a double-spend has occurred is to compare the two cakes’ histories and note that their provenance goes back to and , a non-sequential pair of events (i.e. a forked timeline) from Controller 2.
2. There is no global Controller (state machine). This example happens across multiple independent interacting state machines: Controllers 1, 2, and 3. They have no visibility of each other, aside from the tokens they exchange.
Thus, the double-spend on Controller 2 makes Controller 2 faulty, but Controllers 1 and 3 are honest. Yet, Controller 2’s double-spend has propagated, via the tokens it has sent, to affect the other controllers.
This paper provides mathematics that allows Controllers 1 and 3 to detect that an illegal operation has occurred — as in the case of Controller 2’s construction of an exponential cake — while imposing minimal costs and restrictions on the system. Examples of costs that are not minimal include: all controllers trust one another because it is assumed that only incorruptible institutions are allowed to become controllers; there is only One Controller, so the problem is trivial; tokens are stateless and all token transfers are symmetrically reversed (i.e. token transfers should be ‘perfectly bracketed’); or, everything that ever happens to a resource gets recorded on that resource and stored, for every resource, forever. As we will see, our solution is both more efficient and more flexible than all of the above. And while the maths to prove this is highly nontrivial, the actual construction is quite simple, involving just three flags and a so-called Cut rule.
1.3. Jargon: linear tokens across independent controllers
A linear token is just some digital resource that is supposed to be used once. The word ‘token’ may have connotations of blockchains, but here we intend the word more generally: examples include cryptocurrency tokens; or tokens of some fiat currency;3 a record of a title to a house; a digital record of some item on a container ship; or even a digital permission, such as an exclusive write lock.
A controller is an independent state machine.4 This could be a blockchain; or the accounts ledger of a bank; or a national Land Register (a national database of home ownership); or a shipping company’s database. A controller is anything that can evolve its own state, without necessarily depending on anything external.
By independent collaborating controllers we mean that there are multiple controllers — multiple independent state machines — each evolving their local state independently of the others, but in collaboration with them by exchanging messages and/or tokens.
Immediately, a problem arises: digital resources can be copied. In technical jargon, they are naturally non-linear. There is no a priori reason that a token that is supposed to be linear (= used once), could not be copied and used twice. In the blockchain literature this is called a double-spend (see Subsection 1.4).
We can now abstract to the following mathematical scenario:
• We fix a set P of state machines which we call controllers.
• Controllers perform state transitions, and may collaborate by sending each other tokens (= resources).
This abstraction of communicating state machines is a simple but fair representation of how tokenised systems actually collaborate. And even in this simple model, we see the problem: if controller sends a token to controller , and controller is unsafe and breaks linearity by double-spending that token, then the entire system is at risk of becoming unsafe, because any action that requires multiple tokens might use tokens whose provenance includes both sides of the double-spend, i.e. which are dependent on two spends that cannot be put in linear order (because they both spend the same token).
1.4. Existing work
The precise term ‘double spend’ predates blockchain. The first use we can find in print is a conference paper presented in 1989 and published in conference proceedings in 1990 [Cdv90] (see page 298 item 3, “When double spending of a check is found”). The term appeared in a popular science article in Scientific American in 1992 [Cha92] and was standard by the time Nakamoto used it in 2008 [Nak08]. The actual concept of a double spend in the context of digital tokens seems to originate in a paper from 1983 [Cha83] (see page 202, subsection 3.3 ‘Deposit Transaction’, item 11: “Bank adds note to comprehensive list of cleared notes and stops if note already on list”).5
The consistent-histories problem has many names. In blockchain systems it is studied as atomic cross-chain swap, bridge, wrapper, and general cross-ledger communication safety [Her18, HLS22, ZABZ21, BVGC21, ZHL19]. In distributed databases and distributed systems, related concerns appear as serialisability, atomic commitment, consensus-based transaction commit, and linearisability [Pap79, BG81, GL06, HW90]. In financial-market infrastructure, the same family of problems is discussed using the vocabulary of delivery-versus-payment, payment-versus-payment, tokenised deposits, tokenised reserves, unified ledgers, and atomic settlement [Com17, BE18, SKL20, Ban23, KLRZ25, Adr26]. Finally, the linear-resource aspect of the problem is naturally related to the vocabulary of linear logic [Gir87], which is part of why we name our Cut rule ‘Cut’ (the other reason being, of course, that it literally does cut controllers); and the exponential cake from Figure 1 is thus called because (like the exponential modality of linear logic) it can be copied and deleted.6
In this paper, we abstract away from domain-specific mechanisms. We give an order-theoretic treatment of independently evolving controllers connected by attestation, which we use to study how we can compress local history using Cut, while retaining the ability to detect contradictory spend histories.
1.5. The One True Controller (isn’t there)
Can we dissolve the problem by assuming all transactions settle on a single global controller? We argue that this is not realistic, because:
1. Major institutions — banks, central banks, blockchain communities — will not delegate their state to a common authority, for cultural and competitive reasons.
2. A successful candidate One True Controller would face prohibitive congestion and rent-seeking pressure: see the recent BIS working report [Shi26] and accompanying Financial Times analysis [Nan26].
3. Even if the One True Controller were built, applications benefiting from weaker trust models would split off, recreating the multi-controller world. The plural in “consistent histories” is essential: we need consistency across controllers, not consistency within one (which is a distinct and easier problem).
1.6. Outline of the solution: reducible controller tags
We start with a naive solution to the consistent histories problem:
Tag every resource with its complete history. These tags are carried around with the resource, and grow with each operation on it.
With the naive solution, it is easy to check for double-spends: for any two resources, just check their resource tags to see if they share an ancestor, or more generally, if they share an ancestor that was supposed to be linear but which was consumed by two distinct transactions.
Unfortunately, the naive solution is quite expensive. Every resource has to carry a complete history of everything that has happened to it, and everything it depends on, and everything that happened to its dependencies, and everything they depend on, and so on, transitively. Every token transfer imposes a cost not just now but on everything that comes after that transfer, cumulatively and forever. Can we do better?
We propose a more sophisticated solution, which comes in two parts:
1. Tags carry a reduced (= edited) version of the resource’s history. This reduced history tag grows as the resource evolves ...
2. ...but in certain circumstances controllers may carry out a Cut operation to edit (‘cut out’) parts of a tag that are no longer necessary, thus reducing its size.7
Concretely, a tag is structured as a path of times carrying flags which record each controller’s role in the history (a ‘next-index pointer’ to the next controller in the chain). The Cut operation (precise definition in Section 4) is a fully asynchronous operation which locally contracts three consecutive entries in a tag into two, eliminating a middle index while preserving contradiction structure.
The fundamental results of Cut are as follows:
• Theorem 5.6.2 and Corollary 5.6.3.
Consider the exponential cake example from Figure 1 and Example 1.2.1. Note that on the right-hand side of the Figure, we have two cakes, and the issue with this is not each individual piece of cake but the fact that the history of these two resources taken together is not consistent: it contains an illegal double-spend (specifically: and are contradictory).
So we want to analyse when a user can trust that their set of resources, taken together, has a consistent history.
Theorem 5.6.2 and Corollary 5.6.3 state that if the user trusts all of the active controllers in the tags of all of the resources in their current set of resources, then those resources have a consistent history, and in particular it contains no double-spends.
The power and the beauty of this is that the user does not need to trust controllers of cut tags: to ensure consistent histories, it is enough to trust what is active (and be right in those trust assumptions; but see next item).8
• Theorem 6.4.3 and Corollary 6.4.6.
These strengthen the previous results, at the cost of a bit more computation (a discussion is in Subsection 6.1 and Example 6.4.9). We show how one can prove — without trust assumptions on correct behaviour by controllers, but at the cost of a bit more work — that a set of tagged resources has a consistent history, even when the tags have been reduced using Cut operations.
The power of this is that no trust assumptions (whether correct or not) are required, and furthermore, consistency can be demonstrated between users who might not share the same trust assumptions.
The overall effect of this mathematics is to provide a space-efficient operation Cut which, in senses we make mathematically formal, safely minimises trust assumptions. With Cut, tokens need not be forever burdened with detailed tracing of the controllers through which they have travelled. This makes cross-controller transfers more economical, since they need not impede the fungibility of the token.
We can view Cut as a potent generalisation of the token-wrapping technique used in ICS-20 [Goe24]. This was originally designed to make it possible for an application to temporarily transfer tokens to another controller (perhaps for speed or co-location with other tokens), and then transfer them back. This is a common and desirable pattern. The generalisations here, which are significant, are that:
1. Cut is not a wrapper and does not require tokens to necessarily be immediately unwrapped in the same order they were wrapped, and
2. Cut allows stateful tokens whereas wrapping cannot (i.e. our cake can transition to an ‘eaten’ state).
So Cut is more general and more powerful than ICS-20; but still, it is in a similar spirit.
1.7. Map of paper
1. Section 1 is the Introduction. You Are Here.
2. Section 2 introduces the notion of a top-tree (sequential bounded semilattice) in Definition 2.1.1. This is a model of sequential computation, possibly with non-sequential behaviour. We also introduce the notion of a located semilattice in Definition 2.2.2, which is a suitable notion of forest of top-trees.
3. Section 3 introduces a located semilattice with Cut in Definition 3.2.1.
4. Section 4 introduces paths , derivations , initial prefixes, circuits , active indexes, and (active) inconsistency of circuit-derivations.
5. Section 5 proves many results (a map of them is at the start of the Section), including Theorem 5.6.2 and corollaries, that an inconsistent circuit-derivation has an active inconsistent index.
6. Section 6 strengthens this to an absolute criterion using a notion of C-closure of a set of times, in Theorem 6.4.3 and corollaries.
7. In Section 7 we return to the notion of located semilattice and give an alternative, and in a sense more abstract, characterisation of its structure.
8. Section 8 concludes with a discussion of the mathematics, and comments on related and future work.
9. For the reader’s convenient reference, we collect the main definitions and notation of this paper in Figure 2, with pointers.
List of Figures
1The exponential cake (Example 1.2.1)4
2Map of notation, with pointers (Subsection 1.7)9
3Example of a top-tree (a sequential bounded semilattice; Remark 2.1.5)12
4A sequential located semilattice as a forest of top-trees with controller-preserving, expansive, contradiction-preserving attestation (Remark 2.2.3)17
5The exponential cake as a sequential located semilattice (Example 2.3.4).20
6Flag ordering in Definition 3.2.128
8Attestation (Definition 3.4.3(3))36
9Derivations (Definition 4.1.1(4))38
10Two visualisations of (Remark 4.1.4(7))43
11Proof dependency diagram for Section 547
12Illustration of Lemma 5.2.249
13-closure of (Definition 6.2.1)64
14Future work: the exponential bike (Remark 8.4.1)84
2. Located semilattices
2.1. Top-trees (sequential bounded semilattices)
We start with a very simple model of sequential computation with ‘algebraic fork detection’. Definition 2.1.1 is an abstract description of the transition system of a single controller (= state machine); the reader who prefers diagrams might find it helpful to look at Figure 3 and at the worked example in Example 2.1.4.
1. A bounded semilattice is a tuple
such that:
(a) X is a set of elements which we may call states or times.
Above, elements increase left-to-right, so that intuitively time flows from left to right.
(b) : X X is an idempotent, commutative, and associative binary operation which we may call the join of the semilattice.
(c) As standard, write when , and note that this gives the structure of a partial order. We may also write or when .
(d) X are bottom and top elements such that
2. Call and incomparable when .
3. Call a bounded semilattice sequential when for every X we have
4. We may call the inconsistent element and we may call a such that consistent.
5. We may call a sequential bounded semilattice a top-tree for short; see Remark 2.1.5.
Suppose that X is a bounded semilattice (Definition 2.1.1(1)), and write for the partial order on X defined by when . Then the following are equivalent:
1. is sequential (Definition 2.1.1(3)).
2. For every X, . In words: incomparable elements have an inconsistent join.
3. X is a tree with as its root. More formally: for every X, is a linear order on X with as a least element.9
In words: a top-tree is a tree with a top.
By routine calculations.
Define X and order these elements by the reflexive-transitive closure of
Thus and are incomparable continuations of the partial history , while lies on a separate branch.
Some example joins (least upper bounds) are:
Thus when two consistent elements lie on the same branch, their join is the later one. When two consistent elements lie on different branches, their join is , reflecting that the two histories are incomparable and cannot be placed on a single sequential branch. For example and , but not .
We can think of a sequential bounded semilattice structurally as a tree representing the branching structure of possible evolutions of some sequential process, with a top element adjoined to represent computations that have deviated from admissible paths, as illustrated in Figure 3 and in Example 2.1.4.12
Why do we call ‘inconsistent’, and (if ) ‘consistent’?13 We can reply that and are just bounding elements in the semilattice: we can call them what we want. Fair enough, the reader might respond, but by what intuition would we want to call ‘inconsistent’, and (if not equal to ) ‘consistent’?
We are interested in modelling Byzantine (= faulty / hostile) behaviour, thus, we want our branching structure to reflect the possibility that the process might not be sequential (even though this is faulty behaviour). So we need a top value, to represent nonsequentiality.14
Thus, a sequential bounded semilattice is a tree, with a top element; thus, a top-tree.
The top element is the least upper bound of any pair of elements coming from distinct branches of the body of the tree. This neatly represents non-sequential behaviour, i.e. behaviour that is ‘inconsistent’ with being on any single branch of the behaviour tree.
Or to put it another way, is an ‘algebraic fork detector’; it is where we go when we detect a fork.
Conversely describes a process that has displayed no behaviour, or no behaviour aside from initialising, and this behaviour is ‘consistent’ with being on any branch of the behaviour tree, i.e. it is the root of the tree.
The reader is welcome to think of however they find most intuitive: e.g. as a top element, as an exception value, as a point at infinity, as a fork detector, or as a final element.
We mention two elementary lemmas which will be useful later:
Suppose X is a bounded semilattice and suppose X. Then
just means and similarly for . The result follows by monotonicity of join.
Suppose X is a sequential bounded semilattice and suppose X and (so and are consistent). Then and are incomparable if and only if they contradict.
Definition 2.1.1 makes a top-tree a poset (with antisymmetry: ). Relaxing to a preorder would permit coequal but non-equal elements — that is, two elements each of which is the other, but which differ. This is distinct from a fork, in which neither element is the other.
Coequality might be useful, e.g. when two changes to unrelated state commute, or when a concrete model carries intensional structure that is not visible to .
Since any preorder quotients to a poset, there is no essential mathematical difference here. We choose posets here as a simple and convenient design point.
Top-trees are not a complicated idea — just a tree with a top element — but to our knowledge they have not previously been precisely identified in the literature as an algebraic definition. A notion of top-tree appears in [AHLT05] as a data-structure interface for fully dynamic forests; this is not connected to the top-trees from Definition 2.1.1.
2.2. Located semilattices
Top-trees from Definition 2.1.1(5) arise very naturally from sequentiality/serialisability: they abstract the state of a sequential, possibly Byzantine process.
We now add a notion of attestation to our model. Intuitively, attestation is how one location (or process) can update its view of the state of another location (or process).
A special feature of how we formulate attestation is that
controllers can attest to each other opportunistically: attesting to some other controller does not limit a controller’s future actions (aside from not being able to consistently attest to directly contradictory states from that same other controller).
This matters. It ensures that cross-controller applications can operate swiftly and smoothly (or at least, if they do not, it is not because any controller feels reluctant to make attestations).
For example, in Figure 1, if controller 1 attests to one fork of controller 2, and controller 3 attests to another fork of controller 2, it is crucial that controllers 1 and 3 can still attest to each other. Attesting to one controller never limits your ability to attest to another controller.
The only thing a controller cannot consistently do is to attest to directly contradictory states at the same controller: if, in Figure 1, controller 1 attests to , then it cannot later attest to (or any element after ). But this does not inherently limit the actions of controller 1; it just makes controller 1 a
good observer of the world around it, and able to detect Byzantine behaviour. In particular, it is not contradictory for controller 1 to attest to and also to attest to controller 3 having attested to . We will return to this point in Subsection 8.2.3 (non-transitivity of attestation).
We are now ready to formally define located semilattices and attestation:
A located semilattice consists of a tuple
— we may drop the subscripts henceforth — where
1. Ctrl is a set of controllers, and Time is a set of times.
2. ctrl : Time Ctrl assigns to each time Time a controller ctrl, which we call the controller or the location of .
3. : Time Time is an attestation function. By convention associates to the left, so that means .
4. If Ctrl then we define Time the times at by
5. For each controller Ctrl,
(i.e. the set of times controlled by , where is restricted to times in Time) forms a bounded semilattice (Definition 2.1.1), with as its join.
6. In view of point 5 above, we may use notation as follows, for Time and ctrl ctrl:
(a) We may write as , because as per point 5 the times controlled by the controller ctrl ctrl form a semilattice under .
(b) We may write for the partial order of Time, thus for Time we have when (and equivalently, when ). We may also write to mean .
(c) We may write for the top element and for the bottom element in Time.
(d) Following Definition 2.1.1(4) and Remark 2.1.5, we may call the inconsistent time at , and we may call any Time such that a consistent time. We may drop the subscript where this is unimportant or clear from context, writing just and . For example, is short for (where recall that ctrl).
7. We assume the following properties of for every Time such that ctrl ctrl and ctrl ctrl:
(a) Attestation is controller-preserving:
(b) Attestation is expansive:15
or equivalently: .
(c) Attestation is contradiction-preserving ( is from Definition 2.1.3): implies Intuitively: attesting to a contradiction is a contradiction; in the language of blockchain, attesting to a fork is a fork; and in the language of order-theory, attesting to incomparable times leads to incomparable times.
8. If Time is sequential for every Ctrl, then we may call a sequential located semilattice.
1. Visually, we can imagine a sequential located semilattice from Definition 2.2.2 as a forest of top-trees (sequential bounded semilattices), as illustrated in Figure 4 (note: we illustrated a top-tree in Figure 3).
2. The diagram also illustrates what makes a sequential located semilattice more than just a forest of top-trees: the attestation function . Attestation plays a dual role in a located semilattice:
(a) Within a single controller (i.e. a controller attesting to itself), behaves like semilattice join. So if ctrl ctrl Ctrl then is the semilattice join on Time. It is idempotent, commutative, and associative, with bottom and top . It is also the mechanism by which sequential histories are compared: is equal to (when precedes ), or equal to (when precedes ), or equal to (when and are on distinct branches of the top-tree Time.
(b) Across distinct controllers (i.e. a controller attesting to a distinct controller) is how one controller records information about (‘attests to’) another controller. So if ctrl ctrl then is a -controlled time. The operator is not necessarily commutative or associative, but it is expansive, meaning that , and this encodes that advances its local time by recording information about . Contradiction is transported across : if then .
Some notation will be useful:
1. Suppose is a located semilattice. We may drop the subscripts. Write CTime for the set of consistent times in Time, and if Ctrl then we may write CTime for the consistent times in Time controlled by . In symbols:
2. Recall that Definition 2.1.3 defines to mean where and are elements of a bounded semilattice. However, in Definition 2.2.2(7c) we write for and elements of a located semilattice (not a bounded semilattice). We can do this, because in that Definition we also assumed ctrl ctrl, and we insisted in Definition 2.2.2(5) that for a controller , Time (the set of times controlled by ) does indeed form a sequential bounded semilattice, with as its join. So far, so good.
We extend to the case where Time and and do not necessarily have the same controller, as follows:
(a) If ctrl ctrl then when , just as in Definition 2.1.3.
(b) If ctrl ctrl then . In words: times at distinct controllers cannot contradict.
Suppose is a located semilattice and . Then
• if
• then ctrl ctrl and .
Attestation is an expansive operator, as per Definition 2.2.2(7b). Later on we will encounter flags, which are also expansive, as per Definition 3.1.1(2). So expansivity is a recurring theme in our development.
The property of an operator being expansive — — is also called inflationary or extensive in the literature. We prefer expansive because: ‘expansive’ has a convenient noun ‘expansivity’, whereas arguably ‘inflationary’ does not (‘inflationarity’? ‘inflativity’? ‘inflation’ would work but is less direct); and it is unambiguous (‘extensive’ and ‘extensivity’ sound like ‘extensional’ and ‘extensionality’). Tastes differ so if the reader prefers inflationary or extensive then they are welcome to mentally translate and no harm will come of it.
Definition 2.2.2 will serve our needs very well in what follows, but there are certainly ways we can imagine to reformulate or generalise it. Two may deserve particular mention:
1. A slightly different way of looking at the same ideas is presented in Section 7. Depending on taste, the reader might prefer it, and if so they are welcome to skip ahead.
2. Attestation from Definition 2.2.2(3) is single-shot: it takes one time and one time and forms one time . We could structurally generalise this to a multi-shot version , where is a set of times — perhaps is some set of prerequisites or preconditions for the controller of to make progress, and this set does not come in any particular order and perhaps it is convenient for this to be structurally reflected in the attestation. We do not do this here because the single-shot version will be entirely sufficient for our needs. Should our needs change in future work, there would be no structural barrier to such a generalisation.
2.3. Examples of located semilattices
Located semilattices may be motivated by interacting state machines, but as a mathematical framework they have their own quite interesting identity. We give some examples to indicate how they can accommodate aspects of logical connectives, the exponential cake, games, state machines, and closure operators:
1. Example 2.3.2 is a simple but not self-evident example of a located semilattice attestation with two controllers and an attestation whose cross-controller behaviour has the flavour of a simple three-valued logic connective.
2. Example 2.3.3 is an even simpler example, where the attestation is just identified with logical , regardless of whether it is cross-controller or not.
3. Example 2.3.4 moves away from truth-tables: we render the exponential cake as a located semilattice.
4. Example 2.3.5 moves further towards process-flavoured examples: we render the children’s game of paper-scissors-stone as a located semilattice.
5. Example 2.3.6 illustrates a state machine as a located semilattice. There are two participants: one represents the state machine, and the other represents inputs to that machine, via attestation.
6. Example 2.3.7 takes a new direction and has a more order-theoretic flavour. Attestation is identified with a closure operator.
This should give some sense for some of the things to which located semilattices can be applied.
Define a sequential located semilattice Ctrl Time ctrl such that:
• Ctrl P Q (so there are two controllers).
• Time Ctrl 3 where 3 f b t. We endow 3 with the order
so that f and t for Ctrl. We let tv (short for ‘truth-value’, because 3 looks like values of a three-valued logic), and we define : 3 3 to be least upper bound and t f and f t and b b:
• ctrl.
• We define as follows:
Thus when , we have that tv is equal to t if tv b b, and is equal to b if tv b.
This is a located semilattice:
• is controller-preserving.
• is expansive because tv either returns t or (if tv b) it returns tv.
• It is easy to check that is contradiction-preserving.
Attestation is not monotone in either component. For example:
1. f b but
2. f b but
A simple variant of Example 2.3.2 is monotone. We take everything as in that example, except that we define tv by
This too is controller-preserving, expansive, and contradiction-preserving. We will generalise this when we consider the principal attestation in Example 7.4(2).
We return to Figure 1 and interpret it as a located semilattice (Definition 2.2.2). We illustrate this in Figure 5.
The three Controllers correspond to Ctrl 1 2 3. Nodes are times in Time, with ctrl ctrl ctrl ctrl 1, and similarly for Controllers 2 and 3.
Write Time@2 for Controller 2’s state on the forked branches sending the cake toward Controllers 1 and 3 (Figure 5 labels the pre-fork time ). By construction and are incomparable, so , i.e. .
The dashed lines in Figure 5 are attestations. When Controller 2 receives the cake at event , it advances its local time by attesting to Controller 1’s state at . When Controller 1 receives a cake back at , it attests to (along the upper branch); when Controller 1 later receives a cake via Controller 3 at , it attests to a state that transitively depends on .
Define a sequential located semilattice Ctrl Time ctrl such that:
• Ctrl Alice Bob (so there are two controllers).
• Time Ctrl Play where Play paper scissors stone.
It is convenient to give Play a bounded semilattice structure such that play for every play Play, and there are no other comparisons (so for example paper scissors )
• We define as follows:
– play play for Ctrl and play Play.
– For Ctrl and play Play we define:
• ctrl play.
Intuitively, this represents a simplified paper-scissors-stone game where attestation represents a play of the game:
• If a play survives the attestation unchanged, as in paper stone paper then this is a win.
• If a play goes to , then this represents a loss, a draw, or an invalid round.
This is a located semilattice:
• is controller-preserving.
• is expansive because play either returns play or .
• is contradiction-preserving. The argument is by cases. The nontrivial case is when and paper scissors stone so that
(meaning: ). Define
– If or then is immediate.
– If then it must be that
But we assumed and therefore , and thus .
Note that attestation is not monotone in either component. For example:
1. stone but
2. paper but
Define a sequential located semilattice Ctrl Time ctrl such that:
• Ctrl JosefK Prozess (so there are two controllers).
• Time Ctrl State where State . We let range over 0 1 2 and range over all of State. We endow State with the usual order on numbers, with as a top element:
• ctrl.
• We define as follows:
The reader can check that each Time is just ordered as State:
and this is clearly a sequential bounded semilattice. It is easy to check that is controller-preserving and expansive. is also contradiction-preserving, for suppose . It follows that or (or both). Then or as required.
is not monotone in the first component. For each Ctrl,
This is non-monotonicity of a particularly illuminating kind. Attestation has a flavour of moving a sequential process forward: each can only be moved forward by attesting to 1; otherwise the attestation fails.
Imagine that Prozess is a bureaucratic system, implementing some process. JosefK is the person trying to navigate it. The state represents that has correctly received (here modelled by ‘attested to’) forms 1 up to , and in this state, is waiting for to provide form 1. There are infinitely many forms for to fill in, and at each step has to perfectly fill in precisely the correct next form or will reject it (this rejection is modelled mathematically by transitioning to ).16 Thus for ,
So “form 1, then form 2” succeeds (or at least, it does not fail), while “form 2, then form 1” fails.
We highlight this example because the non-monotonicity of attestation is (or rather, can be) here a feature of what we want to model. It reflects our underlying interest in modelling sequential processes. Thus, non-monotonicity is not a bug.
Lest Examples 2.3.5 and 2.3.6 give an impression that a monotone attestation would a priori be bad, we give an example in which on the contrary this is possible and meaningful:
Define a structure Ctrl Time ctrl as follows:
• Fix some set Fact of facts.
• Let Ctrl be any nonempty set.
• For each Ctrl fix some set powFact such that is closed under arbitrary (possibly empty, possibly infinite) set intersection, and Fact (the technical term for this is a closure system or Moore family [CM03, DP02]).
We call an inference. Thus, every inference is a set of facts, but not every set of facts is an inference.
• If Fact then define
and call this the -closure of . We think of - as a notion of deduction by ; given a set of facts , is the inference that can draw from . Note that each has its own notion of inference.17
• Time Ctrl . We endow Time with a partial order by
• ctrl.
• We define as follows:
It is routine to check that is controller-preserving and expansive. It is also routine to check that is idempotent, commutative, and associative on each Time, with as bottom element and Fact as the top element.
We give the core of the proof of associativity. First, we note two very simple facts:
• If Fact and then if and only if .
• if and only if :
We now reason as follows on (where we omit the subscript for clarity):
Taking to equal each side in turn, we conclude that , and by similar reasoning we also conclude . Thus , and associativity follows.
as defined above is not in general contradiction-preserving, which means by Definition 2.2.2(7c) that we do not quite have a located semilattice (yet).
Let us note that this is not necessarily a bad thing. It usefully illuminates a design space of generalisations of Definition 2.2.2.
To now obtain contradiction preservation and thus a located semilattice, we mention three options:
1. A necessary and sufficient condition is just to insist for every Ctrl that
2. A stronger condition is to insist that all notions of inference are identical: always. This is perhaps a bit stronger than we might like here.
3. An arguably more interesting condition is this:
Intuitively, this is a well-pointedness condition: controllers may have different notions of inference, but any contradiction is witnessed by (at most) two globally contradictory facts.18
Further examples of located semilattices appear throughout the body of this text, and in Section 7 (alternative presentation).
3. Located semilattices with Cut
3.1. Flags and flag-sets
A flag on a located semilattice Ctrl Time ctrl is a function
which we write in the style of a modality as Q (rather than as a function Q), such that for every Time:
1. Q is controller-preserving: ctrlQ ctrl.
2. Q is expansive: Q .
So in words: a flag is a controller-preserving, expansive operator on times.
Suppose Ctrl Time ctrl is a located semilattice with a flag Q, and suppose . Write that
has the form Q or just Q
when the following hold:
1. (so is a consistent time), and
2. Q for some Time.
When Q is consistent, we may say that has the flag .
A flag-set on a located semilattice is a set of flags on (Definition 3.1.1) such that for every Q and we have:
We say that flag application is injective where consistent. Put another way: if two times (Q and above) have flags and are equal, then those flags are equal.
Suppose Ctrl Time ctrl is a located semilattice with a flag-set , and suppose . Define flag by
• flag Q when Q for Q .
• flag undef when Q for every Q .
Above, undef is a special value used to represent a partial function as a total function. Traditionally in programming this would be written , but we are already using for ‘false’, and for ‘the least element of a bounded semilattice’ (Definition 2.1.1(1)).
We warm up with an easy lemma:
Suppose Ctrl Time ctrl is a located semilattice with a flag-set , and suppose Ctrl. Then:
1. Q for every Q .
2. As a corollary, flag undef .
We make a couple of simple observations about flags’ behaviour:
Suppose is a located semilattice with a flag-set . Then:
1. It is possible for a time to not have any flag.
2. It is possible for a flag to exist but no time to have it.
We consider each part in turn:
1. Consider the inconsistent time for some Ctrl. This has no flag, as noted in Remark 3.1.6.
2. To illustrate the design space, we provide an even more extreme counterexample, of a flag on a located semilattice such that no time has that flag. Let the inconsistent or top flag TopFlag : Time Time be such that TopFlag always. Then TopFlag is a flag by our definition, but by construction no time has it.
More liberal notions of flag-set are possible. For instance we could permit multiple flags on a time. However, Definition 3.1.3 as written will suit our purposes here.
3.2. Located semilattices with Cut: the flag-set
3.2.1. The definition
A located semilattice with Cut is a located semilattice with the cutting flag-set (we discuss why this flag-set in Remark 3.2.3)
where for each the three flags
• , read nextindex-,
• , read cutme-, and
• , read cutyou-
have the following properties for every index and every time Time such that ctrl ctrl:
1. .
2. .
3. If then .
4. .
5. The mapping
is injective. In words: flags with distinct symbol-index pairs, are distinct flags.19
For the reader’s convenience, we present Definition 3.2.1 as a diagram:
• A representation of properties 1 to 4 is sketched in Figure 6.
• Arrows indicate -relations coming from properties 1, 2, and 3.
• Property 4 is represented by the absence of a -directed path between and (they always lie on distinct branches).
Also, we give pointers to where each of the properties is technically used in the proofs to follow:
1. Property 5 gives Lemma 3.2.5 and ensures that any consistent time always has at most one flag.
2. Property 1 allows a process to use Inc to ready itself to be Cut. We use it in Lemma 4.2.2 (times increase) for the case of Intro.
3. Property 2 allows a process to use Inc to ready itself to execute a Cut. We use it in Lemma 4.2.2 (times increase) for the case of Intro.
4. Property 3 allows a process to complete a Cut. We use it in Lemma 4.2.2 (times increase) for the case of Cut, and also in Lemma 3.2.4, which is key to creating active inconsistent indexes in the proof of Corollary 5.5.3.
5. Property 4 is arguably the most technically subtle condition. It plays a key role in Proposition 5.5.4, where we use it to derive a contradiction from right-incompatible cuts.
Intuitively, the flags in Definition 3.2.1 are an abstract protocol for Cut (= edge-contraction) in a linear path:
1. The flag means my successor is index .
2. The flag means my successor is index , and I am ready to cut from my path. The inequality is the preparation step, where the process asserts its readiness to cut. The symbol represents a raised pair of scissors, about to cut.
3. The flag means my successor is index , and I am ready to be cut. The inequality is the preparation step, where the process asserts its readiness to be cut. The symbol represents a lowered pair of scissors, in the process of cutting.
4. The idea of the Cut rule is that two polarities and cancel out to make a :
The inequalities for represent possible completion steps, such that gets cut and the cutting index (written above) continues to point to index as its new successor.
5. The contradiction is a consistency condition: it ensures that and are impossible (i.e. we have to pick whether to cut or be cut), and furthermore it ensures that and are impossible, meaning that once we enter a cut-me or a cut-you state, we are committed to this and cannot back out.
The details of making this all work are quite involved (see Figure 9), but that is the intuition.
Lemmas 3.2.4 and 3.2.5 will be useful later. The proof of Lemma 3.2.4, while simple enough, is geometrically clear from Figure 6; there is no path from a -node to a lesser -node:
Suppose is a located semilattice with Cut and suppose Time and ctrl ctrl, and suppose . Then
Lemma 3.2.5 is a convenient wrapper for Definition 3.2.1(5). It just states that flags with different names do generate distinct times, always (so that for example is never possible, provided all times concerned are consistent):
Suppose is a located semilattice with Cut and suppose Time and and Q . Then
The conditions above — particularly those in Definitions 3.2.1 and 3.1.1 — are what we need for the proofs below.
But we can imagine further properties, which might be relevant in future work. We list some here:
1. If then and .
2.
3. , provided ctrl ctrl (required so that the is well-defined).
4. If then .
5. ...and so on.
Note that these extra properties are not forbidden; our results below will be valid whether or not they hold.
3.2.2. Scope-extrusion: a computational rule for flags
Definition 3.2.7 extends the notion of flag with an additional well-behavedness property:
Suppose Ctrl Time ctrl is a located semilattice. Say that a flag Q : Time Time has (lax) scope-extrusion or is scope-extruding when for every Time
Suppose Ctrl Time ctrl is a located semilattice and suppose Q : Time Time is a scope-extruding flag on in the sense of Definition 3.2.7. Suppose Time. Then
As a corollary, the following derivation-step is valid on paths:
We call the scope-extrusion property in Definition 3.2.7 lax, because this is an inequality, not an equality. We discuss why, in part 2 below.
1. Lemma 3.2.8 gives scope-extrusion a strong computational interpretation: it means that flags really do behave like flags, in the sense that a controller can attest to a time without changing its flag (provided no inconsistency is introduced). This intuition becomes structurally important in Remark 4.1.4(7c), where it gives a nice computational interpretation to Cut.
Another way to see the value of scope-extrusion is to look at Figure 10. If we want controllers to be able to evolve between adopting one of the flags in that Figure, and the other steps necessary for the cut, then scope-extrusion and Lemma 3.2.8 would allow us to do that.
2. Why is scope-extrusion lax? Suppose we take an equality in Definition 3.2.7. We want to permit to evolve into via some internal computation (a computation which our logic abstracts over), thus we assume (Definition 3.2.1(1)), i.e. or equivalently . But scope-extrusion interacts with the rest of our system in perhaps unexpected ways. Suppose we have that scope-extrudes over (Definition 3.2.7) strictly, i.e. with an equality, and note that by Definition 3.1.1(2). Then we could reason as follows, for CTime:
Thus and by Definition 3.1.3 , contradicting the distinctness condition in Definition 3.2.1(5).
3. Intuitively, serves a dual purpose:
• is how ctrl accepts (attests to) information from ctrl, and
• where ctrl ctrl is how we partially order states of ctrl (as per Lemma 2.1.2 and Definition 2.2.2(6b)).
Now a flag represents, intuitively, an ‘operating mode’ of a controller, and represents a (very abstract notion of) state transition. Using in the scope-extrusion principle Q Q separates inputting information from taking a computational step to integrate that information.
4. We never actually use scope-extrusion in the proofs.
That reflects that it has computational meaning, but this paper is about proof, not computation. The weaker our assumptions are — while still deriving the
main result Theorem 5.6.2 — the more powerful that result is.20 We see from part 2 of this Remark and from Remark 4.1.4(7c) that there is a non-trivial interaction between the computationally relevant principle of lax scope-extrusion and the rest of our framework — but the maths in this paper will not need to know whether our located semilattices with Cut are computational, or not.21 Accordingly, for generality and simplicity, we omit scope-extrusion from Definition 3.1.1 even though computationally relevant flags will likely have the property.
3.3. Consistency
Remark 3.2.9(2) should give us pause for thought: the incompatibility of scope-extrusion-up-to-equality with the other axioms, is not evident. We should prove consistency. We will do this by constructing various models of our axioms. We will produce four, of increasing levels of complexity and realism:
1. In Proposition 3.3.1 we present a simple and accessible model which is sufficient to prove consistency.
2. Definition 3.3.2 shows how to leverage the simple model to something more elaborate, in a pleasingly modular manner.
3. Definition 3.4.3 and Proposition 3.4.5 present a more elaborate construction.
4. Definition 3.4.3 presents a version which (modulo some practical considerations, like hashing some data values) is close to how we envisage a practical implementation might look.
3.3.1. Consistency
A (sequential) located semilattice with Cut as per Definition 3.2.1 exists.
We must exhibit a concrete instance of Ctrl Time ctrl with Cut. We provide the following relatively simple and compact example:
1. Ctrl (so there is only one controller; we consider a multiple-controller extension in Definition 3.3.2).22
2. Time (ni stands for ‘next index’, cm stands for ‘cut me’, and cu stands for ‘cut you’).
3. We define ctrl : Time Ctrl by ctrl.
4. We endow Time with a partial order Time2 defined as the least transitive reflexive relation such that for every and every Time we have:
for
5. We define : Time Time by
Above, refers to least upper bound in Time according to the partial order from part 4 of this example.
6. We specify flags by letting symbols act on times as follows:
We briefly sketch why this structure is indeed a located semilattice with Cut:
1. Time (at the unique controller ) is a top-tree by construction in clause 4 above.
2. Attestation (at the unique controller ) is a semilattice join operation by construction.
3. Attestation is controller-preserving (there is only one controller), expansive (because it is a join operation) and contradiction-preserving (because it is a join operation), as per Definition 2.2.2(7).
4. Flag application is expansive by construction, as per Definition 3.1.1(2).
5. Flag application is injective where consistent as per Definition 3.1.3. We indicate why. Suppose Q . It follows from the flag action in clause 6 above that and Q Q and . Thus Q and as required.
The model given in Proposition 3.3.1 has only one controller. However, this paper is motivated by how digital resources can move across controllers, so it would be nice to see a concrete model in which this could happen. Fortunately, we can just use our existing one-controller model and systematically multiply it with itself:
Suppose Ctrl Time ctrl is a located semilattice with Cut with just one controller. Define a located semilattice with Cut
as follows:
1. Ctrl0 1 2 3.
2. Time Time.
3. , or equivalently (since has one controller) .
4. ctrl.
5. Q Q , for each flag Q.
Continuing the notation of Definition 3.3.2, Ctrl Time ctrl is indeed a located semilattice with Cut.
First, note that for each Ctrl, Time is just a copy of Time (so single-controller behaviour is as in Proposition 3.3.1). The only difference now is that controllers can also attest to one another’s times. We check the rules for attestation and flag application from Definitions 2.2.2(7), 3.1.1, and 3.1.3, and we see that they all hold.
3.4. An inductive construction
Subsection 3.3.1 exhibits single-controller and multi-controller located semilattices. The notion of attestation in those models is simple: the state of a controller is a local view of a global notion of state, in the sense that attestation just updates local state with the view of another controller.
We now give another construction with a more sophisticated notion of attestation. A time consists of a tuple where is a controller identifier, is a local state, and is a list of views into the times of the other controllers.
This is closer to what a realistic implementation would look like. In a real implementation, for efficiency reasons, we might prefer to store as a list of cryptographically succinct digests of the other controllers’ times. Aside from that, the construction which now follows is essentially a realistic rendering of what a real-life located semilattice (with or without Cut) might look like.
Some notation will be helpful:
Suppose is a set and 1 and is an -tuple of elements of . We may switch freely between function and tuple notation for . Suppose 1 and . Then define list update : by
This is the tuple obtained by updating the th entry to . For example:
For this subsection we fix the following data:
Above, Time so that ctrl, and Time so that ctrl. We write 1... for compactness.
Figure 8. Attestation (Definition 3.4.3(3))
1. We fix some number 1, and we define 1... by
1... will be the set of controllers in the located semilattice which we are about to construct.
2. We fix X a bounded semilattice such that (we call this nondegenerate).
Define a located semilattice Ctrl Time ctrl as follows:
1. Ctrl 1...: controllers are natural numbers.
2. Times Time are defined following the rules in Figure 7.
In particular, every time has the form , or , or where 1... and X and is a list of 1 times (but not every such tuple is a time; only the ones that can be derived using the rules in Figure 7). There, consistent with Definition 2.2.2(4) and Notation 2.2.4(1), we write Time for the times controlled by controller , and CTime for the consistent times controlled by controller (so CTime Time).
3. Attestation is defined for Time and Time as per the rules in Figure 8.
We reason by induction on , following the clauses in Figure 7:
• Suppose for some Ctrl. Then as required.
• Suppose for some Ctrl. Then as required.
• Suppose for some Ctrl. Then 1... and we use facts of semilattices and the inductive hypothesis.
We must prove is controller-preserving, expansive, and contradiction-preserving, and that Time is a bounded semilattice for each 1....
• Controller-preserving. ctrl ctrl is a fact of Figure 8.
• Expansive: . We work by induction on .
– Suppose . Then and we are done.
– Suppose and . Then and and by Lemma 3.4.4 , so we are done.
– Suppose . Then and we are done.
– Suppose and ctrl. Then and we are done.
– Suppose and ctrl. Then 1...: (as per the second subcase of the fourth clause in Figure 8), and then and we are done.
– Suppose ctrl ctrl and and . There are two clauses for this in Figure 8 depending on whether , or for some 1... (the first clause, which returns ) — or not. We consider just this latter case. Then
and we use facts of semilattices and the inductive hypotheses on the .
– Suppose ctrl ctrl and and where . Then using facts of semilattices and Lemma 3.4.4 we calculate that
We use the inductive hypothesis on .
• Contradiction-preserving: if ctrl ctrl and ctrl ctrl then implies . By a routine induction on times in Figure 8. Suppose . Following the structure of Figure 8, it must be that or that for some 1.... It is then routine to check that follows.
• Time is a bounded semilattice for each 1.... By a routine induction on times in Figure 8, taking . We just note that when , acts as semilattice join on and , and acts componentwise and inductively on the lists, and it defaults to when it detects a contradiction in any component.
4. Paths and circuits
4.1. Paths
Throughout this Section, we assume that Ctrl Time ctrl is a located semilattice with Cut.
1. Define an -prepath to be an -tuple of consistent times, for 1. (Following Definition 2.2.2(6d), a time is consistent when .) In symbols and using Notation 2.2.4(1):
2. It will be convenient to write prepaths right-to-left, so that the first element of a prepath is written on the right, not on the left:
This might seem odd until we realise that this is the ordering that a list would have if we first push , then we push , then , and so on until . Thus is the th element to be pushed on the list and it is on the left, and is the first element to be pushed on the list and it is on the right.
3. Suppose is an -prepath. We introduce some notation:
(a) We may call an index in when 1 length.
(b) We write index for the set of indexes in .
(c) We write length for the number of indexes in (i.e. for the size of index).
(d) We write for the value at the -th index of (thus: the th projection of ).
4. Define derivation-trees, or just derivations, inductively by the rules in
Figure 9. We introduce some notation:
(a) Write root for the prepath that is at the root of .
(b) Write index for indexroot (the set of indexes of the prepath which derives).
(c) If index then write for root (the -index value of the prepath which derives).
(d) In Figure 9 we insert subscripts to record the indexes involved in the derivation step as appropriate, as in or . We may omit these indexes where they are unimportant or understood. This is just because, usually, when we discuss Cut we typically want to prove something for which the choice of index really matters23 whereas when we discuss other rules, the index (while still necessary) is not typically central to the discussion.
(e) Disambiguation alert. in Figure 9 has a side-condition flag flag. For clarity, we will unpack what precisely this means. Not every time has a flag, and as per Definition 3.1.4, flag is a total function which returns a special value undef if its argument has no flag to return. Thus, both sides of the condition flag flag are defined, always, and unpacking what this means: if has a flag then has the same flag, and if has a flag then has the same flag, and if has no flag then has no flag, and if has no flag then has no flag.
5. Define Path the set of -paths to be the set of -prepaths that are equal to root for some valid derivation . That is: Path is the set of -prepaths that are inductively derivable by the rules in Figure 9.
6. We may omit the annotations on prepaths and paths, if is unimportant or understood.
We take a moment to rephrase Figure 9, less diagrammatically and more programmatically.
We can specify the derivation rules in Figure 9 using Notation 4.1.2 as follows, where we write for the path above the line in the derivation rule (if there is one) and we write for the path below the line:
1. : where , provided and flag flag (and provided is consistent).
2. Init There is no above the line. 2 ::, where :: denotes concatenation of tuples (provided is consistent and is consistent for every 2 ).
3. : where (provided is consistent).
4. : where (provided is consistent).
5. : where and and , provided index (and provided is consistent).
6. The bracketed consistency conditions above spell out conditions which technically we do not need to state because they are structurally built in to our definitions — but we mention them anyway, for clarity: in Definition 4.1.1(1)
a prepath is defined to be an -tuple of consistent times for 1, and in the definition of : we assume is a consistent time. Thus, the derivation rules are subject to a well-formedness condition that times remain consistent below the line, so that a derivation rule can only be applied where it does not introduce an inconsistent time below the line, for any controller Ctrl.
We discuss the derivation rules in Figure 9 in turn:
1. Each of the derivation rules with a path above the line — Inc, Intro, Intro, and Cut — changes precisely one index of the path. This is a deliberate choice which reflects that we are modelling a distributed system. A rule that modifies two path indexes simultaneously would be a rule whose implementation might require synchronous coordination between controllers. Synchronous coordination would by definition undermine the ‘distributed’ nature of our ‘distributed system’. Part of the point of inventing located semilattices with Cut was precisely to implement a Cut-like structure such that synchronous coordination between controllers is not required.
2. Init starts a derivation with a path in which each time points to the previous time.
3. allows a controller at index to evolve to any later time with the same flag (if any), subject only to a restriction that doing so must retain consistency. In an implementation, controllers would not just evolve times randomly, but our mathematics is designed to be general, so it makes no restrictions here. For our purposes this is a good thing, because it minimises our assumptions and so maximises the applicability of our results.
4. The same-flag restriction in Inc is very important, because we use other flags to control flag-transitions: Intro for transitioning from to ; Intro for transitioning from to, and Cut for transitioning from to for . No derivation rule lets us transition from to , and this matters: see Lemma 5.1.1.
5. allows a controller to transition from a ‘’-state to a ‘’-state, meaning intuitively that is ready to be cut by some to its left.
6. allows a controller to transition from a ‘’-state to a ‘’-state, meaning intuitively that is ready to cut some to its right.
7. The Cut rule. We reproduce the rule here for convenient reference:
In words, we will say that in this rule index cuts index to . This might look a bit complicated, so we read through it. Encoded in the pattern of attestations above is the following sequence of actions, which we also draw diagrammatically in Figure 10:
(a) Index transitions from to using Intro.
(b) In parallel with the previous step, index transitions from to using Intro.
(c) Index attests to the state of (the controller at) index , using Inc with expansivity (Definition 2.2.2(7b)) and then scope-extrusion (see Definition 3.2.7 and subsequent discussion). We illustrate this step in detail:
(See also equation (1) in Lemma 3.2.8 and Remark 3.2.9(4).)
(d) Index attests to using Inc with Definition 2.2.2(7b).
(e) Index transitions to using .
Note: when we write ‘index’ above, we should more precisely write ‘the controller at index’; e.g. “Index transitions” should be “The controller at index transitions”. However, this may look messy so we omit it for clarity. The reader is welcome to mentally restore ‘the controller at’ everywhere, if preferred.
8. We use the specific pattern of attestations of Cut at three points in our proofs below:
(a) In point 4 in the proof of Lemma 5.5.1, we use the fact that the time at the -index has the form .
(b) In point 1 in the proof of Proposition 5.5.4, we use the fact that the time at the -index has (in the notation used for Cut in Figure 9) the form .
(c) In point 2 in the proof of Proposition 5.5.4, we use the fact that the time at the -index has (in the notation used for Cut in Figure 9) the form , which by flag expansivity is to .
Definition 4.1.5 will become important later, but we mention it here:
Suppose is a derivation of a path .
1. Call an index index-inactive when index and and for some Q . For clarity, we give an illustration of a path such that indexes 3 and 2 are 4 1-inactive. Arrows are just annotations to illustrate intuitively to which index a flag points:
Path :
2. Call an index index-inactive when is inactive in root — thus, when index and and for some Q .
3. If and are unimportant or understood then we might just call inactive.
4. If is not inactive then call active.
4.2. Initial prefixes
The derivations specified in Figure 9 are tree structures, but furthermore they are nonbranching trees — also known as lists — since every derivation rule has either zero (for Init) or one assumption (all other rules). This justifies a definition which will prove very useful, starting with Definition 4.3.2:
Suppose and are derivations and is an initial prefix of , and suppose index. Then .
We check each of the rules in Figure 9 and note that times always increasing is a fact from the inequalities in Definition 2.2.2:
• Inc follows from the side-condition in that rule.
• Init has no assumptions so there is nothing to prove.
• Intro follows from Definition 3.2.1(1), that .
4.3. Circuits
Recall from Definition 4.1.1(3d) that if is a path and index then denotes the th element of (which is just a length-tuple of times).
1. Define a circuit to be a pair of paths with the same length and such that ctrl ctrl for every 1
where length length. Note that the controllers of and need not be equal.
2. Define the length of a circuit length to be length length the common length of its two paths.
3. Define a circuit-derivation of a circuit to be a pair of derivations deriving and respectively.
4. (a) Suppose is a circuit-derivation of a circuit . We define index and index to be equal to index (or equivalently equal to index), which following Definition 4.1.1(3b) is just the set 1 length.
(b) Call an index in a circuit-derivation active when is active in at least one of and in the sense of Definition 4.1.5.
(c) Call doubly active when is active in both and (so doubly active implies active).
(d) Call inactive when is inactive in both of and (so is inactive when it is not active).
1. Call an index in a circuit-derivation inconsistent when there exist initial prefixes of , and of , such that:
(a) is doubly active in in the sense of item 4c of this Definition.
(b) , thus by Notation 2.2.4(2) that ctrl ctrl and . Note: recall that ctrl ctrl is guaranteed from Definition 4.3.1(1) for length, but not if length.
2. Call a circuit-derivation inconsistent when it contains an inconsistent index as per item 1 of this Definition, and call not inconsistent or just consistent when it does not contain any inconsistent index.
3. Call an index in a circuit-derivation active inconsistent when:
(a) is active in in the sense of Definition 4.3.1(4b), and
(b) is inconsistent in in the sense of item 1 of this Definition.
4. Call a circuit-derivation active inconsistent when it contains an active inconsistent index.
A few notes on Definition 4.3.2(1) (inconsistent index in a circuit):
1. being inconsistent in does not necessarily imply that is active in . For instance, might have been doubly active and inconsistent in some initial prefix, and then it got Cut and became inactive.
2. does not necessarily imply that is inconsistent in . The condition is stronger than that: a contradiction has to arise in an initial prefix of the circuit-path (Definition 4.2.1(2)) in which is doubly active.
3. As per Definition 4.3.1(1) if length then ctrl ctrl, but if length then it may be that ctrl ctrl.
Proposition 4.3.4 is a useful repackaging of Lemma 2.2.5:
This is a good place to take stock. Our main result will be Theorem 5.6.2, that an inconsistent circuit-derivation is active inconsistent: i.e. part 2 of Definition 4.3.2 implies part 4.
The mathematics from here to that Theorem exists to prove this implication, and we have set up our definitions and notations so as to make this proof as slick as possible. Yet even so, the argument is far from obvious.
Where does the complexity (and subtlety!) come from?
One reason is that it is an inherently nontrivial result. But there is another reason: there are many moving parts to keep track of: notions of active vs. inactive index, notions of instances of Cut and how these can (and cannot) nest, notions of path and path evolution and derivation, and so on.
The definitions have several layers and moving parts, so that even though we have set up our definitions so that the result we want can be quite plainly stated as above, this simple statement stands in front of a detailed structure in a rich design space, which we will need to carefully navigate in the proofs so as to arrive at the result that we want.
We conclude with some notation which will be useful shortly. We collect it here, for easy reference:
Suppose and are derivations.
1. Write when an instance of appears in , and say that contains a cut centred on .
2. For rulenameIncIntroIntro, write when an instance of appears in , and say that contains an instance of rulename centred on .
3. Say that a circuit-derivation contains a right-incompatible pair of cuts at some index when and and .
4. Say that contains right-compatible cuts at some index when if (for some and ) and also (for some and ) then . Note that if contains right-compatible cuts at , then it does not follow that is actually cut in or : it just means that if is cut in both and , then the rightmost indexes in both cuts (the and above) are equal.
5. Properties of paths and circuits
The proofs of this section have a nice shape, but there is a lot of detail. For the reader’s convenient reference, we include a mini-map of this Subsection:
1. Subsection 5.1: persistence. Lemma 5.1.1 and its corollaries. Once a flag appears on a time, later derivation steps cannot change it. Thus, once a controller enters the ‘ready to be cut’ state, it can never leave it.
2. Subsection 5.2: flag nesting and affine cuts. Lemma 5.2.2, Proposition 5.2.3 and Lemma 5.2.5. Pointer jumps must be properly nested; an index can be cut at most once; and the endpoints of a cut remain active immediately after that cut.
3. Subsection 5.3: inactive if and only if cut. Lemma 5.3.1 and Proposition 5.3.3. This has the flavour of a soundness and completeness result: an index is inactive in the final path of a derivation (a condition with a semantic flavour) if and only if some cut centred on that index occurs in the derivation (a condition with a syntactic flavour).
4. Subsection 5.4: Matryoshka cut geometry. Proposition 5.4.1 and corollaries. Cuts cannot cross one another: cuts are either disjoint, equal, or nested, and furthermore we have a ‘Matryoshka doll’ property that every index inside a cut interval must itself be the midpoint of some nested cut.
5. Subsection 5.5: (in)compatible cuts. Lemma 5.5.1 and Proposition 5.5.2, and Corollary 5.5.3 and Proposition 5.5.4. If two derivations cut the same inconsistent index to the same right endpoint (a ‘compatible’ pair of cuts) then the inconsistency propagates to the smaller index. Thus cutting an inconsistency with a compatible cut creates a new inconsistency closer to the right end of the path. If two derivations cut the same index to different right endpoints (an ‘incompatible’ pair of cuts) then the incompatibility of the cutme and cutyou flags creates an active inconsistency at a lesser index. Thus cutting an inconsistency with an incompatible cut also creates a new inconsistency closer to the right end of the path.
6. Subsection 5.6: inconsistent implies active inconsistent. Theorem 5.6.2 and its two corollaries. Choose the least inconsistent index. As per Subsection 5.5, this index cannot be inactivated without creating a smaller active inconsistency. Thus the least inconsistent index is active inconsistent, and if any inconsistent index appears, then an active inconsistent index is present.
We sum this up as a diagram in Figure 11, from Lemma 5.1.1 through to Theorem 5.6.2.
Throughout this Section, we will assume that Ctrl Time ctrl is a (not necessarily sequential) located semilattice with Cut.
5.1. Persistence of
Suppose is a derivation and index and is an initial prefix of (Definition 4.2.1; a nonempty initial segment of ). Then
Note from Definition 3.1.3 that each time has at most one flag, so we can sensibly talk about ‘the flag of a time at an index’ and how a derivation-rule from Figure 9 can (and can not) modify it.
We work by induction on derivations: we consider each rule from Figure 9 and check that it cannot turn a time with a -flag into a time with a different flag.
• Rule Inc. By the construction of the rule and its assumption that the flag does not change.
• Rule Init. Trivial from the form of the rule: Init has no assumptions, so here has no initial segments other than itself, as per Definition 4.2.1.
• Rule Intro. Routine from the form of the rule.
• Intro. Routine from the form of the rule. Note from Lemma 3.2.5 that we cannot use Intro to turn a -flagged time at some index into a -flagged time, because this would require an equality of the form , which by the Lemma is impossible.
• Rule Cut. Routine from the form of the rule, again using Lemma 3.2.5.
Suppose is a derivation and suppose index. Then
• if is -inactive (Definition 4.1.5)
• then for some such that .
Let be the least initial prefix of such that is -inactive for some (one such prefix exists, namely itself with and , but it might not be least). By the form of the rules in Figure 9 and Lemma 3.2.5, the final derivation-step in must be an instance of . It follows from the form of the Cut derivation rule that . We now use Lemma 5.1.1.
Suppose is a derivation and index. Then
• if and
• then for some such that .
The reverse implication for Corollaries 5.1.2 and 5.1.3 does not hold: it is possible for yet is active and uncut.
To see how, just consider a trivial derivation consisting of Init from Figure 9, followed by an instance of : then is active, uncut, and .
We can use a path with two indexes and one controller , as illustrated:
Then both indexes 1 and 2 are active and uncut, yet 2.
5.2. Flag nesting and affine cuts
Lemma 5.2.2 is a simple property with a straightforward proof, but it is very useful. We need a helper lemma first:
Suppose is a derivation and suppose index and 1. Then for some index such that .
By a routine induction on derivations. We consider only instances of derivation rules that might affect the index :
• The case of follows by the inductive hypothesis and the condition that the flag of the index is unchanged.
• The case of Init is a structural fact of the rule.
• The cases of and are routine from the inductive hypothesis.
• The case of is routine from the structure of the derivation rule.
Suppose is a derivation and is an initial prefix of and 1 index. Then
• if for some Q and some index,
• then for some and for some index such that (equivalently: ).
This is illustrated for the reader’s convenience in Figure 12.
We work by induction on the length of . We consider possibilities:
• Suppose . We consider cases for :
– Suppose . Then we take Q and .
– Suppose . By Lemma 5.2.1 Q for some flag and some . If we can now prove that then we can take and we are done. So suppose not: suppose . By Corollary 5.1.2 Q for some and some such that . But we assumed and we have , so . This contradicts injectivity of flag application (Definition 3.1.3), so we are done.
• Suppose (so is a proper initial prefix of ). Then we consider subcases for the final derivation rule in , writing for the initial prefix of up to but not including its final derivation-rule. We consider only instances of derivation rules that might affect the index :
– The case of . By the side-condition flag flag.
– The case of . There is nothing to prove because in this case cannot have a proper subderivation.
– The cases of and . From the fact that these rules do not change the index on the flag.
– The case of for some and such that . By inductive hypothesis (because is shorter than ) where . There are now two further subcases: Suppose . Then by inductive hypothesis (since is an initial prefix of ) for some Q and some index such that . Suppose . Then by Lemma 5.2.1 (noting that so 1), for some Q and some index such that , so that . In either case, after the Cut we have that , and the result follows.
Suppose is a derivation. Then for each index, contains at most one cut centred on .
Consider two distinct instances of Cut in , centred on :
• for some and . Write for the initial prefix of up to and including this Cut.
• for some and . Write for the initial prefix of up to and not including this Cut.
We will show that this is impossible.
For concreteness — and without loss of generality, since is non-branching as observed in Definition 4.2.1 — suppose is an initial prefix of . We now consider cases:
• Suppose and . By the structure of the Cut rule, . By the structure of the Cut rule again, . But we see from the derivation rules that this is impossible: none of Intro, Intro, or Cut can transform a time of the form into a time of the form (for any flag Q) for .
• Suppose and . Then and and . This contradicts Lemma 5.1.1, so this case is impossible.
• Suppose . Then and and . This contradicts Corollary 5.1.2, so this case is impossible.
• Suppose . Then and and . This contradicts Lemma 5.2.2, so this case is impossible.
Corollary 5.2.4 is a technical property which will be useful later: if the flag of active points at , then is active. We mention it here because it follows directly from Lemma 5.2.2:
We reason by contradiction. Suppose is active and and suppose is inactive, meaning by Definition 4.1.5 that there exists index such that and . There are now three subcases:
• Suppose . Then is inactive, contradicting our assumption.
• Suppose . Then and also where . This contradicts Lemma 3.2.5.
• Suppose . Then and and . This contradicts Lemma 5.2.2.
All three subcases are impossible, so we have a contradiction as required.
We mention one more small observation, with a slightly non-obvious proof:
Suppose is a derivation and suppose that the final derivation-step in is . Then and are active in .
We will prove this by contradiction.
Suppose is inactive in . By Corollary 5.1.2 for some index . However, we assumed that the final derivation-step in is , and it follows from the structure of the Cut rule in Figure 9 that . This contradicts injectivity of flag application (Definition 3.1.3).
The slightly non-obvious part of the proof is that the Cut rule does not place restrictions on the flag of , so we cannot use the same argument to derive that is active. However, with our results so far another slick argument does work: we now know that is active in , and that , so we can use Corollary 5.2.4 to conclude that is active in .
5.3. Inactive if and only if Cut
Lemma 5.3.1 (Cut implies inactive) is straightforward given the machinery we have built already. The other direction (inactive implies Cut) is just a bit harder, and we prove it in Proposition 5.3.3:
Suppose is a derivation and index. Then
• if for some index such that (in words: if is bracketed by some Cut in ),
• then is inactive in .
Suppose is a derivation and index. Then
• if for some index such that 2 — note: it follows from this assumption that 3, since the least possible value for index is 1 —
• then for some index such that .
We reason by induction on . Write for the initial prefix of up to and not including its final derivation step (if such an initial prefix exists). We consider possibilities for the final derivation step in :
• Suppose concludes with (where may or may not equal ). By assumption in Inc the flag of is equal to the flag of . We use the inductive hypothesis on .
• Suppose concludes with Init. Then does not exist but there is nothing to prove because is guaranteed.
• Suppose concludes with . By the structure of the rule, this derivation rule may change a -flagged time in into a -flagged time in , but it does not change the index pointer . We use the inductive hypothesis on .
• Suppose concludes with . As for the case of .
• Suppose concludes with . If then we can just take and and our instance of Cut is the final derivation step in and we are done. If then we use the inductive hypothesis on .
Proposition 5.3.3 presents the reverse implication to Lemma 5.3.1, as promised:
We reason by induction on .
Unpacking Definition 4.1.5, is inactive when there exist such that for Q . By Lemma 5.3.2 there is a index such that and . Let be the initial prefix of up to but not including that instance of Cut.
There are now three cases depending on whether , , or . We consider each in turn:
• Suppose . Then we have found our instance of , where and , and we are done.
• Suppose . From the form of , it must be that and . So by Definition 4.1.5 is -inactive in . By inductive hypothesis
for some index such that . We note that so and we are done.
• Suppose . From the form of , it must be that and . So by Definition 4.1.5 is -inactive in . By inductive hypothesis for some index such that . We note that so and we are done.
Corollary 5.3.4 is a convenient wrapper for Proposition 5.3.3:
Suppose is -inactive in , for some and . By Proposition 5.3.3 we obtain . We set to be the initial prefix of up to and not including the Cut, and to be the initial prefix of up to and including the Cut.
We note that is active in . Because, if were inactive then by Proposition 5.3.3 it would be cut, meaning that would contain two cuts centred on , which is impossible by Proposition 5.2.3.
5.4. Matryoshka cut geometry
A Matryoshka doll is a traditional wooden figurine which opens to contain a smaller figurine inside it, which itself opens up, nesting recursively all the way down until there is no space left. Cuts display similar geometric structure:
It might be helpful to illustrate Proposition 5.3.3 with a diagram:
Above, we assume we know that a exists. We illustrate this with a pair of upper braces.
Then within this Cut must be nested — all the way down, like a series of Russian (Matryoshka) dolls — some structure of cuts cutting every index between 8 and 3, and every index between 3 and 1. We illustrate this with pairs of lower braces.
We emphasise that the point here is that cuts nest and also that this nesting is ‘space-filling’ in the sense that every index between the outermost cut indexes (8 to 1, in this example) is cut.
The lower braces are vertically offset so they do not overlap, but note that there is no external sense of time in which they must be totally ordered; there is just the times and the nesting implicit in the indexes themselves (as we make formal in a moment in Corollary 5.4.3). For example: the must occur at times before the times of the , but there is no external sense in which it must necessarily occur before or after (say) the .
Corollary 5.4.3 makes formal an observation in Remark 5.4.2, and it will be useful later on in Proposition 5.5.4:
Suppose that:
• is a derivation.
• index and index, and furthermore .
• .
Then there exist initial prefixes of , and of , such that:
• ends with the (by Proposition 5.2.3 unique) instance of .
• ends with the (likewise unique) instance of .
• or or .
Intuitively: if appears in then any distinct cut centred on indexes between and must come before and nested inside that Cut.
The machinery we have built so far gives a slick proof.
Let be the initial prefix of up to and including the instance of . Because and also , either or or . We consider each possibility:
• Suppose . Then by affine cuts (Proposition 5.2.3) and and the result follows trivially.
• Suppose . By Matryoshka cuts (Proposition 5.4.1) there is some cut in centred on and nested between and , and by affine cuts (Proposition 5.2.3) that cut must be the instance of .
• Suppose . As for the previous case.
Suppose that:
• is a derivation.
• and for index and index.
Then precisely one of the following conditions must hold:
This is just a symbolic way of saying that the two cuts must either be equal, side-by-side, or nested.
By routine arguments from Corollary 5.4.3.
5.5. (In)compatible cuts
5.5.1. Compatible cuts
Lemma 5.5.1 is a technical property which will help us prove Proposition 5.5.2:
Suppose that:
• is a circuit-derivation.
• index is doubly active in (Definition 4.3.1(4c); is active in both and as per Definition 4.1.5).
• extends with one derivation step , and extends with one derivation step . Note that these two Cuts are both centred on , and are right-compatible (i.e. they both cut to the same right index ).
• .
Given the above, we have that:
1. is inactive in .
2. is doubly active in .
3. length, so by Definition 4.3.1(1) ctrl ctrl and ctrl ctrl.
4. is inconsistent in .
The proof is just a matter of chasing definitions and checking structure, but we have built up quite a lot of structure and definitions by now, so we give full details. We consider each part in turn:
1. is Cut in both derivations of , so it is inactive by Lemma 5.3.1.
2. is doubly active in by Lemma 5.2.5 (cut endpoints active).
3. By construction index index, and it follows using Definition 4.3.1(1) that length. Furthermore .
4. By the form of the Cut rule, and for suitable and . We assumed so by Definition 2.2.2(7c) (since ctrl ctrl and ctrl ctrl) as required.25
Let be the least inconsistent index in ; note by construction that has right-compatible cuts at all indexes up to and including . There are now two cases:
• Suppose is active in . Unpacking Definition 4.3.1(4b), is active in at least one of or in the sense of Definition 4.1.5. Then we set and by Definition 4.3.2(3) we are done.
• Suppose is inactive in meaning by Definition 4.3.1(4d) that is inactive in both and in the sense of Definition 4.1.5. We will derive a contradiction. By Corollary 5.3.4 (since is inactive in and ), we have the following data:
– Instances of Cut: for some ; and for some . By our assumption of right-compatible cuts, .
– An initial prefix of , consisting of derivation-steps from up to and not including the instance of , such that is active in .
– An initial prefix of , consisting of derivation-steps from up to and not including the instance of , such that is active in .
– Initial prefixes of and of consisting of the initial prefixes of and respectively including the cuts.
– Note by Lemma 5.3.1 that is inactive in and and in all initial prefixes of and respectively that contain them.
Now we assumed that is inconsistent in , so by Definition 4.3.2(1) there exist initial prefixes of and of such that is active in both, and . Furthermore and are the greatest initial prefixes of and respectively at which is active, so that must be an initial prefix of . It follows by Proposition 4.3.4(1) that . Thus, the conditions of Lemma 5.5.1 are satisfied — we have a circuit-derivation in which is doubly active and and and extend and with and — and so we have that is (doubly) active inconsistent in . It follows from Definition 4.3.2(1) that is inconsistent in . However, we assumed that is the least inconsistent index in , so the existence of this lesser inconsistent contradicts leastness of , and we are done.
5.5.2. Incompatible cuts
Suppose that:
1. is a circuit-derivation of .
2. contains an instance of where index.
3. contains an instance of where index.
4. (it will not matter whether , , or ).
5. has right-compatible cuts at all indexes strictly less than .
Then we have:
1. either contains an instance of for some index such that ,
2. or contains an active inconsistent index such that .
For clarity and to help with intuition, we illustrate the situation considered in this Corollary. In the diagram below, pairs of braces denote instances of Cut ( in path and in path ):
This diagram suggests that in path , either is the index that cut , or some other index has been inconsistent. This result proves that this intuition is accurate.
By assumption contains an instance of , so by Proposition 5.3.3 (since ) contains an instance of for some index such that .
• Suppose . Then contains an instance of and , so we are done.
• So now suppose . By the form of we know that there is an initial prefix of (up to and including the instance of in ), such that . By Lemma 5.2.5 (cut endpoints active) is active in . By and Proposition 5.4.1 (Matryoshka cuts) (because ) there exists an initial prefix of up to and not including some instance of Cut centred on , and by the form of the Cut rule for some . By Lemma 3.2.4 (since ) , thus and is inconsistent in .
By Proposition 5.5.2 (since and has right-compatible cuts at all indexes strictly less than ) there exists an active inconsistent index in such that , and since also is active inconsistent such that , and again we are done.
Let be the least index such that contains a right-incompatible pair of cuts in and in . By our assumption of right-incompatibility , so without loss of generality suppose . Write
• for the initial prefix of (Definition 4.2.1) up to the (by Proposition 5.2.3 unique) instance of in , and
• for the initial prefix of up to the instance of in .
Because is the least index with a right-incompatible cut pair in , any cut-pairs in at indexes less than are right-compatible.
Now by Corollary 5.5.3,
• either contains an active inconsistent index such that .
• or for some ,
In the former case we are done: is an active inconsistent index, and has right-compatible cuts at all indexes less than , and thus at all indexes no greater than .
So suppose we are in the latter case and . We note that
We note that:
1. concludes with and from the structure of the Cut rule in Figure 9 it follows that
for some CTime (cf. Remark 4.1.4(8b)).
2. contains an instance of . Write for the initial prefix of up to and not including that Cut. From the structure of the Cut rule
for some CTime.
We now reason as follows:
By Lemma 2.1.6 (contradiction is monotone) we conclude that
Now is active in by construction, and by Lemma 5.2.5 (cut endpoints active) is active in because it is the endpoint of . is an initial prefix of and is an initial prefix of , thus is an inconsistent index in .
Since , the leastness of implies that has right-compatible cuts at all indexes no greater than . Thus by Proposition 5.5.2 there is an active inconsistent index such that has right-compatible cuts at all indexes no greater than .
5.6. Main result: inconsistent index implies active inconsistent index
We are now ready to prove our main result, Theorem 5.6.2, that if a circuit-derivation contains an inconsistent index, then it contains an active inconsistent index. Before we get to the Theorem, it might be helpful to recall some intuitions about what ‘inconsistent index’ and ‘active inconsistent index’ mean (which are made precise in Definition 4.3.1):
• An index is inconsistent in when there are initial prefixes of and at which was active in both derivations and inconsistent.
• An index is active inconsistent when it is inconsistent and, in at least one of the derivations, has not yet been cut.
Note that:
• ‘Being inconsistent’ is not the same thing as ; to be inconsistent, there must be a contradiction at two times during which was active (whence the mention of initial prefixes).
• The import of Theorem 5.6.2 is not “You cannot inactivate an active inconsistency”. It is “inactivating an active inconsistency, itself creates another active inconsistency”. It might be helpful to think of this in terms of cover-ups. Recall the expression “it’s not the crime, it’s the cover-up”: committing a crime is one thing, but covering up a crime is in itself a crime. The proof of Theorem 5.6.2 has a similar flavour, that you cannot just eliminate an active inconsistency by cutting it away; the act of cutting an inconsistency, itself creates an active inconsistency elsewhere.
Suppose is a circuit-derivation. Suppose index is an inconsistent index (Definition 4.3.2(1)). Then there exists index such that:
• and
• has right-compatible cuts at all indexes no greater than (Definition 4.3.6(4)) and
• is active inconsistent in (Definition 4.3.2(3)).
For clarity, we unpack this result in more detail:
• if there exist initial segments of and of and an index index such that is active in both and , and ,
• then there exists some index index which is no greater than , such that is active in at least one of and , and has right-compatible cuts up to , and there exist initial segments of and of such that .
Corollary 5.6.3 might look abstract, but it is actually a very practical result. Participants can prove the consistency of a circuit-derivation, provided that their trust assumptions are valid: if they trust every active controller in the circuit to never produce conflicting times, and if this trust assumption is correct, then the circuit-derivation is indeed consistent.
Corollary 5.6.4 will be useful later:
Suppose is an inconsistent circuit-derivation. Then the least inconsistent index is active inconsistent, and has right-compatible cuts at all indexes no greater than (i.e. up to and including) .
Suppose is inconsistent. By Theorem 5.6.2 there exists a no greater active inconsistent index such that has right-compatible cuts at all indexes no greater than . But an active inconsistent index is also an inconsistent index, so by leastness of we have that .
6. A Stronger Safety Property
6.1. Motivation
Corollary 5.6.3 allows participants to prove the consistency of a circuit-derivation based on trust assumptions:
• if they correctly trust every active controller in to never produce conflicting times,
• then the circuit-derivation is consistent.
Recall that this matters because our circuit evolution rules from Figure 9 generalise token (un)wrapping to a local, non-blocking Cut operation.
We now improve on Corollary 5.6.3 by removing its trust requirement. With a bit more work we can strengthen its guarantee such that participants can prove absolutely — without needing to trust any other controllers — that a circuit-derivation is consistent. For example, this would be useful for proving things to participants with different trust assumptions.
In particular, if we prove that, among active controllers, all the times that they have attested to (and all the times they have attested to, and so on) are consistent, then the circuit-derivation must be consistent (Theorem 6.4.3). In principle, creating this proof requires only information about past times of active controllers.
Taking a step back, we see a tradeoff:
• Proofs-with-trust as per Corollary 5.6.3 are fast, but they are contingent on trust assumptions. This has two effects: if participant A’s trust assumptions are wrong then Corollary 5.6.3 cannot protect it; and A’s proofs might not compose with proofs of other participants, if these other proofs are contingent on trust assumptions that are not a superset of A’s trust assumptions.
• Absolute proofs as per Theorem 6.4.3 are somewhat slower and harder to produce, but in return we obtain better composability properties: participants can provide absolute correctness proofs (with no trust required!), which are convincing even across different trust assumptions.
6.2. Additional machinery: -closure of
Suppose Ctrl Time ctrl is a located semilattice and Time is a set of times and Ctrl is a set of controllers. Define the -closure of , to be the least set of times with the following properties, also illustrated in Figure 13:
1. Contains the -controlled subset of .
2. Closed under -attestation.
Suppose Ctrl Time ctrl is a located semilattice and Time and Ctrl. Then:
1. If then ctrl.
2. If then .
3. If then , and if furthermore ctrl then also .
We consider each part in turn:
1. We examine the two clauses in Definition 6.2.1 or Figure 13 and see that they only add times whose controllers are in .
2. Suppose . By Definition 2.2.2(6b) this means precisely that ctrl ctrl and . We use Definition 6.2.1(2).
3. Suppose . By expansivity of attestation (Definition 2.2.2(7b)) so by part 2 of this result . If furthermore ctrl then by CAttest in Figure 13 (equivalently: Definition 6.2.1(2)) .
6.3. Additional machinery: chain of cuts
Here and for the rest of this Section we suppose Ctrl Time ctrl is a located semilattice with Cut.
A notion of a chain of cuts will help us in Lemma 6.3.3 and Theorem 6.4.3:
Suppose is a derivation and index and is inactive in . Define the chain of cuts of in to be a tuple such that:
1.
2. , , ..., are inactive in .
3. is active in .
4. There exist index such that for each 1 we have .
Suppose is a derivation and index and is inactive in . Then the chain of cuts of in from Definition 6.3.1 is well-defined.
By an easy induction on the index .
By Proposition 5.3.3 (inactive implies cut) is cut to some lesser . By Proposition 5.2.3 (affine cuts) that cut is unique, so is uniquely defined. There are now two possibilities:
• If is active in then the chain of cuts from is .
• If is inactive then we use the inductive hypothesis on . We let be (by inductive hypothesis well-defined) chain of cuts from . Then :: ( prepended to ) is the chain of cuts from .
Note by Corollary 5.6.4 that has right-compatible cuts at all indexes no greater than . Also recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is cut; we may use ‘inactive’ and ‘cut’ synonymously.
Suppose there exists some such that is inactive in . Let 1 be least such (so that is greatest in such that is inactive in ). We will derive a contradiction.
Note that is cut to in both and , because we have assumed right-compatible cuts at all indexes up to and including . So we assume there exist such that
We assumed that is active in , so by Lemma 5.3.1 (cut implies inactive; if then would be cut and thus inactive). Also by the chain of cuts which we assumed exists in , by Lemma 5.3.1 (cut implies inactive) every index from (inclusive) to (exclusive) is inactive in . Since , we have that is inactive and thus cut in .
We now examine :
• Let be the index such that ( because ).
• Using Corollary 5.4.4 (cuts nest) must get cut to an index no less than in , because for some index, and . Let be the initial prefix of up to and not including that (by Proposition 5.2.3 unique) instance of Cut. So is active in and for some and some consistent time .
• But also . Let be the initial prefix of up to and including the (by Proposition 5.2.3 unique) instance of . By Lemma 5.2.5 (cut endpoints active) is active in , and by the structure of the Cut rule for some consistent time .
• By Lemma 3.2.4 (since ) , meaning that is an inconsistent index in . By leastness of , it follows that .
So we have concluded that . Now because it must be that 1 and . Furthermore recall:
•
• and ‘cut’=‘inactive‘, so that every for 1 is inactive.
• We chose least such that is inactive in .
Putting this all together, it must be that 2.
Thus we have established that for some index (we do not care what it is precisely)
and
Let be the initial prefix of up to and not including the (by Proposition 5.2.3 unique) instance of . Write for the initial prefix of up to and including the (by Proposition 5.2.3 unique) instance of .
It follows from the structure of the Cut rule for , and from Definition 3.1.1(2) (flags are expansive), that
for some ,
and by construction is active in . It follows from the structure of the Cut rule for that
for some ,
and by Lemma 5.2.5 (cut endpoints active) is active in .
By Definition 3.2.1(4) . By contradiction-preservation (Definition 2.2.2(7c))
By Lemma 2.1.6 (contradiction is monotone) we obtain
By construction is active in and , and the former is an initial prefix of and the latter is an initial prefix of , and it follows that is an inconsistent index in . This contradicts the leastness of .
6.4. Absolute consistency results
Recall from the start of Subsection 6.3 that we have supposed that Ctrl Time ctrl is a located semilattice with Cut.
Definitions 6.4.1 and 6.4.2 will help us to express our results:
Suppose is a circuit-derivation of a circuit . Then:
1. Write actTime for the set of active times in (Definition 4.1.5(4)), and actCtrl for the set of active controllers in . In symbols:
2. We define actIndex actIndex (where recall that is the path derived by ), and similarly for actTime, and actCtrl. We also define
3. Note that actIndex, actTime and actCtrl are not the set of indexes, times, and controllers respectively that have been active at some initial prefixes of and ; they are the sets of active indexes, times, and controllers in the paths derived by the circuit-derivation .
Theorem 6.4.3 provides a method to prove that a circuit-derivation is consistent, using only information from its active controllers — specifically, the actCtrl-closure of actTime. Recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is cut, so putting this together with Theorem 6.4.3, it means that for the purposes of determining whether a circuit-derivation is consistent, we really can cut out, in the sense of delete, the inactive controllers from a circuit-derivation, if we wish:
Suppose is a circuit-derivation and write
(actTime and actIndex are from Definition 6.4.1.) Then:
1. If is inconsistent in the sense of Definition 4.3.2(2), then (Definition 6.2.1) is inconsistent in the sense of Definition 6.4.2.
2. As a corollary using the contrapositive, if is consistent then is consistent.
Before we give the proof of Theorem 6.4.3, it might be helpful to give an intuition for how this proof works. There are a lot of symbols but the geometry of it is quite simple: suppose an index is active inconsistent, and suppose we cut it with . Consider the Cut rule in Figure 9 and note that the time at index (the right-hand end of the Cut) has the form where is the time of the cut index. The reader can check that is preserved, in the sense that is in the C-closure of the active times after the Cut. So this Theorem works because the C-closure is (by design) precisely what is required to ‘remember’ times of all cut indexes.
Suppose is inconsistent.
Recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is Cut.
Let be the least inconsistent index in . By Corollary 5.6.4 is active inconsistent.
If is active in both and then by Definition 6.2.1(1) and is inconsistent and we are done.
So without loss of generality suppose is active in and inactive (thus cut, by Proposition 5.3.3) in . Unpacking Definition 4.3.2(3), let be the initial segment of up to the (by Proposition 5.2.3 unique) Cut at which is cut in . Write
We assumed that is inconsistent, so some initial prefix of exists such that . By Lemma 4.2.2 (times increase) and Lemma 2.1.6 (contradiction is monotone) we have that
Let be the chain of Cuts from in (Definition 6.3.1). By Lemma 6.3.3 we have that are all active in , and by Definition 6.3.1(3) we have that is active in , and by Definition 4.3.1(1) we have that ctrl ctrl. Thus following Definition 6.4.1(2) we have that
Some notation will be helpful:
• For each 1... write for the initial prefix of up to and not including the instance of in (for some ; we do not care what it is), and
• write for the initial prefix of up to and including that Cut.
• Write , so this is the (by Lemma 4.2.2 -greatest) active time at index in .
• Write and write ( is not Cut in ).
Note that ctrl ctrl (not ctrl ctrl).
We prove by reverse induction on 1... that . In words: the time at index immediately before it is cut in , is in .
• If then by Definition 6.3.1(3) is active in so .
• For the induction step, suppose 1 and suppose . We note by the form of the Cut rule in Figure 9 and Lemma 4.2.2 (times increase) that
for some ctrl-controlled time (cf. Remark 4.1.4(8b)). Given equation (2) above, ctrl. By Lemma 6.2.2(2) and by Lemma 6.2.2(3) (since ctrl) as required.
Now we assumed that is active in and , so we have
Thus by Definition 6.2.1(1). Our induction above proves that , and , so is inconsistent in the sense of Definition 6.4.2 as required.
Corollary 6.4.6 is a helpful wrapper for Theorem 6.4.3. Notation 6.4.4 and Definition 6.4.5 will help us to state it:
Suppose Time and Time. Then:
1. Say that is upper-bounded by , and say that upper-bounds , and write , when precedes some element of . In symbols:
2. Say that is upper-bounded by , and say that upper-bounds , and write , when for every .
Suppose is a circuit-derivation and write
Then:
1. If Time is a consistent -attestation-closed set of upper bounds for , then is also a consistent -attestation-closed set of upper bounds for .
2. As a corollary, if
• is a circuit-derivation (Definition 4.3.1(3)), and
• a consistent actCtrl-attestation-closed set of upper bounds (Definition 6.4.5 ) can be given for actTime, then
We consider each part in turn:
1. By a routine induction on , matching clauses 1 and 2 of Definition 6.2.1 with clauses 2 and 3 in Definition 6.4.5.
2. Suppose is a consistent -attestation-closed set of upper bounds for . By part 1 of this result is a consistent -attestation-closed set of upper bounds for . It follows using Lemma 2.1.6 (contradiction is monotone) that is consistent, so by Theorem 6.4.3(2), is consistent.
Corollary 6.4.6 provides an absolute (= not requiring trust assumptions) way to prove that a circuit-derivation is consistent: just provide a consistent actCtrl-attestation-closed set of upper bounds for actTime!
It only remains to show how to construct a consistent actCtrl-attestation-closed set of upper bounds for actTime. We give a scheme for this now. A definition will be helpful:
Suppose Ctrl and Time and and Time. Say that is the most recent ctrl-time attested to by in when:
In words, the most recent time ctrl-attested by is the most recent ctrl-time for which some attestation to that time, by a time controlled by , is upper-bounded by .26
Example 6.4.9 (Algorithm to compute a -attestation-closed set of upper bounds). Suppose we are given and write actCtrl for the set of active controllers and actTime for their times in . We proceed according to the following algorithm:
1. Message all the controllers in — that is, message the active controllers in the circuit-derivation — and ask them for their set of most recent times
and ask for the most recent times they have attested to for each other
(so is the -controlled time that controller reports as being the most recent time it has attested to for ).27 If any of the and are inconsistent (i.e. equal to or respectively) then fail. Otherwise, proceed. Note that these times may arrive as succinct digests in the cryptographic sense (e.g. some kind of hash), not as the original data structure. So in fact what we might actually have is sig and sig, where sig is short for ‘signature’. This will not be a problem, as we shall see.
2. For each controller , request the following proofs:28
(a) Proofs of for every such that ctrl. Thus, the controller must prove that the most recent time that it reported, is later than all of the active times in that are controlled by .
(b) Proofs of for every . Thus, the controller must prove that the most recent time that it reported, is later than all of the times that the other controllers report having attested to for .
We cannot prove this ourselves because we might only have sig and sig, but we can send those signatures to and expect it to look them up, recognise the corresponding full times, and provide cryptographically verifiable digests of the corresponding proofs. If any of the controllers fails to provide all of the requested proofs, then fail. Otherwise, proceed.
3. Succeed and output
We claim that if the algorithm above succeeds, then the that it computes is a consistent -closed set of upper bounds for , in the sense of Definition 6.4.5. We must prove that
• is consistent in the sense of Definition 6.4.2, and
• it upper-bounds in the sense of Notation 6.4.4, and
• it is a -attestation closed set of upper bounds in the sense of Definition 6.4.5.
is consistent by construction because if above then the algorithm fails and returns no output.
upper-bounds by construction because the algorithm requires proofs of for every actTime.
We now argue that is a -attestation closed set of upper bounds. Suppose where ctrl ctrl; write ctrl and ctrl. Suppose is the most recent time attested to for by .
By the second conjunct in the definition of ‘most recent’ in Definition 6.4.8, we have that . But we also have , so we are done.
This almost completes our argument, but there remains one outstanding detail: we write above that should be the most recent time that controller has attested to for controller , and we assume the ‘most recent’ property when we appeal to Definition 6.4.8 above.
How can we be sure that really is the most recent time that attests to for ? We know that , but there is no proof of the ‘most recent’ property.
This is not obvious in general, but for the ‘practical’ located semilattice in Definition 3.4.3 this can be proved: just check that (for being second projection of a tuple)
In words: just check that the time reported by is equal to some local state plus the times that reports having attested to for the other controllers’ times. This might seem tautological — why not just go into directly? — but remember that these times might be delivered as a compact cryptographic digest, such that we can check that the digests compose correctly without necessarily knowing directly what is inside them.
7. Alternative presentation of located semilattices with
Cut
We will now reformulate the notions of located semilattice and located semilattice with Cut from Definitions 2.2.2 and 3.2.1. We do not use these reformulated versions in the main proofs, but it is still interesting to revisit the definitions.
There are two nice things about this reformulation (which is why we present it here), and one less nice thing (which is why we did not take this as a primitive definition).
1. The reformulation is compact, and arguably elegant. This is nice.
2. The reformulation unifies the ‘located semilattice’ structure with the ‘with flags’ structure. These are now both manifestations of a single abstraction, which we call an attestation Y X. This is also nice.
3. The presentation in Definitions 2.2.2 and 3.2.1 is more verbose, concrete and accessible.
It may be best to think of this Section as being retrospective: in retrospect we gain an interesting view of what we have been doing.29
Suppose X and Y are bounded semilattices and suppose X.
1. Say that contradicts and write when .
2. The set Y X of all functions from Y to X inherits a natural pointwise bounded semilattice structure from X, as follows:
(a) Y X when Y.
(b)
(c)
(d)
3. Call a function : Y X X strongly contradiction-preserving when30
4. Call : X X expansive when
Write ExpanX for the set of expansive functions from X to itself
considered as a bounded semilattice with the pointwise ordering from part 2 as follows:
5. An attestation from Y to X is a not necessarily monotone, strongly contradiction-preserving map from Y to ExpanX. Write Y X for the set of attestations from Y to X.
6. Call : X X a self-attestation. So a self-attestation is a strongly contradiction-preserving map from X to expansive functions from X to itself.
7. We may sometimes write : Y X (rather than : Y X) for a function that is an attestation, and we may write application of attestation postfix as . So is shorthand for .
Suppose X and Y are bounded semilattices and suppose X (we may drop the X and Y subscripts).
1. The function
is an attestation in X X. We may call this the linear attestation. This example easily instantiates to many concrete examples, just by concretely instantiating X to any datatype that admits some kind of sensible ordering
— possibly after adjoining a top and/or bottom element to make it into a bounded semilattice if it is not one already. Examples include:
(a) Finite lists or finite trees with a top element, ordered by is-initial-prefix-of.
(b) Possibly inconsistent propositional theories ordered by subset inclusion.
(c) The real line with endpoints.
(d) ...and so on.
2. Let : Y X be any bounded semilattice morphism. Then
is an attestation in Y X. We may call this a principal attestation.
3. Semilattice join X X X is an attestation function
in X X. We may call this the join attestation and we may write it . The join attestation is just a special case of a principal attestation where we take Y X and id : X X (identity function).
4. Let : Y X be a bounded semilattice morphism. Then
is an attestation in Y X.
5. Let X powPnt be any join-semilattice in the powerset of a set Pnt such that Pnt X — another word for this is that X is a semitopology [Gab24, Gab25]. Let X X be any relation. Then
is an attestation. In some sense which we will not make formal here, this seems to be the only parametric scheme for attestations on X. We give the intuition. Given parametricity (so we cannot use any particular structure of and aside from knowing that they are sets), expansiveness forces and contradiction-preservation forces , so ; and if we are parametric in the sense that we are not allowed to examine at any specific structure of X or Pnt, the only remaining choice is whether to return or all of Pnt, and this choice is made by .
6. We give an example of a non-attestation. Note that ExpanX (the set of expansive functions from X to itself) has a bounded semilattice structure defined pointwise as per Definition 7.2(2). Then the identity function
is not an attestation in ExpanX X, because it is not strongly contradiction-preserving. Suppose . Then the reader can check that it does not in general follow that .
Suppose X and Y are bounded semilattices and suppose : Y X is an attestation.
1. Call separating when for every Y
In words: if and are equal and consistent (non-) then . Note that being separating is not just the condition of being injective.
2. Call monotone when
In words: : Y ExpanX is monotone from Y to Expan with the pointwise ordering.
We are now ready to propose our alternative versions of the notions of located semilattice from Definition 2.2.2, and located semilattice with Cut from Definition 3.2.1:
A located semilattice (contrast with Definition 2.2.2) consists of a tuple
where
1. Ctrl is a set of controllers,
2. Time Ctrl is a Ctrl-indexed set of pairwise disjoint bounded semilattices. For Ctrl we may call Time a -component (or just a component, if is unimportant or understood), and we may call Time a time. When Time we say that is controlled by , and we may write ctrl.
3. : Time Time is a Ctrl2-indexed family of attestations from Time to Time.
4. We further restrict so that . Here is the join self-attestation from Example 7.4(3). In words: the self-attestations in the indexed family are just the join attestation from Example 7.4(3).
5. If every component Time is a sequential bounded semilattice — i.e. a top-tree — then call sequential.
1. Define CuttingPoset the cutting-flag bounded semilattice to be the top-tree (= sequential bounded semilattice) generated as the reflexive transitive closure of Figure 6, with top and bottom elements and adjoined.
2. A located semilattice with Cut (contrast with Definition 3.2.1) is a located semilattice such that:
(a) For each Ctrl, the -component Time is equipped with a separating monotone attestation : CuttingPoset Time.
(b) If Time then and .
(c) Define a function : CuttingPoset Time Time by
We insist is injective on CuttingPoset, in the strong sense that
(Recall that CTime is from Notation 2.2.4(1) and this just means that Q and are consistent, i.e. not equal to .)
Definitions 7.6 and 7.7 are appealing, but they come with a price:
1. Definitions 7.6 and 7.7 are compact and identify the recurring abstraction of an attestation (Definition 7.2(5)). This is an interesting mathematical object which is worth pointing out.
2. This way of setting up the definitions highlights some structure that was always clearly present, but had perhaps been somewhat buried under notation. For example: by ordering flags explicitly into a poset CuttingPoset in Definition 7.7 following Figure 6, we turn that Figure from something illustrative into something definitive, so that properties 1 to 4 in Definition 3.2.1 become geometric observations about CuttingPoset as a top-tree. In particular, attestation is strongly contradiction-preserving as per Definition 7.2(3), so the geometric fact that and are on distinct branches in CuttingPoset as a top-tree gives us the important and characteristic cross-controller contradiction axiom (Definition 3.2.1(4)). This is very nice.
3. However, the original notion of located semilattice in Definition 2.2.2 has its own appeal.
(a) It is arguably more accessible to a first-time reader.
(b) In Definition 2.2.2 the join structure is derived from the attestation , so there is just a singular notion of ‘attestation’. In Definition 7.6 the join structure of each Time is primitive, then a family of cross-controller attestations is introduced ...which we then have to assemble into a single function in order to express the injectivity condition in Definition 7.7(2c).
There is no right or wrong here. There is a design space of definitions here, whose shape remains to be explored.
8. Conclusions
8.1. Many controllers is not a problem, if they can collaborate
In 1983 Chaum noticed a problem that in a system of communicating state machines (‘controllers’), one of those machines might send messages that are both consistent with its history up to that point, but that are inconsistent with each other [Cha83]. This is the consistent histories problem, of which the classic instance is spending the same unit of money more than once: the ‘double-spend’. We discuss existing solutions to this in Subsection 1.4.
We have seen how located semilattices model multiple independent but collaborating controllers, and located semilattices with Cut provide a solution to the consistent histories problem. In located semilattices with Cut, tags recording a resource history can be pruned, and — provided that this pruning follows the rules of Cut which we propose and analyse — the existence of inconsistency is preserved even after forgetting. That is, in a sense made formal by Theorems 5.6.2 and 6.4.3 (as discussed in Subsection 1.6), we can safely forget history.
This is a technical and mathematical answer to the core practical problem of fragmentation [Shi26].31 In fact, fragmentation is only a problem if controllers struggle to collaborate, and forgetting history is only a problem if it creates a danger that histories that were visibly unsafe, become (after forgetting/reduction) not visibly unsafe. If histories are safely reducible and controllers can collaborate efficiently and within well-understood and properly-controlled safety parameters, then this ceases to be a problem and becomes an innocuous technical fact, or even a performance feature.32
At this point it might be useful to return to the BIS working report, which approaches this issue from the point of view of collaborating central banks rather than collaborating blockchains.
The BIS working report [Shi26] notes the impossibility of the One True Controller, but it goes beyond this to critique blockchains as currently constituted. The paper is academic in tone and content, but its critique is valid and cuts deep. It is worth reading the final paragraphs of the Conclusion:
The analysis of this paper [meaning [Shi26] -authors’ note] underlines the importance of going back to the basics of money as a coordination mechanism. The classical insight – from Menger to Jevons to Kiyotaki and Wright – is that money is valuable because of the breadth of its acceptance network. The modern insight, developed here, is that decentralised consensus mechanisms systematically undermine this breadth by fragmenting the user base across competing platforms. The feedback loop runs in the wrong direction: instead of greater acceptance leading to greater use (the virtuous circle of money), congestion on one chain leads to exit to another chain. This is not to deny the genuine innovations of blockchain technology [but] A purely decentralised monetary system, without the anchor of a trusted central authority, is structurally predisposed to fragmentation. The question for policymakers is whether the genuine innovations of blockchain technology can be harnessed while preserving the institutional foundations that make a unified monetary system possible.
In short, the BIS report proposes a model of a small number of completely trusted controllers (e.g. national banks). The problem of fragmentation is ‘solved’ by assuming that these banks never misbehave. This is not quite the One True Controller, but it is the One Small Clique of True Controllers, which really amounts to the same thing. Their critique of blockchains is that blockchains cannot make this trust assumption, so fragmentation becomes dangerous.
To this passage we would note that located semilattices with Cut from this paper – while also academic – can be viewed precisely as a technical answer to the challenge posed by fragmentation.
We would argue that the issue is not really whether there is a One True Controller (‘the anchor of a trusted central authority’ as the BIS report puts it) nor multiple controllers (a ‘fragmented user base’). Fragmentation is not inherently bad, but it may be perceived as bad if it means that controllers cannot collaborate.
Located semilattices with Cut are a mathematical, yet real and implementable, schema to help address this. With the mathematics of this paper, we would not need to insist that the world agree on a single controller. Instead, we can organise our system so that resource histories are composable and reducible. We would argue that this looks past the symptoms and directly addresses the root problem and cause.
8.2. Design alternatives: other Cut rules
Our Cut rule from Figure 9 is carefully designed to be local and asynchronous (as per Section 1.6 and Remark 4.1.4) while making Theorems 5.6.2 and 6.4.3 hold. The rule certainly exists in a design space, and it is almost certainly not the only possible working design. We briefly consider the design space, including one possibility that probably works (left-handed cut) and some possibilities that probably do not (rightmost attestation and transitive attestation).
8.2.1. Cut is chiral: right vs left
Our flag system requires that if multiple adjacent active controllers are flagged , then the leftmost must be cut first: a controller to its left must be flagged , and then the leftmost time can be cut, followed by the next leftmost, and so on. Call this Cut a left-handed Cut.
This forced ordering helps to enforce consistency: different paths in a circuit cutting in different orders (disallowed by our flags) can produce circuits with an inconsistent derivation but no active inconsistent controller.33
However, we just need adjacent times to be cut in the same order. It is likely possible to design an alternative right-handed Cut that enforces that in multiple adjacent -flagged controllers, the rightmost adjacent time must be cut.
With left-handed Cut, we ended up reasoning about right-compatible cuts (see Definition 4.3.6). With right-handed Cut, proofs would probably reason about left-compatible cuts instead. The resulting system would have many of the same desirable properties.
We have seen no compelling reason to prefer one over the other.
8.2.2. Rightmost Attestation
Our paths represent (compressed) histories of objects, with the rightmost path element representing the controller where the object started: it is always active.
We could require that before cutting time , the rightmost time must have attested to . In practice, this corresponds to requiring the ‘issuer’ of the object to sign off on (and check consistency of) any cuts. This preserves the consistency property nicely: if our circuit has an inconsistent derivation, then it has two inconsistent (possibly inactive) controller times in it, and if they’re both inactive, that means the rightmost controller attested to both, and so is active inconsistent.
Unfortunately, this sacrifices the locality of cuts, which was one of our goals. By ‘locality’ we mean that we want a group of controllers to be able to receive an object, transfer it among themselves, and then be able to cut as much as possible — without having to communicate outside the group.
For example, a farmer might issue crop futures, which are then owned and traded by any number of markets and people. The farmer does not want to be bothered whenever traders want to do a cut. They only need to review the crop future when it is time to collect the crops.
8.2.3. Transitive Attestation
We return to a discussion in Remark 2.2.1. Attestation is not transitive:
in general. Suppose it were. Then we would have this lovely property (where and are at the same controller):
In an implementation, it would suffice to insist that before a controller can attest to time , it must attest to all times attested to in (times preceding) .
This gives some very nice properties. It becomes easy to design cut rules that preserve consistency properties: so long as someone active must attest to a time before it is cut, then the cut time is forever ‘remembered’ by someone active.
Unfortunately, transitive attestations have a drawback: attestation is technically more expensive (because we cannot just ‘attest to stuff’; we have to find out the transitive closure of that stuff), and worse, attestation becomes much more of a commitment, which is problematic.
Suppose some controller forks into times and where . Now, any controller who attests to cannot later attest to a controller who attested to . Furthermore, with transitive attestations, any controller who attests to ’s time cannot later attest to a controller who attested to ’s time (because the former transitively depends on and the latter transitively depends on ). So because one controller forked, the system can end up partitioned into subsets of (correct) controllers who can no longer attest to each other.
We want an attestation system that encourages communication: controllers should feel confident in attesting to each other opportunistically, without fear that this might limit their options later. Transitive attestations ruin that: every attestation means potentially cutting off communication with other controllers.
The lack of structure of the not-necessarily-transitive attestations used in this paper is a feature, not a bug: it permits and encourages consequence-free opportunistic attestation.
8.3. Consistent history
Consistent history is one of the most basic properties digital objects can have. Given two digital objects, we may want to know if they contradict in the deep sense that in order to have both, some controller must misbehave. The maths in this paper is parametric over what ‘misbehaviour’ means precisely, but we have in mind in particular the canonical example of an illegal double-spend.34
We have shown that in order to check for consistent history, it is not necessary to know (or store) all the times of all the controllers involved in the production of a pair of resources. It can suffice merely to know the active times from a path corresponding to each object. Naively, this path corresponds to an upper bound on the most recent time each controller affected the object’s history, but we have shown how, with a little work, we can cut controllers from this path.
For a given set of objects, a user who trusts all the controllers of all the active times from the object’s paths knows (from Subsection 5.6) that the objects’ history is consistent. If there is some contradictory fork, then it is impossible that all dishonest controllers are inactive in all the paths. This is the key connection between paths and trust assumptions. With Theorem 6.4.3, it is even possible to prove that the objects have consistent history (without trust assumptions), although assembling this proof may require requesting new “” proofs from the active controllers.
Our mathematics is parametric over the precise bookkeeping systems used to track and update objects’ paths, perform attestations, and prove serialisability. This is certainly implementable and picking optimal choices for given use cases is future work. However, we note that the mathematical framework presented here is applicable to extremely general classes of interacting systems — they just have to be located semilattices. We have also shown that tracking — and crucially, cutting — trust assumptions across heterogeneous trust domains is possible, even in an open system with few constraints on how objects behave. We are not aware of other frameworks with this level of generality and power.
Today’s interacting systems typically do not track trust assumptions, and do not use attestations and cuts to remove trust assumptions that are no longer necessary. Instead, they rely on blind trust (e.g. US banks must trust assets given to them by the Federal Reserve); or on precisely matched trust assumptions (e.g. applications on Ethereum can rely precisely on Ethereum’s trust assumptions, and so interacting with each other does not change trust assumptions). But blind trust is not scalable, is not possible for all applications, and can be expensive and slow, since the trusted controller must be extremely trustworthy, and will have a lot of demand. Existing trust assumption trackers generally cannot remove the requirement to trust a controller that has affected an object’s history (e.g. taint tracking [WGDW22] or IFC [LAGM17]), unless the application can somehow check all the integrity properties it needs from available data (e.g. balance checks in wrapped tokens [Goe24]).
Our mathematics opens the door for something better: cross-controller applications with the ability to cut trust assumptions. Applications can run on whatever controllers suit them best according to their tradeoffs for cost, speed, and trustworthiness. With accurate trust tracking, attestations, and Cut, applications are much more free to interact, safely and effectively.
8.4. Future work
Much remains to be done, especially to take the mathematical foundation of this paper and engineer it to a practical and useful implementation.
We hypothesise that objects can carry tags which track active controllers in a path corresponding to their history. The design of these tags, and proof that they correspond to such paths, is future work. These tags would resemble taint tracking [WGDW22] or IFC Integrity labels [LAGM17], but controller tags are not quite either. Comparison (and possible combination with) taint tracking or IFC techniques is future work.
Our paths model the history of a single (possibly stateful) object: a linear path from controller to controller. Thus the exponential cake from Figure 1 may move between controllers, and may change state (i.e. get eaten).
But in practice, digital objects may also be combined, so that the integrity of a single object may depend on multiple source objects. Consider for example the exponential bike in Figure 14. This depends on two wheels (and a frame, whose source is not illustrated). The exponential bike is ‘inconsistent’ all by itself, because its two wheels were generated by double-spending one wheel.35 We believe that the mathematics in this paper can be extended to address the exponential bike. Just follow the paths of the two wheels, in the sense of Definition 4.1.1, and detect the contradiction. Our theory of controller tags should be compatible with this natural example.
More generally, it remains future work to explore how the mathematics in this paper will interact with the design space of all possible transformations of digital tokens, and possible use-cases for these ideas. As we consider these, it may emerge that a single framework can encompass many or all use-cases of interest, or perhaps different extensions will be in some sense intrinsically different, e.g. requiring intrinsically different notions of Cut.36
It may be that attestation can be implemented with Incrementally Verifiable Computation [KST22] similar to roll-up blockchains [TSH22], but we have not implemented or formally modelled any specific real system. Studying a possible correspondence with available verifiable computation techniques, and possibly exploiting it for implementation, is future work.
The problem that this paper addresses is real. The mathematical ideas which we propose in this paper stand as pure mathematics in their own right, and correctness of the results has been checked in a Lean formalisation [Har26]. It is reasonable to speculate that, with some further investment in research and software engineering, these ideas could become a foundation for practically useful systems.
References
Adr26. Tobias Adrian, Tokenized finance, IMF Notes 2026/001, International Monetary Fund, 2026. doi:10.5089/9798229042468.068 (cit. on p. 6.)
AHLT05. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG) 1 (2005), no. 2, 243–264. doi:10.1145/1103963.1103966 (cit. on p. 15.)
Ban23. Bank for International Settlements, Blueprint for the future monetary system: Improving the old, enabling the new, Annual economic report 2023, chapter iii, Bank for International Settlements, Basel, June 2023. https://www.bis.org/publ/arpdf/ar2023e3.htm (cit. on pp. 3 and 6.)
Ban25. , The next-generation monetary and financial system, Annual economic report 2025, chapter iii, Bank for International Settlements, Basel, June 2025. https://www.bis.org/publ/arpdf/ar2025e3.htm (cit. on p. 3.)
BB23. BIS Innovation Hub and Bank of England, Project meridian: Innovating transactions with synchronisation, Tech. report, Bank for International Settlements, Basel, April 2023. https://www.bis.org/about/bisih/topics/fmis/meridian.htm
(cit. on p. 3.)
BBE25. BIS Innovation Hub, Bank of England, and European Central Bank, Project meridian FX: Exploring synchronised settlement in FX, Tech. report, Bank for International Settlements, Basel, April 2025. https://www.bis.org/publ/othp94.htm (cit. on p. 3.)
BE18. Bank of Japan and European Central Bank, Securities settlement systems: Delivery-versus-payment in a distributed ledger environment, Project stella report, Bank of Japan and European Central Bank, 2018. https://www.ecb.europa.eu/pub/pdf/other/stella_project_report_march_2018.pdf (cit. on p. 6.)
BG81. Philip A. Bernstein and Nathan Goodman, Concurrency control in distributed database systems, ACM Computing Surveys 13 (1981), no. 2, 185–221. doi:10.1145/356842.356846 (cit. on p. 6.)
BHG87. Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley, Reading, Massachusetts, 1987. https://www.microsoft.com/en-us/research/people/philbe/book/ (cit. on p. 3.)
BVGC21. Rafael Belchior, André Vasconcelos, Sérgio Guerreiro, and Miguel Correia, A survey on blockchain interoperability: Past, present, and future trends, ACM Computing Surveys 54 (2021), no. 8, 1–41. doi:10.1145/3471140 (cit. on p. 6.)
Cdv90. David Chaum, Bert den Boer, Eugène van Heyst, Stig Fr. Mjølsnes, and Adri Steenbeek, Efficient Offline Electronic Checks (extended abstract), Advances in Cryptology – EUROCRYPT ’89: Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Belgium, April 10– 13 (Berlin, Heidelberg) (Jean-Jacques Quisquater and Joos Vandewalle, eds.), Lecture Notes in Computer Science, vol. 434, Springer, 1990, pp. 294–301. doi:10.1007/3-540-46885-4_31 (cit. on p. 6.)
Cha83. David Chaum, Blind signatures for untraceable payments, Advances in Cryptology: Proceedings of Crypto 82 (Boston, MA) (David Chaum, Ronald L. Rivest, and Alan T. Sherman, eds.), Springer, 1983, pp. 199–203. doi:10.1007/978-1-4757-0602-4_18 (cit. on pp. 6 and 78.)
Cha92. , Achieving electronic privacy, Scientific American 267 (1992), no. 2, 96–101. doi:10.1038/scientificamerican0892-96 (cit. on p. 6.)
CM03. Nathalie Caspard and Bernard Monjardet, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Applied Mathematics 127 (2003), no. 2–3, 241–269. doi:10.1016/S0166-218X(02)00209-3 (cit. on p. 25.)
Com92. Committee on Payment and Settlement Systems, Delivery versus payment in securities settlement systems, CPSS Publications 6, Bank for International Settlements, Basel, September 1992. https://www.bis.org/cpmi/publ/d06.htm (cit. on p. 3.)
Com17. Committee on Payments and Market Infrastructures, Distributed ledger technology in payment, clearing and settlement: An analytical framework, CPMI report 157, Bank for International Settlements, 2017. https://www.bis.org/cpmi/publ/d157.htm (cit. on p. 6.)
DP02. Brian A. Davey and Hilary A. Priestley, Introduction to lattices and order, 2nd ed., Cambridge University Press, Cambridge, 2002. doi:10.1017/CBO9780511809088 (cit. on p. 25.)
Gab24. Murdoch J. Gabbay, Semitopology: decentralised collaborative action via topology, algebra, and logic, College Publications, August 2024, ISBN: 9781848904651. (cit. on p. 75.)
Gab25. , Semitopology: a topological approach to decentralised collaborative action, The Journal of Logic and Computation (2025), https://doi.org/10.1093/logcom/exae050. doi:10.1093/logcom/exae050 (cit. on p. 75.)
Gir87. Jean-Yves Girard, Linear logic, Theoretical Computer Science 50 (1987), no. 1, 1–101. doi:10.1016/0304-3975(87)90045-4 (cit. on pp. 4 and 7.)
GL06. Jim Gray and Leslie Lamport, Consensus on transaction commit, ACM Transactions on Database Systems 31 (2006), no. 1, 133–160. doi:10.1145/1132863.1132867 (cit. on p. 6.)
Goe20. Christopher Goes, The Interblockchain Communication Protocol: An Overview, May 2020, https://github.com/cosmos/ibc/blob/8d9d3b6fe7309b034df8457760b3bbd11d24b8e1/archive/papers/2020-05/build/paper.pdf#L2. (cit. on p. 3.)
Goe24. , Draft Spec for Multi-Denom Packets ICS20 v2, March 2024, https://github.com/cosmos/ibc/blob/main/spec/app/ics-020-fungible-token-transfer/README.md. (cit. on pp. 3, 10, and 82.)
Har26. Anthony Hart, Consistent Histories in Lean 4, July 2026, Direct download of zip archive: https://zenodo.org/api/records/21074395/files-archive. doi:10.5281/zenodo.21074395 (cit. on pp. 3 and 84.)
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, p. 245–254. doi:10.1145/3212734.3212736 (cit. on pp. 3 and 6.)
HLS22. Maurice Herlihy, Barbara Liskov, and Liuba Shrira, Cross-chain deals and adversarial commerce, The VLDB Journal 31 (2022), no. 6, 1291–1309. doi:10.1007/s00778-021-00686-1 (cit. on p. 6.)
HW90. Maurice P. Herlihy and Jeannette M. Wing, Linearizability: A correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems 12 (1990), no. 3, 463–492. doi:10.1145/78969.78972 (cit. on p. 6.)
Kap04. Michael Kaplan, Three blind phreaks, Wired 12 (2004), no. 02, Archived copy available at https://www.social-engineer.org/wiki/archives/Hackers/hackers-The-Badir-Brothers-Social-Engineer.htm. (cit. on p. 78.)
KLRZ25. Tansaya Kunaratskul, Ashley Lannquist, Andre Reslow, and Nicolas Zhang, Central bank exploration of tokenized reserves, Fintech Notes 2025/011, International Monetary Fund, 2025. doi:10.5089/9798229025324.063 (cit. on p. 6.)
KST22. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla, Nova: Recursive zero-knowledge arguments from folding schemes, Advances in Cryptology – CRYPTO 2022, Lecture Notes in Computer Science, vol. 13510, Springer, 2022, Cryptology ePrint Archive, Paper 2021/370, pp. 359–388. doi:10.1007/978-3-031-15985-5_13 (cit. on p. 83.)
LAGM17. Jed Liu, Owen Arden, Michael D. George, and Andrew C. Myers, Fabric: Building open distributed systems securely by construction, J. Comput. Secur. 25 (2017),
no. 4–5, 367–426. doi:10.3233/JCS-15805 (cit. on pp. 82 and 83.)
Nak08. Satoshi Nakamoto, Bitcoin: A peer-to-peer electronic cash system, https://bitcoin.org/bitcoin.pdf, 2008. (cit. on p. 6.)
Nan26. Toby Nangle, Stablecoin fracturedcoin, Alphaville, Financial Times, 10 March 2026, Available at https://www.ft.com/content/4724ae3f-04a7-4ca3-8221-2244c7644faa. (cit. on p. 7.)
Pap79. Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM 26 (1979), no. 4, 631–653. doi:10.1145/322154.322158 (cit. on pp. 6 and 81.)
Ros71. Ron Rosenbaum, Secrets of the little blue box, Esquire (1971), 116ff, Reprinted in Slate, 2011. Scan available via the History of Phone Phreaking archive: https://historyofphonephreaking.org/docs.php. https://www.slate.com/articles/technology/the_spectator/2011/10/the_article_that_inspired_steve_jobs_secrets_of_the_little_blue_.html (cit. on p. 78.)
Shi26. Hyun Song Shin, Tokenomics and blockchain fragmentation, Bank for International Settlements (2026), no. 1335, Available at https://www.bis.org/publ/work1335.pdf (permalink). (cit. on pp. 7, 78, and 79.)
SKL20. Ghiath Shabsigh, Tanai Khiaonarong, and Harry Leinonen, Distributed ledger technology experiments in payments and settlements, FinTech Notes 2020/001, International Monetary Fund, 2020. doi:10.5089/9781513536330.063 (cit. on p. 6.)
TSH22. Louis Tremblay Thibault, Tom Sarry, and Abdelhakim Senhaji Hafid, Blockchain scaling using rollups: A comprehensive survey, IEEE Access 10 (2022), 93039– 93054. doi:10.1109/ACCESS.2022.3200051 (cit. on p. 83.)
Tyg96. J. D. Tygar, Atomicity in electronic commerce, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (PODC ’96), ACM, 1996, pp. 8–26. doi:10.1145/280449.280458 (cit. on p. 3.)
WGDW22. Dong Wang, Yu Gao, Wensheng Dou, and Jun Wei, Dista: Generic dynamic taint tracking for java-based distributed systems, 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2022, pp. 547–558. doi:10.1109/DSN53405.2022.00060 (cit. on pp. 82 and 83.)
ZABZ21. Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt, SoK: Communication across distributed ledgers, Financial Cryptography and Data Security (Nikita Borisov and Claudia Diaz, eds.), Lecture Notes in Computer Science, vol. 12675, Springer, 2021, pp. 3–36. doi:10.1007/978-3-662-64331-0_1 (cit. on p. 6.)
ZHL19. Alexei Zamyatin, Dominik Harz, Joshua Lind, Panayiotis Panayiotou, Arthur Gervais, and William J. Knottenbelt, XCLAIM: Trustless, interoperable, cryptocurrency-backed assets, 2019 IEEE Symposium on Security and Privacy (SP), IEEE, 2019, pp. 193–210. doi:10.1109/SP.2019.00085 (cit. on p. 6.)
Thanks. We are very grateful to Christopher Goes, Tobias Heindel, and Anthony Hart for support and feedback on this paper.
Notes
1Linear logic has a connective ! which permits copying and erasing a logical resource. It is called the exponential. ↩
2This process of creating two distinct timelines from one timeline is often called a fork. Thus we can truly say that you can have your cake and eat it too, provided you have a fork. ↩
3After all, most fiat balances are just digital ledger entries. ↩
4The word ‘sovereign’ is sometimes used here, as in ‘sovereign controller’. This is not quite what we intend. For example: a child is an independent entity from its parents, in the sense that the child has its own mental state and can emit and receive messages and exchange tokens as such. However, the child would not normally be called ‘sovereign’. For a nice worked example of the economic and political consequences of jumbling up the notions of independence, freedom, and sovereignty, see https://www.lrb.co.uk/blog/2021/january/sovereign-britain. ↩
5Arguably, a deeper reason that double-spend became a noun in its own right, is that the double-spend is the canonical simplest inconsistent pair of actions. Using the notation of this paper, the double-spend is the conceptually simplest pair of times such that . As such, one can argue that double-spend is to electronic cash, as excluded middle ‘P or not-P’ is to logic. In this view, the evolution of the terminology from 1983 to 1992 from ‘stops if note already on list’ to ‘double-spend’, reflects a real deepening of understanding of what is mathematically essential to the 1983 observation. This way of thinking of about things is mathematically suggestive. There is a field of logic called paraconsistent logic, which permits and to exist without full contradiction. In the notation of this paper (where is the inconsistent element) this would amount to permitting , even where and are two halves of a double-spend. This would correspond to a system that might (but is not obliged to) try to reconcile an inconsistency somehow, short of simply rejecting it outright. Exploring paraconsistent electronic cash, and seeing if this might even be practically useful, is out-of-scope for this paper, but it would be an interesting concept for future research. ↩
6...as per the illustration, by converting it into a plate of crumbs and then removing the plate. ↩
7The terminology ‘Cut’ is a deliberate riff on cuts in proof-theory, which make long derivations shorter. Our Cut rule is not a logical cut, but there are some structural similarities between them. ↩
8The English phrases “Keep your friends close, and your enemies closer” and “I’ve got my eye on you” both reflect this. We supervise what we distrust. ↩
9The word ‘tree’ has surprisingly many possible meanings. A tree is: a type of plant (if you are a botanist); or a connected acyclic graph (if you are a graph theorist and don’t mind picking a root); or a poset such that for every , is linearly ordered (if you are an order theorist or combinatorialist); or a poset such that every is well-ordered (if you are a set theorist); or a special case of a Hasse diagram (if you are an automata theorist). These can mean different things: e.g. (nonnegative rationals) is a tree to an order theorist (it is a linear order with a least element), but not to a graph theorist (there is no useful covering relation between nodes) or a set theorist (it is not well-ordered). Here, we mean ‘tree’ in the order-theoretic sense, though if X is finite then this coincides with the graph-theoretic and set-theoretic notions. (The botanical use of the word ‘tree’ is on its own strange branch and we are at a loss to explain it. Perhaps an early botanist read a mathematics textbook?) ↩
10We will care most about the case that is also sequential (Definition 2.1.1(3)), but this definition does not require that. ↩
11The symbol (here denoting contradiction) quotes a standard symbol for proof by contradiction, where we write a lightning bolt when we arrive at a contradiction from our assumptions. The literature contains numerous symbols for this. The first author was taught to use , but this clashes visually with the symbol we use for attestation in Definition 2.2.2. Another common symbol for this is . Should we use that instead? No, no, no! We are already using for the bottom element of a top-tree; we would get notational pathologies like and (instead of and ); because we are calling the consistent element, so using the same or similar symbol to denote contradiction seems an invitation to confusion; and finally because might suggest whereas means , which is in fact the precise dual to that notion. ↩
12Subtlety alert: when we describe the process as ‘sequential’, we do not intend that its state space is just a straight line from to with no forks. We mean, as per the definition, that all paths back to from a non-state, are straight lines with no forks. ↩
13The condition excludes the degenerate case of the one-element bounded semilattice, in which every element is inconsistent, because every element is equal to . Thanks to Anthony Hart for pointing this out. We could exclude the one-element model by insisting on , but such a condition would not be algebraic (i.e. it would not be expressed purely in terms of a positive equality), so we should avoid doing this if possible. Furthermore, the one-element model seems to be harmless, in the sense that it does not invalidate any of the results we want to prove. So, we do not exclude it. ↩
14...or more generally, we need a value to represent Byzantine behaviour. The Byzantine behaviour we will care most about, for now, is nonsequentiality, so in the end this will amount to the same thing. ↩
15It might be helpful to recall that by part 6b, denotes the partial order of times at the same controller, so property 7b only makes sense because of property 7a. ↩
16Because State it is also never-ending (because is infinite) and without purpose (because there is no terminal value aside from failure ). ↩
17For example: Alice (who is British) might observe Bob slurping noodles and infer that Bob is rude and uncouth, so Bob slurpsBob slurps Bob rude. In contrast, Akiko (who is Japanese) might observe the same slurping and infer that Bob enjoyed his noodles and is being quite polite, so Bob slurpsBob slurps Bob not rude. ↩
18One might like to say that everybody agrees that and is inherently contradictory, in some global sense. Oh, if only. ↩
19Our cutting flags are indexed from 0 but our path indexes in Definition 4.1.1(3a) will be indexed from 1. Is this an off-by-one error? Yes and no. There is a mismatch, but it is deliberate. We leave 0 in here, so that in the later Definition, index 1 elements in paths can still have a cutting flag , , or — even if the index 0 happens to be off the edge of the path. This is just like a train line map with arrows to stations that are off the map. ↩
20In the game of proving theorems, using fewer assumptions to prove the same conclusion, is a win. ↩
21Perhaps we just want to sit around a whiteboard proving theorems. Some people (including the first author) may enjoy this for its own sake. ↩
22...but for consistency the model does not have to be fancy. It just has to exist. ↩
23There are many examples of such results, but see Proposition 5.3.3 for a particularly clear example of the genre. ↩
24Insisting on index avoids an edge case where 1 and and 1 . This could happen because the Init rule in Figure 9 does not restrict . We will not need the Corollary in this edge case (which seems to do our proofs no harm otherwise), so we exclude it here. ↩
25As per Remark 4.1.4(8a), here we use the structure of the Cut rule from Figure 9, that the -index has the form where is precisely the time at the -index. We can see that what really matters is that the -index has a time of the form where , but that condition is a little bit longer to write out. ↩
26In the equation above, we can (equivalently, and without loss of generality) limit the universal quantification over to be over all . This is because we assume in the implication, and by Definition 2.2.2(7b) (attestation expansive) . ↩
27In principle we could unify with . That is, we could argue that the most recent time that attests to for itself, should be the most recent time for . But for purposes of exposition we keep and separate. ↩
28These proofs of are exactly the same kind of proofs a (non-) controller needs to perform attestation: it must know that the new time it is attesting to does not conflict with previous attestations. In sequential systems (where any unordered times conflict), this means the new time is after the most recent time (from the same controller) it attested to: . So in an implementation, collecting these proofs requires no special machinery beyond what is already required to support attestations. ↩
29Similarly, in school we learn about addition and multiplication of numbers, and in university we may learn about groups, rings, and fields, as clean retrospective algebraic generalisations. ↩
30This is clearly related to the condition of being contradiction-preserving from Definition 2.2.2(7c). So why is it called ‘strong‘ here? This is just a fussy point of terminology. Morally Definitions 7.2(3) and 2.2.2(7c) are indeed the same, but technically they are not: in the former, is curried from some Y to some X X; in the latter, is a function in Time Time Time. The word ‘strong‘ is just to remind ourselves that preserves contradictions in Y and also X. The reader might call us pedants, but we would take that as a compliment. ↩
31In the vocabulary of this paper we can sum up ‘fragmentation’ (in the sense it is used in finance and cryptocurrency, usually with negative connotations) as “a tendency for real-life systems to develop multiple independent controllers”. We discuss how this happens in our discussion of the One True Controller in Subsection 1.5). ↩
32For example, we do not complain that there are multiple telephone networks and standards (each optimised for local conditions, hardware, and economic circumstances), because we have good mathematics and engineering to make them collaborate seamlessly for the user. It was not always thus. Some readers might remember that when you placed a long distance call, you could actually hear the connections being made — and, famously, even hijack the process. In fact this system, and its exploits, are an important part of early computing history, as described in [Ros71]. For further reading on a true story from the 1990s which beggars belief yet is strangely reminiscent of some modern stories from blockchain, see [Kap04]. We mention this particularly to illustrate that while the 2020s are not the 1970s or the 1990s, issues with multiple controllers on digital networked computing systems are not at all new. On the contrary, this is a recurrent problem ...and it can be and has been overcome. ↩
33This insight was hard-won: we spent many hours staring at broken lemmas until we understood this. ↩
34A special case of this is serialisability: can the history of the objects be phrased as a serial order of events, each of which is correct given all that have gone before [Pap79]. ↩
35The reader who objects here that it is not the bike that is exponential, but its wheel, so that this should really be called ‘the exponential-wheeled bike’ — is correct. Congratulations! You have qualified for a career in logic. ↩
36An analogy: set theory is a foundation for all of mathematics; on the other hand natural numbers generalise in many ways, including to complex numbers, rings, and lattices. It remains to be understood whether Figure 9 will, within its own application domain, behave more like set theory, or more like numbers. ↩