Noncryptographic selection protocols
Noncryptographic selection protocols
复制标题
非加密选择协议
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
U. Feige
选择任务概括了一些研究得很好的问题，如集体抛硬币和领导者选举。我们提出了新的选择协议在全信息模型，和新的负面结果。特别是当有（1+/spl delta/）n/2个好的参与者时，我们给出了一个以概率/spl Omega/（/spl delta//sup 1.65/）选择好的领导者的协议，并证明了每个领导者选举协议的成功概率为O（/spl delta//sup 1-/spl epsiv//），对于每个/spl epsiv/>0。以前已知的协议，这个问题的成功概率是指数小的1//spl δ/，并没有平凡的成功概率的上限是已知的。
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.