Search papers, labs, and topics across Lattice.
This paper investigates efficient counting algorithms in content-oblivious (CO) ring networks, where nodes communicate only via pulses. They present an $O(n^{1.5})$ pulse algorithm for anonymous rings with a leader and an $O(n\log^2 n)$ algorithm for rings with IDs, establishing an $\Omega(n\log n)$ lower bound for counting in CO. A novel simulator for classic message passing is also introduced, achieving $O(b)$ pulses per process for sending a $b$-bit message in one simulated round, applicable to general 2-edge-connected networks after preprocessing.
Content-oblivious networks can count and simulate message passing far more efficiently than previously thought, shrinking the pulse complexity from $O(n^3)$ to $O(n \log^2 n)$ for counting and $O(b)$ per process for message simulation.
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 $\Omega(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.
