James Aspnes
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, ω(t2) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in t, ω(t2/log2t) local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any t-resilient asynchronous consensus protocol requires ω(t2/log2t) local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.
- ABRAHAMSON, K. 1988. On achieving consensus using a shared memory. In Proceedings of the 7th Annual ACM Symposium on the Principles of Distributed Computing (Toronto, Ont., Canada, Aug. 15-17). ACM, New York, pp. 291-302. Google Scholar
- ALON, N., AND Naoa, M. 1990. Coin-flipping games immune against linear-sized coalitions. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 46-54.Google Scholar
- ALua, R., ATTIYA, H., AND TAUBENFELD, G. 1994. Time-adaptive algorithms for synchronization. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 800-809. Google Scholar
- ASpNES, J. 1993. Time- and space-efficient randomized consensus. J. Algorithms 14, 3 (May), 414-431. Google Scholar
- ASpNES, J. 1997. Lower bounds for distributed coin-flipping and randomized consensus. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 559-568. Google Scholar
- ASPNES, J., AND HERLIHY, M. 1990. Fast randomized consensus using shared memory. J. Algorithms 11, 3 (Sept.), 441-461. Google ScholarDigital Library
- ASPNES, J., AND WAARTS, O. 1996. Randomized consensus in O(n log2 n) operations per processor. SIAM J. Comput. 25, 5 (Oct.), 1024-1044. Google ScholarDigital Library
- ATTIYA, U., DOLEV, D., AND SHAVIT, N. 1989. Bounded polynomial randomized consensus. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. 16-19). ACM, New York, pp. 281-294. Google Scholar
- AUMANN, Y. 1997. Efficient asynchronous consensus with the weak adversary scheduler. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (Santa Barbara, Calif., Aug. 21-24). ACM, New York, pp. 209-218. Google Scholar
- AUMANN, Y., AND BENDER, M. 1996. Efficient asynchronous consensus with a value-oblivious adversary scheduler. In Proceedings of the 23rd International Conference on Automata, Languages, and Programming (July). Springer-Verlag, New York, pp. 622-633. Google Scholar
- BEN-OR, M., AND LINIAL, N. 1989. Collective coin flipping. In Randomness and Computation, vol. 5 of Advances in Computing Research, Silvio Micali, ed. JAI Press, Greenwich, Conn., pp. 91-115.Google Scholar
- BEN-OR, M., LINIAL, N., AND SAKS, M. 1987. Collective coin flipping and other models of imperfect randomness. In Combinatorics, vol. 52 of Colloquia Mathematic Societatis Janos Bolyai (Eger, Hungary). pp. 75-112.Google Scholar
- BRACHA, G., AND RACHMAN, O. 1990. Approximated counters and randomized consensus. Tech. Rep. 662. Technion, Israel.Google Scholar
- BRACHA, G., AND RACHMAN, O. 1991. Randomized consensus in expected O(n2 log n) operations. In Proceedings of the 5th Workshop on Distributed Algorithms. Springer-Verlag, New York, pp. 143-150. Google Scholar
- CHANDRA, T.D. 1996. Polylog randomized wait-free consensus. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (Philadelphia, Pa., May 23-26). ACM, New York, pp. 166-175. Google Scholar
- CHOR, B., FRIEDMAN, J., GOLDREICH, O., HASTAD, J., RUDICH, S., AND SMOLENSKY, R. 1985. The bit extraction problem or t-resilient functions. In Proceedings of the 2nd Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 396-407.Google Scholar
- CHOR, B., ISRAELI, A., AND LI, M. 1987. On processor coordination using asynchronous hardware. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, pp. 86-97. Google Scholar
- CLEVE, R., AND IMPAGLIAZZO, R. 1993. Martingales with Boolean final value must make jumps of O(1/n1/2) with constant probability. Unpublished manuscript.Google Scholar
- COOPER, J., AND LINIAL, N. 1993. Fast perfect-information leader-election protocol with linear immunity. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 662-671. Google Scholar
- DOLEV, D., DWORK, C., AND STOCKMEYER, L. 1987. On the minimal synchronism needed for distributed consensus. J. ACM 34, 1 (Jan.), 77-97. Google ScholarDigital Library
- DWORK, C., HERLIHY, M., PLOTKIN, S., AND WAARTS, O. 1992. Time-lapse snapshots. In Proceedings of the Israel Symposium on the Theory of Computing and Systems. Springer-Verlag, New York, pp. 154-170. Google Scholar
- FICH, F., HERLIHY, M., AND SHAVIT, N. 1993. On the space complexity of randomized synchronization. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (Ithaca, N.Y., Aug. 15-18). ACM, New York, pp. 241-250. Google Scholar
- FISCHER, M., LYNCH, N. A., AND PATERSON, M.S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr.), 374-382. Google ScholarDigital Library
- FRIEDMAN, J. 1992. On the bit extraction problem. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 314-319.Google Scholar
- HARPER, L. H. 1966. Optimal numberings and isoperimetric problems on graphs. J. Combinat. Theory 1, 385-394.Google ScholarCross Ref
- HERLIHY, M. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1 (Jan.), 124-149. Google ScholarDigital Library
- LICHTENSTEIN, D., LINIAL, N., AND SAKS, M. 1989. Some external problems arising from discrete control processes. Combinatorica 9, 269-287.Google ScholarCross Ref
- LouI, M. C., AND ABU-AMARA, H.H. 1987. Memory requirements for agreement among unreliable asynchronous processes. In Advances in Computing Research, vol. 4, Franco P. Preprata, ed. JAI Press, Greenwich, Conn., pp. 163-183.Google Scholar
- LYNCH, N.A. 1996. Distributed Algorithms. Morgan-Kaufmann, San Mateo, Calif. Google Scholar
- SAKS, M. 1989. A robust non-cryptographic protocol for collective coin flipping. SIAM J. Disc. Math. 2, 2, 240-244. Google ScholarDigital Library
- SAKS, M., SHAVIT, N., AND WOLL, U. 1991. Optimal time randomized consensus-Making resilient algorithms fast in practice. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 28-30). ACM, New York, pp. 351-362. Google Scholar
- VAZlRANI, U. 1985. Towards a strong communication complexity theory, or generating quasirandom sequences from two communicating slightly-random sources. In Proceedings of the 17th Annual ACM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 366-378. Google Scholar
Index Terms
- Lower bounds for distributed coin-flipping and randomized consensus
Recommendations
Faster randomized consensus with an oblivious adversary
Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Faster randomized consensus with an oblivious adversary
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computingTwo new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Locally scalable randomized consensus for synchronous crash failures
SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architecturesWe consider bit communication complexity of binary consensus in synchronous message passing systems with processes prone to crashes. A distributed algorithm is locally scalable when each process contributes to the complexity measure an amount that is ...
Comments