Fast Broadcast in Highly Connected Networks
arxiv(2024)
摘要
We revisit the classic broadcast problem, wherein we have k messages, each
composed of O(logn) bits, distributed arbitrarily across a network. The
objective is to broadcast these messages to all nodes in the network. In the
distributed CONGEST model, a textbook algorithm solves this problem in O(D+k)
rounds, where D is the diameter of the graph. While the O(D) term in the
round complexity is unavoidablex2014given that Ω(D) rounds
are necessary to solve broadcast in any graphx2014it remains
unclear whether the O(k) term is needed in all graphs. In cases where the
minimum cut size is one, simply transmitting messages from one side of the cut
to the other would require Ω(k) rounds. However, if the size of the
minimum cut is larger, it may be possible to develop faster algorithms. This
motivates the exploration of the broadcast problem in networks with high edge
connectivity.
In this work, we present a simple randomized distributed algorithm for
performing k-message broadcast in O(((n+k)/λ)log n) rounds in any
n-node simple graph with edge connectivity λ. When k = Ω(n),
our algorithm is universally optimal, up to an O(log n) factor, as its
complexity nearly matches an information-theoretic Ω(k/λ) lower
bound that applies to all graphs, even when the network topology is known to
the algorithm.
The setting k = Ω(n) is particularly interesting because several
fundamental problems can be reduced to broadcasting Ω(n) messages. Our
broadcast algorithm finds several applications in distributed computing,
enabling O(1)-approximation for all distances and
(1+ϵ)-approximation for all cut sizes in Õ(n/λ)
rounds.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要