Decentralized Polling With Respectable Participants

Abstract : We consider the polling problem in a social network where respectable participants do 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 a posteriori verifications, can efficiently enable polling without the need for any central authority or heavyweight cryptography. More specifically, we present a scalable distributed polling protocol where (i) misbehaving nodes are exposed with a non-null probability, (ii) the reputation of honest nodes is never tarnished, and (iii) the probability of malicious participants violating privacy is traded 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 privacy parameter, so that in a system of N nodes with B < sqrt(N) malicious 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 our protocol over 400 PlanetLab nodes with a privacy parameter k = 2. The polling result suffers a relative error of less than 10% in the face of message losses, crashes and asynchrony inherent in PlanetLab. In presence of malicious nodes, our experiments show that the impact on the polling result is (4k + 2)B on average, consistently lower that the theoretical bound of (6k + 2)B.
Type de document :
[Research Report] RR-6890, INRIA. 2009, pp.16
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
Contributeur : Kévin Huguenin <>
Soumis le : mardi 14 avril 2009 - 07:00:02
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 10 juin 2010 - 17:51:54


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


  • HAL Id : inria-00371708, version 1


Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec, Maxime Maxime Monod. Decentralized Polling With Respectable Participants. [Research Report] RR-6890, INRIA. 2009, pp.16. 〈inria-00371708〉



Consultations de la notice


Téléchargements de fichiers