<p>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?</p>

<p>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.</p>

<p>--- Details ---</p>

<p><strong>Dynamic Network.</strong>
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.</p>

<p>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.</p>

<p><strong>How nodes communicate.</strong>
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)$.</p>

<p><strong>Binary Consensus.</strong>
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:</p>

<ul>
<li><p>validity means that for $z \in \{0, 1\}$, if all nodes have $z$ as its initial input, then the only possible decision is $z$.</p></li>
<li><p>termination means that each node must eventually decide.</p></li>
<li><p>agreement means that all nodes must have the same decision.</p></li>
<li><p>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.</p></li>
</ul>

<p><strong>Question.</strong> 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 &lt; \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 &lt; \delta' &lt; \frac{1}{3}$?.</p>

CC BY-SA 3.0
2015-09-01T15:49:22.390Z
it appears research level to me! the whole question seems to be built on a research framework! seriously consider [cstheory.se]! can you define "randomized δ-error protocol"? try also [chat]
vzn
CC BY-SA 3.0
2015-09-01T15:56:28.913Z
are you familiar with [Paxos](https://en.wikipedia.org/wiki/Paxos_(computer_science)), "a family of protocols for solving consensus in a network of unreliable processors"? does it not match the requirements for some reason? there are many (standard) [consensus protocols](https://en.wikipedia.org/wiki/Consensus_(computer_science)#Some_consensus_protocols), can you give an example of a "randomized δ-error protocol for Consensus"?
vzn
CC BY-SA 3.0
2015-09-03T03:37:51.080Z
@vzn No, I'm not really familiar with this topic. Thus I thought that this question is well-known, and I was hoping for a quick answer here. Seems like this is not well-known then. I wasn't aware of the TCS stackexchange before, I'll try to ask the admin to cross post this question there.
Irvan
CC BY-SA 3.0
2015-09-03T03:59:32.177Z
suggest try to fit it into the following framework. [The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) (2000)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6738) / Fisher. there are some impossibility results known & could your idea possibly violate any?
vzn
CC BY-SA 3.0
2015-09-10T09:53:32.457Z
Do you assume that, when an instance of your blackbox consensus algorithm fails, all nodes are aware that the consensus algorithm has failed? This seems to depend on the precise properties of the dynamic network that you're assuming...
Peter
CC BY-SA 3.0
2015-09-10T10:07:11.790Z
@Peter No unless your protocol is specifically designed to be able to do that. The only way for the nodes to communicate is through broadcasting and receiving messages. E.g., the lack of message from a particular node may mean something. There are no "magical" communication channels otherwise.
Irvan
CC BY-SA 3.0
2015-09-10T10:10:12.490Z
@Peter Also this question is more of a whether it is possible to obtain a better protocol using a black box protocol. For example, in Sum, each node can run the protocol multiple times (either in parallel or in a row) and takes a majority. Using Chernoff's bound, for any $0 < \delta' < \delta < \frac{1}{3}$, one can obtain protocol with $\delta'$ error from a $\delta$ error protocol for Sum by executing the protocol a constant amount of time and taking a majority as the answer.
Irvan
<ds.algorithms><reductions><dc.distributed-comp>
Is it possible to boost the error probability of a Consensus protocol over dynamic network?
Irvan
# Is it possible to boost the error probability of a Consensus protocol over dynamic network?

(Asked by: username_0 on 2015-08-24)

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}$?.

**Tags:** ds.algorithms, reductions, dc.distributed-comp
> **Comments:**
> **username_1**: it appears research level to me! the whole question seems to be built on a research framework! seriously consider [cstheory.se]! can you define "randomized δ-error protocol"? try also [chat]  
> **username_1**: are you familiar with [Paxos](https://en.wikipedia.org/wiki/Paxos_(computer_science)), "a family of protocols for solving consensus in a network of unreliable processors"? does it not match the requirements for some reason? there are many (standard) [consensus protocols](https://en.wikipedia.org/wiki/Consensus_(computer_science)#Some_consensus_protocols), can you give an example of a "randomized δ-error protocol for Consensus"?  
> **username_0**: @vzn No, I'm not really familiar with this topic. Thus I thought that this question is well-known, and I was hoping for a quick answer here. Seems like this is not well-known then. I wasn't aware of the TCS stackexchange before, I'll try to ask the admin to cross post this question there.  
> **username_1**: suggest try to fit it into the following framework. [The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) (2000)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6738) / Fisher. there are some impossibility results known & could your idea possibly violate any?  
> **username_2**: Do you assume that, when an instance of your blackbox consensus algorithm fails, all nodes are aware that the consensus algorithm has failed? This seems to depend on the precise properties of the dynamic network that you're assuming...  
> **username_0**: @Peter No unless your protocol is specifically designed to be able to do that. The only way for the nodes to communicate is through broadcasting and receiving messages. E.g., the lack of message from a particular node may mean something. There are no "magical" communication channels otherwise.  
> **username_0**: @Peter Also this question is more of a whether it is possible to obtain a better protocol using a black box protocol. For example, in Sum, each node can run the protocol multiple times (either in parallel or in a row) and takes a majority. Using Chernoff's bound, for any $0 < \delta' < \delta < \frac{1}{3}$, one can obtain protocol with $\delta'$ error from a $\delta$ error protocol for Sum by executing the protocol a constant amount of time and taking a majority as the answer.  

---

## 0 answers

