Papers for

distributed system builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

New choreographic logic links program proofs and network behaviors

Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming

Abstract: A new approach to the theory of choreographic languages has recently been proposed, based on the interpretation of choreographies with finite behaviors as proofs in an extension of linear logic. This paper further develops this approach to cyclic proofs to be capable of representing infinite behaviors, and prove a completeness result for choreographies with respect to the class of lock-free networks. We show that in a choreographies-as-proofs correspondence, the proof equivalence induced by rule permutations corresponds to bisimilarity, and that, under adequate assumption on the procedure definitions, the proof search procedure has a finite search space, and can be used to extract a choreography from a network.

Wed 21 OctLogic in Computer Science
The gist
Communicating computers often follow preset sequences called choreographies to avoid confusion or deadlock. This paper shows how such choreographies can be analyzed and created using ideas from logic, treating them like mathematical proofs. The authors extend previous work to handle repeated or endless behaviors and prove their method fully captures a wide range of safe network interactions. They also show how to recover a choreography by examining the network communication patterns themselves.
Open → 2610.29736v1

Fast graph algorithms maintain connectivity and spanning trees instantly

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

Abstract: We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

Wed 30 SeptData Structures and Algorithms
The gist
Graphs show how things are connected, like roads between cities or friends in a network, and keeping track of changes quickly is important. The authors developed fast algorithms that update key graph properties, like whether everything stays connected or finding the cheapest way to link all points, even when connections change. These algorithms work quickly in the worst case and use randomness in a limited way that makes them reliable against tricky situations. This improves on previous approaches that were slower for certain problems.
Open → 2610.00491v1

Networks with two parents per agent achieve exact information aggregation

Optimal Networks for Agentic Information Aggregation

Abstract: We study information aggregation in the networked learning model introduced by Kearns, Roth, and Ryu (SODA 2026). There is a fixed distribution over $d$ features and a common label. Agents learn in topological order on a directed acyclic graph. Each observes a subset of the features and its parents' predictions, fits a linear predictor to minimize mean squared error, and passes only its prediction forward. The global predictor is the best linear predictor using all features. Kearns, Roth, and Ryu show that the output agent's error approaches the global predictor's error along sufficiently deep paths with suitable feature coverage, while insufficient depth can prevent aggregation even in large networks. In contrast to their main focus on a given graph and feature allocation, we consider the limits of the model under two settings. In the adaptive designer setting, a designer chooses the graph, feature allocation, and output agent knowing the distribution. In the oblivious designer setting, the designer fixes all three before an adversary chooses the distribution. Each agent observes one feature and receives predictions from a limited number of parents. We call the aggregation exact when the output agent matches the global predictor exactly. For $d\ge3$, we show that no finite depth guarantees exact aggregation for every distribution with one parent per agent, even when the designer knows the distribution. In contrast, two parents per agent suffice for exact aggregation even in the oblivious designer setting. A fixed graph, feature allocation, and output agent achieve this for every distribution at depth $O(d\log d)$. Knowing the distribution reduces the depth to $O(d)$. Both constructions use $O(d^2)$ agents, with a very large constant for two parents. We show the bounds on the depth and number of agents are all optimal up to constant factors.

Mon 28 SeptMachine LearningComputer Science and Game Theory
The gist
This paper looks at how groups of agents (or computers) can work together to learn from pieces of information they each see. The authors study how the way agents connect and share predictions affects how well they can match the best overall prediction using all information. They find that if each agent only gets one parent's input, it’s impossible to perfectly match the best prediction. But if each agent gets two parents’ inputs, then it is possible, even if the network design doesn’t know the information ahead of time. They also find efficient ways to build such networks with reasonable size and depth.
Open → 2609.35537v1

Precise executable Paxos pseudocode improves understanding and debugging

Specifying Paxos for System Builders: Pseudocode Made Executable

Abstract: This paper presents a precise executable specification---as a faithful mapping from the pseudocode---of Paxos for System Builders, a practical protocol for replication and consensus in distributed systems. Paxos for System Builders has both a robust implementation in C and a clean pseudocode for critical protocol details. This paper shows how the protocol pseudocode can be expressed easily, essentially line-by-line, in a precise high-level language, DistAlgo, for direct execution in distributed systems. Precise specification and direct execution help significantly in understanding the protocol logic and in automatically checking, tracing, and visualizing protocol runs. They also led to discoveries and fixes of small, difficult-to-catch omissions and liveness bugs in the pseudocode though not the C code. The resulting program also has acceptable performance while having similar size as the pseudocode.

Thu 10 SeptDistributed, Parallel, and Cluster Computing
The gist
Distributed computer systems need to agree on decisions reliably, but the rules for doing this, called Paxos, can be confusing and tricky to get right. This paper shows how the common Paxos instructions can be turned into a clear, step-by-step program that a computer can run directly. The authors found that doing this helped them spot small mistakes in the original instructions and understand how the system works better. Their program runs well and is about as simple as the original instructions.
Open → 2609.12239v1