DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.9

The Steady-States of Splitter Networks

Authors: Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

We introduce splitter networks, which abstract the behavior of conveyor belts found in the video game Factorio. Based on this definition, we show how to compute the steady-state of a splitter network. Then, leveraging insights from the players community, we provide multiple designs of splitter networks capable of load-balancing among several conveyor belts, and prove that any load-balancing network on n belts must have Ω(n log n) nodes. Incidentally, we establish connections between splitter networks and various concepts including flow algorithms, flows with equality constraints, Markov chains and the Knuth-Yao theorem about sampling over rational distributions using a fair coin.

Cite as

Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves. The Steady-States of Splitter Networks. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{couetoux_et_al:LIPIcs.FUN.2024.9,
  author =	{Cou\"{e}toux, Basile and Gastaldi, Bastien and Naves, Guyslain},
  title =	{{The Steady-States of Splitter Networks}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.9},
  URN =		{urn:nbn:de:0030-drops-199174},
  doi =		{10.4230/LIPIcs.FUN.2024.9},
  annote =	{Keywords: Factorio, splitter networks, flow, balancer, steady-state}
}

Search Results

Documents authored by Gastaldi, Bastien

The Steady-States of Splitter Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message