Decentralized Polling With Respectable Participants

Abstract : 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 specifcally, 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 (6k + 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 (4k + 1)B on average, consistently lower that the theoretical bound of (6k + 2)B.
Type de document :
Communication dans un congrès
13th International Conference On Principles Of Distributed Systems (OPODIS), Dec 2009, Nimes, France. 2009, 〈10.1007/978-3-642-10877-8_13〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
Contributeur : Kévin Huguenin <>
Soumis le : jeudi 14 mars 2013 - 15:41:52
Dernière modification le : jeudi 15 novembre 2018 - 11:57:35
Document(s) archivé(s) le : samedi 15 juin 2013 - 02:25:07


Fichiers produits par l'(les) auteur(s)



Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec, Maxime Monod. Decentralized Polling With Respectable Participants. 13th International Conference On Principles Of Distributed Systems (OPODIS), Dec 2009, Nimes, France. 2009, 〈10.1007/978-3-642-10877-8_13〉. 〈inria-00429678〉



Consultations de la notice


Téléchargements de fichiers