Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems

摘要

The role of argumentation in supporting various forms of interaction among possibly conflicting autonomous agents has been explicitly recognized in the literature. In argumentation, conflict management is carried out by the formal process of defeat status computation. In this paper we consider the generalization of this process to a distributed setting. We show that significant stabilization problems may arise even in relatively simple cases. A fundamental negative result is then proved: no general self-stabilizing algorithm exists for distributed defeat status computation, indicating that self-stabilizing algorithms for this problem can be defined only under specific conditions. Accordingly, we focus on two cases: an algorithm tailored to a specific family of inference graphs, that include only rebutting defeaters, and an algorithm that applies to any inference graph, also including undercutting defeaters, but may provide (cautiously) incorrect results for some nodes. For both algorithms the worst-case round complexity is analyzed and it is proved that no algorithms with lower complexity exist for the same tasks.