A Formalization of the Correctness of the Floodsub Protocol

Ankit Kumar Panagiotis Manolios · 2025

Read A Formalization of the Correctness of the Floodsub Protocol by Ankit Kumar Panagiotis Manolios (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19013.txt.

Introduction

Ankit Kumar and Panagiotis Manolios give the first machine-checked proof that a popular messaging protocol behaves as promised. Their 2025 paper concerns Floodsub, a peer-to-peer publish-subscribe system where nodes join and leave freely and pass each new message to all neighbors but the sender.

To state what correct means, they define a stripped-down specification, Broadcastsub, which hides wiring and subscriptions and keeps only the delivery promise. The proof shows every run of Floodsub matches the specification, using a method called well-founded simulation that reasons locally about states and their successors. The authors note it is the first mechanized refinement proof for a real-world pubsub protocol.

Catalog record

CREATORAnkit Kumar Panagiotis Manolios
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19013

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Formalization of the Correctness of the Floodsub Protocol Ankit Kumar Panagiotis Manolios Abstract Floodsub is a simple, robust and popular peer-to-peer publish/subscribe (pubsub) protocol, where nodes can arbitrarily leave or join the network, subscribe to or unsubscribe from topics and forward newly received messages to all of their neighbors, except the sender or the originating peer. To show the correctness of Floodsub, we propose its specification: Broadcastsub, in which implementation details like network connections and neighbor subscriptions are elided. To show that Floodsub does really implement Broadcastsub, one would have to show that the two systems have related infinite computations. We prove this by reasoning locally about states and their successors using Well-Founded Simulation (WFS). In this paper, we focus on the mechanization of a proof which shows that Floodsub is a simulation refinement of Broadcastsub using WFS. To the best of our knowledge, ours is the first mechanized refinement-based verification of a real world pubsub protocol. 1 Introduction Peer-to-Peer (P2P) systems are decentralized distributed systems, which constitute overlay networks built over physical networks, such as the Internet [ 3 ] . These systems are characterized by self-organization, being able to handle highly dynamic network configurations, with nodes being able to join or leave the overlay network, which allows for scalability in the size of the networks. Publish/Subscribe ( pubsub ) systems are P2P systems that allow (1) consumers of information (subscriber nodes) to query the system, and (2) producers of information (publisher nodes) to publish information to the system. Publishers are able to send messages to multiple recipients without them having to know who the subscribers are. This is achieved by associating subscriptions and messages with topics . For example, in a chat room application, each room is a pubsub topic and clients post chat messages to rooms, which are received by all other clients (subscribers) in the room. The Scribe system [ 6 ] was a first attempt at providing topic-based pubsub functionality over the Pastry P2P network [ 34 ] . A most basic implementation of pubsub systems is Floodsub [ 37 , 2 ] . In Floodsub, nodes are free to leave or join the network. Every node has information about its neighboring nodes and their subscriptions. Whenever a node joins, subscribes to or unsubscribes from a topic, it updates its neighboring nodes. Messages are forwarded to all neighbors that subscribe to the topic of the message, except the source (originating node) of the message, or the node that forwarded this message. Our implementation of Floodsub is based on its specification [ 37 ] . However, we did not do any conformance testing or cross validation against existing implementations. And we do not model Ambient Peer Discovery, which is a way for nodes to learn about their neighbors, and is described in the specification as being external to the protocol. Given our model of Floodsub protocol, how can we verify that it actually is an implementation of a pubsub system? We need a specification for a pubsub system and some notion of correctness. We propose Broadcastsub [ 2 ] as the specification for a P2P pubsub system. Broadcastsub nodes can freely leave and join the network. Nodes maintain a list of topics they subscribe to. However, there is no notion of neighboring nodes. Messages are broadcasted “magically” to all the subscribers in a single transition. Notice that Broadcastsub is the simplest P2P pubsub system, where implementation details like subscription updates, neighboring nodes and their subscriptions are abstracted. In this paper, we focus on the mechanization of the proof that Floodsub is a simulation refinement [ 32 ] of Broadcastsub using Well-Founded Simulation (WFS) [ 24 ] in ACL2 Sedan ( ACL2s ) [ 13 , 7 ] . To show that Floodnet implements Broadcastnet, we will prove that Floodnet is a simulation refinement of Broadcastnet. Why are we proving a simulation refinement? Because we are comparing two P2P systems at different levels of abstraction. In a Broadcastsub network, a message broadcast propagates to all subscribers (of the message) instantly. However, in a Floodsub network, a message may require several hops from one node to another, until it reaches all of the subscribers. It is often the case that a lower-level implementation takes several steps to match a step of its higher level specification. Proving a WFS guarantees that Floodsub states and related Broadcastsub states have related computations. This notion of correctness implies that the two systems satisfy the same ACTL^{*}\setminus{X} [ 5 ] properties. WFS proofs are structural and local, requiring proofs about states and their successors, instead of infinite paths, thereby allowing proofs to be amenable to formal verification. This work is a piece of a larger puzzle that allows us to reason about more complex P2P systems using compositional refinement [ 26 , 25 ] , which we want to extend all the way down to Gossipsub [ 36 ] . Since our models are public, protocol engineers will be able to easily define/extend their own P2P systems and attempt to show that their model is a refinement of one of our existing ones. Our proof of refinement spells out exactly how the proof breaks, if these conditions are not satisfied. Hence, our contribution can also be used to tag P2P systems with the kinds of network attacks they are prone to, corresponding to the refinement conditions that were not satisfied. We make the following contributions: (1) Formal, executable, open and public models of Floodsub and Broadcastsub protocols expressed as transition systems, and (2) a mechanized proof in ACL2s showing that Floodsub is a simulation refinement of Broadcastsub. We discuss related work in Section 5 ; and ours is the first mechanized refinement-based verification of a real world pubsub protocol. While refinement is a standard formal method, it has never been previously applied to P2P pubsub protocols like FloodSub. Our models and proofs are publicly available in our repository [ 22 ] . Overall, our code consists of 476 theorems proved, and 10277 lines of lisp code. Paper Outline. Section 2 describes Floodnet and Broadcastnet models for Floodsub and Broadcastsub, respectively. Section 3 describes the refinement theorem. Section 4 is a discussion about the theorem proving process and effort that went into this proof. Section 5 discusses related work. Section 6 concludes. 2 Model Descriptions We model Floodsub and its specification Broadcastsub using transition systems consisting of states and transition relations (boolean functions on 2 states) that depend on transition functions. We call our models Floodnet and Broadcastnet respectively. In this section we will explain each of our transition system models in a top-down fashion. The state models are self explanatory. The interesting parts of the following code listings are the transition relations, where we place conditions, not only as sanity checks or for cases, but also as guards to disallow illegal behaviour, like requiring that a peer leaving a network is already in the network. We will discuss such conditions in detail. 2.1 Broadcastnet The state of a Broadcastnet is stored in a map from peers to their corresponding peer-states. We represent peers by natural numbers. A Broadcastnet peer state is a record consisting of (i) pubs : the set of topics

Read the complete text