Majority is Not Always Supreme: Less Can Be More When Voting with Compromised Nodes

摘要

We consider binary voting in a replica voting setup with a small number of redundant components. Seeking to understand the implications of corrupted components on voting schemes, we consider a simplified setup where one node is highly compromised and the remaining nodes are functionally homogenous. We show that if the homogenous nodes are slightly better than average at voting correctly and the highly compromised node is sufficiently bad, a random dictator leads to a better outcome than a majority vote.