Max-Consensus in a Max-Plus Algebraic Setting: The Case of Switching Communication Topologies

Because of their use for distributed decision making, consensus algorithms have attracted a lot of interest in recent years. Coordination between entities requires that they share information over a network, and develop a consistent view regarding objectives and relevant information on the environment, i.e., reach a consensus. In practice, communication topologies may change over time, either as a consequence of disturbances or in an attempt to improve performance. Max-consensus is a specific consensus algorithm, which is particularly important in applications such as minimum time rendezvous and leader election. In this contribution, we propose an approach to analyze max-consensus algorithms in time-variant communication topologies, which is based on max-plus algebra. In this framework max-consensus algorithms become piecewise linear and may be analyzed easily. The conditions needed to achieve max-consensus and the convergence rate of the algorithm for different communication graphs are studied. This contribution is an extension of the work in Monajemi Nejad et al. (2009), where max-consensus was studied for time-invariant communication topologies.