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

  • $\begingroup$ it appears research level to me! the whole question seems to be built on a research framework! seriously consider Theoretical Computer Science! can you define "randomized δ-error protocol"? try also Theoretical Computer Science Chat $\endgroup$
    – vzn
    Sep 1, 2015 at 15:49
  • $\begingroup$ are you familiar with Paxos, "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, can you give an example of a "randomized δ-error protocol for Consensus"? $\endgroup$
    – vzn
    Sep 1, 2015 at 15:56
  • $\begingroup$ @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. $\endgroup$
    – Irvan
    Sep 3, 2015 at 3:37
  • $\begingroup$ suggest try to fit it into the following framework. The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) (2000) / Fisher. there are some impossibility results known & could your idea possibly violate any? $\endgroup$
    – vzn
    Sep 3, 2015 at 3:59
  • $\begingroup$ 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... $\endgroup$
    – Peter
    Sep 10, 2015 at 9:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.