Early-Deciding Consensus is Expensive and Efficient Distributed Source Detection with Limited Bandwidth

In consensus, the n nodes of a distributed system seek to take a consistent decision on some output, despite up to t of them crashing or even failing maliciously, i.e., behaving “Byzantine”. It is known that it is impossible to guarantee that synchronous, deterministic algorithms consistently decide on an output in fewer than f + 1 rounds in executions in which the actual number of faults is f ≤ t. This even holds if faults are crash-only, and in this case the bound can be matched precisely. However, the question of whether this can be done efficiently, i.e., with little communication, so far has not been addressed. In this work, we show that algorithms tolerating Byzantine faults and deciding within f + 2 rounds must send \Omega(nt + t^2 f ) messages; as a byproduct, our analysis shows that decision within f + 1 rounds is impossible in this setting (unless f = t). Moreover, we prove that any crash-resilient algorithm deciding in f + 1 rounds has worst-case message complexity \Omega(n^2 f ). Interestingly, this changes drastically if we restrict the fault model further. If crashes are orderly, i.e., in each round, each node picks an order in which its messages are sent, and crashing nodes successfully transmit a prefix of their sequence, deciding in f + 1 rounds can be guaranteed with O(nt) messages.

And

Title: Efficient Distributed Source Detection with Limited Bandwidth
Given a simple graph G = (V, E) and a set of sources S \subseteq V , denote for each node v in V by L^(\infty)_v the lexicographically ordered list distance/source pairs (d(s, v), s). For integers d, k in N \cup {\infty}, we consider the source detection, or (S, d, k)-detection task, requiring each node v to learn the first k entries of L_v or all entries (d(s, v), s) in L^(\infty)_v satisfying that d(s, v) ≤ d. Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k = \infty requires each source s in S to build a complete BFS tree rooted at s, whereas the special case of d = \infty and S = V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model running in d + k rounds, and demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions.