Asynchronous Crash-Tolerant Consensus in Directed Graphs: Randomization and Topology Knowledge
share
Consider a directed point-to-point network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete directed networks in which not all pair of nodes are connected by a communication channel. Our prior work [35] presented a tight condition, Condition CCA, for achieving approximate consensus in asynchronous networks. This paper proves tight necessary and sufficient conditions on the directed communication graphs for solving exact and approximate consensus under different assumptions. Particularly, we present the following results: -Randomization: We show that Condition CCA from [35] is also necessary and sufficient for solving exact consensus in asynchronous directed networks using randomized algorithms. This result implies that randomization does not affect feasibility of consensus in our context. -Limited Topology Knowledge: We are interested in the algorithms in which nodes only have k-hop neighborhood knowledge and propagate state values to nodes that are at most k-hops away. The family of algorithms of interest is called iterative k-hop algorithms. Unlike the algorithm in [35], these algorithms does not flood the network, and each node does not need the full topology knowledge. For iterative k-hop algorithms, we derive a family of tight conditions, namely Condition k-CCA for 1≤ k≤ n, for solving approximate consensus in asynchronous directed networks. -Topology Discovery: We consider the case where nodes initially have only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors. We show that Condition CCA from [35] is necessary and sufficient for asynchronous approximate consensus with one-hop neighborhood knowledge. One result that may be of independent interest is a topology discovery mechanism to learn and "estimate" the topology in asynchronous directed networks with crash faults.
READ FULL TEXT