Bounded Memory in Distributed Networks
Ran Ben Basat, Keren Censor-Hillel, Yi‐Jun Chang, Wenchen Han, Dean Leitersdorf, Gregory Schwartzman · 2025
The recent advent of programmable switches makes distributed algorithms readily deployable in real-world datacenter networks. However, there are still gaps between theory and practice that prevent the smooth adaptation of CONGEST algorithms to these environments. In this paper, we focus on the memory restrictions that arise in real-world deployments. We introduce the μ-CONGEST model where on top of the bandwidth restriction, the memory of nodes is also limited to μ words, in line with real-world systems. We provide fast algorithms of two main flavors.