Memory requirements for agreement among unreliable asynchronous processes. Some external problems arising from discrete control processes. LICHTENSTEIN, D., LINIAL, N., AND SAKS, M.Optimal numberings and isoperimetric problems on graphs. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. Impossibility of distributed consensus with one faulty process. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (Ithaca, N.Y., Aug. On the space complexity of randomized synchronization. In Proceedings of the Israel Symposium on the Theory of Computing and Systems. DWORK, C., HERLIHY, M., PLOTKIN, S., AND WAARTS, O.On the minimal synchronism needed for distributed consensus. DOLEV, D., DWORK, C., AND STOCKMEYER, L.In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). Fast perfect-information leader-election protocol with linear immunity. Martingales with Boolean final value must make jumps of O(1/n1/2) with constant probability. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. On processor coordination using asynchronous hardware. In Proceedings of the 2nd Annual Symposium on Foundations of Computer Science. The bit extraction problem or t-resilient functions. CHOR, B., FRIEDMAN, J., GOLDREICH, O., HASTAD, J., RUDICH, S., AND SMOLENSKY, R.In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (Philadelphia, Pa., May 23-26). In Proceedings of the 5th Workshop on Distributed Algorithms. Randomized consensus in expected O(n2 log n) operations. Approximated counters and randomized consensus. 52 of Colloquia Mathematic Societatis Janos Bolyai (Eger, Hungary). Collective coin flipping and other models of imperfect randomness. 5 of Advances in Computing Research, Silvio Micali, ed. In Proceedings of the 23rd International Conference on Automata, Languages, and Programming (July).

Efficient asynchronous consensus with a value-oblivious adversary scheduler.

In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (Santa Barbara, Calif., Aug. Efficient asynchronous consensus with the weak adversary scheduler. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. Randomized consensus in O(n log2 n) operations per processor. Fast randomized consensus using shared memory. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). Lower bounds for distributed coin-flipping and randomized consensus. Time- and space-efficient randomized consensus. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). Time-adaptive algorithms for synchronization.

ALua, R., ATTIYA, H., AND TAUBENFELD, G.

In Proceedings of the 31st Annual Symposium on Foundations of Computer Science. Coin-flipping games immune against linear-sized coalitions. In Proceedings of the 7th Annual ACM Symposium on the Principles of Distributed Computing (Toronto, Ont., Canada, Aug. On achieving consensus using a shared memory. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors. 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 ω( t 2/log 2 t) local coin flips in any model that can be simulated deterministically using atomic registers. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in t, ω( t 2/log 2 t) local coins are needed. We show that to guarantee at most constant bias, ω( t 2) 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. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures.

Coin flip random