Noncryptographic Selection Protocols

Selection tasks generalize some well studied problems, such as collective coin flipping and leader election. We present new selection protocols in the full information model, and new negative results. In particular when there are (1+/spl delta/)n/2 good players, we show a protocol that chooses a good leader with probability /spl Omega/(/spl delta//sup 1. 65/), and show that every leader election protocol has success probability O(/spl delta//sup 1-/spl epsiv//), for every /spl epsiv/>0. Previously known protocols for this problem have success probability that is exponentially small in 1//spl delta/, and no nontrivial upper bounds on the success probability were known.

Authors

• Uriel Feige

Keywords

• Cryptographic protocols
• Nominations and elections
• Broadcasting
• Upper bound
• Computational modeling
• Communication standards
• Communication channels
• Boolean functions
• Selection Protocol
• Head And Tail
• Good Leadership
• Leader Election
• Lower Bound
• Coalition
• Proof Of Theorem
• Random Walk
• Selection Problem
• Random Strategy
• Root Of The Tree
• Universal Constant
• Probability 1
• Power-of-two
• Robust Protocol
• Random Labeling
• Random Bits
• High Probability Of Success
• Majority Of Players
• Protocol Execution
• Broadcast Messages
• Toy Example