The steady-states of splitter networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910576056205312 |
|---|---|
| author | Couëtoux, Basile Gastaldi, Bastien Naves, Guyslain |
| author_facet | Couëtoux, Basile Gastaldi, Bastien Naves, Guyslain |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05472 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The steady-states of splitter networks Couëtoux, Basile Gastaldi, Bastien Naves, Guyslain Discrete Mathematics 05C21 G.2.2; F.2.2 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. |
| title | The steady-states of splitter networks |
| topic | Discrete Mathematics 05C21 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2404.05472 |