Semitopology: a topological approach to decentralised collaborative action
arXiv:2303.09287v5 [cs.LO] 11 Jan 2025
We introduce semitopology, a generalisation of point-set topology that removes the restriction that intersections of open sets need necessarily be open. The intuition is that points represent participants in a decentralised system, and open sets represent collections of participants that collectively have the authority to collaborate to update their local state; we call this an actionable coalition.
Examples of actionable coalition include: majority stakes in proof-of-stake blockchains; communicating peers in peer-to-peer networks; and even pedestrians working together to not bump into one another in the street. Where actionable coalitions exist, they have in common that: collaborations are local (updating the states of the participants in the coalition, but not immediately those of the whole system); collaborations are voluntary (up to and including breaking rules); participants may be heterogeneous in their computing power or in their goals (not all pedestrians want to go to the same place); participants can choose with whom to collaborate; and they are not assumed subject to permission or synchronisation by a central authority.
We develop a topology-flavoured mathematics that goes some way to explaining how and why these complex decentralised systems can exhibit order, and gives us new ways to understand existing practical implementations.
Semitopology is also interesting in and of itself, having a rich and interesting theory which quickly deviates from standard accounts on topological spaces. It soon becomes clear that the most interesting semitopologies are rather ill-behaved from the usual viewpoint, as they are never Hausdorff. A notion of ‘transitive open sets’ (topens) becomes central to the story, as topens define subsets of participants who should decide the same value in a distributed system that tries to achieve consensus, and points are called ‘regular’ when they have a topen neighbourhood. The theory is then further developed by introducing intertwined points, closures, closed sets, and two interesting characterisations of regularity.
Additional Key Words and Phrases: Topology, semitopology, decentralised computation, distributed systems, consensus
1. INTRODUCTION
1.1. What is a ‘decentralised collaborative action’, and what is a semitopology?
A system is decentralised when it is distributed over several machines and furthermore the system as a whole is not centrally controlled. Most blockchain systems and peer-to-peer networks are decentralised (they are distributed over multiple participants, and no single entity controls the system). The internet is also (mostly) decentralised, at least in principle.1 Common practical problems from daily life can also be understood in terms of decentralised collaborative action: for example when we drive along a road, or walk around in a shop, we collaborate with the other agents (drivers, or shoppers) in a local and decentralised manner to avoid collisions.
So decentralised collaborative action is everywhere, but it has gained particular interest recently to designers of computer systems because it is an essential feature of many modern highly-decentralised computer systems, such as blockchains. So at a very high level, what do we have?
(1) There is a notion of what I will call an actionable coalition (or just open set). This is a set P of participants with the capability, though not the obligation, to act collaboratively to advance (= update / transition) the local state of the elements in , possibly but not necessarily in the same way for every .2
(2) is trivially an actionable coalition. Also we assume that P is actionable, since if it were not then literally nothing could ever get done.
(3) A sets union of actionable coalitions, is an actionable coalition.
Some important notes about this:
(1) State must be stored and updated locally (if state were centralised, then whoever controls the state has de facto control of the system, which would not be decentralised).
(2) An actionable coalition can progress locally, without consulting the rest of the system (if they had to, then the system would not be decentralised).
(3) Being a member of an actionable coalition does not imply control. Actionable coalitions describe legal collaborations, but do not imply any obligation.
(4) If is an actionable coalition for , and is another participant in , then is also an actionable coalition for . Note that this makes actionable coalitions look a bit like open sets in a topology.
So we can now introduce our first mathematical abstraction: we identify participants as points, and we let open sets be actionable coalitions. An actionable coalition is a coalition of participants with the capacity to act. They are not obliged to act, and if they do their action need not be identical across all participants, but the potential exists for this set to collaborate to progress their states. This leads us to the definition of a semitopology.
Suppose P is a set. Write pow(P) for the powerset of P (the set of subsets of P).
A semitopological space, or semitopology for short, consists of a pair (P Open(P)) of
— a (possibly empty) set P of points, and
— a set Open(P) pow(P) of open sets,
such that:
(1) Open(P) and POpen(P).
(2) If Open(P) then Open(P).3
We may write Open(P) just as Open, if P is irrelevant or understood, and we may write Open for the set of nonempty open sets.
The reader will recognise a semitopology as being like a topology on P, but without the condition that the intersection of two open sets necessarily be an open set. This reflects the fact that the intersection of two actionable coalitions need not itself be an actionable coalition.
1.2. How does this lead to new maths?
To get a flavour of our mathematical results, consider a fundamental problem in any decentralised system: ensuring that its participants remain in agreement, for some suitable sense of ‘agree’.
To take a simple example from blockchain: if we reach a situation where half of the nodes say that we have paid for a service, and the other half say that we have not — then everyone has a problem, because the system has become incoherent and it is not clear how the system as a whole can restore coherence and progress.4 This phenomenon is called forking, and blockchain designers really want to avoid it!
We will call our mathematical abstraction of agreement, antiseparation. In a little more detail, antiseparation properties are coherence properties that are guaranteed to hold of a decentralised system just by analysing the structure of its actionable coalitions. If we recall the usual separation axioms of topology — such as , , Hausdorff, and so on — note that these separation conditions have to do with the existence of non-intersecting open sets (or similar). Concretely, antiseparation assumptions on semitopologies are dual to this; they give various senses in which open neighbourhoods must intersect.
It turns out that these are interesting properties to have, because they determine participants who should decide the same value in a distributed system that tries to achieve consensus. It turns out that we can get surprisingly detailed information about consensus behaviour in decentralised systems just from quite weak and abstract antiseparation assumptions on the actionable coalitions (= open sets).
We emphasise this point: sometimes we can predict important macro properties of a system’s behaviour without knowing anything about its specifics, so long as we have certain good properties on its actionable coalitions.
Let us start by considering a simple situation where participants are trying to agree on a binary consensus problem: whether to announce a single value ‘true’ or ‘false’. Continuing the theme of simplicity, assume some finite nonempty set of participants and let their actionable coalitions be just any set of participants that forms a majority (so it contains strictly more than half of the set of all participants). Now suppose that the participants in some actionable coalition have communicated and have agreed on ‘true’. Because they form an actionable coalition, they are entitled to act and to announce ‘true’, and so they do. They have now all committed to this state update and they cannot change their minds.
So: can this system fork? Consider some participant . If wants to make progress, is must also agree on ‘true’, because all of its actionable coalitions intersect with and so contain at least one participant that has committed to ‘true’ and cannot change its mind. This does not mean that has to agree on ‘true’; it could choose not to progress, or it could break the rules. But, by definition if does want to progress legally, then the decision has been made and it must eventually go along with the majority. Thus, we have proved that any progress that is made by one participant within the rules (...must be shared with some actionable coalition of that participant, and since all such coalitions intersect it ...) must eventually be followed any other participant that also progresses. Thus forking is impossible.
The reader may already be familiar with this example, but note that this antiseparation property comes simply from the structure of the actionable coalitions. There is no need to consider the protocol, or even how values are interpreted.
Surprisingly, it turns out that antiseparation-style behaviour is common, and arises even if we do not require actionable coalitions that are simple majorities. For example, let participants be 0 11 22 and let actionable coalitions be generated by sets of three consecutive numbers starting at an even number 2 2 2, and suppose again that we are trying to agree on ‘true’ or ‘false’. Note that in contrast to the previous example, actionable coalitions need not intersect. Yet, the moment one triplet of participants commits to ‘true’, the rest of the system is obliged to eventually agree, if all participants play by the rules. Now this particular example system is not particularly safe or desirable in practice, because we can imagine that 0 1 2 agree on ‘true’, and 4 5 6 acting independently but in good faith agree on ‘false’, and then 3 cannot legally progress, because within 2 3 4, 2 has announced ‘true’ and 4 has announced ‘false’ and 3 cannot agree with both. But, we know that if all participants do legally progress, then they announce the same value. So this example illustrates how antiseparation can arise even when actionable coalitions are rather small.5
The two examples above are quite different. In one, all actionable coalitions intersect, and in the other they mostly do not. This suggests that a ‘general mathematics of (anti)separation’ is possible, based on the study of actionable coalitions. In a nutshell, that mathematical story is what we will develop.
The notion of actionable coalitions is introduced in this document, but in retrospect we see them everywhere. For example: Some blockchain systems make actionable coalitions explicit, e.g. in the XRP Ledger [SYB14] and the Stellar network [LLM19] the notion of actionable coalition is represented explicitly in the engineering architecture of the system. Social choice theorists have a similar notion called a winning coalition [Rik62, Item 5, page 40], which is used to study voting systems; and if the reader has a background in logic then they may be reminded of a whole field of generalised quantifiers (a good survey is in [Wes11]).6 Cross-chain systems (which operate or translate across multiple blockchain) inherently have to deal with heterogeneous actionable coalitions, since the actionable coalitions of one blockchain need not be (and usually are not) identical to those of another. Concrete algorithms to attain consensus often use a notion of quorum [Lam98; LSP82] for a participant ; simply put, this is a set of participants whose unanimous adoption of a value guarantees that will eventually also adopt this value. If quorums are majorities (more than half) or supermajorities (more than two-thirds) of all participants then quorums already are actionable coalitions; if not, then we can obtain an actionable coalition in a natural way by considering any set such that every participant (element) has some subset that is a quorum for .
1.3. Who should read this paper?
(1) Practitioners looking for a mathematical framework that subsumes what they’re already doing, puts it in a broader context, creates a common language to speak with one another and with mathematicians, and suggests new engineering options.
(2) Theoreticians looking for maths to help design the next generation of advanced decentralised computer systems.
(3) Pure mathematicians who might be pleased to discover a new topology-adjacent field and might see it as a fresh research opportunity.7
(4) Mathematicians looking to get into practical systems. Real systems are often messy, because they have to accommodate a messy reality. Semitopologies provide a useful abstraction that can help us to understand what is going on at a high level.
1.4. Why did I write it?
Numerous authors have recently studied designing systems where participants have different opinions on who is part of the system or on who is trustworthy or not [ACTZ24; SWRM21; CLZ23; LCL23; BKK22; GPG18; LLM19; LGM19; FHNS22; LL23]. These systems go by names such as (permissionless) fail-prone systems and (heterogeneous) quorum systems (more discussion, with more references, is in Subsection 7.2).
Most of these systems are (or to be more precise: they directly give rise to) semitopologies, and it seems to me that the literature above is, in fact, rediscovering topology through semitopology, but they did not know it. Here, we make the connection to classical mathematics explicit, and build on it to obtain results that matter and say something about the (expected) behaviours of these new classes of systems.
1.5. Map of the paper
(1) Section 1 is the Introduction. You Are Here.
(2) In Section 2 we show how continuity corresponds to local agreement (Definition 1.1.2 and Lemma 2.2.4).
(3) In Section 3 we introduce transitive sets, topens, and intertwined points. These are all different views on the anti-separation well-behavedness properties that will interest us. Most of Section 3 is concerned with showing how these different views relate and in what senses they are equivalent (e.g. Proposition 3.6.9). Transitive sets are guaranteed to be in agreement (in a sense made precise in Theorem 3.2.2 and Corollary 3.2.3), and we take a first step to understanding the fine structure of semitopologies by proving that every semitopology partitions into topen sets (Theorem 3.5.4), plus other kinds of points which we classify in the next Section.
(4) In Section 4 we start to classify points in more detail, introducing notions of regular, weakly regular, and quasiregular points (Definition 4.1.4).8 Regular points are those contained in some topen set, and they display particularly good behaviour. Regularity will be very important to us and we will characterise it in multiple ways: see Remark 4.2.5. (A survey of characterisations of weak regularity requires more machinery and appears in Remark 5.4.8.)
(5) In Section 5 we study closed sets, and in particular the interaction between intertwined points, topens, and closures. Typical results are Proposition 5.4.3 and Theorem 5.6.2 which characterise sets of intertwined points as minimal closures. The significance to consensus is discussed in Remarks 5.5.1 and 5.5.5.
(6) In Section 6 we study unconflicted and hypertransitive points, leading to two useful characterisations of regularity in Theorems 6.2.2 and 6.5.8.
(7) In Section 7 we conclude and discuss related and future work. We discuss connections with related work in Subsection 7.2.
Algebraic topology has been applied to the solvability of distributed-computing tasks in various computational models (e.g. the impossibility of wait-free -set consensus using read-write registers and the Asynchronous Computability Theorem [HS93; BG93; SZ93]; see [HKR13] for a survey). Semitopology is not topology, and this is not a paper about algebraic topology applied to the solvability of distributed-computing tasks!
This paper is about the mathematics of actionable coalitions, as made precise by point-set semitopologies; their antiseparation properties; and the implications to partially continuous functions on of them. If we discuss distributed systems, it is by way of providing motivating examples or noting applicability.
2. SEMITOPOLOGY
2.1. Definitions, examples, and some discussion
2.1.1. Definitions.
Recall from Definition 1.1.2 the definition of a semitopology.
(1) As a sets structure, a semitopology on P is like a topology on P, but without the condition that the intersection of two open sets be an open set.
(2) As a lattice structure, a semitopology on P is a bounded complete join-subsemilattice of pow(P).9
(3) Every semitopology (P Open) induces two natural topological completions: the least topology that contains Open, and the greatest topology contained in Open. But there is more to semitopologies than just their topological completions, because:
(a) We are explicitly interested in situations where intersections of open sets need not be open.
(b) Completing to a topology loses information. For example: the ‘many’, ‘all-but-one’, and ‘more-than-one’ semitopologies in Example 2.1.4 express three distinct notions of quorum, yet if P is infinite then for all three, the least topology containing them is the discrete semitopology (Definition 2.1.3(1)), and the greatest topology that they contain is the trivial topology P (Example 2.1.4(4)). See also the overview in Subsection 7.1.
Semitopologies are not topologies. We take a moment to spell out one concrete difference:
In topologies, if a point has a minimal open neighbourhood then it is least (= unique minimal). In semitopologies, a point may have multiple distinct minimal open neighbourhoods.
To see that in a topology every minimal open neighbourhood is least, just note that if and then . So if and are two minimal open neighbourhoods then is contained in both and by minimality is equal to both.
To see that in a semitopology a minimal open neighbourhood need not be least, it suffices to provide an example. Consider (P Open) defined as follows, as illustrated in Figure 1:
—
— Open 0 11 20 1 2
Note that 1 has two minimal open neighbourhoods: 0 1 and 1 2.
2.1.2. Examples.
As standard, we can make any set Val into a semitopology (indeed, it is also a topology) just by letting open sets be the powerset:
(1) Call (P pow(P)) the discrete semitopology on P.
We may call a set with the discrete semitopology a semitopology of values, and when we do we will usually call it Val. We may identify Val-the-set and Val-the-discrete-semitopology; meaning will always be clear.
(2) When (P Open) is a semitopology and Val is a semitopology of values, we may call a function : P Val a value assignment. Note that a value just assigns values to points, and in particular we do not assume a priori that it is continuous, where continuity is defined just as for topologies (see Definition 2.2.1).
We consider further examples of semitopologies:
(1) Every topology is also a semitopology; intersections of open sets are allowed to be open in a semitopology, they are just not constrained to be open. In particular, the discrete topology is also a discrete semitopology (Definition 2.1.3(1)).
(2) The initial semitopology () and the final semitopology () are semitopologies.
(3) An important discrete semitopological space is B with the discrete semitopology Open( We may silently treat as a (discrete) semitopological space henceforth.
(4) Take P to be any nonempty set. Let the trivial semitopology (this is also a topology) on P have
So (as usual) there are only two open sets: the one containing nothing, and the one containing every point.10 The only nonempty open is P itself, reflecting a notion of actionable coalition that requires unanimous agreement.
(5) Suppose P is a set and pow(P) is nonempty and up-closed (so if and P then , then (P) is a semitopology. This is not necessarily a topology, because we do not insist that is a filter (i.e. is closed under intersections). We give four sub-examples for different choices of pow(P).
(a) Take P to be any finite nonempty set. Let the supermajority semitopology have
So is open when it contains at least two-thirds of the points. Two-thirds is a typical threshold used for making progress in consensus algorithms.
(b) Take P to be any nonempty set. Let the many semitopology have
For example, if P then open sets include evens 2 and odds 2 . Its notion of open set captures an idea that an actionable coalition is a set that may not be all of P, but does at least biject with it.
(c) Take P to be any nonempty set. Let the all-but-one semitopology have
This semitopology is not a topology. The notion of actionable coalition here is that there may be at most one objector (but not two).
(d) Take P to be any set with cardinality at least 2. Let the more-than-one semitopology have
This semitopology is not a topology. This notion of actionable coalition reflects a security principle in banking and accounting (and elsewhere) of separation of duties, that functional responsibilities be separated such that at least two people are required to complete an action — so that errors (or worse) cannot be made without being discovered by another person.
(6) Take P (the set of real numbers) and let open sets be generated by intervals of the form [0) or ( 0] for any strictly positive real number 0. This semitopology is not a topology, since (for example) (1 0] and [0 1) are open, but their intersection 0 is not open.
(7) In [NW94] a notion of quorum system is discussed, defined as any collection of pairwise intersecting sets. Quorum systems are a field of study in their own right, especially in the theory of concrete consensus algorithms.
Every quorum system gives rise naturally to a semitopology, just by closing under arbitrary unions. We obtain what we will call an intertwined space (Notation 3.6.5; a semitopology all of whose nonempty open sets intersect).11 Going in the other direction is interesting for a different reason, that it is slightly less canonical: of course every intertwined space is already a quorum system; but (for the finite case) we can also map to the set of all open covers of all points.
To give one specific example of a quorum system from [NW94], consider grid of cells with quorums being sets consisting of any full row and a full column; note that any two quorums must intersect in at least two points. We obtain a semitopology just by closing under arbitrary unions.
One class of examples of semitopologies deserves its own discussion. Consider an arbitrary logical system with predicates Pred and entailment relation .12 Call Φ Pred deductively closed when Φ implies Φ. Then take
— P Pred, and
— let Open be Pred or the complement to a deductively closed set Φ, so PredΦ.
Note that an arbitrary union of open sets is open (because an arbitrary intersection of deductively closed sets is deductively closed), but an intersection of open sets need not be open (because the union of deductively closed sets need not be deductively closed). This is a semitopology.
2.1.3. Why the name ‘semitopologies’, and other discussion
When we give a name ‘semitopologies’ to things that are like topologies but without intersections, this is a riff on
—‘semilattices’, for things that are like lattices with joins but without meets (or vice-versa), and
—‘semigroups’, for things that are like groups but without inverses.
But, this terminology also reflects a real mathematical connection, because semitopologies are semilattices are semigroups, in standard ways which we take a moment to spell out:
— A semitopology (P Open) is a bounded join subsemilattice of the powerset pow(P), by taking the join to be sets union and the bounds and to be and P respectively.
— A semilattice is an idempotent commutative monoid, which is an idempotent commutative semigroup with an identity, by taking the multiplication to be and the identity element to be ( becomes what is called a zero or absorbing element, such that always).
We noted in Remark 2.1.6 that every semitopology is a semilattice. This is true, but the reader should not read this statement as reductive: semitopologies are not just semilattices.
To see why, consider the following two simple semitopologies, as illustrated in Figure 2:
(1) (P Open) where P 0 1 2 and Open 0 11 20 1 2.
(2) ( ) where P 0 2 and 020 2.
Note that the semilattices of open sets Open and are isomorphic — so, when viewed as semilattices these two semitopologies are the same (up to isomorphism).
However, (P Open) is not the same semitopology as ( ). There is more than one way to see this, but perhaps the simplest indication is that for every continuous : (P Open) ( ), there is no continuous map : ( ) (P Open) such that is the identity (we will define continuity in a moment in Definition 2.2.1(2) but it is just as for topologies, so we take the liberty of using it here). There are a limited number of possibilities for and , and we can just enumerate them and check:
— If and and , then (22 Open, and if then (00 Open.
— If and and , then (21 Open, and if then (00 Open.
— Other possibilities are no harder.
A similar observation holds for topologies: for example, if we write ( ) for the rational numbers with their usual open set topology, and ( ) for the real numbers with their usual open set topology, then their topologies are isomorphic as lattices, with one direction of the isomorphism given just by maps to . This counterexample works for semitopologies too since every topology is also a semitopology.
However, we would still argue that the counterexample in Figure 2 is inherently stronger; not just because it is smaller (two and three points instead of countably and uncountably many) but also because — while we can recover from in a natural and canonical way by forming a completion — the upper semitopology in Figure 2 is not a priori canonically derived from the lower one. The two semitopologies in Figure 2 seem to be distinct in some structural way, yet they still corresponding to the same semilattice, so we see that there is other structure here, which is not reflected by the pure semilattice derived from their open sets.
We conclude with some easy predictions about the theory of semitopologies, made just from general mathematical principles. Fewer axioms means:
(1) more models,
(2) finer discrimination between definitions, and
(3) (because there are more models) more counterexamples.
So we can expect a theory with the look-and-feel of topology, but with new models, new distinctions between definitions that in topology may be equivalent, and some new definitions, theorems, and counterexamples — and this indeed will be the case.
Note that fewer axioms does not necessarily mean fewer interesting things to say and prove. On the contrary: if we can make finer distinctions, there may also be more interesting things to prove; and furthermore, assumptions we make can become more impactful in a weaker system, because these assumptions may exclude more models than would have been the case with more powerful axioms.
For example consider semigroup theory and group theory: every group is a semigroup, but both groups and semigroups have their own distinct character, literature, and applications. To take this to an extreme, consider the terminal theory, which has just one first-order axiom: . This ‘subsumes’ groups, lattices, graphs, and much besides, in the sense that every model of the terminal theory is a group, a lattice, and a graph, in a natural way. But this theory is so strong, and its models so restricted (just the singleton model with one element) that there is not much left to say about it. Additional assumptions we may make on elements add literally nothing of value, because there was only one element to begin with!
2.2. Continuity, and its interpretation
We can import the topological notion of continuity and it works fine in semitopologies, and the fact that there are no surprises is a feature. In Remark 2.2.5 we explain how these notions matter to us:
We import standard topological notions of inverse image and continuity:
(1) Suppose P and are any sets and : P is a function. Suppose . Then write -1() for the inverse image or preimage of , defined by
(2) Suppose (P Open) and ( ) are semitopological spaces (Definition 1.1.2). Call a function : P continuous when the inverse image of an open set is open. In symbols:
(3) Call a function : P continuous at P when
In words: is continuous at when the inverse image of every open neighbourhood of () contains an open neighbourhood of .
(4) Call a function : P continuous on P when is continuous at every .
The top-down implication is immediate, taking -1().
For the bottom-up implication, given and an open neighbourhood (), we write
Above, is the open neighbourhood of in the preimage of , which we know exists by Definition 2.2.1(3).
It is routine to check that -1(), and since this is a union of open sets, it is open.
Suppose that:
— (P Open) is a semitopology and
— Val is a semitopology of values (Definition 2.1.3(1)) and
— : P Val is a value assignment (Definition 2.1.3(2); an assignment of a value to each element in P).
Then:
(1) Call locally constant at P when there exists Open such that
So is locally constant at when it is constant on some open neighbourhood of .
(2) Call locally constant when it is locally constant at every P.
This is just by pushing around definitions, but we spell it out:
— Suppose is continuous, consider P, and write (). By our assumptions we know that -1() is open, and -1(). This is an open neighbourhood on which is constant, so we are done.
— Suppose is locally constant, consider P, and write (). By assumption we can find Open on which is constant, so that -1().
Lemma 2.2.4 tells us that we can view the problem of attaining agreement across an actionable coalition (as discussed in Subsection 1.1) as being the same thing as computing a value assignment that is continuous on that coalition (and possibly elsewhere).
To see why, consider a semitopology (P Open) and following the intuitions discussed in Subsection 1.1 view points P as participants; and view open neighbourhoods Open as actionable coalitions that include . Then to say “ is a value assignment that is continuous at ” is to say that:
— assigns a value or belief to P, and
— is part of a (by Lemma 2.2.4 continuity) set of peers that agrees with and (being open) can progress to act on this agreement.
Conceptually and mathematically this reduces the general question
How can we model collaborative action?
(which, to be fair, has more than one possible answer!) to a more specific research question
Understand continuous value assignments on semitopologies.
We then devote ourselves to elaborating (some of) a body of mathematics that we can pull out of this idea.
2.3. Neighbourhoods of a point
Definition 2.3.1 is a standard notion from topology, and Lemma 2.3.2 is a (standard) characterisation of openness, which will be useful later:
Suppose (P Open) is a semitopology and P and Open. Then call an open neighbourhood of when .
In other words: an open set is (by definition) an open neighbourhood precisely for the points that it contains.
Suppose (P Open) is a semitopology and suppose P is any set of points. Then the following are equivalent:
— Open.
— Every point in has an open neighbourhood in .
In symbols we can write:
An initial inspiration for modelling collaborative action using semitopologies, came from noting that the standard topological property described above in Lemma 2.3.2, corresponds to the quorum sharing property in [LGM19, Property 1]; the connection to topological ideas had not been noticed in [LGM19].
3. TRANSITIVE SETS & TOPENS
3.1. Some background on sets intersection
Some notation will be convenient:
Suppose , , and are sets.
(1) Write
When holds then we say (as standard) that and intersect.
(2) We may chain the notation, writing for example
(3) We may write for (), thus when .
Note on design in Notation 3.1.1: It is uncontroversial that if and then should hold precisely when — but there is an edge case! What truth-value should return when or is empty?
(1) It might be nice if would imply . This argues for setting
(2) It might be nice if were monotone on both arguments (i.e. if and then ). This argues for setting
(3) It might be nice if always — after all, should a set not intersect itself? — and this argues for setting
even if we also set for nonempty . All three choices are defensible, and they are consistent with the following nice property:
We choose the second — if or is empty then — because it gives the simplest definition that precisely when .
We list some elementary properties of from Notation 3.1.1(1):
(1) if and only if .
(2) if and only if .
(3) () if and only if () ().
(4) If and then .
(5) Suppose . Then implies , and implies .
(6) If then and .
By facts of sets intersection.
3.2. Transitive open sets and value assignments
Theorem 3.2.2 clarifies why transitivity is interesting: continuous value assignments are constant — if we think of points as participants, ‘constant function’ here means ‘in agreement’ — across transitive sets.
Suppose that:
— (P Open) is a semitopology.
— Val is a semitopology of values (a nonempty set with the discrete semitopology; see Definition 2.1.3(1)).
— : P Val is a value assignment (Definition 2.1.3(2)).
— P is a transitive set (Definition 3.2.1) — in particular this will hold if is topen — and .
Then:
(1) If is continuous at and then (().
(2) As a corollary, if is continuous on , then is constant on .
In words we can say:
Continuous value assignments are constant across transitive sets.
Part 2 follows from part 1 since if (() for any , then by definition is constant on . So we now just need to prove part 1 of this result.
Consider . By continuity on , there exist open neighbourhoods -1(()) and -1(()). By construction (because and ). By transitivity of it follows that . Thus, there exists , and by construction ((().
Corollary 3.2.3 is an easy and useful consequence of Theorem 3.2.2:
Suppose that:
— (P Open) is a semitopology.
— : P Val is a value assignment to some set of values Val (Definition 2.1.3).
— is continuous on topen sets Topen.
Then
By Theorem 3.2.2 is constant on and . We assumed that and intersect, and the result follows.
A converse to Theorem 3.2.2 also holds:
Suppose that:
— (P Open) is a semitopology.
— Val is a semitopology of values with at least two elements (to exclude a degenerate case that no functions exist, or they exist but there is only one because there is only one value to map to).
— P is any set.
Then
— if for every and every value assignment : P Val, continuous at and implies ((),
— then is transitive.
We prove the contrapositive. Suppose is not transitive, so there exist Open such that and yet . We choose two distinct values Val and define to map any point in to and any point in P to .
Choose some and . It does not matter which, and some such and exist, because and are nonempty by Lemma 3.1.3(6), since and ).
We note that ( and ( and is continuous at and P, yet () ().
We can sum up what Theorem 3.2.2 and Proposition 3.2.4 mean, as follows:
Suppose (P Open) is a semitopology and Val is a semitopology of values with at least two elements. Say that a value assignment : P Val splits a set P when there exist such that is continuous at and and () (). Then Theorem 3.2.2 and Proposition 3.2.4 together say in words that:
P is transitive if and only if it cannot be split by a value assignment that is continuous on .
Intuitively, transitive sets characterise areas of guaranteed agreement.
This reminds us of a basic result in topology about connected spaces [Wil70, Chapter 8, section 26]. Call a topological space (T Open) disconnected when there exist open sets Open such that (in our notation: ) and T; otherwise call (T Open) connected. Then (T Open) is disconnected if and only if (in our terminology above) it can be split by a value assignment. Theorem 3.2.2 and Proposition 3.2.4 are not identical to that result, but they are in the same spirit.
The notion of transitive set gives us enough to comment on the two examples in Subsection 1.1. Recall that we considered:
(1) A nonempty finite set with open sets Open() (‘actionable coalitions’) being majority subsets .
(2) Integers with open sets Open() generated by triplets 2 2 2.
The reader can check that in ( Open()) every set is transitive, because every pair of nonempty open sets intersect; thus, no can be split by a value assignment that is continuous on . In contrast, the reader can check that in ( Open()), most sets are not transitive, including (for example) 0 4. This lack of transitivity reflects an intuitive observation we made in Subsection 1.1 that our second example was ‘not necessarily particularly safe or desirable in practice’; in our more technical language, we can now note that there exists a value assignment that splits 0 4, yet is continuous at 0 and 4. What ( Open()) does satisfy is the weaker (but still useful!) safety property that any continuous value assignment that is continuous everywhere, is constant (corresponding to our informal observation that “if all participants do legally progress, then they announce the same value”).15 This reflects a useful intuition, that the topological notion of ‘continuity at a point’, corresponds to an intuition of as a participant ‘following the rules’.
3.3. Examples and discussion of transitive sets and topens
We may routinely order sets by subset inclusion; including open sets, topens, closed sets, and so on, and we may talk about maximal, minimal, greatest, and least elements. We include the (standard) definition for reference:
Suppose (P) is a poset. Then:
(1) Call P maximal when and minimal when .
(2) Call P greatest when and least when .
(1) is transitive, for any single point P.
(2) The empty set is (trivially) transitive. It is not topen because we insist in Definition 3.2.1(2) that topens are nonempty.
(3) Call a set P topologically indistinguishable when (using Notation 3.1.1) for every open set ,
It is easy to check that if is topologically indistinguishable, then it is transitive.
(1) Take P 0 1 2, with open sets , P, 0, and 2. This has two maximal topens 0 and 2 as illustrated in Figure 3 (top-left diagram).
(2) Take P 0 1 2, with open sets , P, 0, 0 1, 2, 1 2, and 0 2. This has two maximal topens 0 and 2, as illustrated in Figure 3 (top-right diagram).
(3) Take P 0 1 2 3 4, with open sets generated by 0 1, 1, 3, and 3 4. This has two maximal topens 0 1 and 3 4, as illustrated in Figure 3 (lower-left diagram).
(4) Take P 0 1 2, with open sets generated by 0, 1, 2, 0 1, and 1 2. This has three maximal topens 0, 1, and 2, as illustrated in Figure 3 (lower-right diagram).
(5) Take the all-but-one semitopology from Example 2.1.4(5c) on : so P with opens , , and for every . This has a single maximal topen .
(6) The semitopology in Figure 7 has no topen sets at all ( is transitive and open, but by definition in Definition 3.2.1(2) topens have to be nonempty).
We take a moment for a high-level discussion of where we are going.
The semiopologies in Example 3.3.3 invite us to ask what makes these examples different (especially parts 1 and 2). Clearly they are not equal, but that is a superficial answer in the sense that it is valid just in the world of sets, and it ignores semitopological structure.
For comparison: if we ask what makes 0 and 1 different in , we could just to say that 0 , but this ignores what makes them different as numbers. For more insight, we could note that 0 is the additive unit whereas 1 is the multiplicative unit of as a semiring; or that 0 is a least element and 1 is the unique atom of as a well-founded poset; or that 1 is the successor of 0 of as a well-founded inductive structure. Each of these answers gives us more understanding, not only into 0 and 1 but also into the structures that can be given to itself.
So we can ask:
What semitopological property or properties on points can identify the essential nature of the differences between the semitopologies in Example 3.3.3?
There would be some truth to saying that the rest of our investigation is devoted to developing and understanding answers to this question! In particular, we will shortly define the set of intertwined points in Definition 3.6.1. Example 3.6.2 will note that 10 1 2 in Example 3.3.3(1), whereas 11 in Example 3.3.3(2), and for every in Example 3.3.3(3).
Here and elsewhere, we might omit open sets that are unions of open sets that are illustrated. For example, we explicitly draw the universal open set in the left-hand diagrams above, but not in the right-hand diagrams above. Meaning is clear and we get cleaner diagrams.
Fig. 3: Examples of topens (Example 3.3.3)
3.4. Closure properties of transitive sets
Transitive sets have some nice closure properties which we treat in this Subsection — here we mean ‘closure’ in the sense of “the set of transitive sets is closed under various operations”, and not in the topological sense of ‘closed sets’.
Topens — nonempty transitive open sets — will have even better closure properties, which emanate from the requirement in Lemma 3.4.3 that at least one of the transitive sets or is open. See Subsection 3.5.
Suppose (P Open) is a semitopology and P. Then:
(1) If is transitive and , then is transitive.
(2) If is topen and is nonempty and open, then is topen.
Suppose that:
— (P Open) is a semitopology.
— P are transitive.
—At least one of and is open.
Then:
(1) Open .
(2) If then is transitive.
(1) We simplify using Definition 3.2.1 and our assumption that one of and is open. We consider the case that is open:
The argument for when is open, is precisely similar.
(2) Suppose . By Lemma 3.1.3(3) (at least) one of the following four possibilities must hold:
If then by part 1 of this result we have as required. The other possibilities are no harder.
A chain of sets is a collection of sets that is totally ordered by subset inclusion .16
We may call a chain ascending or descending if we want to emphasise that we are thinking of the sets as ‘going up’ or ‘going down’.
Suppose (P Open) is a semitopology and suppose is a chain of transitive sets (Definition 3.4.4). Then is a transitive set.
Suppose . Then there exist such that and . But is totally ordered, so either or . In the former case it follows that so that by transitivity of ; the latter case is precisely similar.
3.5. Closure properties of topens
Definition 3.5.1 will be useful in Lemma 3.5.2(2):
Suppose (P Open) is a semitopology. Call a set of nonempty open sets Open a clique when its elements pairwise intersect.17 In symbols:
Open is a clique when
Note that if is a clique then every is nonempty, since if then by by Lemma 3.1.3(1).
Suppose (P Open) is a semitopology. Then:
(1) If and are an intersecting pair of topens (i.e. ), then is topen.
(2) If is a clique of topens (Definition 3.5.1), then is topen.
(3) If is a nonempty ascending chain of topens then is topen.
(1) is open because by Definition 1.1.2(2) open sets are closed under arbitrary unions, and by Lemma 3.4.3(2) is transitive.
(2) is open by Definition 1.1.2(2). Also, if then there exist such that and . We assumed , so by Lemma 3.4.3(1) (since and are open) we have as required.
(3) Any chain is pairwise intersecting. We use part 2 of this result.18
Suppose (P Open) is a semitopology. Then every topen is contained in a unique maximal topen.
Consider defined by
By Lemma 3.5.2(1) this is a set of topens. By construction they all contain , and by our assumption that they pairwise intersect (since they all contain , at least), so by Lemma 3.5.2(2) is topen. It is easy to check that this is the unique maximal transitive open set that contains .
Suppose (P Open) is a semitopology. Then any P, and in particular P itself, can be partitioned into:
— Some disjoint collection of maximal topens.
—A set of other points, which are not contained in any topen.
Routine from Corollary 3.5.3.
It may be useful to put Theorem 3.5.4 in the context of the terminology, results, and examples that will follow below. We will have Definition 4.1.4(3&6) and Theorem 4.2.6. These will allow us to call a point contained in some maximal topen regular, to call the maximal topen of a regular point its community, and a point that is not contained in any topen irregular. Then Theorem 3.5.4 says that a semitopology P can be partitioned into:
— Disjoint maximal communities of regular points which, in a sense made formal in Theorem 3.2.2, are a coalition acting together — and
— a set of irregular points, which are in no community and so are not members of any coalition.
We give examples in Example 3.3.3 and Figure 3, and we will see more elaborate examples below (see in particular the collection in Example 5.6.10).
In the special case that the entire space consists of a single topen community, there are no irregular points and all participants are guaranteed to agree, where algorithms succeed. For the application of a single blockchain trying to arrive at consensus, this discussion tells us that we want the underlying semitopology to consist of a single topen, because this means that all participants are guaranteed to agree, where algorithms succeed. A semitopology that consists of a single topen set is precisely one all of whose open sets intersect, and the reader familiar with literature on quorum systems (for example [LGM19]) will recognise this as corresponding to the quorum intersection property.
3.6. Intertwined points
3.6.1. The basic definition, and some lemmas
Suppose (P Open) is a semitopology and P.
(1) Call and intertwined when is transitive. Unpacking Definition 3.2.1 this means:
By a mild abuse of notation, write
when and are intertwined
(2) Define (read ‘intertwined of ’) to be the set of points intertwined with . In symbols:
We return to the examples in Example 3.3.3. There we note that:
(1) 10 1 2 and 00 1 and 21 2.
(2) 11 and 00 and 22.
(3) 00 1 2 and 32 3 4 and 2 P.
(4) 00 and 11 and 22.
(5) P for every .
(6) for every .
Here is one reason to care about intertwined points; a value assignment is constant on a pair of intertwined points, where it is continuous:
Suppose Val is a semitopology of values and : P Val is a value assignment (Definition 2.1.3) and P and . Then if is continuous at and , then (().
We might suppose that being intertwined is transitive. Lemma 3.6.4 shows that this is not necessarily the case (the case when is transitive at is an important well-behavedness property, which we will call being unconflicted; see Subsection 6.1 and Definition 6.1.1):
Suppose (P Open) is a semitopology. Then:
(1) The ‘is intertwined’ relation is reflexive and symmetric.
(2) is not necessarily transitive. That is: does not necessarily imply .
We conclude with an easy observation:
Suppose (P Open) is a semitopology. Call P intertwined when
In words: P is intertwined when all of its points are pairwise intertwined.
Lemma 3.6.6 will be useful later, notably for Lemma 4.1.9:
Routine by unpacking the definitions.
3.6.2. Pointwise characterisation of transitive sets
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is transitive.
(2) (meaning by Definition 3.6.1 that is transitive) for every .
The special case of Lemma 3.6.8 where is an open set will be particularly useful:
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is topen.
(2) Open and .
In words we can say:
A topen is a nonempty open set of intertwined points.
Recall that we call a topological space (P Open) Hausdorff (or ) when any two points can be separated by pairwise disjoint open sets. Using the symbol from Notation 3.1.1, we rephrase the Hausdorff condition as
we can simplify to
and thus we simplify the Hausdorff condition just to
Note how distinct and being intertwined is the opposite of being Hausdorff: when , and they cannot be separated by pairwise disjoint open sets. Thus the assertion in Proposition 3.6.9 is a negation to the Hausdorff property:
This is useful because for semitopologies as applied to consensus,
— being Hausdorff means that the space is separated (which is probably a bad thing, if we are looking for a system with lots of points in consensus), whereas
— being full of intertwined points means by Theorem 3.2.2 that the system will (where algorithms succeed) be full of points whose value assignment agrees (which is a good thing).
In the blockchain literature, we say that a blockchain forks when it partitions into two sets of participants with incompatible beliefs about the state of the system. In this light, we can view Theorem 3.2.2 as a result making precise sufficient conditions to ensure that this does not happen.
3.7. Strong topens: topens that are also subspaces
3.7.1. Definition and main result.
Let us take stock and recall that:
— is topen when it is a nonempty open transitive set (Definition 3.2.1).
— is transitive when implies for all Opens (Definition 3.2.1).
— means that (Notation 3.1.1).
But, note above that if is topen and then need not intersect inside . It could be that and intersect outside of (an example is in the proof Lemma 3.7.2 below).
Definition 3.7.1 spells out a standard topological construction in the language of semitopologies:
Suppose (P Open) is a semitopology and suppose P is a set of points. Write ( Open ) for the semitopology such that:
— The points are .
— The open sets have the form for Open.
We say that ( Open ) is with the semitopology induced by (P Open).
We may call ( Open ) a subspace of (P Open), and if the open sets are understood then we may omit mention of them and just write:
A subset P is naturally a (semitopological) subspace of P.
The property of being a (maximal) topen is not necessarily closed under taking subspaces.
It suffices to exhibit a semitopology (P Open) and a subset P such that is topen in (P Open) but is not topen in ( Open ). We set:
as illustrated in Figure 4 (left-hand diagram). Now:
— is topen in (P Open), because every open neighbourhood of 0 — that is 0 2, 0 1, and P
— intersects with every open neighbourhood of 1 — that is 1 2, 0 1, and P.
— is not topen in ( Open ), because 0 is an open neighbourhood of 0 and 1 is an open neighbourhood of 1 and these do not intersect.
Lemma 3.7.2 motivates the following definitions:
Suppose , , and are sets. Write , and say that and meet or intersect in , when () ().
Suppose , , and are sets. Then:
(1) The following are equivalent:
(2) if and only if .
(3) If then .
From Definition 3.7.3, by elementary sets calculations.
Suppose (P Open) is a semitopology and recall from Definition 3.2.1 the notions of transitive set and topen.
(1) Call P strongly transitive when
(2) Call a strong topen when is nonempty open and strongly transitive,
Suppose (P Open) is a semitopology and P. Then:
(1) If is strongly transitive then it is transitive.
(2) The reverse implication need not hold (even if (P Open) is a topology): it is possible for to be transitive but not strongly transitive.
We consider each part in turn:
(1) Suppose is strongly transitive and suppose . By Lemma 3.7.4(2) . By strong transitivity . By Lemma 3.7.4(3) . Thus is transitive.
(2) It suffices to provide a counterexample. This is illustrated in Figure 4 (right-hand diagram). We set:
— P 0 1 2, and
— Open 10 11 20 1 2.
— We set 0 2.
We note that (P Open) is a topology, and it is easy to check that is transitive — we just note that 0 11 2 and 0 11 2. However, is not strongly transitive, because 0 11 21.
Suppose (P Open) is a semitopology and suppose Open. Then the following are equivalent:
(1) is a strong topen.
(2) is a topen in ( Open ) (Definition 3.7.1).
Suppose is a strong topen; thus is nonempty, open, and strongly transitive in (P Open). Then by construction is open in ( Open), and the strong transitivity property of Definition 3.7.5 asserts precisely that is transitive as a subset of ( Open ).
Now suppose is a topen in ( Open); thus is nonempty, open, and transitive in ( Open ). Then is nonempty and by assumption above Open.19 Now suppose Open and . Then by Lemma 3.7.4(2) , so by transitivity of in ( Open ) also , and thus by Lemma 3.7.4(3) also .
3.7.2. Connection to lattice theory.
There is a notion from order-theory of a join-irreducible element (see for example in [DP02, Definition 2.42]), and a dual notion of meet-irreducible element:
Call an element in a lattice
— join-irreducible when is not a bottom element, and is not a join of two strictly smaller elements: if then , or , and
— meet-irreducible when is not a top element, and is not a meet of two strictly greater elements: if then or .
This definition is typically given for lattices, but it makes just as much sense for semilattices as well.
(1) Consider the lattice of finite (possibly empty) subsets of , with adjoined as a top element. Then is join-irreducible; is not a bottom element, and if then either or .
(2) Consider with the final segment semitopology such that opens are either or sets . Then is meet-irreducible; is not a top element, and if then either or .
(3) Consider the integers with the lattice structure in which meet is minimum and join is maximum. Then every element is join- and meet-irreducible; if then or , and similarly for .
We spell out how this is related to our notions of transitivity from Definitions 3.2.1 and 3.7.5:
Suppose (P Open) is a semitopology and P. Then:
(1) is strongly transitive if and only if is meet-irreducible in ( Open ) (Definition 3.7.1).
(2) is transitive if is meet-irreducible in ( Open ).
(3) If is transitive it does not necessarily follow that is meet-irreducible in ( Open ).
We reason as follows:
(1) is meet-irreducible in ( Open ) means that () ( implies or . is strongly transitive when (taking the contrapositive in Definition 3.7.5(1)) ()( implies or . That these conditions are equivalent follows by straightforward sets manipulations.
(2) We can use part 1 of this result and Lemma 3.7.6(1), or give a direct argument by sets calculations: if then ()( and by meet-irreducibility or as required.
(3) Figure 4 (left-hand diagram) provides a counterexample, taking 0 1 and 0 2 and 1 2. Then () ( but it is not the case that or .
The proof of Lemma 3.7.10 not hard, but the result is interesting for what it says, and also for what it does not say:
(1) The notion of being a strong topen maps naturally to something in order theory; namely that is meet-irreducible in the induced poset Open which is the set of open sets of the subspace ( Open ) of (P Open).
(2) However, this mapping is imperfect: the poset is not a lattice, and it is also not a sub-poset of Open — even if is topen. If Open were a topology and closed under intersections then we would have a lattice — but it is precisely the point of difference between semitopologies vs. topologies that open sets need not be closed under intersections.
(3) Being transitive does not correspond to meet-irreducibility; there is an implication in one direction, but certainly not in the other.
So, Lemma 3.7.10 says that (strong) transitivity has a flavour of meet-irreducibility, but in a way that also illustrates — as did Proposition 5.6.6(2) — how semitopologies are different, because they are not closed under intersections, and have their own behaviour.
3.7.3. Topens in topologies.
We conclude by briefly looking at what ‘being topen’ means if our semitopology is actually a topology. We recall a standard definition from topology:
Suppose (P Open) is a semitopology. Call P hyperconnected when all nonempty open subsets of intersect.20 In symbols:
Suppose (P Open) is a semitopology. Then if P is transitive then it is hyperconnected.
Suppose . Then and by transitivity as required.
What is arguably particularly interesting about Lemma 3.7.13 is that its reverse implication does not hold, and in quite a strong sense:
Suppose (P Open) is a semitopology and P. Then:
(1) can be hyperconnected but not transitive, even if (P Open) is a topology (not just a semitopology).
(2) can be hyperconnected but not transitive, even if is an open set.
It suffices to provide counterexamples:
(1) Consider the semitopology illustrated in the lower-left diagram in Figure 3 (which is a topology), and set 0 4. This has no nonempty open subsets so it is trivially hyperconnected. However, is not transitive because 0 13 4 yet 0 13 4.
(2) Consider the semitopology illustrated in the top-right diagram in Figure 3, and set 0 1. This has two nonempty open subsets, 0 and 0 1, so it is hyperconnected. However, is not transitive, because 01 2 yet 01 2.
We know from Lemma 3.7.6(2) that ‘transitive’ does not imply ‘strongly transitive’ for an arbitrary subset P, even in a topology. When read together with Lemmas 3.7.13 and 3.7.14, this invites the question of what happens when
— (P Open) is a topology, and also
— is an open set.
In this natural special case, strong transitivity, transitivity, and being hyperconnected, all become equivalent:
We assumed is open, so the equivalence above can also be thought of as
strongly transitive transitive all nonempty open subsets intersect. We prove a chain of implications:
— If is a strong topen then it is a topen by Lemma 3.7.6(1).
— If is a topen then we use Lemma 3.7.13.
— Suppose is hyperconnected, so every pair of nonempty open subsets of intersect; and suppose Open and . Then also () (). Now and are open: because is open; and P is a topology (not just a semitopology), so intersections of open sets are open. By transitivity of we have . Since and were arbitrary, is strongly transitive.
4. INTERIORS, COMMUNITIES & REGULAR POINTS
4.1. Community of a (regular) point
Definition 4.1.1 is standard:
Suppose (P Open) is a semitopology and P. Define interior() the (open) interior of by
Suppose (P Open) is a semitopology and P. Then interior() from Definition 4.1.1 is the greatest open subset of .
Suppose (P Open) is a semitopology and P. Then if then interior() interior().
Routine using Lemma 4.1.2.
Suppose (P Open) is a semitopology and P. Then:
(1) Define K() the community of by
(2) Extend K to subsets P by taking a sets union:
(3) Call a regular point when its community is a topen neighbourhood of . In symbols: is regular when K()Topen
(4) Call a weakly regular point when its community is an open (but not necessarily topen) neighbourhood of . In symbols: is weakly regular when K()Open
(5) Call a quasiregular point when its community is nonempty. In symbols: is quasiregular when K()Open
(6) If is not regular then we may call it an irregular point, or just say that it is not regular.
(7) If P and every is regular/weakly regular/quasiregular/irregular then we may call a regular/weakly regular/quasiregular/irregular set respectively (see also Definition 6.1.1(2)).
Suppose (P Open) is a semitopology and P. Then:
(1) If is regular, then is weakly regular.
(2) If is weakly regular, then is quasiregular.
(1) In Figure 4 (left-hand diagram), 0, 1, and 2 are three intertwined points and the entire space 0 1 2 consists of a single topen set. It follows that 0, 1, and 2 are all regular and their community is 0 1 2.
(2) In Figure 3 (top-left diagram), 0 and 2 are regular and 1 is weakly regular but not regular (1K0 1 2 but 0 1 2 is not topen).
(3) In Figure 3 (lower-right diagram), 0, 1, and 2 are regular and is quasiregular (K(1).
(4) In Figure 3 (top-right diagram), 0 and 2 are regular and 1 is neither regular, weakly regular, nor quasiregular (K).
(5) In a semitopology of values (Val pow(Val)) (Definition 2.1.3) every value Val is regular, weakly regular, and unconflicted.
(6) In with its usual topology (which is also a semitopology), every point is unconflicted because the topology is Hausdorff and by Equation 1 in Remark 3.6.10 this means precisely that so is intertwined just with itself. Furthermore is not (quasi/weakly)regular, because K( interior(.
Suppose (P Open) is a semitopology and P. Then:
(1) might not be quasiregular (i.e. K(); thus by Lemma 4.1.6 it is also not weakly regular and not regular.
(2) might be quasiregular but not weakly regular (i.e. K() but K()); and
(3) might be weakly regular but not regular (i.e. K() Topen).
We consider each part in turn:
(1) Point 0 in Example 4.1.7(6) is not quasiregular.
(2) Point 1 in Example 4.1.7(2) (illustrated in Figure 3, top-left diagram) is weakly regular (K 0 1 2) but not regular (K(1) is open but not topen).
(3) Point in Example 4.1.7(3) (illustrated in Figure 3, lower-right diagram) is quasiregular (K( 1 is nonempty but does not contain ).
Suppose (P Open) is a semitopology. Then:
(1) If all nonempty open sets intersect then (P Open) is regular (meaning that every P is regular).
(2) The reverse implication need not hold: it is possible for (P Open) to be regular but not all open sets intersect (cf. Corollary 4.3.3).
We consider each part in turn:
(1) By Lemma 3.6.6(2) PTopen (since it is transitive and open). By Lemma 3.6.6(1) P for every P, thus K( interior( P. Thus K()Topen for every P, so P is regular.
(2) It suffices to provide a counterexample. We take any discrete semitopology with at least two elements; e.g. (0 1 pow(0 1)). Then 01, but by Corollary 4.2.7 0 and 1 are both regular.
When we started looking at semitopologies we gave some examples in Example 2.1.4. These may seem quite elementary now, but we run through them commenting on which spaces are regular, weakly regular, or quasiregular:
— Any discrete semitopology is regular; topen neighbourhoods are just the singleton sets.
— The initial semitopology is regular: it has no topen neighbourhoods, but also no points. The final semitopology is regular: it has one topen neighbourhood, containing one point. The trivial topology is regular; it has a single topen neighbourhood that is P itself.
— The supermajority semitopology is regular. It has one topen neighbourhood containing all of P.
— The many semitopology is regular if P is finite (because it is equal to the trivial semitopology), and not even quasiregular if P is infinite, because (for infinite P) for every point. For example, if P and is even and is odd, then evens 2 and odds 2 are disjoint open neighbourhoods of and respectively.
— The all-but-one semitopology is regular for P having cardinality of 3 or more, since all points are intertwined so there is a single topen neighbourhood which is the whole space. If P has cardinality 2 or 1 then we have a discrete semitopology (on two points or one point) and these too are regular, with two or one topen neighbourhoods.
— The more-than-one semitopology is not even quasiregular for P having cardinality of 4 or more. If P has cardinality 3 then we get the left-hand topology in Figure 4, which is regular. If P has cardinality 2 then we get the trivial semitopology, which is regular.
— Take P (the set of real numbers) and let open sets be generated by intervals of the form [0) or ( 0] for any strictly positive real number 0. The reader can check that this semitopology is regular.
— Any quorum system induces an intertwined semitopology, as outlined in Example 2.1.4(7). By Lemmas 4.1.9(1) and 3.6.6 this is a regular semitopology, and every nonempty open set is a topen neighbourhood.
We pause to recap:
(1) K() always exists and always is open. It may or may not be empty, may or may not be topen, and may or may not contain .
(2) When K()Topen we call ‘regular’, which suggests that non-regular behaviour — K() and/or K() Topen, or even K( — is ‘bad behaviour’, and being regular ‘good behaviour’. But what is this good behaviour that regularity implies? Theorem 3.2.2 (continuous value assignments are constant on topens) tells us that a regular is surrounded by a topen neighbourhood of points K( interior() that must agree with it under continuous value assignments. Using our terminology community and regular, we can say that the community of a regular shares its values.
(3) We can sum up the above intuitively as follows:
(a) We care about transitivity because it implies agreement.
(b) We care about being open, because it implies actionability.
(c) Thus, a regular point is interesting because it is a participant in a maximal topen neighbourhood and therefore can i) come to agreement and ii) take action on that agreement.
(4) The question then arises how the community of can be (semi)topologically characterised. We will explore, notably in Theorem 4.2.6, Proposition 5.4.10, and Theorem 5.6.2; see also Remark 5.6.1.
4.2. Further exploration of (quasi-/weak) regularity and topen sets
Recall three common separation axioms from topology:
(1) : if then there exists some Open such that ()xor(), where xor denotes exclusive or.
(2) : if then there exist Open such that for 1 2.
(3) , or the Hausdorff condition: if then there exist Open such that for 1 2, and . Cf. the discussion in Remark 3.6.10.
Even the weakest of the well-behavedness property for semitopologies that we consider in Definition 4.1.4 — quasiregularity — is in some sense strongly opposed to the space being Hausdorff/ (though not to being ), as Lemma 4.2.2 makes formal.
We consider each part in turn:
(1) By the Hausdorff property, . By the quasiregularity property, K() . It follows that K(. But by construction in Definition 4.1.4(1), K() is an open interior. Thus Open. The result follows.
(2) It suffices to provide an example. We use the left-hand semitopology in Figure 4. Thus P 0 1 2 and Open is generated by 0 1, 1 2, and 2 0. All nonempty open sets intersect, so by Lemma 4.1.9(1) P is regular. It is also (Remark 4.2.1).
Lemma 4.2.3 confirms in a different way that regularity (Definition 4.1.4(3)) is non-trivially distinct from weak regularity and quasiregularity:
Suppose (P Open) is a semitopology and P. Then:
(1) K()Open.
(2) K() is not necessarily topen; equivalently K() is not necessarily transitive. (More on this later in Subsection 4.4.)
K() is open by construction in Definition 4.1.4(1), since it is an open interior.
For part 2, it suffices to provide a counterexample. We consider the semitopology from Example 3.3.3(1) (illustrated in Figure 3, top-left diagram). We calculate that K0 1 2 so that K(1) is an open neighbourhood of 1 — but it is not transitive, and thus not topen, since 02.
Further checking reveals that 0 and 2 are two maximal topens within K(1).
So what is K()? We start by characterising K() as the greatest topen neighbourhood of , if this exists:
(1) Since is regular, by definition, K() is topen and is a neighbourhood of . It remains to show that K() is a maximal topen. Suppose is a topen neighbourhood of ; we wish to prove K( interior(). Since is open it would suffice to show that . By Proposition 3.6.9 for every , and it follows immediately that .
(2) Suppose is a maximal topen neighbourhood of . First, note that is open, and by Proposition 3.6.9 , so K(). By assumption K() and both are topen so by Lemma 3.5.2(1) K() is topen, and by maximality K() .
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is regular, or in full: K()Topen.
(2) K() is the greatest topen neighbourhood of .
(3) K() is a maximal topen neighbourhood of .
(4) has a maximal topen neighbourhood.
(5) has some topen neighbourhood.
We prove a cycle of implications:
(1) If K() is a topen neighbourhood of then it is maximal by Lemma 4.2.4(1). Furthermore this maximal topen neighbourhood of is necessarily greatest, since if we have two maximal topen neighbourhoods of then their union is a larger topen neighbourhood of by Lemma 3.5.2(1) (union of intersecting topens is topen).
(2) If is the greatest topen neighbourhood of , then certainly it is a maximal topen neighbourhood of .
(3) If is a maximal topen neighbourhood of , then certainly has a maximal topen neighbourhood.
(4) If has a maximal topen neighbourhood then certainly has a topen neighbourhood.
(5) Suppose has a topen neighbourhood . By Corollary 3.5.3 we may assume without loss of generality that is a maximal topen. We use Lemma 4.2.4(2).
Theorem 4.2.6 has numerous corollaries:
Suppose (P Open) is a semitopology and P and Open. Then is regular.
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is regular.
(2) is weakly regular and K( K() for every K().
We prove two implications, using Theorem 4.2.6:
— Suppose is regular. By Lemma 4.1.6(1) is weakly regular. Now consider K(). By Theorem 4.2.6 K() is topen, so it is a topen neighbourhood of . By Theorem 4.2.6 K() is a greatest topen neighbourhood of . But by Theorem 4.2.6 K() is also a greatest topen neighbourhood of , and K() K() since they both contain . By Lemma 3.5.2(1) and maximality, they are equal.
— Suppose is weakly regular and suppose K( K() for every K(), and consider K(). Then holds, since K( K(). By Proposition 3.6.9 K() is topen, and by weak regularity K(), so by Theorem 4.2.6 is regular as required.
Suppose (P Open) is a semitopology and P. Then if is regular and K() then is regular and has the same community.
Suppose (P Open) is a semitopology. Then the following are equivalent for P:
— is a maximal topen.
— and K() for every .
4.3. Intersection and partition properties of regular spaces
Proposition 4.3.1 is useful for consensus in practice. Suppose we are a regular point and we have reached consensus with some topen neighbourhood . Suppose further that our topen neighbourhood intersects with the maximal topen neighbourhood K() of some other regular point . Then Proposition 4.3.1 tells us that we were inside K() all along. See also Remark 5.3.3.
Suppose (P Open) is a semitopology and P is regular and Topen is topen. Then
Suppose (P Open) is a semitopology and suppose P are regular. Then
(See also Corollary 6.4.6, which considers similar properties for and that are not necessarily regular.)
We prove two implications.
— Suppose there exists K()K(). By Corollary 4.2.10 ( is regular and) K( K( K().
— Suppose K( K(). By assumption K(), so K(). Thus K() K().
Corollary 4.3.3 is a simple characterisation of regular semitopological spaces (it is also a kind of continuation to Lemma 4.1.9(2)):
Suppose (P Open) is a semitopology. Then the following are equivalent:
(1) (P Open) is regular.
(2) P partitions into topen sets: there exists some set of topen sets such that for every and P .
(3) Every P has a cover of topen sets: there exists some set of topen sets such that .
The proof is routine from the machinery that we already have. We prove equivalence of parts 1 and 2:
(1) Suppose (P Open) is regular, meaning by Definition 4.1.4(7&3) that K()Topen for every P. We set K() P. By assumption this covers P in topens, and by Proposition 4.3.2 the cover is a partition.
(2) Suppose is a topen partition of P. By definition for every point there exists such that and so has a topen neighbourhood. By Theorem 4.2.6(5&1) is regular.
We prove equivalence of parts 2 and 3:
(1) Suppose is a topen partition of P, and suppose . Then trivially .
(2) Suppose every P has a cover of topen sets. Then P has a cover of topen sets; write it . By Corollary 3.5.3 we may assume without loss of generality that is a partition, and we are done.
The moral we take from the results and examples above (and those to follow) is that the world we are entering has rather different well-behavedness criteria than those familiar from the study of typical Hausdorff topologies like . Put crudely:
(1) ‘Bad’ spaces are spaces that are not regular. with its usual topology (which is also a semitopology) is an example of a ‘bad’ semitopology; it is not even quasiregular.
(2) ‘Good’ spaces are spaces that are regular. The supermajority and all-but-one semitopologies from Example 2.1.4(5a&5c) are typical examples of ‘good’ semitopologies; both are intertwined spaces (Notation 3.6.5).
(3) Corollary 4.3.3 shows that the ‘good’ spaces are just the (disjoint, possibly infinite) unions of intertwined spaces.
4.4. Examples of communities and (ir)regular points
By Definition 4.1.4 a point is regular when its community is a topen neighbourhood. Then a point is not regular when its community is not a topen neighbourhood of . We saw one example of this in Lemma 4.2.3. In this subsection we take a moment to investigate the possible behaviour in more detail.
(1) We noted in Example 4.4.1(6) and Lemma 4.1.8(1) that for the real numbers with its usual topology, every is not regular. Then and K( for every .
(2) We continue the semitopology from Example 3.3.3(1) (illustrated in Figure 3, top-left diagram), as used in Lemma 4.2.3:
—
— Open is generated by 0 and 2. Then:
— 00 1 and K interior(00.
— 21 2 and K interior(22.
— 10 1 2 and K0 1 2.
(3) We take, as illustrated in Figure 5 (left-hand diagram):
—
— Open is generated by 1 2, 0 1 3, 0 2 4, 3, and 4. Then:
— 0 1 2 and K( interior(1 2 for 0 1 2.
— K() for 3 4.
(4) We take, as illustrated in Figure 5 (right-hand diagram):
—
— Open is generated by 1, 2, 3, 4, 0 1 2 3, and 0 1 2 4. Then:
— 00 1 2 and K1 2.
— K(0) is not transitive and consists of two distinct topens 1 and 2.
— 0 K(0).
See Remark 5.6.3 for further discussion of this example.
(5) The reader can also look ahead to Example 5.6.10. In Example 5.6.10(1), every point is regular and K(. In Example 5.6.10(2), no point is regular and K(.
Suppose (P Open) is a semitopology and P. Then precisely one of the following possibilities must hold, and each one is possible:
(1) is regular: K() and K() is topen (nonempty, open, and transitive).
(2) K() is topen, but K().
(3)
(4) K() is open but not transitive. (Both K() and K() are possible.)
(1) To see that can be regular, consider P 0 with the discrete topology. Then K(0.
(2) To see that it is possible for K() to be topen but is not in it, consider Example 4.4.1(3). There, P 0 1 2 3 4 and 00 1 2 and K1 2. Then K(0) is topen, but 0 K(0). (Another, slightly more compact but more distant, example is in the lower-right semitopology in Figure 3.)
(3) To see that K( is possible, consider Example 4.4.1(1) (the real numbers with its usual topology). Then by Remark 3.6.10 and so K( interior(. (See also Example 5.6.10(2) for a more elaborate example.)
(4) To see that it is possible for K() to be an open neighbourhood of but not transitive, see Example 4.4.1(2). There, P 0 1 2 and 110 1 2 K(1), but 0 1 2 is not transitive (it contains two disjoint topens: 0 and 2). To see that it is possible for K() to be open and nonempty yet not contain and not be transitive, see Example 4.4.1(4) for , and see also Remark 5.6.3 for a discussion of the connection with minimal closed neighbourhoods.
The possibilities above are clearly mutually exclusive and exhaustive.
5. CLOSED SETS
5.1. Closed sets
In Subsection 5.1 we check that some familiar properties of closures carry over from topologies to semitopologies. There are no technical surprises, but this is in itself a mathematical result that needs to be checked. From Subsection 5.3 and the following Subsections we will study the close relation between closures and sets of intertwined points.
Suppose (P Open) is a semitopology and suppose P and P. Then:
(1) Define P the closure of to be the set of points such that every open neighbourhood of intersects . In symbols using Notation 3.1.1:
(2) As is standard, we may write for . Unpacking definitions for reference:
Suppose (P Open) is a semitopology and suppose P. Then taking the closure of a set is:
(1) Monotone: If then .
(2) Increasing: .
(3) Idempotent: .
By routine calculations from Definition 5.1.2.
Suppose (P Open) is a semitopology and P and Open. Then
if and only if
Suppose (P Open) is a semitopology and suppose P.
(1) Call a closed set when .
(2) Call a clopen set when is closed and open.
(3) Write Closed for the set of closed sets (as we wrote Open for the open sets; the ambient semitopology will always be clear or understood).
Suppose (P Open) is a semitopology and suppose P. Then is closed and contains . In symbols:
(1) Take P 0 1 and Open 00 1. Then the reader can verify that:
— 0 is open.
— The closure of 1 is 1 and 1 is closed.
— The closure of 0 is 0 1.
— and 0 1 are the only clopen sets.
(2) Now take P 0 1 and Open 010 1.22 Then the reader can verify that:
— Every set is clopen.
— The closure of every set is itself.
If Closed then P.
Suppose (P Open) is a semitopology and P and pow(P). Then:
(1) and P are closed.
(2) If every is closed, then is closed. Or succinctly in symbols:
(3) is equal to the intersection of all the closed sets that contain it. In symbols:
The usual characterisation of continuity in terms of inverse images of closed sets being closed, remains valid:
5.2. Duality between closure and interior
The usual dualities between closures and interiors remain valid in semitopologies. There are no surprises but this still needs to be checked, so we spell out the details:
Suppose (P Open) is a semitopology and Open and Closed. Then:
(1) interior(). The inclusion may be strict.
(2) interior(). The inclusion may be strict.
(3) interior(P P.
(4) P Pinterior().
The reasoning is just as for topologies, but we spell out the details:
(1) By Lemma 5.1.3(2) . By Corollary 4.1.3 interior() interior(). By Lemma 4.1.2 interior(), so we are done. For an example of the strict inclusion, consider with the usual topology (which is also a semitopology) and take 1) (1 2). Then interior( 2).
(2) By Lemma 4.1.2 interior() . By Lemma 5.1.3(1) interior(). By Definition 5.1.5(1) (since we assumed Closed) , so we are done. For an example of the strict inclusion, consider with the usual topology and take 0. Then interior().
(3) Consider some P. By Definition 4.1.1 interior(P) when there exists some Open such that . By definition in Definition 5.1.2(1) this happens precisely when .
(4) By Definition 5.1.2(1), P precisely when there exists some Open such that P. By facts of sets this means precisely that . By Definition 4.1.1 this means precisely that interior().
Suppose (P Open) is a semitopology and Open and Closed. Then:
(1) interior().
(2) interior( interior(interior()).
5.3. Transitivity and closure
We explore how the topological closure operation interacts with taking transitive sets.
Suppose (P Open) is a semitopology and P is transitive and Open. Then
Suppose (P Open) is a semitopology and Topen and Open. Then the following are equivalent:
In retrospect we can see the imprint of topens (Definition 3.2.1) in previous work, if we look at things in a certain way. Many consensus algorithms have the property that once consensus is established in a quorum , it propagates to .
This is apparent (for example) in the Grade-Cast algorithm [FM88], in which participants assign a confidence grade of 0, 1 or 2 to their output and must ensure that if any participant outputs with grade 2 then all must output with grade at least 1. In this algorithm, if a participant finds that all its quorums intersect some set that unanimously supports value , then the participant assigns grade at least 1 to . From our point of view here, this is just taking a closure in the style we discussed in Remark 5.1.1. If unanimously supports and participants communicate enough, then eventually every member of assigns grade at least 1 to . Thus, Proposition 5.3.2 suggests that, to convince a topen to agree on a value, we can first convince an open neighbourhood that intersects the topen, and then use Grade-Cast to convince the closure of that open set and thus in particular the topen which we know must be contained in that closure.
We conclude with an easy observation which will be useful later. Recall from Notation 3.6.5 the notion of an intertwined space being one such that all nonempty open sets intersect. Then we have:
Suppose (P Open) is a semitopology and suppose Topen. Then the following are equivalent:
(1) P is intertwined.
(2)
5.4. Closed neighbourhoods and intertwined points
5.4.1. Definition and basic properties
Suppose (P Open) is a semitopology. We generalise Definition 2.3.1 as follows:
(1) Call P a neighbourhood when it contains an open set (i.e. when interior() ), and call a neighbourhood of when P and contains an open neighbourhood of (i.e. when interior()). In particular:
(2) P is a closed neighbourhood of P when is closed and interior().
(3) P is a closed neighbourhood when is closed and interior() .
(1) If is a closed neighbourhood of in the sense of Definition 5.4.1(2) then is a closed neighbourhood in the sense of Definition 5.4.1(3), just because if interior() then interior() .
(2) is not enough for to be a closed neighbourhood of ; we require the stronger condition interior(). For instance take P 0 1 and Open 1 P (the Sierpiński space; see Figure 8), and consider and 0. Then but interior(, so that is not a closed neighbourhood of .
Recall from Definition 3.6.1 the notions of and . Proposition 5.4.3 packages up our material for convenient use in later results.
Suppose (P Open) is a semitopology and P. Then:
(1) We can characterise when is intertwined with as follows:
(2) As a corollary,
(3) Equivalently:
Thus in particular, if is a closed neighbourhood of then .
(4) is closed and P is open.
(1) We just rearrange Definition 3.6.1. So
rearranges to
We now observe from Definition 5.1.2 that this is precisely
(2) We just rephrase part 1 of this result.
(3) Using part 2 of this result it would suffice to prove
We will do this by proving that for each -component on the left there is a on the right with ; and for each -component on the right there is an on the left with :
— Consider some Open with . We set , so that trivially . By Lemma 5.2.1(1) interior(), so interior().
— Consider some Closed such that interior(). We set interior(). Then , and by Lemma 5.2.1(2) .
(4) Part 3 of this result exhibits as an intersection of closed sets, and by Corollary 5.1.11(2) this is closed. By Lemma 5.1.9(1) its complement P is open.
Suppose (P Open) is a semitopology and P.
(1) Write nbhd(Open Open and call this the open neighbourhood system of P.
(2) Write nbhd(Closed Closed and call this the closed neighbourhood system of P.
If (P Open) is a topology, then nbhd() is a filter (a nonempty up-closed down-directed set) and this is often called the neighbourhood filter of .
We are working with semitopologies, so Open is not necessarily closed under intersections, and nbhd() is not necessarily a filter. Figure 6 illustrates examples of this: e.g. in the left-hand example 0 10 2nbhd(0) but 0 nbhd(0), since 0 is not an open set.
We can relate Proposition 5.4.3 to a concept from topology. Following standard terminology ([Bou98, Definition 2, page 69] or [Eng89, page 52]), a cluster point P of Open is one such that every open neighbourhood of intersects every . Then Proposition 5.4.3(2) identifies as the set of cluster points of nbhd() Open.
5.4.2. Application to characterise (quasi/weak) regularity
Recall that Theorem 4.2.6 characterised regularity in multiple ways, including as the existence of a greatest topen neighbourhood. Proposition 5.4.10 below does something similar, for quasiregularity and weak regularity and the existence of closed neighbourhoods (Definition 5.4.1), and Theorem 5.6.2 is a result in the same style, for regularity.
Here, for the reader’s convenience, is a summary of the relevant results:
(1) Proposition 5.4.9: is quasiregular when is a closed neighbourhood.
(2) Proposition 5.4.10: is weakly regular when is a closed neighbourhood of .
(3) Theorem 5.6.2: is regular when is a closed neighbourhood of and is a minimal closed neighbourhood.
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is weakly regular, or in full: K() (Definition 4.1.4(4)).
(2) is a closed neighbourhood of (Definition 5.4.1(2)).
(3) The poset of closed neighbourhoods of ordered by subset inclusion, has a least element.
(4) is least in the poset of closed neighbourhoods of ordered by subset inclusion.
We prove a cycle of implications:
— Suppose interior(). By Proposition 5.4.3(4) is closed, so this makes it a closed neighbourhood of as per Definition 5.4.1.
— Suppose is a closed neighbourhood of . By Proposition 5.4.3(3) is the intersection of all closed neighbourhoods of , and it follows that this poset has as a least element.
— Assume the poset of closed neighbourhoods of has a least element; write it . So Closed is a closed neighbourhood of and thus by Proposition 5.4.3(3) .
— If is least in the poset of closed neighbourhoods of ordered by subset inclusion, then in particular is a closed neighbourhood of and it follows from Definition 5.4.1 that interior().
Recall from Definition 4.1.4 that K( interior():
Suppose (P Open) is a semitopology and P. Then K().
Suppose (P Open) is a semitopology and P. Then:
(1) If weakly regular then K(). In symbols:
(2) As an immediate corollary, if is regular then K().
We can combine Theorem 5.4.12 with Corollary 4.2.8:
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is regular.
(2) is weakly regular and for every K().
Note a subtlety to Corollary 5.4.13: it is possible for to be regular, yet it is not the case that for every (rather than for every K()). For an example consider the top-left semitopology in Figure 3, taking and ; then 10 but 00 1 and 10 1 2.
To understand why this happens the interested reader can look ahead to Subsection 6.1: in the terminology of that Subsection, needs to be unconflicted in Corollaries 4.2.8 and 5.4.13.
5.5. Intersections of communities with open sets
Proposition 5.5.3 and Lemma 5.5.2 tell us some interesting and useful things:
— Suppose a weakly regular wants to convince its community K() of some belief. How might it proceed? By Proposition 5.5.3 it would suffice to seed one of the open neighbourhoods in its community with that belief, and then compute a topological closure of that open set; in Remark 5.5.5 we discuss why topological closures are particularly interesting.
— Suppose is regular, so it is a member of a transitive open neighbourhood, and wants to convince its community K() of some belief. By Lemma 5.5.2 need only convince some open set that intersects its community (this open set need not even contain ), and then compute a topological closure as in the previous point.
Suppose (P Open) is a semitopology and P is regular (so K()Topen). Suppose Open. Then
In word:
If an open set intersects the community of a regular point, then that community is included
in the closure of the open set.
Proposition 5.5.3 generalises Theorem 5.4.12, and is proved using it. We regain Theorem 5.4.12 as the special case where K():
Suppose (P Open) is a semitopology and P is weakly regular (so K()Open). Suppose Open. Then:
(1) K() implies .
(2) As a corollary, implies .
Note in Proposition 5.5.3 that it really matters that — that is, that is an open neighbourhood of and not just an open set in .
To see why, consider the example in Lemma 4.2.3 (illustrated in Figure 3, top-left diagram): so P 0 1 2 and Open P02. Note that:
—
— If we set 00 1 2 then this is open, but 0 10 1 2.
— If we set 0 1 20 1 2 then 0 1 2.
Topological closures will matter because we will develop a theory of computable semitopologies which will (amongst other things) deliver a distributed algorithm to compute closures.
Thus, we can say that from the point of view of a regular participant , Proposition 5.5.3 and Lemma 5.5.2 reduce the problem of
wishes to progress with value
to the simpler problem of
wishes to find an open set that intersects with the community of , and work with this open set to agree on (which open set does not matter; can try several until one works).
Once this is done, the distributed algorithm will safely propagate the belief across the network.
Note that no forking is possible above (this is when a distributed system that was in agreement, partitions into subsets that are committed to incompatible values); all the action is in finding and convincing the K(), and then the rest is automatic.
5.6. Regularity, maximal topens, & minimal closed neighbourhoods
We are now ready to complete this arc by stating and proving Theorem 5.6.2. This establishes a pleasing — and not-at-all-obvious — duality between ‘has a maximal topen neighbourhood’ and ‘has a minimal closed neighbourhood’.
Equivalence of parts 1 and 2 is just Theorem 4.2.6(2).
For equivalence of parts 2 and 3 we prove two implications:
— Suppose is regular. By Lemma 4.1.6(1) is weakly regular. Now consider a closed neighbourhood . Note that has a nonempty interior by Definition 5.4.1(3), so pick any such that
It follows that interior( K(), and is regular, so by Corollary 5.4.13 , and then by Proposition 5.4.10(2&4) (since interior()) . Putting this all together we have
so that as required.
— Suppose is weakly regular and suppose is minimal in the poset of closed neighbourhoods ordered by subset inclusion. Consider some K(). By Proposition 5.4.3(3) , and by minimality it follows that . Thus also K( K(). Now K() was arbitrary, so by Corollary 4.2.8 is regular as required.
Recall Example 4.4.1(4), as illustrated in Figure 5 (right-hand diagram). This has a point 0 whose community K1 2 is not a single topen (it contains two topens: 1 and 2).
A corollary of Theorem 5.6.2 is that 00 1 2 cannot be a minimal closed neighbourhood, because if it were then 0 would be regular and K(0) would be a maximal topen neighbourhood of 0.
We check, and see that indeed, 0 contains two distinct minimal closed neighbourhoods: 0 1 and 0 2.
Theorem 5.6.2(3) looks like Proposition 5.4.10(4), but
— Proposition 5.4.10(4) regards the poset of closed neighbourhoods of (closed sets with a nonempty open interior that contains ),
— Theorem 5.6.2(3) regards the poset of all closed neighbourhoods (closed sets with a nonempty open interior, not necessarily including ).
So the condition used in Theorem 5.6.2(3) is strictly stronger than the condition used in Proposition 5.4.10(4). Correspondingly, the regularity condition in Theorem 5.6.2(1) can be written as K()Topen, and (as noted in Lemma 4.1.6 and Example 4.1.7(2)) this is strictly stronger than the condition K() used in Proposition 5.4.10(1).
Corollary 5.6.5 makes Remark 3.6.10 (intertwined is the opposite of Hausdorff) a little more precise:
Suppose (P Open) is a Hausdorff semitopology (so every two points have a pair of disjoint neighbourhoods). Then if P is regular, then is clopen.
Suppose (P Open) is a semitopology. Then:
(1) Every maximal topen is equal to the interior of a minimal closed neighbourhood.
(2) The converse implication holds if (P Open) is a topology, but need not hold in the more general case that (P Open) is a semitopology: there may exist a minimal closed neighbourhood whose interior is not topen.
(1) Suppose is a maximal topen. By Definition 3.2.1(2) is nonempty, so choose . By Proposition 5.4.3(4) is closed, and using Theorem 4.2.6
Thus is weakly regular and by Proposition 5.4.10(1&4) is a least closed neighbourhood of .
(2) It suffices to provide a counterexample. This is Example 5.6.8 below. However, we also provide here a breaking ‘proof’, which throws light on precisely what Example 5.6.8 is breaking, and illustrates what the difference between semitopology and topology can mean in practical proof. Suppose interior() is the nonempty open interior of some minimal closed neighbourhood : we will try (and fail) to show that this is transitive. By Proposition 3.6.9 it suffices to prove that for every . So suppose and and . By Definition 5.1.2(1) , so that is a strictly smaller closed set. Also, is nonempty because it contains .
If (P Open) is a topology then we are done, because interior() would necessarily be open, contradicting our assumption that is a minimal closed neighbourhood. However, if (P Open) is a semitopology then this does not necessarily follow: need not be open, and we cannot proceed.
Consider the semitopology illustrated in Figure 7. So:
—
— Open is generated by where:
Then for every P we have:
(1) is intertwined only with itself.
(2)
The semitopology illustrated in Figure 7, and specified in Lemma 5.6.7, contains sets that are minimal amongst closed sets with a nonempty interior, yet that interior is not topen:
— , , , and are clopen, because is the complement of and is the complement of , so they are their own interior.
— is a minimal closed neighbourhood (which is also open, being itself), because
— 3 0 is closed because it is the complement of , and it is its own interior, and
— its two nonempty subsets 3 and 0 are closed (being the complement of and respectively) but they have empty open interior because 3 and 0 are not open.
— is not transitive because 3 and 0 are not intertwined: 3 and 0 and .
— Similarly , , and are minimal closed neighbourhoods, which are also open, and they are not transitive.
We further note that:
(1) 00, because its complement is equal to (Definition 5.1.2; Lemma 5.1.9). Similarly for every other point in P.
(2) 00, as noted in Lemma 5.6.7. Similarly for every other point in P.
(3) K interior(0 as noted in Lemma 5.6.7, so that 0 is not regular (Definition 4.1.4(1)), and 0 is not even weakly regular or quasiregular. Similarly for every other point in P.
(4) 0 has two minimal closed neighbourhoods: and . Similarly for every other point in P.
This illustrates that is possible, where is a minimal closed neighbourhood of .
The results and discussions above tell us something interesting above and beyond the specific mathematical facts which they express.
They demonstrate that points being intertwined (the from Definition 3.6.1) is a distinct semitopological notion. A reader familiar with topology might be tempted to identify maximal topens with interiors of minimal closed neighbourhood (so that in view of Proposition 3.6.9, being intertwined would be topologically characterised just as two points being in the interior of the same minimal closed neighbourhood).
This works in topologies, but we see from Example 5.6.8 that in semitopologies being intertwined has its own distinct identity.
We conclude with one more example, showing how an (apparently?) slight change to a semitopology can make a big difference to its intertwinedness:
(1) with open sets generated by any covering collection of pairwise non-parallel rational lines
— meaning a set of solutions to a linear equation for , , and integers — is a semitopology.
This consists of a single (maximal) topen: lines are pairwise non-parallel, so any two lines intersect and (looking to Proposition 3.6.9) all points are intertwined. There is only one closed set with a nonempty open interior, which is the whole space.
(2) with open sets generated by all (possibly parallel) rational lines, is a semitopology. It has no topen sets and (looking to Proposition 3.6.9) no two distinct points are intertwined. For any line , its complement is a closed set, given by the union of all the lines parallel to . Thus every closed set is also an open set, and vice versa, and every line is an example of a minimal closed neighbourhood (itself), whose interior is not a topen.
5.7. More on minimal closed neighbourhoods
We make good use of closed neighbourhoods, and in particular minimal closed neighbourhoods, in Subsection 5.6 and elsewhere. We take a moment to give a pleasing alternative characterisation of this useful concept.
5.7.1. Regular open/closed sets
The terminology ‘regular open/closed set’ is from the topological literature. It is not directly related to terminology ‘regular point’ from Definition 4.1.4(3), which comes from semitopologies. However, it turns out that a mathematical connection does exist between these two notions. We outline some theory of regular open/closed sets, and then demonstrate the connections to what we have seen in our semitopological world.
Suppose (P Open) is a semitopology. Recall some standard terminology from topology [Wil70, Exercise 3D, page 29]:
(1) We call an open set Open a regular open set when interior().
(2) We call a closed set Closed a regular closed set when interior().
(3) Write and for the sets of regular open and regular closed sets respectively.
Suppose (P Open) is a semitopology and Open and Closed. Then:
(1) interior() is a regular open set.
(2) is a regular closed set.
Suppose (P Open) is a semitopology and P. Then K().
Suppose (P Open) is a semitopology and Open. Then interior() is a regular open set.
The regular open and the regular closed sets are the same thing, up to an easy and natural bijection:
Suppose (P Open) is a semitopology. Then
— the topological closure map - and
— the topological interior map interior(-)
define a bijection of posets between and ordered by subset inclusion.
Suppose (P Open) is a semitopology and Open and Closed. Then:
(1) is a regular open set if and only if P is a regular closed set if and only if is a regular closed set.
(2) is a regular closed set if and only if P is a regular open set if and only if interior() is a regular open set.
5.7.2. Intersections of regular open sets.
An easy observation about open sets will be useful:
Suppose (P Open) is a semitopology and Open. Then the following are equivalent:
(1) .
(2) interior().
(3) interior() interior().
First we prove the equivalence of parts 1 and 2:
(1) Suppose . By Lemma 5.2.1(1) interior().
(2) Suppose there is some interior(). Then is an open neighbourhood of and , so by Definition 5.1.2(1) as required.24
Equivalence of parts 1 and 3 then follows easily by two applications of the equivalence of parts 1 and 2.
Lemma 5.7.8 is true in topologies as well, but it is not prominent in the literature. Two standard reference works [Eng89; Wil70] do not seem to mention it. It appears as equation 10 in Theorem 1.37 of [Kop89], and as a lemma in -base25 (we thank the mathematics StackExchange community for the pointers). We mention this to note an interesting contrast: this result is as true in topologies as it is in semitopologies, but somehow, it matters more in the latter than the former.
Suppose (P Open) is a semitopology and P. Then the following conditions are equivalent:
(1) and have a nonintersecting pair of open neighbourhoods.
(2) and have a nonintersecting pair of regular open neighbourhoods.
In Definition 3.6.1(1) we defined in terms of open neighbourhoods of and as follows:
In the light of Corollary 5.7.10, we could just as well have defined it just in terms of regular open neighbourhoods:
Mathematically, for what we have needed so far, this latter characterisation is not needed. However, it is easy to think of scenarios in which it might be useful. In particular, computationally it could make sense to restrict to the regular open sets, simply because there are fewer of them.
5.7.3. Minimal nonempty regular closed sets are precisely the minimal closed neighbourhoods
We consider each part in turn:
(1) Suppose is a minimal closed neighbourhood. Write interior() and interior(). Because is a closed neighbourhood, by Definition 5.4.1 . By Lemma 5.1.6 Closed. Using Corollary 5.2.2 interior( interior(interior() interior(, so that is a closed neighbourhood, and by minimality . But then interior() so is regular, as required.
(2) Suppose is a nonempty regular closed set, so that interior(). It follows that interior() and this means precisely that is a closed neighbourhood.
In Theorem 5.6.2 we characterised the point being regular in terms of minimal closed neighbourhoods. We can now characterise the minimal closed neighbourhoods in terms of something topologically familiar:
Suppose (P Open) is a semitopology and Closed. Then the following are equivalent:
(1) is a minimal nonempty regular closed set.
(2) is a minimal closed neighbourhood.
We prove two implications:
— Suppose is a minimal closed neighbourhood. By Lemma 5.7.12(1) is a nonempty regular closed set. Furthermore by Lemma 5.7.12(2) if is any other nonempty regular closed set contained in , then it is a closed neighbourhood, and by minimality it is equal to . Thus, is minimal.
— Suppose is a minimal nonempty regular closed set.
By Lemma 5.7.12(2) is a closed neighbourhood. Furthermore by Lemma 5.7.12(1) if is any other closed neighbourhood then it is a nonempty regular closed set, and by minimality it is equal to .
5.8. How are and related?
Recall the definitions of and :
— The set is the closure of . By Definition 5.1.2 this is the set of such that every open neighbourhood intersects with . By Definition 5.1.5 is closed.
— The set is the set of points intertwined with . By Definition 3.6.1(2) this is the set of such that every open neighbourhood intersects with every open neighbourhood . By Proposition 5.4.3(4) is closed.
So we see that and give us two canonical ways of generating a closed set from a point P. This invites a question:
How are and related?
Lemma 5.8.2 rephrases Remark 5.8.1 more precisely by looking at it through sets complements.
Suppose (P Open) is a semitopology and P. Then:
(1) POpen Open.
(2) POpen Open Open.
(3) POpen Open.
In words, we can say: P is the union of the open sets such that avoids them, and P is the union of the open sets such that avoids their closures.
(1) We reason as follows:
(2) Example 5.8.4 below shows that is possible for regular.
(3) Write interior(). By standard topological reasoning, is the complement of the union of the open sets that do not contain , and interior() is the greatest open set such that Open . We assumed that is nonempty, so , thus . Then by part 1 of this result , and by Proposition 5.5.3(2) . Using more standard topological reasoning (since ) , and the result follows.
Thus we see that 000 1, and 0 is regular since 0interior(00 1Topen.
We have one loose end left. We know from Theorem 5.6.2(3) that is a minimal closed neighbourhood (closed set with nonempty open interior) when is regular. We also know from Proposition 5.8.3 that is possible, even if is regular.
So a closed neighbourhood in between and is impossible by minimality, but can there be any closed sets (not necessarily having a nonempty open interior) in between and ?
Somewhat counterintuitively perhaps, this is possible:
Suppose (P Open) is a semitopology and P. Then it is possible for there to exist a closed set P with , even if is regular.
It suffices to provide an example. Consider with the semitopology whose open sets are generated by
— final segments for (cf. Example 3.7.9(2)), and
— 0 1 2 3 4 5 6 7 8 9.
The reader can check that 00 and 00 1 2 3 4 5 6 7 8 9. However, there are also eight closed sets 0 1, 0 1 2, ..., 0 1 2 3 8 in between 0 and 0.
We will study further but to make more progress we need the notion of a(n un)conflicted point. This is an important idea in its own right:
6. (UN)CONFLICTED POINTS: TRANSITIVITY OF
6.1. The basic definition
In Lemma 3.6.4 we asked whether the ‘is intertwined with’ relation from Definition 3.6.1(1) is transitive — answer: not necessarily.
Transitivity of is a natural condition. We now have enough machinery to study it in more detail, and this will help us gain a deeper understanding of the properties of not-necessarily-regular points.
We consider some examples:
(1) In Figure 3 top-left diagram, 0 and 2 are unconflicted and intertwined with themselves, and 1 is conflicted (being intertwined with 0, 1, and 2). If the reader wants to know what a conflicted point looks like: it looks like 1.
(2) In Figure 3 top-right diagram, 0 and 2 are unconflicted and intertwined with themselves, and 1 is conflicted (being intertwined with 0, 1, and 2).
(3) In Figure 3 lower-left diagram, 0 and 1 are unconflicted and intertwined with themselves, and 3 and 4 are unconflicted and intertwined with themselves, and 2 is conflicted (being intertwined with 0, 1, 2, 3, and 4).
(4) In Figure 3 lower-right diagram, all points are unconflicted, and 0 and 2 are intertwined just with themselves, and 1 and are intertwined with one another.
(5) In Figure 7, all points are unconflicted and intertwined only with themselves.
So is conflicted when it witnesses a counterexample to being transitive. We start with an easy lemma (we will use this later, but we mention it now for Remark 6.1.4):
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is unconflicted.
(2) If P and then .
(3) for every .
(4) is least in the set ordered by subset inclusion.
The proof is just by pushing definitions around in a cycle of implications.
— Part 1 implies part 2. Suppose is unconflicted. Consider P such that , and consider any . Unpacking definitions we have that and so , thus as required.
— Part 2 implies part 3. From the fact that if and only if if and only if .
— Part 3 implies part 4. Part 4 just rephrases part 3.
— Part 4 implies part 1. Suppose is -least in and suppose . Then , so as required.
Lemma 6.1.3 is just an exercise in reformulating definitions, but part 4 of the result helps us to contrast the property of being unconflicted, with structurally similar characterisations of weak regularity and of regularity in Proposition 5.4.10 and Theorem 5.6.2 respectively. For the reader’s convenience we collect them here — all sets below are ordered by subset inclusion:
(1) is unconflicted when is least in .
(2) is weakly regular when is least amongst closed neighbourhoods of . See Proposition 5.4.10 and recall from Definition 5.4.1 that a closed neighbourhood of is a closed set such that interior().
(3) is regular when is a closed neighbourhood of and minimal amongst all closed neighbourhoods. See Theorem 5.6.2 and recall that a closed neighbourhood is any closed set with a nonempty interior (not necessarily containing ).
We know from Lemma 4.1.6(1) that regular implies weakly regular. We now consider how these properties relate to being unconflicted.
6.2. Regular = weakly regular + unconflicted
Suppose (P Open) is a semitopology and P. Then:
(1) If is regular then it is unconflicted. Equivalently by the contrapositive: if is conflicted then it is not regular.
(2) may be unconflicted and neither quasiregular, weakly regular, nor regular.
(3) There exists a semitopological space such that
— every point is unconflicted (so is a transitive relation) yet
— every point has empty community, so that the space is irregular, not weakly regular, and not quasiregular.27
We consider each part in turn:
(1) So consider . We must show that , so consider open neighbourhoods and . By assumption is regular, so unpacking Definition 4.1.4(3) K()Topen. From if follows that K() and by transitivity of K() (Definition 3.2.1(1)) we have as required.
(2) Consider the semitopology illustrated in Figure 7. By Lemma 5.6.7 the point 0 is trivially unconflicted (because it is intertwined only with itself), but it is also neither quasiregular, weakly regular, nor regular, because its community is the empty set. See also Example 6.3.3.
(3) As for the previous part, noting that the same holds of points 1, 2, and 3 in Figure 7.
We can combine Proposition 6.2.1 with a previous result Lemma 4.1.6 to get a precise and attractive relation between being
— regular (Definition 4.1.4(3)),
— weakly regular (Definition 4.1.4(4)), and
— unconflicted (Definition 6.1.1), as follows:
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
— is regular.
— is weakly regular and unconflicted.
More succinctly we can write: regular = weakly regular + unconflicted.28
We prove two implications:
— If is regular then it is weakly regular by Lemma 4.1.6 and unconflicted by Proposition 6.2.1(1).
— Suppose is weakly regular and unconflicted. By Definition 4.1.4(4) K() and by Lemma 3.6.8 it would suffice to show that for any K(). So consider K(). Now by Definition 4.1.4(1) K( interior() so in particular . Thus , and since is unconflicted as required.
We can use Theorem 6.2.2 to derive simple global well-behavedness conditions on spaces, as follows:
Suppose (P Open) is a semitopology. Then:
(1) If the relation is transitive (i.e. if every point is unconflicted) then a point is regular if and only if it is weakly regular.
(2) If every point is weakly regular (i.e. if K() always) then a point is regular if and only if it is unconflicted.
Immediate from Theorem 6.2.2.
6.3. The boundary of
In this short Subsection we ask what points on the topological boundary of can look like:
Suppose (P Open) is a semitopology and P.
(1) As standard, we define
and we call this the boundary of .
(2) In the case that for P then
Points in the boundary of are not regular points:
Suppose (P Open) is a semitopology and P and . Then:
(1) If is regular then K( interior().
(2) If is regular then boundary().
(3) If boundary() then is either conflicted or not weakly regular (or both).
We consider each part in turn:
(1) Suppose is regular. By Theorem 6.2.2 is unconflicted, so that by Lemma 6.1.3(3) ; and also is weakly regular, so that K()Open and K() . Thus K() is an open neighbourhood of that is contained in and thus interior() as required.
(2) This just repeats part 2 of this result, recalling from Notation 6.3.1 that boundary() if and only if interior().
(3) This is just the contrapositive of part 2, combined with Theorem 6.2.2.
Proposition 6.3.2(3) tells us that points on the topological boundary of are either conflicted, or not weakly regular, or perhaps both. It remains to show that all options are possible. It suffices to provide examples:
(1) In Figure 9 (left-hand diagram) the point is on the boundary of 1 1. It is unconflicted (being intertwined just with itself and 1), and not weakly regular (since K(1).
(2) In Figure 9 (middle diagram) the point 1 is on the boundary of 00 1. It is conflicted (since 0 1 2 yet 0 2) and it is weakly regular (since 1K0 1 2).29
(3) In Figure 9 (right-hand diagram) the point 2 is conflicted (since 1 2 3 yet 1 3) and it is not weakly regular, or even quasiregular (since K interior(1 2 3).
We consider the special case of regular spaces (we will pick this thread up again in Subsection 6.4.3 after we have built more machinery):
Suppose (P Open) is a semitopology and P. Then:
(1) If the set is regular, then boundary( and is clopen (closed and open) and transitive.
(2) If P is a regular space (so every point in it is regular) then P partitions into clopen transitive components given by P.
(1) By Proposition 6.3.2 interior(), so by Lemma 4.1.2 is open. By Proposition 5.4.3(4) is closed. By Definition 4.1.4(3) K( interior()Topen. It follows that is (topen and therefore) transitive.
(2) By part 1 of this result each is a clopen transitive set. Using Theorem 6.2.2 every point is unconflicted and it follows that if then .
6.4. The intertwined preorder
6.4.1. Definition and properties
Recall the specialisation preorder on points from topology, defined by
In words: we order points by subset inclusion on their closure .
This can also be defined on semitopologies of course, but we will also find a similar preorder interesting, which is defined using instead of (Definition 6.4.2). Recall that:
— is a closed set and is equal to the intersection of all the closed sets containing , and
— is also a closed set (Proposition 5.4.3(4)) and it is the intersection of all the closed neighbourhoods of (closed sets with an interior that contains ; see Definition 5.4.1 and Proposition 5.4.3(3)).
Suppose (P Open) is a semitopology.
(1) Define the intertwined preorder on points P by:
As standard, we may write when (pronounced ‘ is intertwined-less / intertwined-greater than ’). Calling this the ‘intertwined preorder’ does not refer to the ordering being intertwined in any sense; it just means that we order on (which is read ‘intertwined-’).
(2) Call (P Open) an -complete semitopology (read ‘intertwined-complete’) when for every subset P that is totally ordered by , there exists some P such that .
Being -complete (Definition 6.4.2(2)) is a plausible well-behavedness condition, because finite semitopologies are -complete, since a descending chain of subsets of a finite set is terminating. Real systems are finite (though participants in the system may not be able to access all of them, so they may look infinite ‘from the inside’), so assuming that a semitopology is -complete is a reasonable abstraction of actual finiteness.
There is also the community preorder defined such that when K() K(), which is related to via the fact that by definition K( interior(), so that is a coarser relation (meaning: it relates more points). There is an argument that this would sit more nicely with the condition K() in Lemma 6.4.5, but ordering on K() would relate all points with empty community, e.g. all of the points in Figure 7, and would slightly obfuscate the parallel with the specialisation preorder. This strikes us as unintuitive, so we prefer to preorder on .
Suppose (P Open) is a semitopology and P. Then:
(1) If K() then (meaning that ).
(2) If K() then K() K().
We consider each part in turn:
(1) Suppose K() and recall from Lemma 4.2.3(1) that K()Open, which means that K() is a closed neighbourhood of . We use Proposition 5.4.3(2) and Lemma 5.4.11:30
(2) Suppose K(). By part 1 of this result and Definition 6.4.2 . It is a fact that then interior() interior(). By Definition 4.1.4(1) therefore K() K() as required.
In the rest of this Subsection we develop corollaries of Lemma 6.4.5 (and compare this with Proposition 4.3.2):
Suppose (P Open) is a semitopology and P. Then:
(1) If K() K() then .
(2) If and are weakly regular (so that K() and K()) then
Theorem 6.4.7 is somewhat reminiscent of the hairy ball theorem:31
Suppose (P Open) is an -complete quasiregular semitopology.32 Then:
(1) For every P there exists some regular K().
(2) P contains a regular point.
We consider each part in turn:
(1) Consider the subset P P ordered by . Using Zorn’s lemma (on ), this contains a -minimal element . By assumption of quasiregularity K() , so choose K(). By Lemma 6.4.5(1) and by -minimality and it follows that K(). Thus is weakly regular. Applying similar reasoning to K() we deduce that , and thus K( K(), for every K(), and so by Corollary 5.4.13 is regular.
(2) Choose any P, and use part 2 of this result.
We care about the existence of regular points as these are the ones that are well-behaved with respect to our semitopological model. A semitopology with a regular point is one that — in some idealised mathematical sense — is capable of some collaboration somewhere to take some action.
So Theorem 6.4.7 can be read as a guarantee that, provided the semitopology is -complete and quasiregular, there exists somebody, somewhere, who can make sense of their local network and progress to act. This a mathematical guarantee and not an engineering one, much as is the hairy ball theorem of which the result reminds us.
6.4.2. Application to quasiregular conflicted spaces.
In Proposition 6.2.1(3) we saw an example of an unconflicted irregular space (illustrated in Figure 7): this is a space in which every point is unconflicted but not weakly regular. In this subsection we consider a dual case, of a conflicted quasiregular space: a space in which every point is conflicted yet quasiregular.
One question is: does such a creature even exist? The answer is:
— no, in the finite case (Corollary 6.4.10); and
— yes, in the infinite case (Proposition 6.4.11).
Suppose (P Open) is a finite quasiregular semitopology (so P is finite and every P is quasiregular) — in particular this holds if the semitopology is weakly regular. Then:
(1) For every P there exist some regular K().
(2) P contains a regular point.
In words we can say: every finite quasiregular semitopology contains a regular point.
There exists no finite quasiregular conflicted semitopology (i.e. a semitopology with finitely many points, each of which is quasiregular but conflicted).
Corollary 6.4.10 applies to finite semitopologies because these are necessarily -complete. The infinite case is different, as we shall now observe:
There exists an infinite quasiregular — indeed it is also weakly regular — conflicted semitopology (P Open).
In more detail:
— every P is weakly regular (so K()Open; see Definition 4.1.4(4)) yet
— every P is conflicted (so is not transitive at ; Definition 6.1.1(1)).
Furthermore: P is a topology and contains no topen sets.
Take P to be the set of words (possibly empty finite lists) from 0 and 1. For P write when is an initial segment of and define
Let open sets be generated as (possibly empty) unions of the . This space is illustrated in Figure 10; open sets are down-closed subsets.
The reader can check that (0 1), because 01, and that when or . It follows from the above that
and since every is weakly regular. Yet every is also conflicted, because 0 1 yet (0 1).
This example is a topology, because an intersection of down-closed sets is still down-closed. It escapes the constraints of Theorem 6.4.7 by not being -complete. It contains no topen sets because if it did contain some topen then by Theorem 4.2.6(1&5) there would exist a regular in P.
6.4.3. (Un)conflicted points and boundaries of closed sets.
Recall from Definition 5.4.1 that a closed neighbourhood is a closed set with a nonempty interior, and recall that — the set of points intertwined with from Definition 3.6.1 — is characterised using closed neighbourhoods in Proposition 5.8.3, as the intersection of all closed neighbourhoods that have in their interior.
This leads to the question of whether the theory of might be a theory of closed neighbourhoods. The answer seems to be no: has its own distinct character, as the results and counterexamples below will briefly illustrate.
For instance: in view of Proposition 5.8.3 characterising as an intersection of closed neighbourhoods of , might it be the case that for a closed neighbourhood, interior().
In words: is a closed neighbourhood the union of the points intertwined with its interior? This turns out to be only half true:
Suppose (P Open) is a semitopology and Closed is a closed neighbourhood. Then:
(1) interior().
(2) This subset inclusion may be strict: it is possible for P to be on the boundary of a closed neighbourhood , but not intertwined with any point in that neighbourhood’s interior. This is true even if P is a regular space (meaning that every P is regular).
Suppose (P Open) is a semitopology and P. Then define
and call this the kissing set of and .
Suppose (P Open) is a semitopology. Then the following are equivalent:
— is conflicted.
—There exist P such that and kiss().
—There exist P such that and .
We prove a cycle of implications:
— Suppose is conflicted. Then there exist P such that yet . Rephrasing this, we obtain that . We need to check that K() and K(). We prove K() by contradiction ( K() follows by identical reasoning). Suppose K(). Then by Lemma 6.4.5(1) . But , so , so , contradicting our assumption.
— Suppose and boundary() boundary(). Then certainly .
— Suppose and .
Then and , which is precisely what it means to be conflicted.
We can look at Definition 6.1.1 and Lemma 6.4.14 and conjecture that a point is conflicted if and only if it is in the kissing set of a pair of distinct closed sets. Again, this is half true:
Suppose (P Open) is a semitopology and P. Then:
(1) If is conflicted then there exist a pair of closed sets such that kiss().
(2) The reverse implication need not hold: it is possible for to be in the kissing set of a pair of closed sets and , yet is unconflicted. This is even possible if the space is regular (meaning that every point in the space is regular, including ) and and are closed neighbourhoods.
We consider each part in turn:
(1) If is conflicted then we use Lemma 6.4.14 and Proposition 5.4.3(4).
(2) We provide a counterexample, as illustrated in Figure 11 (right-hand diagram):
—
— Open sets are generated by 1, 2, 3, and 2.
— We set and 1 and 3.
Note that is regular (being intertwined with itself and 2), and and are closed neighbourhoods that kiss at , and 1, 2, and 3 are also regular.
6.5. Regular = quasiregular + hypertransitive
In Theorem 6.2.2 we characterised regularity in terms of weak regularity and being unconflicted. Regularity and weak regularity are two of the regularity properties considered in Definition 4.1.4, but there is also a third: quasiregularity. This raises the question whether there might be some other property such that regular = quasiregular + ?34
Yes there is, and we develop it in this Subsection, culminating with Theorem 6.5.8.
6.5.1. Hypertransitivity
Suppose (P Open) is a semitopology and P and Open. Then
Suppose (P Open) is a semitopology. Call P a hypertransitive point when for every Open,
Call (P Open) a hypertransitive semitopology when every P is hypertransitive.
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is hypertransitive.
(2) For every pair of open sets Open, implies .
(3) For every pair of regular open sets , implies (cf. Remark 5.7.11).
For the equivalence of parts 1 and 2 we reason as follows:
— Suppose is hypertransitive and suppose and . By Lemma 6.5.3 it follows that nbhd() . By hypertransitivity, as required.
— Suppose for every Open, implies , and suppose nbhd() . By Lemma 6.5.3 and therefore .
For the equivalence of parts 2 and 3 we reason as follows:
— Part 2 implies part 3 follows since every open regular set is also an open set.
— To show part 3 implies part 2, suppose for every pair of regular opens , implies , and suppose Open are two open sets that are not necessarily regular, and suppose . We must show that . Write interior() and interior() and note by Lemmas 5.7.3 and 5.1.6 that and are regular open sets and and . Then , so , and follows from Lemma 5.7.8
6.5.2. The equivalence
Suppose (P Open) is a semitopology and p. Then:
(1) If is regular then it is hypertransitive.
(2) If is hypertransitive then it is unconflicted.
(3) The reverse implication need not hold: it is possible for to be unconflicted but not hypertransitive.
(4) It is possible for to be hypertransitive (and unconflicted), but not quasiregular (and thus not weakly regular or regular).
We consider each part:
(1) Suppose is regular and Open and nbhd() . By Definition 4.1.4(3) (since is regular) K() is a topen (= open and transitive) neighbourhood of . Therefore by transitivity as required.
(2) Suppose is hypertransitive and suppose P and . Now consider Open and Open. By our intertwinedness assumptions we have that nbhd() . But is hypertransitive, so as required.
(3) It suffices to provide a counterexample. Consider the bottom right semitopology in Figure 3, and take and 1 and 0 2. Note that:
— is unconflicted, since it is intertwined only with itself and 1.
— and intersect every open neighbourhood of , but , so is not strongly compatible.
(4) It suffices to provide an example. Consider the semitopology illustrated in Figure 3, top-right diagram; so P 0 1 2 and Open 021 20 10 1 2. The reader can check that is hypertransitive, but 11 and K so is not quasiregular.
(Yet) another characterisation of being quasiregular will be helpful:
Equivalence of parts 2 and 3 is immediate from Lemma 6.5.3.
For equivalence of parts 1 and 2, we prove two implications:
— Suppose is quasiregular, meaning by Definition 4.1.4(5) that K() . Pick some K() (it does not matter which). It follows by construction in Definitions 3.6.1(2) and 4.1.4(1) and Lemma 4.1.2 that , so that K(). Using Definition 3.6.1(1) it follows that K() for every nbhd(), as required.
— Suppose K() nbhd(). Then in particular K() P (because POpen), and by Notation 3.1.1(1) it follows that K() .
Compare and contrast Theorem 6.5.8 with Theorem 6.2.2:
Suppose (P Open) is a semitopology and P. Then the following are equivalent:
(1) is regular.
(2) is quasiregular and hypertransitive.
We consider two implications:
— Suppose is regular. Then is quasiregular by Lemma 4.1.6(1&2), and hypertransitive by Lemma 6.5.6(1).
— Suppose is quasiregular and hypertransitive.
By Lemma 6.5.6(2) is unconflicted. If we can prove that is weakly regular (meaning by Definition 4.1.4(4) that K()), then by Theorem 6.2.2 it would follow that is regular as required. Thus, it would suffice to show that K(), thus that there is an open neighbourhood of points with which is intertwined. Write interior(PK()). We have two subcases to consider:
— Suppose nbhd() . By Lemma 6.5.7 (since is quasiregular) we have that K() nbhd(). Thus K() nbhd() , and by hypertransitivity of it follows that K() . But this contradicts the construction of as being a subset of PK(), so this case is impossible.
— Suppose nbhd() . Then there exists some nbhd() such that , and it follows that K() so that K() as required.
Thus is weakly regular, as required.
7. CONCLUSIONS
We start by noticing that a notion of ‘actionable coalition’ as discussed in the Introduction, leads to the topology-like structure which we call semitopologies.
We simplified and purified our motivating examples — having to do with understanding agreement and consensus in distributed systems — to two precise mathematical questions:
(1) understand antiseparation properties, and
(2) understand the implications of these for value assignments.35
We have seen that the implications of these ideas are rich and varied. Point-set semitopologies have an interesting theory which obviously closely resembles point-set topology, but is not identical to it. In particular, dropping the condition that intersections of open sets must be open permits a wealth of new structure, which our taxonomy of antiseparation properties and its applications to value assignments explores.
7.1. Topology vs. semitopology
We briefly compare and contrast topology and semitopology:
(1) Topology: Separation axioms are prominent in the topological literature; I could find no corresponding taxonomy of anti-separation properties.36 Semitopology: Antiseparation, not separation, is our primary interest. We consider a taxonomy of antiseparation properties, including: points being intertwined (see Definition 3.6.1 and Remark 3.6.10), and points being quasiregular, weakly regular, and regular (Definition 4.1.4), (un)conflicted (Definition 6.1.1(2)), and hypertransitive (Definition 6.5.4).37
(2) Topology: If a minimal open neighbourhood of a point exists then it is least, because we can intersect two minimal neighbourhoods to get a smaller one which by minimality is equal to both. Yet, in topology the existence of a least open neighbourhood is not guaranteed (e.g. 0 has no least open neighbourhood). Semitopology: A point may have multiple minimal open neighbourhoods — examples are very easy to generate, see e.g. the top-right example in Figure 3.
(3) Topology: We are typically interested in functions on topologies that are continuous (or mostly so, e.g. (). Thus for example, the definition of Top the category of topological spaces takes continuous functions as morphisms, essentially building in assumptions that continuous functions are of most interest and that finding them is enough of a solved problem that we can restrict to continuous functions in the definition. Semitopology: For our intended application to consensus, we are explicitly interested in functions that may be discontinuous. This models initial and intermediate states where local consensus has not yet been achieved, or final states on semitopologies that include disjoint topens and non-regular points (e.g. conflicted points), as well as adversarial or failing behaviour. Thus, having continuity is neither a solved problem, nor even necessarily desirable.
(4) Sometimes, ideas that come from semitopology project carry over to topology, but they lose impact or become less interesting in doing so. For example: our theory of semitopologies considers notions of topen set and strongly topen set (Definitions 3.2.1 and 3.7.5). In topology these are equivalent to one another, and to a known and simpler topological property of being hyperconnected (Definition 3.7.12).38
(5) Semitopological questions such as ‘is this a topen set’ or ‘are these two points intertwined’ or ‘does this point have a topen neighbourhood’ — and many other definitions, such as our taxonomy of points into regular, weakly regular, quasiregular, unconflicted, and hypertransitive — appear to be novel. Also in the background is that we are particularly interested in properties and algorithms that work well using local and possibly incomplete or even partially incorrect information.
Thus semitopologies have their own distinct character: because they are mathematically distinct, and because modern applications having to do with actionable coalitions and distributed systems motivate us to ask questions that have not necessarily been considered before.
7.2. Related work
Union sets and minimal structures. There is a thread of research into union-closed families; these are subsets of a finite powerset closed under unions, so that a union-closed family is precisely just a finite semitopology. The motivation is to study the combinatorics of finite subsemilattices of a powerset. Some progress has been made in this [Poo92]; the canonical reference for the relevant combinatorial conjectures is the ‘problem session’ on page 525 (conjectures 1.9, 1.9’, and 1.9”) of [Riv85]. See also recent progress in a conjecture about union-closed families (permalink).
There is no direct connection to this work, though the combinatorial properties considered may yet become useful for proving properties of concrete algorithms.
A minimal structure on a set is a subset of pow() that contains and . Thus a semitopology is a minimal structure that is also closed under arbitrary unions. There is a thread of research into minimal structures, studying how notions familiar from topology (such as continuity) fare in weak (minimal) settings [PN01] and how this changes as axioms (such as closure under unions) are added or removed. An accessible discussion is in [Szá07], and see the brief but comprehensive references in Remark 3.7 of that paper. Of course our focus is on properties of semitopologies which are not considered in that literature; but we share an observation with minimal structures that it is useful to study topology-like constructs, in the absence of closure under intersections.
Gradecast converges on a topen. Many consensus algorithms have the property that once consensus is established in a quorum , it propagates to . For example, in the Grade-Cast algorithm [FM88], participants assign a confidence grade of 0, 1 or 2 to their output and must ensure that if any participant outputs with grade 2 then all must output with grade at least 1. If all the quorums of a participant intersect some set that unanimously supports value , then the participant assigns grade at least 1 to .
From the view of our paper, this is just taking a closure, which suggests that, to convince a topen to agree on a value, it would suffice to first convince an open neighbourhood that intersects the topen, and then use Grade-Cast to convince the whole topen. See also Proposition 5.3.2 and Remark 5.3.3.
Algebraic topology as applied to distributed computing tasks. Continuing the discussion of tasks above, the reader may know that solvability results about distributed computing tasks have been obtained from algebraic topology, starting with the impossibility of wait-free -set consensus using read-write registers and the Asynchronous Computability Theorem [HS93; BG93; SZ93] in 1993. See [HKR13] for numerous such results.
The basic observation is that the set of final states of a distributed algorithm forms a simplicial complex, called the protocol complex, and topological properties of this complex, like connectivity, are constrained by the underlying communication and fault model. These topological properties in turn can determine what tasks are solvable. For example: every algorithm in the wait-free model with atomic read-write registers has a connected protocol complex, and because the consensus task’s output complex is disconnected, consensus in this model is not solvable [HKR13, Chapter 4].
This work is also topological, but in a different way: we use (semi)topologies to study consensus in and of itself, rather than the solvability of consensus or other tasks in particular computation models. Put another way: the papers cited above use topology to study the solvability of distributed tasks, but we show here how the very idea of ‘distribution’ can be viewed as having a semitopological foundation.
Of course we can imagine that these might be combined — that in future work we may find interesting and useful things to say about the topologies of distributed algorithms when viewed as algorithms on and in a semitopology.
Fail-prone systems and quorum systems. Given a set of processes P, a fail-prone system [MR98] (or adversary structure [HM00]) is a set of fail-prone sets where, for every 1 , P. denotes the assumptions that the set of processes that will fail (potentially maliciously) is a subset of one of the fail-prone sets. A dissemination quorum system for is a set of quorums where, for every 1 , P, and such that
— for every two quorums and and for every fail-prone set , () and
— for every fail-prone set , there exists a quorum disjoint from .
Several distributed algorithms, such as Bracha Broadcast [Bra87] and PBFT [CL02], rely on a quorum system for a fail-prone system in order to solve problems such as reliable broadcast and consensus assuming (at least) that the assumptions denoted by are satisfied.
Several recent works generalise the fail-prone system model. Under the failure assumptions of a traditional fail-prone system, Bezerra et al. [BKK22] study reliable broadcast when participants each have their own set of quorums. Asymmetric Fail-Prone Systems [CT19] generalise fail-prone systems to allow participants to make different failure assumption and have different quorums. In Permissionless Fail-Prone Systems [CLZ23], participants not only make assumptions about failures, but also make assumptions about the assumptions of other processes; the resulting structure seems closely related to semitopologies, but the exact relationship still needs to be elucidated.
In Federated Byzantine Agreement Systems [Maz15], participants declare quorum slices and quorums emerge out of the collective quorum slices of their members. García-Pérez and Gotsman [GPG18] rigorously prove the correctness of broadcast abstractions in Stellar’s Federated Byzantine Agreement model and investigate the model’s relationship to dissemination quorum systems. The Personal Byzantine Quorum System model [LGM19] is an abstraction of Stellar’s Federated Byzantine Agreement System model and accounts for the existence of disjoint consensus clusters (in the terminology of the paper) which can each stay in agreement internally but may disagree between each other. Consensus clusters are closely related to the notion of topen in Definition 3.2.1(2).
Sheff et al. study heterogeneous consensus in a model called Learner Graphs [SWRM21] and propose a consensus algorithm called Heterogeneous Paxos.
Cobalt, the Stellar Consensus Protocol, Heterogeneous Paxos, and the Ripple Consensus Algorithm [Mac18; Maz15; SWRM21; SYB14] are consensus algorithms that rely on heterogeneous quorums or variants thereof. The Stellar network [LLM19] and the XRP Ledger [SYB14] are two global payment networks that use heterogeneous quorums to achieve consensus among an open set of participants.
Quorum systems and semitopologies are not the same thing. Quorum systems are typically taken to be such that all quorums intersect (in our terminology: they are intertwined), whereas semitopologies do not require this. On the other hand, quorums are not always taken to be closed under arbitrary unions, whereas semitopologies are (see the discussion in Example 2.1.4(7)).
But there are also differences in how the maths has been used and understood. This paper has been all about point-set topology flavoured ideas, whereas the literature on fail-prone systems and quorum systems has been most interested in synchronisation algorithms for distributed systems. We see these interests as complementary, and the difference in emphasis is a feature, not a bug. Some work by the second author and others [LGM19] gets as far as proving an analogue to Lemma 3.5.2 (though we think it is fair to say that the presentation in this paper is much simpler and more clear), but it fails to notice the connection with topology and the subsequent results which we present in this paper.
7.3. Future work
We briefly outline some ways in which this work can be extended and improved:
(1) In Definition 2.1.3 we define a value assignment : P Val to be a function from a semitopology to a codomain Val that is given the discrete semitopology. This is a legitimate starting point, but of course we should consider more general codomains. This could include an arbitrary semitopology on the right (for greatest generality), but even for our intended special case of consensus it would
be interesting to try to endow Val with a semilattice structure (or something like it), at least, e.g. to model merging of distinct updates to a ledger.39 We can easily generate a (semi)topology from a semilattice by taking points to be elements of the lattice and open sets to be up-closed sets, and this would be a natural generalisation of the discrete semitopologies we have used so far.
(2) We have not considered what would correspond to the exponential (or Vietoris) semitopology. Semilattice representation results exist [Bre84], but a design space exists here and we should look for representations well-suited to computationally verifying or refuting properties of semitopologies.
(3) We mentioned in Subsection 7.2 that semitopology is not about algebraic topology applied to solvability of distributed computing tasks. These are distinct topics, and the fact that they share a word in their name does not make them any more equal than a Great Dane and a Danish pastry. But, it is a very interesting question what algebraic semitopology might look like. To put this another way: what is the geometry of semitopological spaces? We would very much like to know.
(4) It remains to consider Byzantine behaviour, by which we mean that some participants may misreport their view of the network in order to ‘invent’ or sabotage quorums and so influence the outcome of consensus.
So for instance we can ask: “What conditions can we put on a semitopology consisting of a single toppen to guarantee that changing it at one point will not make that topen split into two topens?” Thus intuitively, given a semitopology (P Open) we are interested in asking how properties range over an ‘-ball’ of perturbed semitopologies — as might be caused by various possible non-standard behaviours from a limited number of Byzantine points — and in particular we are looking for criteria to guarantee that appropriately-chosen good properties be preserved under perturbation.
(5) We have studied how consensus, once achieved on an open set , propagates to its closure ; see Proposition 5.3.2 and Remark 5.3.3. But this is just half of the problem of consensus: it remains to consider (within our semitopological framework) what it is to attain consensus on some open set in the first place.
That is: suppose (P Open) is a semitopology and : P Var is a value assignment. Then what does it mean, in maths and algorithms, to find a value assignment P Var that is ‘close’ to but is continuous on some open set ? In this paper we have constructed a theory of what it would then be to extend to an that continuously extends to regular points; but we have not yet looked at how to build the . We speculate that unauthenticated Byzantine consensus algorithms (like Information-Theoretic HotStuff [AS21]) can be understood in our setting; unlike authenticated algorithms, unauthenticated algorithms do not rely on one participant being able to prove to another, by exhibiting signed messages, that a quorum has acted in a certain way.
(6) We have not considered morphisms of semitopologies and how to organise semitopologies into a category, in this paper — but see next paragraph.
A more extensive treatment of semitopologies is also available [Gab24] (completed since this paper was first submitted): its first part includes and extends the material in this paper; its second part treats the category of semitopologies and constructs its categorical dual as a category of semiframes; and its third part builds a three-valued logic on semitopologies which we use to study, and expand on, the antiseparation properties we consider here. The reader who found this paper too brief can find further reading there.
REFERENCES
[ACTZ24] Orestis Alpos, Christian Cachin, Björn Tackmann, and Luca Zanolini, Asymmetric distributed trust, Distributed Computing (2024), Available online at https://doi.org/10.1007/s00446-024-00469-1.
[AS21]Ittai Abraham and Gilad Stern, Information Theoretic HotStuff, 24th International Conference on Principles of Distributed Systems, OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference) (Dagstuhl, Germany) (Quentin Bramas, Rotem Oshman, and Paolo Romano, eds.), LIPIcs, vol. 184, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 11:1–11:16.
[BG93]Elizabeth Borowsky and Eli Gafni, Generalized FLP Impossibility Result for T-resilient Asynchronous Computations, Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’93, ACM, 1993, pp. 91–100.
[BKK22] João Paulo Bezerra, Petr Kuznetsov, and Alice Koroleva, Relaxed reliable broadcast for decentralized trust, Networked Systems (Mohammed-Amine Koulali and Mira Mezini, eds.), Lecture Notes in Computer Science, Springer International Publishing, 2022, pp. 104–118.
[Bou98]Nicolas Bourbaki, General topology: Chapters 1-4, Elements of mathematics, Springer, 1998.
[Bra87]Gabriel Bracha, Asynchronous Byzantine agreement protocols, Information and Computation 75 (1987), no. 2, 130–143.
[Bre84]D. A. Bredhikin, A representation theorem for semilattices, Proceedings of the American Mathematical Society 90 (1984), no. 2, 219–220.
[CL02]Miguel Castro and Barbara Liskov, Practical Byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS) 20 (2002), no. 4, 398–461.
[CLZ23]Christian Cachin, Giuliano Losa, and Luca Zanolini, Quorum systems in permissionless networks, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) (Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 253, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, ISSN: 1868-8969, pp. 17:1–17:22.
[CT19]Christian Cachin and Björn Tackmann, Asymmetric Distributed Trust, arXiv:1906.09314 [cs] (2019), arXiv: 1906.09314.
[DP02]B. A. Davey and Hilary A. Priestley, Introduction to lattices and order, 2 ed., Cambridge University Press, 2002.
[Eng89]Ryszard Engelking, General topology, Sigma Series in Pure Mathematics, Heldermann Verlag, 1989.
[FHNS22] Martin Florian, Sebastian Henningsen, Charmaine Ndolo, and Björn Scheuermann, The sum of its parts: Analysis of federated byzantine agreement systems, Distributed Computing 35 (2022), no. 5, 399–417 (en).
[FM88]Paul Feldman and Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC ’88, Association for Computing Machinery, 1 1988, pp. 148–161.
[Gab24]Murdoch J. Gabbay, Semitopology: decentralised collaborative action via topology, algebra, and logic, College Publications, August 2024, ISBN 9781848904651.
[GPG18]Álvaro García-Pérez and Alexey Gotsman, Federated byzantine quorum systems, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[HKR13] Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum, Distributed computing through combinatorial topology, Morgan Kaufmann, 2013.
[HM00]Martin Hirt and Ueli Maurer, Player Simulation and General Adversary Structures in Perfect Multiparty Computation, Journal of Cryptology 13 (2000), no. 1, 31–60.
[HS93]Maurice Herlihy and Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, 1993, pp. 111–120.
[Hul03]Klaus Hulek, Elementary algebraic geometry, Student Mathematical Library, vol. 20, American Mathematical Society, 2003.
[JT04]Tyler Jarvis and James Tanton, The hairy ball theorem via Sperner’s lemma, The American Mathematical Monthly 111 (2004), no. 7, 599–603.
[Kop89]Sabine Koppelberg, Handbook of Boolean algebras, volume 1, North-Holland, 1989, Series editors Robert Bonnet and James Donald Monk.
[Lam98]Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems 16 (1998), no. 2, 133–169.
[LCL23]Xiao Li, Eric Chan, and Mohsen Lesani, Quorum Subsumption for Heterogeneous Quorum Systems, 37th International Symposium on Distributed Computing (DISC 2023) (Dagstuhl, Germany) (Rotem Oshman, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 281, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, pp. 28:1–28:19.
[LGM19] Giuliano Losa, Eli Gafni, and David Mazières, Stellar consensus by instantiation, 33rd International Symposium on Distributed Computing (DISC 2019) (Dagstuhl, Germany) (Jukka Suomela, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 146, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019, pp. 27:1–27:15.
[LL23]Xiao Li and Mohsen Lesani, Open Heterogeneous Quorum Systems, April 2023, arXiv:2304.02156 [cs].
[LLM19] Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, and Jed McCaleb, Fast and secure global payments with Stellar, Proceedings of the 27th ACM Symposium on Operating Systems Principles (New York, NY, USA), SOSP ’19, Association for Computing Machinery, 2019, p. 80–96.
[LSP82]Leslie Lamport, Robert Shostak, and Marshall Pease, The Byzantine Generals Problem, ACM Trans. Program. Lang. Syst. 4 (1982), no. 3, 382–401.
[Mac18]Ethan MacBrough, Cobalt: BFT Governance in Open Networks, February 2018, Available online at https://doi.org/10.48550/arXiv.1802.07240.
[Maz15]David Mazières, The Stellar consensus protocol: a federated model for Internet-level consensus, Tech. report, Stellar Development Foundation, 2015, https://www.stellar.org/papers/stellar-consensus-protocol.pdf (permalink: https://web.archive.org/web/20240629063518/https://stellar.org/learn/stellar-consensus-protocol).
[MR98]Dahlia Malkhi and Michael Reiter, Byzantine quorum systems, Distributed computing 11 (1998), no. 4, 203–213.
[NW94]Moni Naor and Avishai Wool, The load, capacity and availability of quorum systems, Proceedings 35th Annual Symposium on Foundations of Computer Science, vol. 27, IEEE, 1994, pp. 214– 225.
[PN01]Valeriu Popa and Takashi Noiri, On the definitions of some generalized forms of continuity under minimal conditions, Memoirs of the Faculty of Science. Series A. Mathematics 22 (2001), 9–18.
[Poo92]Bjorn Poonen, Union-closed families, Journal of Combinatorial Theory, Series A 59 (1992), no. 2, 253–268.
[Rik62]William H. Riker, The theory of political coalitions, Yale University Press, 1962.
[Riv85]Ivan Rival (ed.), Graphs and order. the role of graphs in the theory of ordered sets and its applications, Proceedings of NATO ASI, Series C (ASIC), vol. 147, Banff/Canada, 1985.
[Rya10]Johnny Ryan, A history of the internet and the digital future, Reaktion Books, 2010.
[Rya11], How the atom bomb helped give birth to the internet, https://arstechnica.com/tech-policy/2011/02/how-the-atom-bomb-gave-birth-to-the-internet/, 2 2011, Permalink: http://web.archive.org/web/20240622221756/https://arstechnica.com/tech-policy/2011/02/how-the-atom-bomb-gave-birth-to-the-internet/.
[SWRM21] Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers, Heterogeneous Paxos, 24th International Conference on Principles of Distributed Systems (OPODIS 2020) (Dagstuhl, Germany) (Quentin Bramas, Rotem Oshman, and Paolo Romano, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 184, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021, ISSN: 1868-8969, pp. 5:1–5:17.
[SYB14]David Schwartz, Noah Youngs, and Arthur Britto, The Ripple Protocol Consensus Algorithm, Ripple Labs Inc White Paper 5 (2014), no. 8, 151.
[SZ93]Michael Saks and Fotios Zaharoglou, Wait-free k-set agreement is impossible: The topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, 1993, pp. 101–110.
[Szá07] Árpád Száz, Minimal structures, generalized topologies, and ascending systems should not be studied without generalized uniformities, Filomat (Nis) 21 (2007), 87–97.
[Wes11]Dag Westerståhl, Generalized quantifiers, The Stanford Encyclopedia of Philosophy (Edward N. Zalta, ed.), Metaphysics research lab, CSLI, Stanford University, summer 2011 ed., 2011, Available online at https://plato.stanford.edu/archives/sum2011/entries/generalized-quantifiers/ (permalink: https://archive.ph/YlP09).
[Wil70]Stephen Willard, General topology, Addison-Wesley, 1970, Reprinted by Dover Publications.
Acknowledgements
I am extremely grateful to an anonymous referee for their careful attention to this material and for their feedback. Thanks to Giuliano Losa and the Stellar Development Foundation for their generous support and funding. Giuliano was instrumental in explaining the issues, reviewing material, and guiding me to interesting problems; thank you for the many interesting discussions and insightful comments.
Notes
1The internet was designed to be an information network that would be resilient to nuclear attack. It did this by being ‘centrifugal’; emphasising node-to-node actions instead of centre-to-centre actions. See [Rya10], summarised by Ars Technica [Rya11]. ↩
2E.g. in a blockchain, we may want all updates to be uniform so that we implement a decentralised ledger; but in a peer-to-peer system or the internet, updates need not be uniform, e.g. if nodes are swapping or forwarding data. ↩
3There is a little overlap between this clause and the first one: if then by convention . Thus, Open(P) follows from both clause 1 and clause 2. If desired, the reader can just remove the condition Open(P) from clause 1, and no harm would come of it. ↩
4coherent (adj.) 1550s, “harmonious;” 1570s, “sticking together,” also “connected, consistent” (of speech, thought, etc.), from French cohérent (16c.), from Latin cohaerentem (nominative cohaerens), present participle of cohaerere “cohere,” from assimilated form of com “together” (see co-) + haerere “to adhere, stick” (etymologyonline: https://www.etymonline.com/word/coherent). ↩
6But, note that voting and generalised quantifiers have a centralised flavour to them. For instance: a vote in the typical democratic sense is a synchronous, global operation (unless the result is disputed): votes are cast, collected, and then everyone gets together — e.g. in a vote counting hall — to count the votes and agree on who won and so certify the outcome. ↩
7We can also learn what things are important and interesting to look at, and what distinctions make a difference in practice; I know that I have. ↩
8The other main classification is conflicted points, in Definition 6.1.1. These properties are connected by an equation: regular = weakly regular + unconflicted; see Theorem 6.2.2. ↩
9Bounded means closed under empty intersections and unions, i.e. containing the empty and the full set of points. Complete means closed under arbitrary (possibly empty, possibly infinite) sets unions. The reader may know that a complete lattice is also co-complete: if we have all joins, then we also have all meets. However, note that there is no reason for the meets in Open to coincide with the meets in pow(P), i.e. for them to be sets intersections. ↩
10According to Wikipedia, this space is also called indiscrete, anti-discrete, concrete, and codiscrete (https://en.wikipedia.org/wiki/Trivial_topology). ↩
11A topologist would call this a hyperconnected space, but be careful! There are multiple such notions in semitopologies, so intuitions need not transfer over. See the discussion in Subsection 3.7.3. ↩
12A validity relation would also work. ↩
13The empty set is trivially transitive and open, so it would make sense to admit it as a (degenerate) topen. However, it turns out that we mostly need the notion of ‘topen’ to refer to certain kinds of neighbourhoods of points (we will call them communities; see Definition 4.1.4). It is therefore convenient to exclude the empty set from being topen, because while it is the neighbourhood of every point that it contains, it is not a neighbourhood of any point. ↩
14‘Transitive open’ ‘topen’, like ‘closed and open’ ‘clopen’. For convenient reference, note that related notions of strong transitivity and topen are in Definition 3.7.5. ↩
15We can be more precise if we like: e.g. cannot be split by a value assignment that is continuous on a contiguous segment of that includes . Continuity on all of is one sufficient condition for this, which corresponds (in the language of consensus) to assuming that all participants are correct. But we digress. ↩
16A total order is reflexive, transitive, antisymmetric, and total. ↩
17We call this a clique, because if we form the intersection graph with nodes elements of and with an (undirected) edge between and when , then is a clique precisely when its intersection graph is indeed a clique. See also Definition 3.7.12. ↩
18We could also use Lemma 3.4.5. The chain needs to be nonempty because and this is open but not topen (= nonempty, transitive, and open). The reader might ask why Lemma 3.4.5 was not derived directly from Lemma 3.4.3(2); this is because (interestingly) Lemma 3.4.5 does not require openness. ↩
19It does not follow from being open in ( Open ) that is open in (P Open), which is why we included an assumption that this holds in the statement of the result. ↩
20Calling this hyperconnected is a slight but natural generalisation of the usual definition: in topology, ‘hyperconnected’ is typically used to refer to an entire space rather than a subset of it. In the case that P, our definition specialises to the usual one. ↩
21It does not follow from Topen that K(: consider P 0 1 and Open 00 1 and ; then Topen yet K(0 1. ↩
22Following Definition 2.1.3 and Example 2.1.4(3), this is just 0 1 with the discrete semitopology. ↩
23We really do mean “ is minimal amongst closed neighbourhoods” and not the weaker condition “ is minimal amongst closed neighbourhoods of ”! That weaker condition is treated in Proposition 5.4.10. See Remark 5.6.4. ↩
24Lemma 6.5.3 packages this argument up nicely with some slick notation, which we have not yet set up. ↩
25See https://topology.pi-base.org/theorems/T000420 (permalink: https://web.archive.org/web/20240108192930/https://topology.pi-base.org/theorems/T000420). ↩
26A longer proof via Corollary 5.1.11(3) and Lemma 5.1.9 is also possible. ↩
27See also Proposition 6.4.11. ↩
28See also a similar result Theorem 6.5.8, and a discussion in Remark 6.5.9. ↩
29This semitopology is also in Figure 3. We reproduce it here for the reader’s convenience so that the examples are side-by-side. ↩
30If the reader prefers a proof by concrete calculations, it runs as follows: Suppose K(), so that in particular . We wish to prove that . So consider ; we will show that , i.e. that every pair of open neighbourhoods of and must intersect. Consider a pair of open neighbourhoods Open and Open. We note that K(), because K()Open and . Choose K() . Now and and , and we conclude that as required. ↩
31This famous result states that every tangent vector field on a sphere of even dimension — this being the surface of a ball of odd dimension — must vanish at at least one point. Intuitively, if we consider a ‘hairy ball’ in three-dimensional space and we try to comb its hairs so they all lie smoothly flat (with no discontinuities in direction), then at least one of the hairs is pointing straight up (i.e. its projection onto the ball is zero). A nice combinatorial proof is in [JT04]. ↩
32Definition 4.1.4(5): a semitopology that is -complete and whose every point has a nonempty community. ↩
33The proof of Theorem 6.4.7 uses Zorn’s lemma. A longer, direct proof of Proposition 6.4.9 is also possible, by explicit induction on size of sets. ↩
34By Lemma 4.1.6(2) being weakly regular is a stronger condition than being quasiregular, thus we would expect to be stronger than being unconflicted. And indeed this will be so: see Lemma 6.5.6(2). ↩
35A value assignment is just a not-necessarily-continuous map from a semitopology to a discrete space. ↩
36The Wikipedia page on separation axioms (permalink) includes an excellent overview with over a dozen separation axioms; no anti-separation axioms are proposed. Important non-Hausdorff spaces do exist; e.g. the Zariski topology [Hul03, Subsection 1.1.1]. ↩
37An extra word on the converse of this: Our theory of semitopologies admits spaces whose points partition into distinct communities, as discussed in Theorem 3.5.4 and Remark 3.5.5. To a professional blockchain engineer it might seem terrible if two points points are not intertwined, since this means they might not be in consensus in a final state. Should this not be excluded by the definition of semitopology, as is done in the literature on quorum systems, where it typically definitionally assumed that all quorums in a quorum system intersect? No! Separation is a fact of life which we permit not only so that we can mathematically analyse it (and we do), but also because we may need it for certain normal situations. For example, most blockchains have a mainnet and several testnets and it is understood that each should be coherent within itself, but different nets need not be in consensus with one another. Indeed, if the mainnet had to agree with a testnet then this would likely be a bug, not a feature. So the idea of having multiple partitions is nothing new per se. It is a familiar idea, which semitopologies put in a powerfully general mathematical context. ↩
38...but (strong) topens are their own thing. Analogy: a projection from to maps to ; this is not evidence that is equivalent to 0! ↩
39We write ‘something like it’ because we might also consider, or consider excluding, possibly conflicting updates. ↩