Papers for

distributed systems developers

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.

Symbolic method speeds probabilistic timing models verification hundredfold

Symbolic Abstraction Refinement

Abstract: Autonomous systems choose actions whose outcomes are uncertain and are subject to time constraints. Probabilistic timed automata (PTAs) model exactly this, and verifying one answers a question about the system's decision-making: the maximum probability of reaching a goal, or the minimum probability of reaching a hazard, that a controller can guarantee. Verification normally works over symbolic states, each pairing a discrete location with a region of clock values, and its difficulty is that the best behavior generally varies within such a region. The PRISM verifier's most capable PTA method responds by splitting regions until each is uniform, rebuilding the transitions that reach them and propagating the split backward through the state graph of a stochastic game, a cascade of graph reconstruction that partitions regions the property never depends on. We present SYMAR, which instead makes the value function symbolic: each symbolic state carries a function from sub-regions of its clock region to probability bounds, so refinement is the appearance of new sub-regions in that function, and previously generated states are never split nor their incoming transitions reconstructed. Both sources of PTA nondeterminism, the timing and the choice of actions, are captured implicitly by the preimage computation that produces those sub-regions. Heuristic forward search then bounds how much refinement is done at all, expanding an And-Or graph from the initial state along the most promising behaviors so that effort is confined to the property-relevant fragment, guided by bounds and preferred actions from a single unrefined run of the existing method; a partial-refinement backup keeps the otherwise combinatorial sub-region count lean, and every stored interval provably contains the true probability. On the PRISM PTA benchmarks, whose subproblems recur in autonomous systems (distributed agreement under contention, leader election, and self-configuration without central coordination), SYMAR is up to 108x faster, solves an instance on which the existing method exhausts the time limit, and is markedly less sensitive to the deadline constant, resolving one instance in a 37-node search graph, unchanged as the deadline triples, where the existing method needs 86,380 abstract states and 73 refinement rounds.

Tue 17 NovArtificial Intelligence
The gist
Verifying autonomous systems that make timed decisions with uncertain outcomes is complicated because their behavior can vary continuously over time. The authors introduce SYMAR, a new technique that represents time more flexibly and avoids repeatedly rebuilding complex parts of the system model. This approach narrows verification effort to the most relevant time ranges and outcomes, making it much faster and more scalable than previous methods. The authors show SYMAR works well on common benchmark problems involving decision-making without central control.
Open → 2611.22404v1

Safety problems in networks with shared counters become solvable under restrictions

Safety Analysis of Parameterized Networks with Shared Counters

Abstract: We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.

Fri 13 NovLogic in Computer Science
The gist
The paper looks at computer networks with many processes sharing counters that can be changed or checked for zero. It studies whether a certain state can be reached by one or all processes, which is usually impossible to decide. The authors found that if there is only one counter or if zero-checks are not allowed, these problems become solvable with efficient methods. Their work helps understand exactly when these types of safety checks can be done by computers.
Open → 2611.18175v1

Generalized sorting matches ordinary sorting efficiency with new algorithm

A Near-Optimal Generalized Sorting Algorithm

Abstract: We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $Θ(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+Ω(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.

Thu 5 NovData Structures and Algorithms
The gist
Sorting is how computers organize lists into order using comparisons. Sometimes, only certain pairs of items can be compared, which makes sorting harder. The authors studied this problem and found a way to sort nearly as quickly as normal sorting, even with these restrictions. Their method uses only a small number of comparisons, close to what standard sorting algorithms require. This shows that limiting which items can be compared doesn’t have to slow down sorting much.
Open → 2611.08397v1

New algorithms reduce congestion in connecting network graphs

Sublinear Approximations for Spanning Tree Congestion

Abstract: The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by deleting an edge of \(T\). In the spanning tree congestion problem we are asked to compute a spanning tree with minimum congestion. We describe two sublinear-ratio approximation algorithms for the spanning tree congestion problem (STC): a simple $\Ot(n^{8/9})$-approximation, and a more involved $\Ot(n^{2/3})$-approximation, where the notation $\Ot$ hides factors polynomial in $\log n$.. Until now, no algorithm with sublinear ratio was known. We also prove that for any fixed $0<\varepsilon<1$, approximation of the spanning tree congestion within $2-\varepsilon$ is NP-hard. This improves the previous best known lower bound $6/5$.

Wed 4 NovData Structures and Algorithms
The gist
Spanning tree congestion measures how crowded connections get when linking all points in a network using a tree structure. The authors developed new methods that find ways to connect all points with less congestion, improving on previous approaches that couldn't guarantee much better than the worst case. Their algorithms approximate the minimum congestion much more efficiently than before, and they also show it's very hard to find near-perfect solutions quickly. This work helps understand limits and possibilities for optimizing network connections.
Open → 2611.06209v1

Faster updates for dynamic graph maximal independent sets against adaptive changes

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

Abstract: We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was $O(m^{2/3})$, given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least $m^{1/2-o(1)}$ update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with $\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24})$ update time against adaptive adversaries. This gives the first polynomial improvement over the $m^{2/3}$ bound for adaptive fully dynamic MIS.

Wed 4 NovData Structures and Algorithms
The gist
Maintaining a special selection of points in a changing network, where no two chosen points connect directly, is important but can be slow when the network changes unpredictably. Previous fast methods only worked if the changes were fixed ahead of time, and slower methods existed for more adaptive situations. The authors created a new method that speeds up updating this selection even when changes depend on previous outcomes. Their approach is the first to improve the speed significantly over older methods in this adaptive setting.
Open → 2611.05932v1

Compact routing methods improve path efficiency with low memory use

Optimal (Randomized) Compact Routing Schemes

Abstract: Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.

Tue 3 NovData Structures and AlgorithmsNetworking and Internet Architecture
The gist
Routing messages efficiently in networks is tricky when each node can only remember a small amount of information. The authors study how to balance short travel paths for messages with minimal storage at each node in various routing models. They present new schemes that reduce the average path stretch (extra distance traveled) while keeping memory use low, sometimes using randomness in routing decisions. Their schemes improve on previous methods and are even proven optimal under certain theoretical assumptions. These improvements apply to both weighted and unweighted networks.
Open → 2611.04744v1

Verusweave benchmark tests fixing proofs in concurrent rust code

VerusWeave: A Benchmark for Proof Repair in Concurrent Verus Programs

Abstract: Concurrent software underpins critical infrastructure, including operating systems and databases, yet thread interactions can have bugs that bypass conventional testing. Verus extends Rust with formal verification capabilities, enabling developers to specify, implement and prove the correctness of concurrent code in the same language. Although coding agents have been explored for automated proof construction, existing Verus benchmarks offer limited coverage of concurrency-specific examples that connect atomic operations to abstract protocols. To address this gap, we introduce VerusWeave, the first benchmark dedicated to concurrent proof repair, derived from four open-source projects. It comprises 75 focused tasks and 17 full-module variants that exercise features used to verify low-level concurrent code. Tasks remove selected proof annotations and require agents to fill gaps, while preserving executable code and specifications. The evaluation harness validates repairs using Verus and a change checker, recording solutions, execution traces, and resource usage. An initial evaluation of four general-purpose coding-agent harnesses achieved 75-85% success on focused tasks and 29-47% on full-module variants, highlighting the challenge of autonomous module-wide repairs. VerusWeave provides a reusable foundation for evaluating automated proof construction for concurrent software.

Fri 30 OctSoftware EngineeringArtificial IntelligenceLogic in Computer Science
The gist
Concurrent software, like the kind inside operating systems, is tricky because threads can cause subtle bugs. The authors created VerusWeave, a set of programming puzzles that test if automated tools can fix missing or broken logical proofs in verified Rust code handling concurrency. These puzzles come from real projects and focus on connecting low-level operations with the bigger correctness rules. Their tests show fixing entire modules automatically is still hard, making VerusWeave a useful tool for improving such automation.
Open → 2611.00287v1

Approximating minimum spanning trees despite corrupted distances

Approximating Minimum Spanning Trees in Metrics under Semi-Random Corruptions

Abstract: We study the problem of finding minimum spanning trees in semi-random corrupted metrics. In this problem proposed by Bateni, Dharangutte, Jayaram, and Wang (COLT'24), we start with a metric space $\mathcal{M} = (X, d)$. The adversary independently corrupts each pairwise distance with probability $p$. The algorithm only observes these possibly corrupted distances and must output a spanning tree whose expected cost (in the true metric) is multiplicatively close to the minimum spanning tree cost. Prior work showed that losing a factor of $Ω(\log n)$ is necessary, even if the algorithm may adaptively select $O(n/\log n)$ points and probe the true distances between them. However, no upper bounds were known. We study three regimes based on whether the adversary can only increase, decrease, or arbitrarily change the corrupted distances. We show the following: (1) In the increase-only setting, we give a polynomial-time $O(1)$-approximation algorithm for any constant $0 \le p < 1$. (2) In the decrease-only setting, we give an $O(\log n)$-approximation algorithm for any constant $0 \le p < 1$. Additionally, we show an $O(\log^4 n)$-approximation algorithm that runs in quasi-polynomial time $n^{O(\log n)}$, for any constant $p \leq 0.1$. Moreover, we show that a polynomial-time algorithm computing an $n^{1/3-\varepsilon}$-approximation is unlikely to exist. (3) In the general setting, where the adversary can both increase and decrease distances, we show an $O(\log n)$-approximation algorithm for every $0 \leq p < \frac{1}{4}$. Further, we show that no $o(n)$-approximation is possible for $\frac{1}{2} \leq p < 1$. Our algorithms answer the main open question in Bateni et al.'s work; moreover, the $O(\log n)$-approximations in the latter two settings are information-theoretically optimal.

Thu 29 OctData Structures and Algorithms
The gist
Finding the cheapest way to connect points (a minimum spanning tree) can be tricky if distances between points might be wrong or altered. The authors study what happens when some distances get corrupted randomly, and they develop algorithms that still find roughly good connections despite these errors. They investigate different cases—when errors only make distances bigger, only smaller, or both—and provide different guarantees on how close their solutions can get to the true best. Their work answers open questions about how well we can do in these challenging situations.
Open → 2610.40594v1

How group interactions shape spreading dynamics on complex networks

Spreading Dynamics on Higher-Order Networks: A Structure-Mechanism-Behavior Perspective with Applications

Abstract: Spreading in real-world networks, including modern communication and networked systems, often unfolds through group interactions rather than isolated pairwise contacts. Higher-order network representations such as simplicial complexes, hypergraphs, and their temporal, multilayer, and directed extensions provide a principled way to encode group interactions. Unfortunately, existing studies on spreading over these substrates remain fragmented and largely model-centric, offering limited insight into how higher-order representations and contagion mechanisms jointly shape emergent dynamics. This review addresses this gap by introducing a structure-mechanism-behavior three-level perspective that provides a systematic mapping from higher-order network structures and spreading mechanisms to collective behaviors. Within this framework, we compare how different higher-order network representations encode group interactions, introduce a taxonomy of contagion mechanisms, and analyze their structural carrying capacity, defined as the ability of a given representation to support specific contagion mechanisms and the associated dynamical behaviors. We further map specific structure-mechanism combinations to three hallmark emergent behaviors, thereby offering a unified cross-level perspective beyond existing model-centric surveys. These insights are particularly relevant for communication systems involving group interactions, such as social information spreading, cooperative protocols, and distributed networked processes. Lastly, leveraging this three-level perspective, we offer a roadmap for guiding and controlling dynamics on higher-order networks, while discussing future directions in representation choice, mechanism design, and data-driven inference.

Thu 29 OctSocial and Information Networks
The gist
Many real-world spreading processes, like how information or diseases spread, happen in groups rather than just between two people. The authors review different ways to represent these group interactions in network models and explain how these shapes and contagion methods together influence the outcomes. They introduce a three-level view linking structure (how groups connect), mechanism (how spreading works), and behavior (what patterns emerge). This helps explain and predict spreading in social networks, communication systems, and distributed processes better than focusing on single models.
Open → 2610.39297v1

Vertex fault tolerant spanners with improved size efficiency

New Fault-Tolerant $(α,β)$-Spanners

Abstract: We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(α,β)$-spanner is a subgraph of $G$ that preserves an $(α,β)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(α,β)$-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing $f$-VFT $(α,β)$-spanners that improve the dependence on $f$, reducing it to polynomial overhead. For every unweighted graph $G=(V,E)$ on $n$ vertices, stretch parameter $k$, and fault parameter $f$, we show: (i) $f$-VFT $(O_ε(k^ε), O_ε(k))$-spanners with $\tilde{O}(f^{exp(1/ε)}\cdot n^{1+1/k})$ edges for any $ε\in (0,1)$. For any fixed constant $ε$, this introduces a $poly(f)$ overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any $δ\in (0,1)$, an $f$-VFT $\left(O_δ(\sqrt{k}),O_δ(k) \right)$-spanner of size $\tilde{O}(f^{1+δ} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+δ}$ compared to the above-mentioned non-faulty analogs. (iii) $f$-VFT $(k,k-1)$ spanner of size $O(k^3 \cdot f \cdot n^{1+\frac{1}{k}})$, nearly matching the lower bound $Ω(f^{1-\frac{1}{k}}n^{1+\frac{1}{k}})$ known for $f$-VFT $(2k-1,0)$ spanners by [Bodwin et al., SODA 2018]. The first result is obtained via a new adaptation of the Baswana--Sen framework to the VFT $(α,β)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.

Sat 24 OctData Structures and Algorithms
The gist
This paper tackles the problem of building networks that stay efficient even when some nodes fail. The authors improve previous methods to create smaller backup networks that still maintain good connectivity despite multiple vertex failures. Their constructions reduce the extra size needed to handle faults from an exponential to a polynomial factor, meaning the networks are much less bloated. They achieve these advances by adapting a known clustering method and analyzing a fault-tolerant greedy approach.
Open → 2610.33934v1

Intelligence extends itself by creating new meanings and purposes

Co-Recursive Semantic Self-Extension: A Mathematical Foundation for Open-Ended Intelligence

Abstract: Artificial intelligence has advanced through scale, data, and computation, yet remains bounded by its representational framework. We ask what makes intelligence open-ended. Every inferential system selects meaningful distinctions, limiting what it can learn. Within a fixed purpose, performance reaches a ceiling set by its semantic domain. Teleological succession, in which purposes arise from earlier ones, faces a similar limit: Boolean-closed purpose-transformations exhaust their reachable semantic territory. We shift from purposes to inferential systems. Drawing on Kant and Gödel, we model cognitive states as partial evaluations over a formal language. Unresolved propositions may be undecided or undecidable. Reasoning can resolve the former but not the latter, leaving a frontier for extension. Non-trivial reductions of undecidable propositions expose undecidable intermediate premises whose reflective reification supports multiple decisive extensions. Finite trace-guided generation remains fallible, requiring meta-level selection and polycontextural exploration. Using Kolmogorov complexity, we show that no architecture with a fixed state description, transition mechanism, and initial condition can generate histories incorporating irreducible algorithmic information. Because physical systems are fixed in this sense, we examine collectives. Coupling finitely many finite agents does not remove the bound. Extension requires persistent external memory preserving semantic content and historical coordinates. Collective generative capacity depends on balancing overlap for transfer with difference for generation. We propose semantic self-extension as a design principle: intelligence should not merely resolve ambiguity within existing meanings, but transform unresolved structures into new spaces of meaning, generating new distinctions, questions, representations, and purposes.

Thu 22 OctArtificial Intelligence
The gist
Intelligence usually learns and solves problems within fixed ideas and goals, which limits how much it can grow or adapt. The authors explain that true open-ended intelligence needs to go beyond just working with existing ideas; it should be able to create new meanings, questions, and goals by exploring what can't be fully decided or solved yet. They use mathematical and philosophical ideas to describe this process and show why fixed systems can’t fully generate new complexity on their own. They suggest that intelligence grows by continually expanding its own framework instead of staying within old limits.
Open → 2610.31097v1

Deterministic methods speed up information spread in radio networks

Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Abstract: We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $\{1,\ldots,N\}$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted; collision detection is unavailable. Our protocol combines amplified reception certificates, adaptive pruning, and permutation selectors. Each pruning iteration costs $\mathcal O(n\log^2n\log\log n)$ rounds. A two-step quadratic contraction limits each receiver and each class of identical closed in-neighborhoods to $\mathcal O(\log\log n)$ qualifying selections. Under an explicit degree-concentration condition, our protocol takes $\mathcal O(m\log^2n(\log\log n)^2)$ rounds. For directed regular graphs with common in- and out-degree $Δ$, our strategy achieves $\widetilde{\mathcal O}(\min\{n\sqrtΔ,n^2/Δ\})$, extending the identifier range of Wu and Chrobak and improving their high-degree bound. At completion entry, let $a\ge1$ count original sources not yet credited as globally disseminated. Permutation selectors reduce our balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. Our geometric protocol attains $\widetilde{\mathcal O}(k^2+nτ+\min\{u^2,(nu)^{2/3}\})$ for an original path cover of scale $k$, weight $τ$, and $u$ exceptions. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs. Within the stated graph classes and identifier ranges, these results answer the polynomial-identifier and average-degree questions of Wu and Chrobak. The unrestricted general-graph cases remain open.

Tue 20 OctData Structures and AlgorithmsComputational ComplexityDistributed, Parallel, and Cluster Computing
The gist
Broadcasting information in wireless networks where messages can collide is challenging, especially when the network layout is unknown. The authors present a new step-by-step approach to ensure messages from all sources reach every node efficiently without random guessing. Their protocol carefully prunes communication paths and uses smart selections to reduce delays. This advances understanding for networks with certain structures and address ranges but leaves more complex cases open.
Open → 2610.28930v1

Parallel greedy matching keeps vertex connections stable in random graphs

Degree Stability of Parallel Greedy Matching in Random Graphs

Abstract: We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.

Sun 18 OctDiscrete MathematicsData Structures and Algorithms
The gist
The paper looks at a process where points in a random network try to pair up with neighbors each round, removing those matched pairs from the network. The authors show that even after many rounds, points still keep many of their initial connections, meaning the network remains well connected for a long time. This stability helps match a consistent number of points each round. Their work uses careful mathematical tools to track how each point’s connections shrink over time instead of just looking at overall trends.
Open → 2610.25507v1

Fast Tendermint agreement bug exposed and two fixes proposed

Revisiting Fast Tendermint: An Agreement Violation and Two Repairs

Abstract: Fast Tendermint reduces Tendermint's good-case latency to two communication steps for n>=5f+1. We show that its published round-change rule violates Agreement: one Byzantine process suffices for every f>=1, and for f>=2 two Byzantine processes suffice without double signing. The failure occurs when a process advances past a round without recording the value that may have been decided there. The Quint specification that accompanies the protocol does not allow this kind of round skipping and is not affected; the violation lies in the published pseudocode. We present two repairs. Walk requires a process to leave each round on a quorum of that round's precommits and to precommit before leaving. It keeps the recorded valid state and removes the wait after a precommit quorum. Justify carries the evidence needed to accept a proposal in the proposal itself, removing both the recorded valid state and the proposer's synchronization wait. Both satisfy Agreement and Validity under asynchrony and Termination under the partially synchronous gossip model of Tendermint and Fast Tendermint. Both retain proposal timeouts. The main text presents the executions that violate Agreement and explains the two repairs. The appendices provide proofs, a brief comparison with other round-change designs, and an extension to chains.

Mon 12 OctDistributed, Parallel, and Cluster ComputingCryptography and Security
The gist
Fast Tendermint is a method for agreeing on a decision quickly in a network even if some participants are dishonest. The paper shows that the current published rules can lead to disagreements if even one participant acts badly, breaking the system’s fundamental promise. This happens because a participant can skip important steps without recording key information. The authors offer two fixes that guarantee agreement and keep the system reliable, even with some network delays and dishonest actors.
Open → 2610.16442v1

Network design method boosts connectivity using density graphs and learning

Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion

Abstract: This paper studies an open network design problem of constructing graph topologies with maximum algebraic connectivity under fixed numbers of vertices and edges. A density-dependent approach is proposed that decomposes the design task into two stages: a high-quality, low-cost structural backbone construction and a reinforcement learning completion stage. The method selects the backbone based on density, using complete multipartite graphs in dense regimes and Cayley graphs in low-to-intermediate regimes, and then refines the remaining edges through a learning-based procedure. Numerical results show that the proposed method achieves high algebraic connectivity with favorable runtime scalability, outperforming existing methods. These results support a structural-family-first strategy for scalable network design.

Thu 8 OctMachine Learning
The gist
Finding the best way to connect points in a network with a fixed number of connections is hard. The authors propose building a strong basic structure depending on how dense the network is, then using learning techniques to add remaining connections wisely. This two-step approach achieves better overall connectivity and runs efficiently, beating some earlier methods. It shows that starting with a good main structure helps make large networks perform better.
Open → 2610.12697v1

Robots meet reliably using fixed distance despite disoriented views

Rendezvous under Variable Disorientation:The Algorithmic Power of Fixed Unit Distance

Abstract: We study deterministic Rendezvous of two robots with lights under weak geometric and synchronization assumptions. Our focus is on Variable Disorientation (VD), where each robot may arbitrarily rotate, reflect, and rescale its local coordinate system at every \Look, and on VD+Fixed-Unit-Distance (FUD), where each robot's local unit distance remains fixed. We consider the one-sided visibility models FSTA and FCOM, and schedulers ranging from the energy-restricted RSYNCH and R-RSYNCH to fully asynchronous executions. Under VD, we prove color-independent impossibility results for FSTA under SSYNCH and for FCOM under ASYNCH, and establish sharp two-color boundaries under RSYNCH and R-RSYNCH. Under VD+FUD, we introduce periodic distance classes, which turn multiplicative changes of the physical distance into predictable cyclic phase shifts. This technique yields a two-color self-stabilizing non-$L$-Rendezvous algorithm for both FSTA and FCOM under RSYNCH and R-RSYNCH even with Non-Rigid movement. Under Rigid movement, periodic distance classes further yield an optimal three-color non-quasi-self-stabilizing algorithm for FSTA under SSYNCH, a four-color FSTA algorithm under $M$-atomic ASYNCH, and a four-color FCOM algorithm under CM-atomic ASYNCH. By guarding the latter phase mechanism with two additional colors and replacing its initial swap by passive initialization, we obtain a six-color FCOM algorithm under full ASYNCH, improving the previous twelve-color upper bound by a factor of two. These results show that a fixed local metric can serve as persistent cyclic memory, and clarify how metric stability, one-sided visibility, and scheduler atomicity jointly determine Rendezvous solvability and color complexity.

Wed 7 OctDistributed, Parallel, and Cluster Computing
The gist
This paper studies how two simple robots can find each other (rendezvous) even when each one sees the world differently – sometimes rotated, flipped, or stretched. The researchers show that if each robot keeps a fixed idea of unit distance, they can use this consistent measure as a kind of memory to coordinate their moves. They design color-based light signals and movement rules that let robots meet under varied conditions, including unpredictable schedules and limited visibility. Their work also clarifies the limits of such rendezvous strategies when this fixed distance information is missing or weaker.
Open → 2610.09713v1

Translating bach programs for better verification of shared data

Modelling Shared-Space Coordination in mCRL2: a Bach-to-mCRL2 Translation Framework

Abstract: Although significant research has focused on the theory and implementation of data-based coordination languages, the critical aspect of their automated verification using model-checking techniques remains underexplored, which is essential for ensuring reliability and correctness in distributed systems. Existing tools, such as Anemone, provide a solid foundation for reachability-based verification of Bach programs. While they effectively analyze properties expressed in terms of state attainability, extending support to more expressive temporal specifications-such as liveness properties or invariants over shared space contents-remains an open opportunity. Such extensions are important to capture comprehensive system behaviors, for instance, ensuring that "a request is always matched by a response" or that "no message is silently lost". Addressing this limitation, we propose an automated translation from Bach to mCRL2, which explicitly represents the shared space, thereby enabling the use of mCRL2's mu-calculus model checker to verify complex properties beyond simple reachability. Complementing this translation, we introduce a systematic method to analyze the shared space in mCRL2 concerning data reachability, by directly expressing properties over the shared space's contents in the mu-calculus, thus providing a clearer framework for verification. This approach enables a novel verification process that combines action-based properties with state-based properties over the shared space contents, a largely unexplored area in current coordination-language verification approaches, offering a new dimension of analysis

Tue 29 SeptLogic in Computer ScienceProgramming Languages
The gist
Making sure complex computer systems work right is hard, especially when many parts share and change data. The paper shows how Bach programs, which coordinate data sharing, can be translated into another language called mCRL2. This helps check not just if states can happen, but also if important ongoing rules are followed, like responses always matching requests. The authors also provide a way to write and check these detailed rules directly about the shared data, improving how system correctness is verified.
Open → 2609.37726v1

Cobalt speeds up distributed large model training by reducing data transfer

Cobalt: Leveraging Expert Co-activation for Efficient Distributed MoE Training

Abstract: Mixture-of-Experts (MoE) has increasingly become a mainstream approach for scaling large language models, as it expands model capacity while keeping computation cost nearly constant. Training large-scale MoE models relies on Expert Parallelism (EP), which distributes expert replicas across GPUs and exchanges tokens through all-to-all communication. The efficiency of EP is often constrained by two system bottlenecks: cross-node token transfers are limited by inter-node bandwidth, while skewed expert workloads lead to imbalanced computation across GPUs. Prior work mitigates these bottlenecks based on per-expert workload statistics, but overlooks the fact that experts could share the communication. In this work, we empirically present the observation that many pairs of experts are frequently co-activated by individual tokens. Motivated by this, we present Cobalt, an efficient MoE training framework that leverages expert co-activation to reduce cross-node traffic and workload imbalance. Cobalt adopts a two-stage expert layout planner that adapts expert layout to the evolving expert co-activation and workload conditions. It periodically co-locates frequently co-activated experts on the same node to reduce the cross-node communication, and performs per-step intra-node adjustment to rebalance the workloads. Subsequently, we develop a communication-aware task assignment method that routes tokens to fewer remote nodes based on the current expert layout. Experiments on 32 B200 GPUs show that Cobalt achieves up to 1.53-2.41 times (1.28-1.89 times on average) of speedup compared to existing MoE training frameworks, while reducing cross-node token traffic by 75.74%-99.26%.

Tue 29 SeptDistributed, Parallel, and Cluster Computing
The gist
Training very large language models often uses a method called Mixture-of-Experts where different parts of the model handle different pieces of data. But sharing data between computers can slow things down, especially when some parts get more work than others. The authors observed that some parts of the model often work together on the same pieces of data. Using this insight, they designed Cobalt, a system that organizes these parts to reduce slow data transfers and balance the work better. Their experiments show that Cobalt can speed up training significantly while cutting down the amount of data sent between computers.
Open → 2609.36959v1

Simple shortest-path trees give good low-stretch spanning trees

Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm

Abstract: Given an undirected weighted graph $G$, a $γ$-approximate low-stretch spanning tree (LSST) $T \subseteq G$ is a tree that approximates the distance metric of $G$ up to a $γ$-factor in expectation. Currently, existing algorithms to find a provably good LSST carefully construct an approximate shortest-path tree from an arbitrary source. The resulting algorithms are intricate. In contrast, practitioners observed that a much simpler heuristic performs surprisingly well: choose an arbitrary root, run Dijkstra's algorithm, and use the resulting shortest-path tree as an LSST. In this paper, we give a smoothed analysis of shortest-path tree algorithms, such as Dijkstra's algorithm, that explains this behavior. We show that adding a small perturbation to the weights of the input graph suffices to turn the shortest path tree rooted at an arbitrary node in the resulting graph into an $\tilde{O}(1)$-approximate LSST. We further show that the set of perturbations can be computed efficiently from few low-diameter decompositions (LDDs). Thus, our proof is also constructive in the sense of giving a novel approach to computing LSSTs.

Mon 28 SeptData Structures and Algorithms
The gist
Finding a tree inside a network that keeps distances roughly the same is usually complicated. The authors explain why simply picking any starting point and running a shortest-path algorithm like Dijkstra’s often works well in practice. They show that if you slightly adjust the network's edge weights, this simple method reliably finds a good approximation. Their approach also gives a new way to efficiently compute such trees.
Open → 2609.35136v1

Signature-free blockchain methods cut consensus delays significantly

Simple and Fast Signature-Free Blockchain Consensus

Abstract: Signature-free protocols avoid the cost of post-quantum signatures. We present two simple signature-free blockchain consensus protocols for eventual synchrony with optimal good-case commit latency (three message delays for \(f<n/3\) and two for \(f<n/5\)), optimistic responsiveness, a block time of only two message delays without speculation, and \(O(n^2)\) communication per view. They instantiate Generic Simplex, a blockchain consensus construction parameterized by a new abstraction called view agreement. The same construction also captures Simplex, Minimmit, and a new synchronous signature-free protocol with optimal good-case commit latency of two message delays for \(f<n/4\).

Sat 26 SeptDistributed, Parallel, and Cluster Computing
The gist
Blockchain systems need to agree on the order of transactions, which often requires complex digital signatures that could be vulnerable to quantum computers. The authors present new ways to reach consensus without these signatures, making the process faster while keeping security guarantees under certain network conditions. Their methods reduce the number of communication steps needed to confirm transactions and work efficiently even when some participants behave badly. These protocols use a new concept called view agreement to coordinate participants reliably.
Open → 2609.32985v1

HyperParallel-FSDP speeds up training of massive AI models on Ascend SuperPods

HyperParallel-FSDP: Topology-Aware Fully Sharded Training with Layout-Driven Muon on Ascend SuperPods

Abstract: Declarative SPMD programming uses tensor sharding descriptions to drive distributed execution, separating parallelization from model code. However, the evaluated PyTorch DTensor stack dispatches every operator below autograd, incurring repeated dispatch and metadata costs, while lacking an inexpensive end-to-end validation path. Existing FSDP and distributed Muon implementations also mismatch two-tier supernode topologies: FSDP relies on explicit parameter packing and unpacking, and Muon's whole-matrix orthogonalization conflicts with parameter sharding. We observe that distributed tensors need only express sharding semantics at the tensor API boundary above autograd, allowing differentiation and kernels to operate on plain tensors. Based on this insight, we present HyperParallel-FSDP, featuring: (1) dual-mode DTensor execution, using one sharding plan for both a production mode with one-time layout resolution and no steady-state dispatch overhead, and a validation mode with end-to-end metadata propagation, fail-fast checks, and gradient-equivalence testing; (2) topology-aware FSDP, with zero-copy intra-supernode collectives, fused inter-supernode reduction, and a cross-layer backward pipeline that avoids waits on slow links; and (3) layout-driven distributed Muon, with sharding-derived communication groups, deduplicated orthogonalization, and shape-fused Newton-Schulz iterations. On Atlas 900 A3 SuperPoD, HyperParallel-FSDP scales from 16 dies to 384 cards (768 ranks), sustaining 421k tokens/s for a 505B-parameter MoE while FSDP communication uses 2.9% of step time. It reduces mean step time by 29.7% versus PyTorch FSDP2 and 25.5% versus Megatron DDP, with Pearson correlation above 0.999997 over 1,000 steps. Distributed Muon improves profiler step time by 5.4-16.0% over competing systems. Source code is available at https://atomgit.com/mindspore/hyper-parallel.

Fri 18 SeptDistributed, Parallel, and Cluster Computing
The gist
Training very large AI models requires splitting them across many processors efficiently. The authors noticed inefficiencies in existing tools that slow down communication and checks during training on specialized Ascend hardware. They designed HyperParallel-FSDP, which organizes data and computation to reduce overhead and improve validation without repeating costly steps. Their system runs much faster than other approaches, handling models with over 500 billion parameters while using fewer communication resources.
Open → 2609.21594v1

Cloud native MPI enables selective process relocation for resilient computing

XMPIaaS: Towards Cloud Native MPI via Cooperative Process Migration

Abstract: Message Passing Interface (MPI) has been the dominant programming model for High Performance Computing (HPC) for three decades, and as HPC workloads increasingly migrate to cloud infrastructure for scalability and cost efficiency, MPI applications must contend with an execution environment fundamentally unlike traditional supercomputers: ephemeral resources, dynamic pricing and preemptable instances. In such a volatile setting, the ability to relocate running MPI processes between nodes without restarting the job is a necessity for cost-effective, resilient execution. Existing approaches either require restarting the entire job from a global checkpoint, or transparently intercepting the full MPI stack at prohibitive complexity. To address these challenges, we propose \name, a cooperative migration system for MPI that enables selective process group migration on-the-fly. When a cloud instance is scheduled for preemption, only the affected ranks are relocated while the remaining processes briefly quiesce and resume in place, avoiding the cost of a full-job checkpoint. \name tackles this through a cooperative protocol between the MPI process management runtime and rank processes. We expose an \texttt{XMPI\_quiesce} interface built atop the MPI Sessions API that allows applications to mark safe migration points, and we extend the Hydra process manager to orchestrate the full migration lifecycle: rank quiescence, CRIU checkpoint/restore, proxy relaunch on the target node, and seamless rank reconnection. We evaluate and show that the cooperative quiesce phase accounts for less than 1.4\% of total migration downtime, and that this downtime is governed by the migrating node's rank count alone, independent of job size, and the instrumentation introduces no measurable overhead during normal execution.

Tue 15 SeptDistributed, Parallel, and Cluster Computing
The gist
High Performance Computing (HPC) programs use MPI to communicate between many computers working together. Moving these programs to the cloud is tricky because cloud computers can stop suddenly or change often. The authors created a system called XMPIaaS that lets parts of these programs move between computers without stopping the whole program. This helps programs keep running smoothly even if some cloud computers are taken away. Their system works efficiently and doesn’t slow down normal program operation.
Open → 2609.16531v1

Sublinear size coalitions can control outputs in complex systems

A Resolution of Friedgut's Conjecture on Influential Coalitions

Abstract: We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

Mon 14 SeptComputational ComplexityDiscrete Mathematics
The gist
Figuring out which small groups of inputs can strongly influence the outcome of a complex function has been a tricky problem, especially when those inputs come from large sets. The authors proved that for any function taking many inputs, there's a relatively small group of them that can be set to force the output to a certain value with very high chance. This resolves a long-standing question and works even when inputs come from large or continuous sets. Their approach used clever encoding techniques and previously known structural insights to make this result possible.
Open → 2609.16401v1

Faster federated learning with first order bilevel optimization

Federated stochastic bilevel optimization with fully first-order gradients

Abstract: Federated stochastic bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning. However, most existing federated stochastic bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices, which leads to longer running times in practice. To address these challenges, we propose a novel federated stochastic variance-reduced bilevel gradient descent algorithm that relies solely on first-order oracles. Specifically, our approach does not require the computation of second-order Hessian and Jacobian matrices, significantly reducing running time. Furthermore, we introduce a novel learning rate mechanism, i.e., a constant single-timescale learning rate, to coordinate the update of different variables. We also present a new strategy to establish the convergence rate of our algorithm. Finally, the extensive experimental results confirm the efficacy of our proposed algorithm.

Mon 14 SeptMachine Learning
The gist
Training complex machine learning models often requires updates that involve heavy math, like second-order derivatives, which slow things down. The authors introduce a new method that avoids these slow calculations by using only simpler first-order information, making training quicker in federated (distributed) setups. They also design a stable learning rate approach that improves how different parts of the model update together. Their experiments show this method works well while saving time.
Open → 2609.16350v1

Deterministic labeling improves fault-tolerant connectivity checks in networks

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

Abstract: For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

Tue 8 SeptData Structures and Algorithms
The gist
Finding out if two points in a network stay connected after some connections fail can be tricky. The authors show a way to give each point and connection a short label so you can quickly tell if two points remain connected after some failures. Their method is both efficient and guaranteed to work for all possible failures up to a given size. This improves on earlier methods by making the labels smaller and by giving stronger guarantees without randomness.
Open → 2609.09031v1

Maximum mutual visibility sets found and built on cactus graphs

The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions

Abstract: Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are \emph{mutually visible} if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a \emph{Mutual Visibility Set} (\MVS) if every pair of vertices in $S$ is mutually visible. The concept of \MVS s in graphs has attracted significant attention since its introduction, as it provides an important structural property of graphs. However, determining a maximum \MVS\ in general graphs is computationally intractable; the decision problem of whether a graph admits an \MVS\ of size at least $k$ has been shown to be \emph{NP-complete}. Thus, prior work has focused on finding maximal \MVS s or restricting attention to specific graph classes. Cactus graphs form a fundamental low-treewidth class, yet the maximum \MVS\ problem for this class remains open. In this paper, we first determine the size of maximum \MVS~in cactus graphs, and introduce two self-stabilizing algorithms that construct such sets. The first algorithm uses a single BFS tree and stabilizes in $O(D)$ rounds with $O(\log n)$ bits per process on average; the second one uses parallel BFS trees and stabilizes in $O(|C_{\max}|+|T_{\max}|)$ rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where $|C_{\max}|+|T_{\max}| = o(D)$.

Mon 7 SeptDistributed, Parallel, and Cluster ComputingDiscrete MathematicsData Structures and Algorithms
The gist
The paper studies a way to pick special points (vertices) on a network (graph) so that each pair can see each other clearly along shortest paths. Finding the largest such set is known to be very hard for general graphs. The authors focus on cactus graphs, a simpler kind of network, and figure out the exact size of the largest set. They also provide two algorithms that can run independently and eventually build these sets automatically in a distributed way.
Open → 2609.07253v1