This paper considers the problem of approximate consensus in directed asynchronous message-passing networks where some nodes may become Byzantine faulty. We obtain a tight necessary and sufficient condition on the underlying directed communication network for asynchronous Byzantine approximate consensus to be achievable. Interestingly, this condition coincides with the tight condition for synchronous Byzantine exact consensus. Our consensus algorithm may be viewed as a non-trivial generalization of an algorithm previously proposed for the special case of complete networks. The tight condition and techniques identified in the paper shed light on the fundamental properties for solving approximate consensus in asynchronous directed networks.

In this work we address the problem of reaching approximate consensus in a complete network ofnnodes, where message deliveries can be delayed by at mostdtime-steps. We consider a mobile adversary, which corrupts at mostfnodes in any step, modeled as asynchronousround. We explicitly study howdaffects the feasibility of the problem. More precisely, we propose a framework to analyze mobile fault-tolerance in the presence of message delays. We prove that approximate consensus is feasible if and only ifn> 4df. We assume no knowledge of time (round index) by the nodes; instead, in our model, whenever a message is sent, it is timestamped by the communication channel. We propose the tightTimeStampsalgorithm, which utilizes timestamps to optimally bound the number of faulty messages.

Consider a point-to-point message-passing network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete networks. We study the feasibility and efficiency of approximate consensus under different restrictions on topology knowledge and the relay depth, i.e., the maximum number of hops any message can be relayed. These two constraints are common in large-scale networks, and are used to avoid memory overload and network congestion respectively. Specifically, for positive integer values k and k', we consider that each node knows all its neighbors of at most k-hop distance (k-hop topology knowledge), and the relay depth is k'. We consider both directed and undirected graphs. More concretely, we answer the following question in asynchronous systems: "What is a tight condition on the underlying communication graphs for achieving approximate consensus if each node has only a k-hop topology knowledge and relay depth k'?" To prove that the necessary conditions presented in the paper are also sufficient, we have developed algorithms that achieve consensus in graphs satisfying those conditions: - The first class of algorithms requires k-hop topology knowledge and relay depth k. Unlike prior algorithms, these algorithms do not flood the network, and each node does not need the full topology knowledge. We show how the convergence time and the message complexity of those algorithms is affected by k, providing the respective upper bounds. - The second set of algorithms requires only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors, but needs to flood the network (i.e., relay depth is n, where n is the number of nodes). 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.

Consider an asynchronous incomplete directed network. We study the feasibility and efficiency of approximate crash-tolerant consensus under different restrictions on topology knowledge and relay depth, i.e., the maximum number of hops any message can be relayed.

We address the problem of Reliable Message Transmission (RMT), in the general adversary model of Hirt and Maurer[2], which subsumes earlier models such as the global or local threshold adversaries. We employ the recently introduced Partial Knowledge Model[8], which captures any case of initial players' topology knowledge. Our main contribution is the determination of a necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary. We propose the RMT-Partial Knowledge Algorithm (RMT-PKA), which solves RMT whenever this is possible, therefore it is a unique algorithm, as defined in[10]. To the best of our knowledge, this is the first unique protocol for RMT against general adversaries in the partial knowledge model.