An Alloy Verification Model for Consensus-Based Auction Protocols
This work addresses the risk of oscillations and failures in distributed systems like UAV fleets or smart grids due to misconfigured or malicious agents, though it is incremental as it builds on existing MCA protocols with a new verification approach.
The paper tackles the problem of verifying the convergence of Max Consensus-based Auction (MCA) protocols, which are used for distributed resource allocation, by proposing a formal model in Alloy. The result shows that MCA is not resilient against rebidding attacks and fails for certain policy combinations, enabling automated verification of convergence for various policy instantiations.
Max Consensus-based Auction (MCA) protocols are an elegant approach to establish conflict-free distributed allocations in a wide range of network utility maximization problems. A set of agents independently bid on a set of items, and exchange their bids with their first hop-neighbors for a distributed (max-consensus) winner determination. The use of MCA protocols was proposed, $e.g.$, to solve the task allocation problem for a fleet of unmanned aerial vehicles, in smart grids, or in distributed virtual network management applications. Misconfigured or malicious agents participating in a MCA, or an incorrect instantiation of policies can lead to oscillations of the protocol, causing, $e.g.$, Service Level Agreement (SLA) violations. In this paper, we propose a formal, machine-readable, Max-Consensus Auction model, encoded in the Alloy lightweight modeling language. The model consists of a network of agents applying the MCA mechanisms, instantiated with potentially different policies, and a set of predicates to analyze its convergence properties. We were able to verify that MCA is not resilient against rebidding attacks, and that the protocol fails (to achieve a conflict-free resource allocation) for some specific combinations of policies. Our model can be used to verify, with a "push-button" analysis, the convergence of the MCA mechanism to a conflict-free allocation of a wide range of policy instantiations.