Lewis Tseng: Asynchronous Crash-Tolerant Consensus in Directed Graphs

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.  I'll first present a tight condition, Condition CCA, for achieving approximate consensus in asynchronous networks (published in PODC15).

Then I'll discuss our recent paper which proves tight necessary and sufficient conditions on directed communication graphs for solving exact and approximate asynchronous consensus under different assumptions. Particularly, we have the following results:

• Randomization: We show that Condition CCA from PODC15, proven tight for approximate consensus, is also necessary and sufficient for solving exact consensus using randomized algorithms. This result implies that considering the randomized and approximate versions of consensus has the same effect on its feasibility.

• Limited Topology Knowledge: We are interested in the algorithms in which nodes only have k-hop neighborhood knowledge and gather state information from nodes at most k-hops away. The family of algorithms of interest is called iterative k- hop algorithms. Unlike the algorithm in PODC15, these algorithms do 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 PODC15 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.