  Collusion occurs when multiple malicious participants of a distributed
protocol work together to sabotage or spy on honest participants. Decentralized
protocols often rely on a subset of participants called workers for critical
operations. Collusion between workers can be particularly harmful to the
security of the protocol. We propose two protocols that select a subset of
workers from the set of participants such that the probability of the workers
colluding together is minimized. Our first solution is a decentralized protocol
that randomly selects workers in a verifiable manner without any trusted
entities. The second solution is an algorithm that uses a social graph of
participants and community detection to select workers that are socially
distant in order to reduce the probability of collusion. We present our
solutions in the context of a decentralized voting protocol proposed by
Schiedermeier et al. [24] that guarantees transparency and verifiability.
Enabling collusion-resistance in order to ensure democratic voting is clearly
of paramount importance thus the voting protocol provides a suitable use case
for our solutions.
