REVIEW 3 major objections 7 minor 70 references
Bounded Memory in Distributed Networks
T0 review · 3 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper pins down the round complexity of triangle listing under a $\mu$-word memory limit per node: $\Theta(n^{1+o(1)}/\sqrt{\mu})$ rounds for $\mu \le n^{4/3}$, matching a new lower bound up to subpolynomial factors.
desk verdict Solid, citable paper: new μ-CONGEST model, tight triangle-listing tradeoff, and useful streaming simulations; appendix machinery is heavy but the concerns about message buffering don't sink it. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument runs on four load-bearing mechanisms. (1) A windowing reduction for the lower bound: any $\mu$-memory algorithm can be simulated by one with $3\mu$ memory that emits cliques only at the ends of non-overlapping windows of $W = \lceil \mu/\ell \rceil$ rounds, and an entropy argument applied per window shows the busiest node must absorb $\Omega(n^{2(k-1)/k}/L^{2/k})$ bits of information, forcing $L \ge \Omega(n^{k-1}/\mu^{k/2})$ windows. (2) The round-space tradeoff for expander routing (Lemma A.2): each node simulates its $\deg(v)$ virtual nodes, a random $1/\alpha$ fraction is sampled, routing runs on the sampled subgraph, and $\alpha^2 \log n$ independent repetitions cover all pairs, giving memory $\lceil \deg(v)/\alpha \rceil \cdot 2^{O(\sqrt{\log n})}$ at an $\alpha^2$ factor in rounds. (3) The round-space tradeoff for expander decomposition (Lemma A.3): the parallel instances of the nibble algorithm are assigned random slots among $\alpha$ rounds so each node stores incoming probabilities of only $\lceil \deg(v)/\alpha \rceil \cdot O(\log n)$ instances, cutting space by $\alpha$ at an $\alpha$ factor in rounds. (4) Degree-class synchronization for the listing step: nodes are split into $\log n$ buckets by degree, the bucket carrying at least $1/\log n$ of the total bandwidth is selected, and a routing tool (Theorem B.6) delivers edges to each bucket node in synchronized chunks of size $\mu$ so that the three edges of every triangle arrive in the same memory batch.
What would settle it
Run the constructions of Lemmas A.2 and A.3 on a small regular expander (a few thousand nodes, degree 3) with $\alpha$ chosen so that $\lceil \deg(v)/\alpha \rceil$ is a small constant, and track the peak number of words stored at any node across all routing iterations and decomposition rounds. The lemmas predict a peak of $\lceil \deg(v)/\alpha \rceil \cdot 2^{O(\sqrt{\log n})}$ words (or $\lceil \deg(v)/\alpha \rceil \cdot O(\log n)$ for the decomposition); if any round requires a node to buffer an amount proportional to $\deg(v)$, for example holding the previous iteration's routing structure while absorbing the next sampled random graph, the memory bound fails and the $n^{1+o(1)}/\mu^{1/2}$-round triangle-listing algorithm does not follow, whereas the $\Omega(n/\sqrt{\mu})$ lower bound would still hold.
Extended reading notes
Core claim
The paper's central claim is that capping each node's memory at $\mu$ words changes the round complexity of distributed subgraph listing in a precisely measurable way, and that the price can be paid smoothly. In $\mu$-CONGEST, the standard CONGEST model with an added bound of $\mu$ words of memory per node and with outputs leaving the node's memory once emitted, every $k$-clique listing algorithm requires $\Omega(n^{k-2}/\mu^{k/2-1})$ rounds (Theorem 1.1). For triangles ($k=3$) this bound is tight up to subpolynomial factors: a randomized algorithm lists every triangle in $n^{1+o(1)}/\mu^{1/2}$ rounds whenever $\mu \le n^{4/3}$ (Theorem 1.2), so at linear memory $\mu = \Theta(n)$ the complexity is $n^{1/2+o(1)}$. The matching algorithm works by making the two engines of near-optimal triangle enumeration memory-aware: expander routing is executed on a random $1/\alpha$ fraction of the virtual nodes and repeated $\alpha^2 \log n$ times, cutting per-node space by $\alpha$ at an $\alpha^2$ factor in rounds (Lemma A.2), while the nibble-based expander decomposition spreads its parallel instances over $\alpha$ rounds so each node buffers only a $1/\alpha$ fraction of the incoming probability mass, cutting space by $\alpha$ at an $\alpha$ factor in rounds (Lemma A.3). The paper further claims that a single node can simulate $p$-pass edge-streaming algorithms in $O(n(\Delta+p))$ rounds with $\mu = M+n$ words by caching all edges in the neighbors of the highest-degree node, that no sublinear-memory simulation can beat $\Omega(n\Delta p)$ rounds, that random-order streams can be generated at the same cost via a distributed Fisher-Yates shuffle scheduled by Birkhoff's theorem, and that one-way-mergeable, fully-mergeable, and composable summaries aggregate in $O(\min\{nM,\sqrt{|I|M}\}+D)$, $O(\log|I|\cdot(M\log(\Delta M/\mu)+D))$, and $O(\log|I|\cdot(M+D))$ rounds respectively.
Load-bearing premise
The load-bearing premise is the correctness of Lemmas A.2 and A.3 in the appendix: that the existing expander-routing and nibble-based expander-decomposition routines can be re-implemented with per-node memory cut by a factor $\alpha$ at the price of only an $\alpha^2$ or $\alpha$ factor in rounds; if either adaptation fails, the $n^{1+o(1)}/\mu^{1/2}$-round triangle-listing upper bound does not follow from the text, while the lower bound would survive.
Editorial extensions
If this is right
- The memory-round tradeoff for triangle listing is characterized up to subpolynomial factors for all $\mu \le n^{4/3}$: an $n^{1+o(1)}/\sqrt{\mu}$-round algorithm exists, and no algorithm can be faster.
- At linear memory $\mu = \Theta(n)$, all triangles are listed in $\Theta(n^{1/2+o(1)})$ rounds, compared with $\tilde{O}(n^{1/3})$ rounds when memory is unbounded, so the memory cap costs a factor of roughly $n^{1/6}$ at this point.
- Any $p$-pass edge-streaming algorithm using $M$ words can be simulated on one node in $O(n(\Delta+p))$ rounds with $\mu = M+n$, and $\Omega(n\Delta p)$ rounds are unavoidable when $\mu \le n/4$, so the neighbor-caching strategy is worst-case optimal.
- Mergeable sketches aggregate in time that depends on the summary size rather than the raw data: approximate quantiles in $O(\sqrt{m\epsilon^{-1}\log(m\epsilon)}+D)$ rounds, heavy hitters in $O(\log m\cdot(\epsilon^{-1}\log(\Delta\epsilon^{-1}/\mu)+D))$ rounds, and linear-sketch metrics such as entropy in $O(\log m\cdot(M+D))$ rounds.
- For $k>3$, the lower bound $\Omega(n^{k-2}/\mu^{k/2-1})$ applies to listing $k$-cliques, but the paper achieves the matching listing algorithm only for triangles; the authors state that larger cliques require additional machinery.
Reading between the lines
- Looking beyond the paper, the sampling-and-repetition trick behind Lemma A.2 is a generic memory reducer: any distributed routine whose space bottleneck is degree-proportional routing structure should admit the same $\alpha$-fold space cut at an $\alpha^2$ round premium, which would extend the tradeoff to spanner and MST constructions built on expander routing.
- The windowed entropy argument only needs the $O(m^{k/2})$ bound on clique copies, so the same technique should yield $\Omega(n/\sqrt{\mu})$-type lower bounds for listing other dense subgraphs whenever a counting bound of that shape is available.
- A natural testable extension is to check whether the $k$-clique gap for $k>3$ can be closed by a memory-low structure that answers 'which edges were deleted' queries on demand, since the paper handles sub-degree memory only by discarding deleted-edge lists and keeping component identifiers.
- Because the distributed shuffle is self-contained, random-order semi-streaming guarantees become available in $\mu$-CONGEST at the same round cost, which may be the cheapest route to better approximation ratios for matching and spanner problems on this hardware.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the μ-CONGEST model, a version of CONGEST in which each node has only μ words of memory, and studies the effect of this memory bound on round complexity. It proves a lower bound for k-clique listing (Theorem 1.1), gives a randomized triangle-listing algorithm claimed to run in n^{1+o(1)}/μ^{1/2} rounds for μ ≤ n^{4/3} (Theorem 1.2), and develops several simulations of streaming algorithms, including p-pass algorithms, random-order streams, and one-way, fully mergeable, and composable summaries (Theorems 1.3–1.8). The main advertised contribution is a near-tight memory-round tradeoff for triangle listing.
Significance. If the upper bound is correct, the triangle-listing tradeoff is a genuine contribution: it shows that reducing per-node memory from the Θ(n^{4/3}) used by standard CONGEST algorithms to μ incurs a round cost of roughly n/√μ, up to subpolynomial factors, and the lower-bound window technique is a nice adaptation of the information-theoretic approach of Izumi and Le Gall. The streaming-simulation results are also useful and appear broadly applicable. However, the central upper bound rests on space-efficient expander routing and decomposition lemmas in Appendix A whose proofs are incomplete in important places, and the lower-bound statement contains inaccuracies that need repair. The paper does not provide machine-checked proofs or code, so independent verification of the appendix is the main burden.
major comments (3)
- [Appendix A.2.1, Lemma A.2] Lemma A.2 is load-bearing for Theorem 1.2 through Theorem B.6, but its proof omits the construction details of the sampled random graph ("We omit the details as they are similar to the proofs in [39]") and explicitly excludes the cost of storing messages at sources and destinations. In Theorem B.6, each node in S is the target of up to 3μ messages during the first routing and again during the duplication phase; the proof does not show that these messages can be buffered within the O(μ) memory together with the routing structure. Since the lemma's own caveat states that worst-case message storage is deg(v)·L, which is Θ(μ) in this application, the memory accounting must be made explicit, for example by a batching argument, before the n^{1+o(1)}/μ^{1/2} upper bound is established as written.
- [Appendix B.2, Theorem B.6] The stated round bound μ/x·n^{o(1)} does not follow from Lemma A.2 for all parameters. To fit the routing structure in memory μ for nodes of degree at least x, Lemma A.2 requires α ≳ (x/μ)·2^{O(√log n)} when x > μ, which makes the round term Ω((x/μ)·2^{O(√log n)}), i.e., max(μ/x, x/μ)·n^{o(1)} rather than μ/x·n^{o(1)}. The theorem statement allows arbitrary 1 ≤ x ≤ Δ with no x ≤ μ assumption. The applications in Appendix B happen to fall in the range x ≤ μ, but the tool statement as written is overclaimed and should be revised or qualified.
- [Section 2.1, Theorem 1.1] The proof fixes G = G_{n,1/2}, whose maximum degree is Θ(n), so it establishes the lower bound only for ℓ = Θ(n); the theorem's stated dependence on a general ℓ ≤ n is not proven by the given argument. In addition, the entropy of μ words is at most O(μ log n) bits, so the step "μ = Ω(n^{2(k−1)/k}/L^{2/k})" should carry a (log n)^{-1} factor. Also, the display Ω(n^{k−1}/(μ^{k/2−1}ℓ)) = Ω(n^{k−2}/μ^{k/2−1}) is not an equality; it should be "≥" under ℓ ≤ n, and the final sentence uses n^{k−2} where the derivation yields n^{k−1}. These issues do not destroy the qualitative n^{1+o(1)}/μ^{1/2} tradeoff, but Theorem 1.1 as stated overclaims.
minor comments (7)
- [Section 2.1] In the description of the modified setup, "w_r = ⌈W/r⌉" should be "⌈r/W⌉"; as written it denotes the wrong window.
- [Lemma 2.7] The notation ρ^{w_max}_{i_max} is confusing: the initial state ρ_i is not window-dependent, so it should be ρ_{i_max}.
- [Appendix B.3] The line "then |E_high|≤|E|/4" should read "≥"; it follows directly from |E_m| ≥ |E|/2 and |E_low| ≤ |E|/4, and the subsequent argument needs the lower bound to remove a constant fraction of edges.
- [Theorem 1.2] Minor grammatical issue: "there exists a algorithm" should be "there exists an algorithm".
- [Section 2.2] In the proof of Theorem 2.10, "For Θ(n) ≤ μ ≤ Θ(n^2)" is inconsistent with the theorem's range μ ≤ n^{2−2/k}; this should be Θ(n^{2−2/k}).
- [References] References [54] and [55] are duplicate entries for the same Lenzen paper and should be merged.
- [Definition 3.3] There is a typo: "in a streaming fasion" should be "in a streaming fashion".
Circularity Check
No significant circularity: the claimed tradeoffs are derived from information-theoretic lower-bound arguments and external expander-decomposition/routing building blocks; flagged proof gaps are completeness risks, not circular reductions.
full rationale
The derivation chain is not circular. Theorem 1.1's lower bound is built from the external information-theoretic framework of Izumi–Le Gall [49] and Rivin [68], adapted to windowed outputs; no step assumes the theorem being proved. Theorem 1.2's upper bound reduces to Lemmas A.2 and A.3, which are new space-round tradeoff adaptations of the external expander-routing and expander-decomposition algorithms of [39] and [20,22]; the target bound n^{1+o(1)}/μ^{1/2} is not an input to these lemmas. The self-citations to [20,22] (co-authored by Y.-J. Chang) are prior published algorithms used as building blocks, not a uniqueness claim or an assumed conclusion, so per the reviewing rules they count as real evidence rather than circularity. The streaming theorems 1.3–1.8 are direct constructions or standard mergeability arguments with no fitted or predicted parameter. Flagged but non-circular: Lemma A.2's proof says 'We omit the details as they are similar to the proofs in [39]' and explicitly warns that its space bound 'does not consider the cost of preparing the messages at the source nodes and the cost of storing the messages at the destination nodes'; since Theorem B.6 invokes Lemma A.2 for nodes receiving up to 3μ messages, the message-buffer cost is a potential completeness gap in the proof of the upper bound, not a circular reduction. Appendix B.3's line 'then |E_high|≤|E|/4' appears to be a sign typo (should be ≥) and is cosmetic. No equation in the paper reduces to its own input, and no prediction is equivalent to a fitted parameter by construction, so the appropriate score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Synchronous rounds with O(log n)-bit messages per edge (CONGEST)
- domain assumption Each node stores at most μ words; μ ≥ Δ unless stated otherwise
- domain assumption Lower bound uses random graph G(n,1/2) as input distribution
- domain assumption Expander routing and decomposition algorithms of [20,22,39,40] are correct
- standard math Birkhoff's theorem: doubly stochastic matrices decompose into permutation matrices
Cite this review
Pith. "Pith review of Bounded Memory in Distributed Networks." pith.science (2026). https://pith.science/paper/QU5C6BUP
@misc{pith2026250611644,
author = {Pith},
title = {Pith review of: Bounded Memory in Distributed Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/QU5C6BUP}},
note = {Machine review of arXiv:2506.11644}
}
abstract
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 $\mu$-CONGEST model where on top of the bandwidth restriction, the memory of nodes is also limited to $\mu$ words, in line with real-world systems. We provide fast algorithms of two main flavors. First, we observe that many algorithms in the CONGEST model are memory-intensive and do not work in $\mu$-CONGEST. A prime example of a family of algorithms that use large memory is clique-listing algorithms. We show that the memory issue that arises here cannot be resolved without incurring a cost in the round complexity, by establishing a lower bound on the round complexity of listing cliques in $\mu$-CONGEST. We introduce novel techniques to overcome these issues and generalize the algorithms to work within a given memory bound. Combined with our lower bound, these provide tight tradeoffs between the running time and memory of nodes. Second, we show that it is possible to efficiently simulate various families of streaming algorithms in $\mu$-CONGEST. These include fast simulations of $p$-pass algorithms, random order streams, and various types of mergeable streaming algorithms. Combining our contributions, we show that we can use streaming algorithms to efficiently generate statistics regarding combinatorial structures in the network. An example of an end result of this type is that we can efficiently identify and provide the per-color frequencies of the frequent monochromatic triangles in $\mu$-CONGEST.
Reference graph
Works this paper leans on
-
[39]
Distributed MST and routing in almost mixing time
Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Proceedings 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 131–140, 2017
work page 2017
-
[1]
IEEE Std 802.1D-2004 (Revision of IEEE Std 802.1D-1998) , pages 1–281, 2004
Ieee standard for local and metropolitan area networks: Media access control (mac) bridges. IEEE Std 802.1D-2004 (Revision of IEEE Std 802.1D-1998) , pages 1–281, 2004. doi:10.1109/IEEESTD.2004.94569
-
[2]
Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):1–28, 2013
work page 2013
-
[3]
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA , pages 739–748. IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.43
-
[4]
Improved routing strategies with succinct tables
Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307–341, 1990. doi: 10.1016/0196-6774(90)90017-9
-
[5]
Routing with polynomial communication- space trade-off
Baruch Awerbuch and David Peleg. Routing with polynomial communication- space trade-off. SIAM J. Discret. Math. , 5(2):151–162, 1992. doi:10.1137/ 0405013
work page 1992
-
[6]
Efficient mea- surement on programmable switches using probabilistic recirculation
Ran Ben-Basat, Xiaoqi Chen, Gil Einziger, and Ori Rottenstreich. Efficient mea- surement on programmable switches using probabilistic recirculation. In 2018 IEEE 26th International Conference on Network Protocols (ICNP) , pages 313–323. IEEE, 2018
work page 2018
-
[7]
Pint: Probabilistic in-band network telemetry
Ran Ben Basat, Sivaramakrishnan Ramanathan, Yuliang Li, Gianni Antichi, Minian Yu, and Michael Mitzenmacher. Pint: Probabilistic in-band network telemetry. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication , pages 662–680, 2020
work page 2020
Show all 70 references
-
[8]
Onos: towards an open, distributed sdn os
Pankaj Berde, Matteo Gerola, Jonathan Hart, Yuta Higuchi, Masayoshi Kobayashi, Toshio Koide, Bob Lantz, Brian O’Connor, Pavlin Radoslavov, William Snow, et al. Onos: towards an open, distributed sdn os. In Proceedings of the third workshop on Hot topics in software defined net...
2014
-
[9]
Tres observaciones sobre el algebra lineal
Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A, 5:147–154, 1946
1946
-
[10]
P4: Programming protocol-independent packet processors
Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, et al. P4: Programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review, 44(3):87–95, 2014
2014
-
[11]
Forwarding metamorphosis: Fast programmable match-action processing in hardware for sdn
Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, and Mark Horowitz. Forwarding metamorphosis: Fast programmable match-action processing in hardware for sdn. ACM SIGCOMM Computer Communication Review, 43(4):99–110, 2013
2013
-
[12]
Trident Programmable Switch
BROADCOM. Trident Programmable Switch. https://www.broadcom.com/ products/ethernet-connectivity/switching/strataxgs/bcm56870-series, 2017
2017
-
[13]
Compact routing messages in self-healing trees
Armando Castañeda, Danny Dolev, and Amitabh Trehan. Compact routing messages in self-healing trees. Theor. Comput. Sci. , 709:2–19, 2018. doi:10. 1016/j.tcs.2016.11.022
2018
-
[14]
Fully compact rout- ing in low memory self-healing trees
Armando Castañeda, Jonas Lefèvre, and Amitabh Trehan. Fully compact rout- ing in low memory self-healing trees. In Nandini Mukherjee and Sriram V. Pemmaraju, editors, ICDCN 2020: 21st International Conference on Distributed Computing and Networking, Kolkata, India, January 4-7...
2020
-
[15]
Tight distributed listing of cliques
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2878–2891, 2021
2021
-
[16]
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Lei...
2020 doi
-
[17]
On distributed listing of cliques
Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf. On distributed listing of cliques. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2020), 2020. doi:10.1145/3382734.3405742
2020
-
[18]
Deterministic expander routing: Faster and more versatile
Yi-Jun Chang, Shang-En Huang, and Hsin-Hao Su. Deterministic expander routing: Faster and more versatile. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC) , pages 194–204, 2024
2024
-
[19]
The complexity of distributed approximation of packing and covering integer linear programs
Yi-Jun Chang and Zeyong Li. The complexity of distributed approximation of packing and covering integer linear programs. In Proceedings of the 2023 ACM 11 SPAA ’25, July 28–August 1, 2025, Portland, OR, USA Ran Ben Basat, Keren Censor-Hillel, Yi-Jun Chang, Wenchen Han, Dean Le...
2023
-
[20]
Near- optimal distributed triangle enumeration via expander decompositions
Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. Near- optimal distributed triangle enumeration via expander decompositions. Journal of the ACM, 68(3):1–36, 2021
2021
-
[21]
Distributed triangle detection via expander decomposition
Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. InProceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 821–840, 2019
2019
-
[22]
Improved distributed expander de- composition and nearly optimal triangle enumeration
Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander de- composition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC) , pages 66–73, New York, NY, USA, 2019. Association for Computi...
2019
-
[23]
Deterministic distributed expander decomposition and routing with applications in distributed derandomization
Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 377–388, 2020
2020
-
[24]
tri, tri again
Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting - (extended abstract). In Marcos K. Aguilera, editor, Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-1...
2012 doi
-
[25]
Sublinear- time distributed algorithms for detecting small cliques and even cycles
Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear- time distributed algorithms for detecting small cliques and even cycles. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019), pages 15:1–15:16, 2019. doi:10.4230...
2019 doi
-
[26]
Near-optimal distributed routing with low memory
Michael Elkin and Ofer Neiman. Near-optimal distributed routing with low memory. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018 , pages 207–216. ACM, 2...
2018 doi
-
[27]
On efficient distributed construction of near optimal routing schemes
Michael Elkin and Ofer Neiman. On efficient distributed construction of near optimal routing schemes. Distributed Comput., 31(2):119–137, 2018. doi:10. 1007/s00446-017-0304-4
2018
-
[28]
Stone age distributed computing
Yuval Emek and Roger Wattenhofer. Stone age distributed computing. In PODC, pages 137–146. ACM, 2013
2013
-
[29]
Graph distances in the streaming model: the value of space
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In SODA, volume 5, pages 745–754, 2005
2005
-
[30]
Orion: Google’s{Software-Defined} networking control plane
Andrew D Ferguson, Steve Gribble, Chi-Yao Hong, Charles Killian, Waqar Mohsin, Henrik Muehe, Joon Ong, Leon Poutievski, Arjun Singh, Lorenzo Vicisano, et al. Orion: Google’s{Software-Defined} networking control plane. In 18th USENIX Symposium on Networked Systems Design and Im...
2021
-
[31]
Possibilities and impossibilities for distributed subgraph detection
Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA) , pages 153–162, 2018
2018
-
[32]
Fisher and F
R.A. Fisher and F. Yates. Statistical Tables for Biological, Agricultural, and Medical Research. Hafner Publishing Company, 1953. URL: https://books.google.co.uk/ books?id=qJI7AAAAMAAJ
1953
-
[33]
Memory requirement for universal routing schemes
Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. In James H. Anderson, editor, Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, Ottawa, Ontario, Canada, August 20-23, 1995, pages 223–230. ACM, 199...
1995
-
[34]
Local memory requirement of universal routing schemes
Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. In Guy E. Blelloch, editor, Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’96, Padua, Italy, June 24-26, 1996, pages 183–188. ACM, 1996. do...
1996
-
[35]
Header-size lower bounds for end-to-end communication in memoryless networks
Pierre Fraigniaud and Cyril Gavoille. Header-size lower bounds for end-to-end communication in memoryless networks. Comput. Networks, 50(10):1630–1638,
-
[36]
Cr-precis: A deterministic summary structure for update data streams
Sumit Ganguly and Anirban Majumder. Cr-precis: A deterministic summary structure for update data streams. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected ...
2007
-
[37]
Memory requirements for routing in distributed networks (extended abstract)
Cyril Gavoille and Stephane Perennes. Memory requirements for routing in distributed networks (extended abstract). In James E. Burns and Yoram Moses, editors, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, ...
1996
-
[38]
On the complexity of local distributed graph problems
Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June ...
2017
-
[40]
New distributed algorithms in almost mixing time via transformations from parallel algorithms
Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Ulrich Schmid and Josef Widder, editors, Proceedings 32nd International Symposium on Distributed Computing (DISC), volume 121 of Leibniz Internationa...
2018
-
[41]
Space-efficient online computation of quantile summaries
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2):58–66, 2001
2001
-
[42]
Stream order and order statistics: Quantile estimation in random-order streams
Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on Computing , 38(5):2044– 2059, 2009
2009
-
[43]
Pingmesh: A large-scale system for data center network latency measurement and analysis
Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray Huang, Dave Maltz, Zhaoyi Liu, Vin Wang, Bin Pang, Hua Chen, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis. InProceedings of the 2015 ACM Conference on Special Interest ...
2015
-
[44]
FRANCIS: fast reaction algorithms for network coordination in switches
Wenchen Han, Vic Feng, Gregory Schwartzman, Michael Mitzenmacher, Min- lan Yu, and Ran Ben-Basat. FRANCIS: fast reaction algorithms for network coordination in switches. CoRR, abs/2204.14138, 2022. arXiv:2204.14138, doi:10.48550/arXiv.2204.14138
-
[45]
B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google’s software-defined wan
Chi-Yao Hong, Subhasree Mandal, Mohammad Al-Fares, Min Zhu, Richard Alimi, Chandan Bhagat, Sourabh Jain, Jay Kaimal, Shiyu Liang, Kirill Mendelev, et al. B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google’s software-defined wan. ...
2018
-
[46]
Hucaby and D
D. Hucaby and D. Hucaby. CCNP BCMSN Exam Certification Guide: CCNP Self- study. CCNP Self-Study. Cisco Press, 2004. URL: https://books.google.co.uk/ books?id=-rnt_ik0mSYC
2004
-
[47]
Intel tofino programmable ethernet switch asic
Intel. Intel tofino programmable ethernet switch asic. https: //www.intel.com/content/www/us/en/products/network-io/programmable- ethernet-switch/tofino-series.html, 2017
2017
-
[48]
P416 intel ® tofino™ native architecture – public version
Intel. P416 intel ® tofino™ native architecture – public version. https://raw.githubusercontent.com/barefootnetworks/Open-Tofino/master/ PUBLIC_Tofino-Native-Arch.pdf, 2021
2021
-
[49]
Triangle finding and listing in CONGEST networks
Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 381–389, 2017
2017
-
[50]
Approximating the permanent
Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149–1178, 1989
1989
-
[51]
Karloff, Siddharth Suri, and Sergei Vassilvitskii
Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of com- putation for mapreduce. In Moses Charikar, editor, Proceedings of the Twenty- First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 , pages 938–948...
2010 doi
-
[52]
On a cut-matching game for the sparsest cut problem
Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi. On a cut-matching game for the sparsest cut problem. Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2007-177, 6(7):12, 2007
2007
-
[53]
Graph partitioning using single commodity flows
Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4), July 2009. doi:10.1145/1538902.1538903
2009
-
[55]
Optimal deterministic routing and sorting on the congested clique
Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages 42–50. ACM, 2013. doi:10.1145/...
2013
-
[56]
Fast routing table construction using small messages: extended abstract
Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages: extended abstract. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 , pages 381–390...
2013
-
[57]
Fast partial distance estimation and applications
Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2...
2015
-
[58]
Locality in distributed graph algorithms
Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput. , 21(1):193–201, 1992. doi:10.1137/0221015
1992 doi
-
[59]
Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou
S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou. Space- Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching. arXiv e-prints, page arXiv:2009.06106, September 2020. arXiv:2009.06106
2009 arXiv
-
[60]
Minimum-weight spanning tree construction in O(log log n) communication rounds
Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. 12 Bounded Memory in Distributed Networks SPAA ’25, July 28–August 1, 2025, Portland, OR, USA Comput., 35(1):120–131, 2005. doi:1...
2025 doi
-
[61]
Openflow: enabling innovation in campus networks.ACM SIGCOMM computer communication review, 38(2):69–74, 2008
Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peter- son, Jennifer Rexford, Scott Shenker, and Jonathan Turner. Openflow: enabling innovation in campus networks.ACM SIGCOMM computer communication review, 38(2):69–74, 2008
2008
-
[62]
Opendaylight: Towards a model-driven sdn controller architecture
Jan Medved, Robert Varga, Anton Tkacik, and Ken Gray. Opendaylight: Towards a model-driven sdn controller architecture. In Proceeding of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks 2014 , pages 1–6. IEEE, 2014
2014
-
[63]
Miller, Richard Peng, and Shen Chen Xu
Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures (SPAA) , pages 196–203. ACM, 2013
2013
-
[64]
Finding repeated elements
Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming, 2(2):143–152, 1982
1982
-
[65]
Distributed Computing: A Locality-Sensitive Approach
David Peleg. Distributed Computing: A Locality-Sensitive Approach . Society for Industrial and Applied Mathematics, USA, 2000
2000
-
[66]
A trade-off between space and efficiency for routing tables
David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510–530, 1989. doi:10.1145/65950.65953
1989
-
[67]
Computing cut-based hierar- chical decompositions in almost linear time
Harald Räcke, Chintan Shah, and Hanjo Täubig. Computing cut-based hierar- chical decompositions in almost linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 227–238. Society for Industrial and Applied Mathematics, 2014
2014
-
[68]
Counting cycles and finite dimensional Lp norms
Igor Rivin. Counting cycles and finite dimensional Lp norms. Adv. Appl. Math., 29(4):647–662, 2002
2002
-
[69]
Polylogarithmic-time deterministic net- work decomposition and distributed derandomization
Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic net- work decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , 2020
2020
-
[70]
with high probability
Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages 81–90, 2004. A Distributed expander decompositio...
2004
-
[2006]
doi:10.1016/j.comnet.2005.09.025
2005 doi
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.