Decentralized Polling with Respectable Participants

We consider the polling problem in a social network where participants care about their reputation: they do not want their vote to be disclosed nor their misbehaving, if any, to be publicly exposed. Assuming this reputation concern, we show that a simple secret sharing scheme, combined with verification procedures, can efficiently enable polling without the need for any central authority or heavyweight cryptography.

More specifically, we present

DPol

, a simple and scalable distributed polling protocol where misbehaving nodes are exposed with a non-zero probability and the probability of dishonest participants violating privacy is balanced with their impact on the accuracy of the polling result. The trade-off is captured by a generic parameter of the protocol, an integer

k

we call the

privacy parameter

, so that in a system of

N

nodes with

$B<\sqrt{N}$

dishonest participants, the probability of disclosing a participant’s vote is bounded by (

B

/

N

)

k

 + 1

, whereas the impact on the polling result is bounded by (6

k

 + 2)

B

.

We report on the deployment of

DPol

over 400 PlanetLab nodes. The polling result suffers a relative error of less than 10% in the face of message losses, crashes and asynchrony inherent in PlanetLab. In the presence of dishonest nodes, our experiments show that the impact on the polling result is (4

k

 + 1)

B

on average, consistently lower that the theoretical bound of (6

k

 + 2)

B

.