A maximum independent set approach for collusion detection in voting pools

From agreement problems to replicated software execution, we frequently find scenarios with voting pools. Unfortunately, Byzantine adversaries can join and collude to distort the results of an election. We address the problem of detecting these colluders, in scenarios where they repeatedly participate in voting decisions. We investigate different malicious strategies, such as naïve or colluding attacks, with fixed identifiers or in whitewashing attacks. Using a graph-theoretic approach, we frame collusion detection as a problem of identifying maximum independent sets. We then propose several new graph-based methods and show, via analysis and simulations, their effectiveness and practical applicability for collusion detection.

► In this paper, we present collusion detection algorithms for volunteer computing.
► We model possible attacks from malicious nodes and define graphs based on these.
► We evaluate the Maximum Independent Set Problem (MIS) in these graphs.
► MIS contributes to correctly identify colluders.
► We also present an algorithm that resists to whitewashing attacks.