CS Paper Radar

Understanding the oversubscription behaviour of DragonFly+ networks

Vlad-Adrian Ulmeanu, Costin Raiciu, Iulian-Ilie Drăcea

cs.NI ·submitted 2026-09-14 17:50 UTC · v1
theory

Abstract

The Max-Host Dragonfly+ topology's original paper proves that there is a 2:1 worst-case oversubscription ratio in expectation for the permutation traffic pattern. We show that the proof only covers a subset of permutation patterns, specifically those in which all host pairs are in different groups, and for any receiver group there are at least two sending hosts in distinct groups. The proof contains two mistakes that cancel out to produce the correct result. Furthermore, the proof implicitly uses an important observation without a backing argument: traffic leaving an indirect group, now forced to follow min-cost paths to receiver groups, can still be split across almost all outgoing global links, in contrast with splitting traffic from a sender group that can naturally select any outgoing group. We prove that the 2:1 ratio holds in expectation for a larger set of patterns, including any permutation. We only need to know that any host sends and receives at most line rate traffic. This constraint can be altered to obtain approximations for expected FCT bounds on any pattern. We also attack the oversubscription problem without the expectation assumption, and find bounds that hold with high probability on permutations for small switch radixes. While in expectation the global layer wiring doesn't affect the oversubscription rate, we experimentally find that it matters in the general case. We find topologies that obtain visible speedups against the default global wiring from the original paper, under $7\%$ for radixes at most $8$.

Closest papers

Nearest neighbours by meaning across the whole index.

Random-Priority Frontier Routing: Tight $Θ(n^c)$ Bounds Against $c$-Node Cartels

cs.DS ·2026-09-01 ·Krišjānis Petručena
theory similarity 0.59
Abstract · 4 pages

We study path diversification in trusted-node networks, where sensitive material is relayed through intermediate nodes, some of which may be compromised. Our randomized routing rule assigns each vertex an independent random priority and repeatedly expands the highest-priority vertex on the global frontier of the explored region. Let $G$ have $n$ vertices, let $s,t$ be honest endpoints, and let $C$ be a set of $c$ compromised intermediate vertices, called a cartel, whose deletion leaves $s$ and $t$ connected. For every fixed $c$ and every fixed target probability $q\in(0,1)$, we prove that $Θ(n^c)$ independent executions are sufficient in the worst case for some route to avoid $C$ with probability at least $q$.

0.39

Prophet Inequalities and Online Contention Resolution for Matchoids

cs.DS ·2026-09-17 ·Calum MacRury, Pranav Nuti, Jan Vondrák
similarity 0.55
Abstract

In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variables with the goal of maximizing the expected value of its selection. The performance of the algorithm is compared to an \textit{omniscient prophet} who observes all of the random variables before having to make its selection. Combinatorial extensions of the classical prophet inequality in which the algorithm gets to pick a subset of the random variables (constrained to belong to some family of feasible sets) have been studied extensively. We study prophet inequalities with a $k$-matchoid constraint (a common generalization of a $k$-matroid intersection constraint and a $k$-bounded hypergraph matching constraint) in two common online arrival models. We give guarantees with respect to the \textit{ex-ante} fractional relaxation of the omniscient prophet, obtaining an ex-ante competitive ratio of $\frac{1}{k+1}$ in the adversarial order case, and $\frac{1-e^{-k}}{k}$ in the random order case. Using the duality framework of Lee and Singla \cite{Lee2018}, this also yields online contention resolution schemes in these settings. Our adversarial-order prophet inequality can be viewed as a generalization of a recent $\frac12$-competitive matroid prophet inequality by Kalantarzadeh and Pashkovich, 2026. This generalization introduces a new framework: coordinated weighted principal partitions across multiple matroids. Our random-order prophet inequality is a generalization of the $k=1$ matroid case of Lee and Singla, 2018. The two results improve previously known competitive ratios for $k$-matroid intersection, which were $\frac{1}{(e+o(1))k}$ and $\frac{1}{k+1}$, respectively.

0.24

Counting in Population Protocols on Graphs

cs.DC ·2026-08-18 ·Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Thorsten Götte, Lukas Hintze +1 more
published similarity 0.55
Abstract · Accepted to DISC 2026

We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph $G=(V,E)$ with $|V|=n$ nodes. In each step, a random scheduler selects an edge uniformly at random, and the incident nodes make a state transition. As per standard assumptions, agents are identical and anonymous, that is, have no identifiers. To break symmetry, in each interaction one of the agents is declared as the initiator uniformly at random. Our size counting protocol uses $\tilde O(n)$ states and stabilizes in $O( B(G) \cdot \log^2(n) + L(G) \cdot \log(n))$ interactions with high probability, where $B(G)$ is the broadcast time and $L(G)$ is the load balancing time. Our protocol is based on novel protocols for sampling independent random bits (given that the scheduler determines an initiator and responder) and approximating $\log n$ up to an additive error of $O(\log \log n)$ with high probability. The latter uses $O(poly\log(n))$ states and $O(B(G)\cdot\log^2 n)$ interactions. Both results may be of independent interest. The main protocol for exact counting requires the presence of a unique leader, the other two do not. None of the protocols requires any knowledge about the graph $G$. We conclude with impossibility results for terminating uniform population protocols that compute graph-size properties (like counting nodes or determining parity) with and without a leader.

0.46

An Optimal Gap-Majority Lemma for Bounded-Round Communication

cs.CC ·2026-10-15 ·Pachara Sawettamalya
similarity 0.54
Abstract

Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing whether $\sum_{i=1}^n f(X_i,Y_i)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we show that a minor adaptation of their approach, together with a more refined analysis, achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

0.25

Weak Composition Theorems for Randomized Communication

cs.CC ·2026-11-12 ·Pachara Sawettamalya
theory similarity 0.54
Abstract

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

0.06

Tight Lower Bounds for Distributional Paging

cs.DS ·2026-10-29 ·Ali Vakilian
similarity 0.53
Abstract

Distributional paging seeks a polynomial-time eviction rule that competes with the optimal \emph{online} policy $\mathrm{OPT}$ when requests come from a known stochastic source. Two algorithms by Lund, Phillips, and Reingold [FOCS, 1994] are canonical. Their randomized \emph{dominating distribution} algorithm, for Markov sources, evicts a page drawn from a distribution over the cache satisfying pairwise linear inequalities; their deterministic \emph{median} algorithm, for sources with independent inter-arrival times across pages, evicts the cached page with the largest lower median of its conditional next-request time. Their original guarantees of $4$ and $5$ were recently improved to $2$ and $4$ by Pabbaraju and Vakilian [ICALP 2025]. We show that neither improved constant can be reduced in its respective source model. For Markov paging, we give two complementary factor-$2$ lower-bound constructions, each with an explicit polynomial-time dominating selector. A directed-cycle family has ratio $2k/(k+1)$, while a recurrent four-page family with cache size three has ratio $2-4\varepsilon/3$. For the independent inter-arrival model, we show that the median algorithm is not $c$-competitive for any $c<4$. These are separate results for distinct stochastic models. Matching the known upper bounds, they establish tight competitive ratios of $2$ and $4$, respectively, improving on previous lower bounds of $1.5907$ and $1.511$.

0.10

Order-selection Prophet Inequality (Almost) Goes I.I.D

cs.DS cs.GT ·2026-10-26 ·Bo Peng, Zhihao Gavin Tang
theory similarity 0.53
Abstract · 75 pages

We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $Γ_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $Γ_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.

0.19

Online Permutation Embedding: Optimal Stopping and Scaling Laws

cs.DS math.PRmath.CO ·2026-08-19 ·Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov
similarity 0.53
Abstract

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

0.50