Papers for

distributed system operators

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.

Local mining improves distributed event rule detection with less communication

Mine Locally, Verify Globally: Exact Recovery, Compilation, and Distortion of Mined Temporal Rules

Abstract: Specification mining extracts temporal rules that describe relationships between events in recorded system traces. Applying these rules in distributed monitoring systems is more difficult because observations come from different nodes, whose clocks may not be synchronized, and events may be lost or reordered during transmission. In this paper, we study how to aggregate the coverage of mined rules across observers, determine whether their temporal windows are needed during monitoring, and characterize their detection under event loss. Our evaluation uses IPv6 packet traces collected from 21 receivers across four continents. We show that local mining followed by global confirmation recovers centralized rule coverage under suitable conditions while substantially reducing communication overhead. In contrast, merging traces with unaligned clocks can distort coverage by introducing incorrect temporal matches. A window-gain criterion identifies rules that require temporal state, while our loss analysis and broker experiments demonstrate why contiguous losses can be more damaging than independent losses. The results identify separate requirements for aggregating observations, selecting monitor state, and handling event loss.

Wed 18 NovDistributed, Parallel, and Cluster ComputingLogic in Computer ScienceNetworking and Internet Architecture
The gist
When computers watch events happening on different machines, it’s tricky to combine what they see because clocks can be unsynchronized and some information might get lost. The authors studied how to collect and check patterns of these events efficiently by mining rules locally and then verifying them globally. This reduces the communication needed and still finds the important relationships between events. They also figured out when keeping track of timing details is important and how losing events affects detection accuracy.
Open → 2611.24902v1

Rounded vertex potentials certify exact maximum flow values efficiently

Rounded Potentials Certify Exact Maximum Flow

Abstract: The textbook certificate for maximum flow is lopsided: the cut takes one bit per vertex, while the flow takes one number per edge. Indeed, some graphs have $Θ(n^2)$ terminal pairs for which every maximum flow uses $Θ(n^2)$ edges. Yet we show that one short number per vertex suffices for both cut and flow: $n$ vertex potentials, each rounded to $O(\log(nW))$ bits, certify the exact maximum $st$-flow value in any directed graph with integer capacities at most $W$. Exact potentials can have exponentially large representations. Rounding them may violate flow conservation, but the total error across any cut is less than one unit, so integrality of cut capacities absorbs it. Checking conservation is local and linear in the capacities, allowing the same certificate to yield new bounds in four models (capacities are polynomially bounded unless stated otherwise): - Online annotated streaming. $\widetilde{O}(n)$ total cost (help plus space) for the maximum $st$-flow value, optimal up to logarithmic factors, answering a question of Thaler (ICALP 2016) on whether $o(n^2)$ is possible. - Broadcast proof-labeling. $O(\log(n+p))$-bit labels certifying a maximum $st$-flow value of $p$ in directed and undirected graphs with arbitrary capacities, optimal for $p\ge n^{Ω(1)}$, settling that regime of a question of Korman, Kutten, and Peleg (Distributed Computing 2010). - Merlin-Arthur verification. $\widetilde{O}(n^3)$ time and $O(n^3\log n)$ proof length for directed All-Pairs Max-Flow, improving on previous verification times of $n^{4+o(1)}$ for general capacities and $n^{3.5+o(1)}$ for unit capacities, and answering a question of Akmal (TheoretiCS 2024). - Nondeterministic algorithms. $O(n^{3.614})$ time for directed All-Pairs Max-Flow, or $n^{3.5+o(1)}$ if $ω=2$: the first subquartic bound for general edge capacities, answering a question of Trabelsi (SODA 2025).

Mon 16 NovData Structures and Algorithms
The gist
Finding the largest amount of flow between two points in a network usually requires complex data per edge. The paper shows that simple numerical labels on each vertex, with a small number of bits, can precisely prove the highest flow possible even in complex graphs. These rounded labels simplify checking and verifying maximum flows and enable faster algorithms for related problems. The authors also demonstrate improved methods for verifying flows in streaming data, distributed systems, and for computing flows between all pairs of nodes.
Open → 2611.20475v1

Load balancing split tasks optimize fragment counts for many bins

Load Balancing with Item Fragmentation and More Bins than Items: Linear-Time and Exact

Abstract: We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, ensuring that the loads of any two bins differ by at most one unit. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. This problem is NP-hard and there exists an $(\mathrm{OPT}+1)$-approximation algorithm that runs in $O(N \log N + B)$ time [Kobert et al., 2014]. The existing algorithm is employed by several widely used production codes for phylogenetic reconstruction. Here, we focus on the case $B \ge N$, that is, bins are at least as numerous as items. This setting arises pervasively in modern parallel and distributed systems, as well as in iterative algorithms that rebalance their workload at every step. In this context, bins are machines or machine cores, and items represent computational tasks (jobs). Our central contribution is a remarkably simple $O(N)$-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using $O(N)$ space. In particular, we prove that an optimum always exists in which every bin receives at most two fragments and provide a characterization of when one fragment per bin suffices. Our result strictly improves the $(\mathrm{OPT}+1)$-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time $(\mathrm{OPT}+1)$-approximation algorithm for the general setting, as it removes the dependency on the number $B$ of bins.

Fri 6 NovData Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
The gist
This paper studies how to spread tasks of different sizes across many machines so each machine does almost the same amount of work. Tasks can be split into smaller pieces assigned to different machines, but the goal is to keep the number of pieces per machine low. The authors focus on situations where there are more machines than tasks and find a simple, fast way to perfectly balance the load with the minimal number of task pieces per machine. This work improves on previous methods and helps systems where work is repeatedly redistributed across many processors.
Open → 2611.09267v1

Crash-tolerant local algorithms improve network stability under failures

Local Distributed Computation under Crash Failures

Abstract: We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors. We introduce consistent neighborhoods: partial radius-$R$ views that agree locally across surviving edges and are complete without crashes. For $R=T+\ell+1$, these views allow local simulation of $T$-round fault-free algorithms that remain correct on subgraphs, satisfying constraints wherever the radius-$\ell$ checking neighborhood contains no crash. On graphs with at most $n$ nodes and maximum degree at most $Δ\geq3$, we construct these views in $O(\min\{n,(Δ-1)^R,RΔf\})$ rounds when a crash bound $f\geq1$ is globally known; the first two bounds require no knowledge of $f$. For $Δ=2$ or girth greater than $2R$, including forests, $O(R)$ rounds suffice. Our upper bounds are essentially tight in suitable parameter regimes. One crash can force $Ω(n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $Δ\geq3$ and sufficiently large $R$, we prove a $(Δ-1)^{R-O(\sqrt R)}$ lower bound even with crashes restricted to round beginnings. We also prove an $Ω(ΔRf)$ lower bound when $R\geq4\lceil\log_{Δ-1}f\rceil+4$ and $n\geqΔRf$. For locally checkable labeling (LCL) problems, we preserve $O(\log^* n)$ complexity under any number of crashes whenever this bound holds without faults on all graphs with a fixed degree bound. In contrast, we construct an LCL on graphs of maximum degree at most five with fault-free complexity $Θ(\log n)$ and crash-tolerant complexity $Θ(n)$. Finally, any fault-free sinkless-orientation algorithm can be transformed to tolerate any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.

Tue 3 NovDistributed, Parallel, and Cluster ComputingData Structures and Algorithms
The gist
This paper looks at how to make local network computations reliable when some computers crash and stop working fully. The authors introduce a way to build consistent local views around each node that still work correctly even if some neighbors fail. They show how these local views allow existing fault-free algorithms to keep working with little extra delay in many cases. The paper also proves limits on how fast such fault-tolerant computations can be done and gives examples where crashes make tasks much slower.
Open → 2611.04898v1

Mixture of experts models reveal hidden routing vulnerabilities in fine tuning

Characterizing Recoverable Expert-Utilization Signatures in Fine-Tuned Mixture-of-Experts LLMs

Abstract: As Mixture-of-Experts (MoE) large language models are increasingly deployed in distributed environments, from federated learning to edge-cloud systems, their architecture harbors an underexplored landscape of security vulnerabilities. Moving beyond textual analysis, we uncover structural memorization: a novel vulnerability where a fine-tuned model memorizes not only its training data but also the internal pathway used to process it, creating a characteristic routing fingerprint unique to the training process. We provide comprehensive empirical evidence that structural memorization emerges consistently even from a few samples, and that its intensity is directly influenced by the choice of trainable modules. We show that these memorized expert pathways can be stealthily recovered through the model's unconditional generation, using only routing and output logits, with no knowledge of the fine-tuning data or procedure. In distributed deployments, this vulnerability is amplified as routing information is exposed at multiple trust boundaries, including federated aggregation points, edge-cloud interfaces, and multi-tenant monitoring systems. Recovery exposes a critical blind spot: traditional membership inference metrics, viewed through the lens of expert routing, fail to identify memorized data corresponding to these structural pathways. To close this gap, we devise composite metrics combining reference model tail likelihood with complexity-aware normalization, significantly improving detection of memorized routing structures. This enables adversaries to pinpoint critical experts shaped by fine-tuning, whether dominant or dormant, and execute targeted attacks such as router manipulation or backdoor injection in realistic distributed settings where attackers lack training data but can observe routing patterns across system components.

Thu 29 OctMachine LearningArtificial IntelligenceCryptography and Security
The gist
Large language models that use a mixture of experts routing system remember not just the data they are trained on but also the unique internal routes taken during training. The authors found that this routing memory can be exposed by watching how the model processes data, even without knowing the original training details. This creates security risks because attackers can detect and exploit these routing patterns in distributed systems where parts of the model run in different places. The authors also created new ways to better detect this hidden memorization, helping to identify vulnerable pathways inside the model.
Open → 2610.41039v1

Federated learning signals reveal different types of data corruption

Different Corruptions, Different Signals: Uncertainty and Loss in Federated Data Quality

Abstract: Federated learning (FL) data corruption can affect either inputs or labels, but it remains unclear whether input-conditional uncertainty and prediction-label loss expose these corruption modes equally. This paper compares two corruption-detection signals in FL: input-conditional uncertainty and prediction-label loss. The uncertainty signal is characterised using a learned aleatoric variance estimate together with Monte Carlo (MC) dropout variance and entropy measures, while the loss is computed against the supplied label. We test these signals against additive image noise and persistent random label flips. On ResNet-20 with CIFAR-10 and SVHN under Dirichlet partitions with data that are not independent and identically distributed (non-IID), the two corruption types behave differently. For persistent random label flips, the within-client per-sample area under the receiver operating characteristic curve (AUC) is 0.85 on CIFAR-10 and 0.95 on SVHN for prediction-label loss, while every uncertainty estimator stays at chance (0.49--0.50). This pattern is consistent with the model remaining confident in the underlying image despite the supplied label being wrong. For image noise, expected-entropy uncertainty rises above chance (0.67 on CIFAR-10 and 0.66 on SVHN), while loss responds comparably (0.64 on both). Each signal is therefore the stronger detector for a different corruption: the prediction-label loss for persistent label flips, and expected-entropy uncertainty for image noise, with its advantage becoming apparent as federation-wide corruption prevalence increases. Robust FL data-quality assessment should match the signal to the corruption rather than rely on uncertainty alone across corruption types.

Fri 25 SeptMachine LearningArtificial IntelligenceComputer Vision and Pattern Recognition
The gist
Data in federated learning can be corrupted either by noisy inputs (like blurry images) or wrong labels (misnamed pictures). This paper shows that two ways to detect these problems—measuring uncertainty in predictions and checking prediction errors against labels—work differently depending on the corruption type. Prediction errors help spot wrong labels, while uncertainty measures better detect noisy inputs. The authors suggest choosing the right detection method based on the kind of corruption to improve data quality in federated learning.
Open → 2609.31454v1