2026-09-08T02:21:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26237 2026-09-05T19:38:58Z ddc:004 open_access

More Bang for the Buck: Superlinear Scaling with Distributed Self-Adjusting Systems (Invited Talk) Köppeler, Jonas Pacut, Maciej Lévai, Tamás Addanki, Vamsi Schmid, Stefan Rétvári, Gábor self-adjusting systems superlinear scaling packet classification Extracting maximum performance from a limited pool of parallel compute resources remains a central challenge. In this paper, we show an optimization technique that allows certain distributed systems to attain faster-than-linear (superlinear) performance improvement with only a linear scaling of the worker pool. Our insight is that (1) dispatching jobs to parallel workers so that the locality of reference in the workers' input increases and (2) implementing the workers with a self-adjusting algorithm to take advantage of the higher locality can yield superlinear scaling in many practical applications. First, we demonstrate our technique in simulations: by scaling textbook self-adjusting algorithms, we obtain 100-3,300x speedup using only 48 CPU cores - up to 70x beyond linear scaling. After that, we re-engineer the default Linux packet classifier to attain a 5-25x raw performance improvement as compared to the vanilla kernel. We demonstrate 800x speedup on synthetic traces and 220x speedup on real firewall traces with 32 CPU cores. Given these insights, we develop a formal model and a set of design guidelines to help understand the applicability of our optimization strategy for particular distributed system workloads. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Köppeler and Maciej Pacut and Tamás Lévai and Vamsi Addanki and Stefan Schmid and Gábor Rétvári 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.3 urn:nbn:de:0030-drops-262377 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode