Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Decentralized Polling with Respectable Participants
 
conference paper

Decentralized Polling with Respectable Participants

Guerraoui, Rachid  
•
Huguenin, Kévin
•
Kermarrec, Anne-Marie  
Show more
2009
Proceedings of the 13th International Conference On Principles of DIstributed Systems (OPODIS)

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 (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.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Guerraoui, Rachid  
Huguenin, Kévin
Kermarrec, Anne-Marie  

EPFL

Monod, Maxime  
Date Issued

2009

Published in
Proceedings of the 13th International Conference On Principles of DIstributed Systems (OPODIS)
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
December 19, 2009
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/44884
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés