Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a randomized $\delta$-error Monte Carlo protocol for Consensus in this setting, is it possible to use this protocol as a black box to obtain another Consensus protocol with smaller error?
Note that for problems with deterministic outcome (such as Sum), this can be done by repeatedly executing the protocol and taking the majority as the answer. However I am unable to figure out how for Consensus, so I wonder whether this is actually impossible to do.
--- Details ---
Dynamic Network. There are $n$ nodes on a dynamic network over synchronous setting (thus the protocol will proceed in rounds). Each node has a unique ID of size $\log(n)$. There are edges connecting pairs of nodes, and this set of edges may change from round to round (but remains fixed throughout any particular round). There may be additional restrictions to the dynamic network that allows the problem to be solved by some protocol (such as having a fixed diameter), but it is irrelevant to our discussion.
The only information known to each node is their unique ID. They do not know $n$ or the topology of the network. In particular, they do not know who their neighbors are in the current round (neighbors are nodes that are adjacent to them with an edge). The only way to figure out the neighbors is after receiving messages from them.
How nodes communicate. The only method of communication between nodes is by broadcasting messages under the $CONGEST$ model (D. Peleg, "Distributed Computing, A Locality-Sensitive Approach"). More specifically, in each round, every node may broadcast an $O(\log n)$ sized message. Then, every node will receive ALL messages that were broadcasted by all of its neighbors in that particular round in an arbitrary order. In particular, nodes may attach their IDs onto their messages, since their IDs are of size $O(\log n)$.
Binary Consensus. The binary consensus problem over this network is as follows. Each node has a binary input ($0$ or $1$), and each must decide either $0$ or $1$ under the the validity, termination, and agreement for consensus with $\delta$ error:
validity means that for $z \in \{0, 1\}$, if all nodes have $z$ as its initial input, then the only possible decision is $z$.
termination means that each node must eventually decide.
agreement means that all nodes must have the same decision.
The error rate means that under worst case input and worst case network, the probability that the protocol does not satisfy any of the three conditions is at most $\delta$ over average coin flips of the protocol's coin.
Question. For a particular set of dynamic networks, suppose we have a lower bound on the average number of rounds incurred by any randomized $\delta$-error protocol $P$ for solving binary consensus under this settings such that $\delta < \frac{1}{3}$, under worst case dynamic network from this set, worst case nodes' inputs, and on average coin flips of the protocol. Does this bound automatically hold for any $\delta'$-error protocol for $\delta < \delta' < \frac{1}{3}$?.
