Lower bounds for distributed coin-flipping and randomized consensus Export

@inproceedings{citeulike:467065, abstract = {We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. We show that to guarantee at most constant bias,\Omega\Gamma t 2 ) local coins are needed, even if (a) the local coins can have...}, author = {Aspnes, James}, citeulike-article-id = {467065}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.9793}, keywords = {agent, consensus, randomized}, pages = {559--568}, posted-at = {2006-01-17 14:19:55}, priority = {4}, title = {Lower bounds for distributed coin-flipping and randomized consensus}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.9793}, year = {1997} }

TY - CONF ID - citeulike:467065 L3 - citeulike-article-id:467065 N2 - We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. We show that to guarantee at most constant bias,\Omega\Gamma t 2 ) local coins are needed, even if (a) the local coins can have... EP - 568 TI - Lower bounds for distributed coin-flipping and randomized consensus SP - 559 KW - agent KW - consensus KW - randomized AU - Aspnes, James PY - 1997/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.9793 ER -