Asynchronous max-consensus protocol with time delays: convergence results and applications

This paper deals with the analysis of the convergence properties of the max-consensus protocol in presence of asynchronous updates and bounded time delays on directed static networks. The work is motivated by real-world applications in distributed decision-making systems, for which max-consensus is an effective paradigm. The main result of this paper is that the strongly connectedness of the directed communication network is a sufficient condition for the asynchronous max-consensus protocol to let a distributed system converge in finite time. Implementation issues are also taken into account, by complementing the theoretical analysis with the definition of a mechanism to detect convergence in a distributed fashion. Finally, a numerical example is given, highlighting both the issues related to the failure of synchronous protocols applied to asynchronous settings and the effectiveness of the proposed asynchronous framework.