Yi-Jun Chang

Yi-Jun Chang, Yang Ze Guan

We study the aggregation problem in synchronous multi-hop radio networks with $O(\log n)$-bit messages and no collision detection. Each node initially holds a value, and the goal is to compute a global aggregate such as the sum of all values. Aggregation tasks arise naturally in wireless sensor networks, where nodes are often battery-powered and radio activity is the dominant source of energy consumption. Accordingly, our main objective is to minimize the energy complexity, defined as the maximum number of rounds in which any node is awake. Our main result is a randomized distributed algorithm that, with high probability, constructs and executes an aggregation schedule in $O(n \operatorname{polylog} n)$ rounds and using $O(Δ^\ast \operatorname{polylog} n)$ energy, where $Δ^\ast$ is the minimum possible maximum degree of a spanning tree of the network graph. This guarantee is nearly optimal: for any aggregation schedule and any graph, there exists a node that must be awake for at least $Δ^\ast$ rounds. As a by-product, the algorithm also computes a spanning tree whose maximum degree is within an $O(\log n)$ factor of $Δ^\ast$, with the same round and energy guarantees. For every tree edge, both endpoints learn that the edge belongs to the tree.

Yi-Jun Chang

In the LOCAL model, low-diameter decomposition is a useful tool in designing algorithms, as it allows us to shift from the general graph setting to the low-diameter graph setting, where brute-force information gathering can be done efficiently. Recently, Chang and Su [PODC 2022] showed that any high-conductance network excluding a fixed minor contains a high-degree vertex, so the entire graph topology can be gathered to one vertex efficiently in the CONGEST model using expander routing. Therefore, in networks excluding a fixed minor, many problems that can be solved efficiently in LOCAL via low-diameter decomposition can also be solved efficiently in CONGEST via expander decomposition. In this work, we show improved decomposition and routing algorithms for networks excluding a fixed minor in the CONGEST model. Our algorithms cost $\text{poly}(\log n, 1/ε)$ rounds deterministically. For bounded-degree graphs, our algorithms finish in $O(ε^{-1}\log n) + ε^{-O(1)}$ rounds. Our algorithms have a wide range of applications, including the following results in CONGEST. 1. A $(1-ε)$-approximate maximum independent set in a network excluding a fixed minor can be computed deterministically in $O(ε^{-1}\log^\ast n) + ε^{-O(1)}$ rounds, nearly matching the $Ω(ε^{-1}\log^\ast n)$ lower bound of Lenzen and Wattenhofer [DISC 2008]. 2. Property testing of any additive minor-closed property can be done deterministically in $O(\log n)$ rounds if $ε$ is a constant or $O(ε^{-1}\log n) + ε^{-O(1)}$ rounds if the maximum degree $Δ$ is a constant, nearly matching the $Ω(ε^{-1}\log n)$ lower bound of Levi, Medina, and Ron [PODC 2018].

Yi-Jun Chang, Yanyu Chen, Dipan Dey et al.

We investigate the \emph{minimum weight cycle (MWC)} problem in the $\mathsf{CONGEST}$ model of distributed computing. For undirected weighted graphs, we design a randomized algorithm that achieves a $(k+1)$-approximation, for any \emph{real} number $k \ge 1$. The round complexity of algorithm is \[ \tilde{O}\!\Big( n^{\frac{k+1}{2k+1}} + n^{\frac{1}{k}} + D\, n^{\frac{1}{2(2k+1)}} + D^{\frac{2}{5}} n^{\frac{2}{5}+\frac{1}{2(2k+1)}} \Big). \] where $n$ denotes the number of nodes and $D$ is the unweighted diameter of the graph. This result yields a smooth trade-off between approximation ratio and round complexity. In particular, when $k \geq 2$ and $D = \tilde{O}(n^{1/4})$, the bound simplifies to \[ \tilde{O}\!\left( n^{\frac{k+1}{2k+1}} \right) \] On the lower bound side, assuming the Erdős girth conjecture, we prove that for every \emph{integer} $k \ge 1$, any randomized $(k+1-ε)$-approximation algorithm for MWC requires \[ \tildeΩ\!\left( n^{\frac{k+1}{2k+1}} \right) \] rounds. This lower bound holds for both directed unweighted and undirected weighted graphs, and applies even to graphs with small diameter $D = Θ(\log n)$. Taken together, our upper and lower bounds \emph{match up to polylogarithmic factors} for graphs of sufficiently small diameter $D = \tilde{O}(n^{1/4})$ (when $k \geq 2$), yielding a nearly tight bound on the distributed complexity of the problem. Our results improve upon the previous state of the art: Manoharan and Ramachandran (PODC~2024) demonstrated a $(2+ε)$-approximation algorithm for undirected weighted graphs with round complexity $\tilde{O}(n^{2/3}+D)$, and proved that for any arbitrarily large number $α$, any $α$-approximation algorithm for directed unweighted or undirected weighted graphs requires $Ω(\sqrt{n}/\log n)$ rounds.

Jérémie Chalopin, Yi-Jun Chang, Giuseppe Antonio Di Luna et al.

In the content-oblivious (CO) model (proposed by Censor-Hillel et al.), processes inhabit an asynchronous network and communicate only by exchanging pulses. A series of works has clarified the computational power of this model. In particular, it was shown that, when a leader is present and the network is 2-edge-connected, content-oblivious communication can simulate classical asynchronous message passing. Subsequent results extended this equivalence to leaderless oriented and unoriented rings, and, under non-uniform assumptions, to general 2-edge-connected networks. The simulator of Censor-Hillel et al. requires $O(n^3b+n^3\log n)$ pulses to emulate the send of a single $b$-bit message, making it impractical even on modest-size networks. We focus on message-efficient computation in CO networks. We study the fundamental problem of counting in ring topologies, both because knowing the exact network size is a basic prerequisite for many distributed tasks and because counting immediately implies a broad class of aggregation primitives. We give an algorithm that counts using $O(n^{1.5})$ pulses in anonymous rings with a leader, an $O(n\log^2 n)$ algorithm for counting in rings with IDs. Moreover, we show that any counting algorithm in CO requires $Ω(n\log n)$ pulses. Interestingly, in the course of this investigation, we design a simulator for classic message passing: in one simulated round, each process can send a $b$-bit message to each of its neighbors using only $O(b)$ pulses per process. The simulator extends to general 2-edge-connected networks, after a pre-processing step that requires $O(n^{8}\log n)$ pulses, where $n$ is the number of processes, allowing thus efficient simulation of asynchronous message passing in general 2-edge-connected networks.