DROPS

Document

Invited Talk

DOI: 10.4230/LIPIcs.SAND.2026.3

More Bang for the Buck: Superlinear Scaling with Distributed Self-Adjusting Systems (Invited Talk)

Authors: Jonas Köppeler, Maciej Pacut, Tamás Lévai, Vamsi Addanki, Stefan Schmid, and Gábor Rétvári

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

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.

Cite as

Jonas Köppeler, Maciej Pacut, Tamás Lévai, Vamsi Addanki, Stefan Schmid, and Gábor Rétvári. More Bang for the Buck: Superlinear Scaling with Distributed Self-Adjusting Systems (Invited Talk). In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 3:1-3:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppeler_et_al:LIPIcs.SAND.2026.3,
  author =	{K\"{o}ppeler, Jonas and Pacut, Maciej and L\'{e}vai, Tam\'{a}s and Addanki, Vamsi and Schmid, Stefan and R\'{e}tv\'{a}ri, G\'{a}bor},
  title =	{{More Bang for the Buck: Superlinear Scaling with Distributed Self-Adjusting Systems}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{3:1--3:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.3},
  URN =		{urn:nbn:de:0030-drops-262377},
  doi =		{10.4230/LIPIcs.SAND.2026.3},
  annote =	{Keywords: self-adjusting systems, superlinear scaling, packet classification}
}

Search Results

Documents authored by Addanki, Vamsi

More Bang for the Buck: Superlinear Scaling with Distributed Self-Adjusting Systems (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message