Printer Friendly

Lower Bounds for Distributed Coin-Flipping and Randomized Consensus.

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]([t.sup.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 whether 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, [Omega]([t.sup.2]/[log.sup.2] t) 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 [Omega]([t.sup.2]/[log.sup.2] t) 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.

Categories and Subject Descriptors: B.3.2 [Memory Structures]: Design Styles-shared memory; B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems)-asynchronous/synchronous operation; C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors)-multiple-instruction-stream, multiple-data-stream processors (MIMD); D.1.3 [Programming Techniques]: Concurrent Programming-distributed programming; D.4.1 [Operating Systems]: Process Management-concurrency, synchronization; D.4.7 [Operating Systems]: Organization and Design-distributed systems; F.2.m [Analysis of Algorithms and Problem Complexity]: miscellaneous

General Terms: Algorithms, Reliability, Theory

Additional Key Words and Phrases: Consensus, impossibility, randomization

1. Introduction

Our results divide naturally into two parts: a lower bound for asynchronous randomized consensus in a wide variety of models, and a still more general lower bound for a large class of collective coin-flipping games that forms the basis of the consensus lower bound but is interesting in its own right.

Consensus is a fundamental problem in distributed computing in which a group of processes must agree on a bit despite the interference of an adversary. (An additional condition forbids trivial solutions that always produce the same answer). In an asynchronous setting, it has long been known that if an adversary can halt a single process, then no deterministic consensus algorithm is possible without the use of powerful synchronization primitives.(1)

In contrast, randomized algorithms can solve consensus in a shared-memory system for n processes even if the adversary can halt up to n - 1 processes. Such algorithms are called wait-free [Herlihy 1991] because any process can finish the algorithm without waiting for slower (or possibly dead) processes. These algorithms work even under the assumption that failures and the timing of all events in the system are under the control of an adaptive adversary--one that can observe and react to all aspects of the system's execution (including the internal states of the processes).

The first known algorithm that solves shared-memory consensus against an adaptive adversary is the exponential-time algorithm of Abrahamson [1988]; since its appearance, numerous polynomial-time algorithms have appeared.(2) Most of these algorithms are built around shared coin protocols in which the processes individually generate many random [+ or -] 1 local coin flips, which are combined by majority voting. The adversary may bias the outcome of the voting by selectively killing processes that have chosen to vote the "wrong" way before they can reveal their most recent votes to the other processes. To prevent the adversary from getting more than a constant bias, it is necessary to collect enough votes that the hidden votes shift the outcome by no more than a constant number of standard deviations. With up to n - 1 failures (as in the wait-free case), this requires a total of [Omega]([n.sup.2]) local coin-flips, and at least [Omega]([n.sup.2]) work in order to communicate these coin-flips.(3)

Improvements in other aspects of consensus algorithms have steadily brought their costs down, from the O([n.sup.4]) total work of Aspnes and Herlihy [1990] to the O([n.sup.2] log n) total work of Bracha and Rachman [1991]. But while these algorithms have steadily approached the [Omega]([n.sup.2]) barrier, none have broken it. However, no proof was known that consensus could not be solved in less than [Omega]([n.sup.2]) time; the barrier was solely a result of the apparent absence of alternatives to using shared coins based on majority voting. Indeed, it was asked in Aspnes [1993] if every consensus protocol contained an embedded shared coin protocol; and (specializing a more general and still open question of Ben-Or and Linial [1989]) if no shared coin protocol in this model could beat the [Omega]([n.sup.2]) cost of majority voting.

1.1. OUR RESULTS. We show that for a shared coin protocol to guarantee at most constant bias despite up to t failures, [Omega]([t.sup.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 whether to hide or reveal each local coin, and (c) the protocol can detect which local coins have been hidden. If the protocol has polynomial bias, meaning that the adversary is permitted to control the outcome of the protocol except for cases whose probability is polynomial in t, [Omega]([t.sup.2]/[log.sup.2] t) local coins are needed. An extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus is then used to show that given an adaptive adversary, any t-resilient asynchronous consensus protocol either executes a shared coin protocol with polynomial bias or carries out an expected [Omega]([t.sup.2]) local flips avoiding it. This implies that t-resilient asynchronous consensus requires an expected [Omega]([t.sup.2]/[log.sup.2] t) local coin flips. Since protocols based on majority voting require only O([t.sup.2]) local coin flips, this lower bound is very close to being tight.

Since we are counting coin-flips rather than operations, the lower bound is not affected by deterministic simulations. So, for example, it continues to hold in message-passing models with up to t process failures (since a message channel can be simulated by an unboundedly large register), or in a shared-memory model with counters or cheap atomic snapshots. Furthermore, since our lower bound assumes that local coin flips can have arbitrary ranges and distributions, we may assume without loss of generality that any two successive coin-flips by the same process are separated by at least one deterministic operation in any of these models--so the lower bound on local coin-flips in fact implies a lower bound on total work.

The lower bound on coin-flipping games is still more general, and holds in any model in which the adversary may intercept up to t local coin-flips before they are revealed, no matter what (deterministic) synchronization primitives or shared objects are available. Furthermore, it is tight in the sense that it shows that no constant-bias shared coin can use less than [Omega]([t.sup.2]) local coins, a bound achieved by majority voting.

1.2. RELATED WORK. Many varieties of collective coin-flipping games have been studied, starting with the work of Ben-Or and Linial [1989]. Many such games assume that the locations of faulty coins are fixed in advance; under these assumptions very efficient games exist.(4) Another assumption that greatly limits the power of the adversary is to require that both the locations and values of faulty coins are fixed in advance; this is the bit extraction problem [Chor et al. 1985; Friedman 1992; Vazirani 1985], in which it is possible to derive completely unbiased random bits.

If none of these limiting assumptions are made, the adversary gains considerably more power. If the adversary can subvert running processes based on the execution of the protocol so far, the best strategy for minimizing the adversary's influence in many models seems to be to take the majority of fair coin-flips, the idea being that the majority function minimizes the influence of any single local coin.(5) Ben-Or and Linial [1989] observed that with a restriction to fair coins, Harper's isoperimetric inequality for the hypercube [Harper 1966] implies that the majority function gives the least power to an off-line adversary that can see all coins before deciding which to change (a one-round protocol), and conjectured that a similar result held for multi-round protocols in which n processes repeatedly executed rounds in which each flipped a coin and the adversary could control all coin-flips of a process once it was subverted.

This conjecture is still open, as the present work applies to systems in which the adversary can only alter one local coin-flip for each process that it subverts. (One can think of this restriction as assuming halting failures rather than Byzantine failures in the processes.) A previous paper with similar scope was that of Lichtenstein et al. [1989], who showed that majority is optimal under the assumption of fair local coins in a sequential game similar to the one we consider here. In their model fair coin-flips are generated one at a time and the adversary may replace up to k of them, its decisions depending only on the values of the coin-flips generated so far. The main difference between their results and ours are: (a) they require fair Boolean-valued local coins, where we allow arbitrary distributions and ranges on the local coins; (b) they allow the adversary to replace a coin-flip with a new value of its choosing, where we assume a weaker adversary that can only hide a coin-flip by replacing it with a fixed value [perpendicular to]; and (c) they obtain a tight result that shows that combining the local coins with the majority function (or, in general, any threshold function) minimizes the adversary's influence over the global coin. This result depends strongly on the assumption of fair local coins and the techniques used to prove it do not appear to generalize to arbitrary distributions on the local coins.

In contrast, our results work for arbitrary distributions, but we do not resolve completely the question of whether majority is optimal in our more general model. We do show that for constant bias the number of faults cannot exceed O([square root of n]), the number tolerated (modulo constant factors) by majority, but for large biases our lower bound diverges from the upper bound given by majority. We believe that a strengthened version of our lower bound could show that majority is asymptotically optimal; this issue is discussed in Section 4.

The best previously known bound for arbitrary local coins is a bound of [Omega](1/[square root of n]) on the influence of an adversary that can hide one coin, due to Cleve and Impagliazzo [1993]. They show that in any martingale sequence starting at 0 and ending at [+ or -] 1, with at least constant probability there is a jump of at least [Omega](1/[square root of n]). To translate this into a result about coin-flipping, one constructs a martingale [X.sub.0], [X.sub.1], ..., [X.sub.n] by letting [X.sub.i] be the conditional expectation of the global coin given the values of the first i coins, and observes that if there is a large jump between [X.sub.i] and [X.sub.i+1] the adversary can get a large influence over the outcome of the game by hiding the (i + 1)-th local coin.

Part of the motivation for our work on coin-flipping games was to show a lower bound on the work used by wait-free shared-memory consensus. A very nice lower bound on the space used by wait-free shared-memory consensus is due to Fich et al. [1993]. They show that any such consensus protocol must use [Omega]([square root of n]) distinct registers to guarantee agreement. Unfortunately, their techniques do not appear to generalize to showing lower bounds on work.

2. Coin-Flipping Games

A collective coin-flipping game [Ben-Or and Linial 1989] is an algorithm for combining many local coins into a single global coin, whose bias should be small even though some of the local coins may be obscured by a malicious adversary. Though the particular coin-flipping games we consider here are motivated by their application to proving lower bounds on distributed algorithms with failures, they abstract away almost all of the details of the original distributed systems and are thus likely to be useful in other contexts.

We assume that the local coins are independent random variables whose ranges and distributions are arbitrary. The values of these variables are revealed one at a time to an adversary who must immediately choose whether to reveal or obscure each value. If the adversary chooses to obscure the value of a particular local coin, the effect is to replace it with a default value [perpendicular to]. Repeating this process yields a sequence of values, some of which are the original values of the random variables and some of which are [perpendicular to]. A function is applied to this sequence to yield an outcome, which may be arbitrary but which we will usually require to be [+ or -] 1. The adversary's power is limited by an upper bound on how many coins it may obscure.

Note that in this description we assume that the adversary cannot predict future local coins; it can only base the decision to reveal or obscure a particular coin on the coin's value and the values of earlier coins. In addition, the adversary's interventions are visible. The coin-flipping game may observe and react to the fact that the adversary has chosen to obscure particular local coins, even though it has no access to the true values of those coins.

Formally, a coin-flipping game is specified by a tree. The leaves of the tree specify the outcomes of the game. Internal nodes correspond to local coin-flips. Coin-flipping games are defined recursively as follows: Fix a set of possible outcomes. A coin-flipping game G with maximum length zero consists of a single outcome; we will call such a game a constant game and abuse notation by writing its outcome simply as G. A coin-flipping game G with maximum length n is either a constant game or consists of

(1) A random variable representing the first local coin-flip in G.

(2) A function mapping the range of this random variable to the set of coin-flipping games with maximum length less than n (the subgames of G). For each value [Alpha] in this range, the resulting subgame is denoted [G.sub.[Alpha]].

(3) A default subgame [G.sub.[perpendicular to]] with maximum length less than n, corresponding to the effect of an adversary choice to hide the first local coin-flip in G.

The above definition represents a coin-flipping game as a tree; if we think of G as the root of the tree its children are the subgames [G.sub.[Alpha]] for each value of [Alpha] and the default subgame [G.sub.[perpendicular to]]. The actual game tree corresponding to playing the game against an adversary is a bit more complicated and involves two plies for each level of G. We may think of the states of this game as pairs (G, k) specifying the current subgame G and the limit k on how many local coins the adversary may hide (i.e., the number of faults). To execute the first local coin-flip in G, two steps occur. First, the outcome [Alpha] of the coin-flip is determined. Second, the adversary chooses between revealing [Alpha], leading to the state ([G.sub.[Alpha]] k); or hiding [Alpha], leading to the state ([G.sub.[perpendicular to]], k - 1).

In order to prevent the adversary from being able to predict the future or the game from being able to deduce information about obscured coins, we demand that all random variables on any path through the game tree be independent.

An adversary strategy specifies for each partial sequence of local coin-flips whether to hide or reveal the last coin. We will write G ?? A for the random variable describing the outcome of G when run under the control of an adversary strategy A. If a game G has real-valued outcomes, then for each number of faults k there exist adversary strategies to maximize or minimize the expected outcome. Define [M.sub.k]G to be the maximum expected outcome and [m.sub.k]G to be the minimum expected outcome. These values can be computed recursively as follows:

--If G has length 0, [M.sub.k]G = [m.sub.k]G = G.

--If G has positive length, then

(1) [M.sub.k](G) = [E.sub.[Alpha]][max([M.sub.k][G.sub.[Alpha]], [M.sub.k-1][G.sub.[perpendicular to]])]

(2) [m.sub.k](G) = [E.sub.[Alpha]][min([m.sub.k][G.sub.[Alpha]], [m.sub.k-1][G.sub.[perpendicular to]])].

Most of the time we will assume that the only possible outcomes of a game are [+ or -] 1. In this case, the quantities [M.sub.k] and [m.sub.k] give a measure of how much influence an adversary with the ability to hide k local coin-flips can get over the outcome. It is necessary to consider both at once: as we will see later, it is always possible to find a game with maximum length n whose minimum expected outcome [m.sub.k] can be any value in the range [-1, 1]. We will be interested in the best such game, that is, the one that attains a particular value of [m.sub.k] while minimizing [M.sub.k] (or, symmetrically, the game that maximizes [m.sub.k] for a particular fixed [M.sub.k]). In general it will turn out to be quite difficult to find this game exactly (although much can be shown about its structure), and so it will be necessary to settle for a lower bound on [M.sub.k]G as a function of n, k, and [m.sub.k]G.

2.1. THE STRUCTURE OF OPTIMAL GAMES. Fix a maximum length n and number of failures k. Let us define the range of a game G to be the interval [[m.sub.k]G, [M.sub.k]G]. Then G (strictly) dominates G' just in case the range of G is a (proper) subset of the range of G'; in other words, if G gives the adversary no more control than G' does. A game G is optimal if it either dominates all other games G' with [m.sub.k]G' = [m.sub.k]G or if it dominates all other games G' with [M.sub.k]G' = [M.sub.k]G. For k [is less than] n, this definition will turn out to be equivalent to saying that no game strictly dominates G.

With each k and game G we can associate a point in a two-dimensional space given by the coordinates [m.sub.k]G and [M.sub.k]G. From this geometric perspective the problem we are interested in is finding for each value of n and k the curve corresponding to the set of optimal games with maximum length n and up to k failures.

For some values of n and k this task is an easy one. If k = 0, then the (n, 0) curve is just the diagonal running from (-1, -1) to (1, 1), since [m.sub.0]G = [M.sub.0]G for all G. If the other extreme holds and k [is greater than or equal to] n, then for any G either [m.sub.k]G = - 1 or [M.sub.k]G = 1, depending on the default outcome of G if all local coins are hidden. It is not difficult to see that if [M.sub.n]G = 1, then [m.sub.n]G can be any value between -1 and 1. For example, G could set its outcome to be the value of the first local coin, or 1 if that coin-flip is hidden; if the adversary wishes to achieve an outcome lower than 1 it must let the first local coin go through. Similarly, if [m.sub.n]G = -1, then [M.sub.n]G can be any value between -1 and 1, Thus, the optimal (n, n) curve consists of the line segment from (-1, -1) to (-1, 1) and the line segment from (-1, 1) to (1, 1).

Equations (1) and (2) have a nice geometrical interpretation that in principle allows one to determine the (n, k) curves of optimal games of maximum length n with k failures. This process is depicted in Figures 1 and 2. Fix a game G. Each subgame [G.sub.[Alpha]] corresponds to a point ([m.sub.k][G.sub.[Alpha]], [M.sub.k][G.sub.[Alpha]]), which must lie somewhere on or above the curve of optimal (n - 1, k) games. The contribution of [G.sub.[Alpha]] to the position of G is given by (min([m.sub.k][G.sub.[Alpha]], [m.sub.k-1][G.sub.[perpendicular to]]), max([M.sub.k][G.sub.[Alpha]], [M.sub.k-1][G.sub.[perpendicular to]])), which is a point in the intersection of the region above the (n - 1, k) curve and the rectangle of points dominated by [G.sub.[perpendicular to]]. Since the value of G is the average of these contributions, it must correspond to some point in the convex closure of this intersection. Provided the (n - 1, k) curve is concave (which is easily proved by induction on n as shown below), then all points in the convex closure are dominated by some point on its lower right edge: the line segment between the optimal (n - 1, k) game [G.sub.0] with [M.sub.k][G.sub.0] = [M.sub.k-1][G.sub.[perpendicular to]] and the optimal (n - 1, k) game [G.sub.1] with [m.sub.k][G.sub.1] = [m.sub.k-1][G.sub.[perpendicular to]].

[Figures 1-2 ILLUSTRATION OMITTED]

Geometrically, this edge is the hypotenuse of a right triangle inscribed between the (n - 1, k) and (n - 1, k - 1) curves such that its sides are parallel to the axes and its right corner is on the (n - 1, k - 1) curve. To take into account all possible choices of [G.sub.[perpendicular to]], it is necessary to consider all such triangles. By taking the minimum of the hypotenuses of these triangles (as shown in Figure 2), we obtain the (n, k) curve of all optimal games of maximum length n subject to up to k failures. Note that if the (n - 1, k) curve is nondecreasing and concave (true for n - 1 = k, true as the induction hypothesis for larger n - 1), we may extend each hypotenuse to its containing line without affecting the minimum, and so the (n, k) curve as the minimum of concave functions is also nondecreasing and concave.

Let us summarize. From the discussion of the constraints on G given [G.sub.[perpendicular to]], we have:

THEOREM 2.1.1. For each coin-flipping game G with maximum length n and up to k failures, there is a G' such that G' dominates G, [G'.sub.[perpendicular to]] dominates [G.sub.[perpendicular to]], G' has exactly two nondefault subgames [G'.sub.0] and [G'.sub.1], [M.sub.k][G'.sub.0] = [M.sub.k-1][G'.sub.[perpendicular to]], and [m.sub.k][G'.sub.1] = [m.sub.k-1][G'.sub.[perpendicular to]].

One consequence of this theorem is that we can replace any optimal G with an equivalent G' in which the first local coin has exactly two outcomes, and in which the adversary never prefers hiding a local coin to revealing one. Since the theorem also applies recursively to all subgames of G, we may assume that these conditions in fact hold throughout G'. Thus no additional power is obtained by allowing more than two outcomes to a coin. However, the theorem does not imply that we can require that all local coins are fair; indeed, for most optimal games they will not be.

In addition, we have shown the following about the shape of the curves corresponding to optimal games:

THEOREM 2.1.2. Fix n and k with k [is less than] n. For each x in [-1, 1], let f(x) be the smallest value of [M.sub.k]G for all G such that [m.sub.k]G = x. Then f is nondecreasing and concave.

Unfortunately, with the exception of some extreme cases like k = n - 1, the (n, k) curves do not appear to have nice algebraic descriptions. So while in principle equations (1) and (2) and the minimum-of-hypotenuses construction constrain the curves completely, to obtain any useful bounds from them we will be forced to resort to approximation.

2.2. LOWER BOUNDS FOR FIXED-LENGTH GAMES. The essential idea of our lower bound for fixed-length coin-flipping games is to choose a family of functions to act as lower bounds for the optimal curves as defined above, and show by repeating the inscribed-right-triangle argument with these functions that they do in fact provide lower bounds on the optimal curves given appropriate parameters. The particular family of functions that we use consists of all hyperbolas that are symmetric about the diagonal from (-1, 1) to (1, -1) and that pass through the corner points (-1, -1) and (1, 1).(6) These hyperbolas are conveniently given by

[tanh.sup.-1] y - [tanh.sup.-1] x = c

for various values of c. The linear (n, 0) curve corresponds exactly to c = 0; the (n, n) curve is the limit as c goes to infinity. Our goal is to compute values of c as a function of n and k such that for all length-n games,

[tanh.sup.-1][M.sub.k]G - [tanh.sup.-1] [m.sub.k]G [is greater than or equal to] c(n, k).

Given c(n - 1, k) and c(n - 1, k - 1), repeating the inscribed-right-triangle construction for the resulting hyperbolas is a not very difficult exercise in analytic geometry. Unfortunately, finding the particular point on the hypotenuse of the particular triangle that minimizes c(n, k) is a bit more involved (details of both steps are given in the next two sections). The ultimate result of these efforts is:

THEOREM 2.2.1. Let G be a game of length n with outcome set {-1, +1}. Then for any k [is greater than or equal to] 0, either [M.sub.k]G = 1, [m.sub.k]G = -1, or

(3) [tanh.sup.-1][M.sub.k]G - [tanh.sup.-1] [m.sub.k]G [is greater than or equal to] k/2 [square root of n].

Proof of Theorem 2.2.1. In this section, we assume that each game has length n in all executions. Our results about such games also apply to any game whose maximum length is n, since we can always extend a branch that terminates early with dummy coin-flips that do not affect the outcome.

The proof is by induction on n. The case n = 0 is trivial. For n = 1, we have either k = 0, in which case [M.sub.k]G = [m.sub.k]G and both sides of (3) are zero, or k [is greater than or equal to] 1, and either [G.sub.[perpendicular to]] = 1 and thus [M.sub.k]G = [G.sub.[perpendicular to]] = 1 or [G.sub.[perpendicular to]] = -1 and thus [m.sub.k]G = [G.sub.[perpendicular to]] = -1.

For larger values of n, we wish to show that if the inequality holds for n it holds for n + 1: Observe first that if k = 0 we again have [M.sub.k]G = [m.sub.k]G and the theorem holds. Thus it remains only to consider the case k [is greater than] 0.

Suppose that the inequality holds for length n games and consider a length n + 1 game G. Consider the pair ([m.sub.k]G, [M.sub.k]G) as a point in [[-1, 1].sup.2]. The coordinates of this point are averages over the same distribution; thus we can treat the point itself as an average (as a two-dimensional vector) of a set S of points in [[-1, 1].sup.2]. The coordinates of the points in this set are given by (min([m.sub.k][G.sub.[Alpha]], [m.sub.k-1][G.sub.[perpendicular to]]), max([M.sub.k][G.sub.[Alpha]], [M.sub.k-1][G.sub.[perpendicular to]])) for each possible value of [Alpha].

Each point (x, y) in S must satisfy three constraints: (i) x is at least [m.sub.k-1][G.sub.[perpendicular to]]; (ii) y is at most [M.sub.k-1][G.sub.[perpendicular to]]; and (iii) [tanh.sup.-1] y - [tanh.sup.-1] x [is greater than or equal to] k/2 [square root of n] (by applying the induction hypothesis to [G.sub.[Alpha]]). The region R defined by these three constraints looks like a rectangle with a concave bite taken out of its bottom right corner, which is the corner with coordinates ([m.sub.k-1][G.sub.[perpendicular to]], [M.sub.k-1][G.sub.[perpendicular to]]). What is useful about this region is that it is defined solely in terms of n, k, and the choice of [G.sub.[perpendicular to]]; and we know that any length n game G has payoffs ([m.sub.k]G, [M.sub.k]G) that, as averages of points in the region, must lie somewhere in its convex closure [bar]R.

Thus, we can prove that our inequality holds for all games G by proving that it holds for any point in the convex closure of a region defined as above.

Let's start with the choice of [G.sub.[perpendicular to]]. By the induction hypothesis,

[tanh.sup.-1][M.sub.k-1][G.sub.[perpendicular to]] - [tanh.sup.-1] [m.sub.k-1][G.sub.[perpendicular to]] [is greater than or equal to] k - 1/2 [square root of n].

Thus, there exists a z such that

[M.sub.k-1] [G.sub.[perpendicular to]] [is greater than or equal to] tanh(z + k - 1/4 [square root of n])

and

[m.sub.k-1] [G.sub.[perpendicular to]] [is less than or equal to] tanh(z - k - 1/4 [square root of n])

For the rest of the proof we will ignore the actual payoffs of [G.sub.[perpendicular to]] and use instead the bounds tanh (z [+ or -] (k - 1)/4 [square root of n]).

Now let us consider the extreme points (x, y) on the curve [tanh.sup.-1] y - [tanh.sup.-1] = k/2 [square root of n]. When y = z + (k - 1)/4 [square root of n], we have the point

([x.sub.0], [y.sub.0]) = (tanh(z - k + 1/4 [square root of n], tanh(z + k - 1/4 [square root of n])).

When x = z + (k - 1)/4 [square root of n], we get

([x.sub.1], [y.sub.1]) = (tanh(z - k - 1/4 [square root of n], tanh(z + k + 1/4 [square root of n])).

We wish to show that every point [bar]R is dominated by a convex combination of these two points.

Fix [Alpha] and let x = min([m.sub.k] [G.sub.[Alpha]], [m.sub.k-1] [G.sub.[perpendicular to]]) and y = max([M.sub.k] [G.sub.[Alpha]], [M.sub.k-1] [G.sub.[perpendicular to]]).

Define:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let (x', y') = [[Lambda].sub.[Alpha]] ([x.sub.0], [y.sub.0]) + (1 - [[Lambda].sub.[Alpha]]) ([x.sub.1], [y.sub.1]). We claim that x [is less than or equal to] x' and y' [is less than or equal to] y.

To prove this claim, consider the three cases in the definition of [[Lambda].sub.[Alpha]] separately. If x [is less than or equal to] [x.sub.0], then x [is less than or equal to] x' = [x.sub.0]; furthermore, y' = [y.sub.0] [is less than or equal to] [M.sub.k-1] [G.sub.[perpendicular to]] [is less than or equal to] max([M.sub.k] [G.sub.[Alpha]], [M.sub.k-1][G.sub.[perpendicular to]]) = y. A similar argument proves the claim when [[Lambda].sub.[Alpha]] = 0. For the middle case, we have x = x' = [[Lambda].sub.[Alpha]] [x.sub.0] + (1 - [[Lambda].sub.[Alpha]] [x.sub.1]) and y [is greater than or equal to] tanh ([tanh.sup.-1](x) + k/2 [square root of n]) which is at least [[Lambda].sub.[Alpha]][y.sub.0] + (1 - [[Lambda].sub.[Alpha]])[y.sub.1] by Lemma 2.2.2.4. Thus, the claim holds.

Let [Lambda] = [E.sub.[Alpha]][[[Lambda].sub.[Alpha]]]. From the claim it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We are left with the task of reducing this expression to a more convenient form. To do so, we apply several inequalities involving hyperbolic functions, proved in the next section. In particular the second-to-last inequality below is given by Lemma 2.2.2.2 and the last is given by Lemma 2.2.2.3.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It remains only to show for all k [is greater than or equal to] 1 and n [is greater than or equal to] 1 that

k/2 [square root of n] [sech.sup.2](1/2 [square root of n]) [is greater than or equal to] k/2 [square root of n + 1].

From the Taylor's series expansion of sech z we have sech z [is greater than or equal to] 1 - (1/2)[z.sup.2]. Setting z = 1/(2 [square root of n]) gives

sech 1/ 2 [square root of n] [is greater than or equal to] 1 - 1/8n.

But then

[sech.sup.2] 1/2 [square root of n] [is greater than or equal to] 1 - 1/4n

and

[sech.sup.4] 1/2 [square root of n] [is greater than or equal to] 1 - 1/2n.

Now for n [is greater than or equal to] 1,

1 - 1/2n [is greater than or equal to] 1 - 1/n + 1 = n/n + 1.

Thus, we have

[sech.sup.4] 1/2 [square root of n] [is greater than or equal to] n/n + 1

so

[sech.sup.2] 1/2 [square root of n] [is greater than or equal to] [square root of n/n + 1]

and

k/2 [square root of n] [sech.sup.2] (1/2 [square root of n]) [is greater than or equal to] k/2 [square root of n + 1].

Thus, if G is a length n + 1 game, we have that

[tanh.sup.-1] [M.sub.k]G - [tanh.sup.-1] [m.sub.k] G [is greater than or equal to] k/2 [square root of n + 1]

and the induction goes through.

2.2.2. Some Inequalities Involving Hyperbolic Functions. These are used in the proof of Theorem 2.2.1.

LEMMA 2.2.2.1. Let 0 [is less than or equal to] A [is less than or equal to] B [is less than] 1. Then

(4) (1 + A) (1 + B) [(2 - A - B).sup.2] [is greater than or equal to] (1 - A) (1 - B) [(2 + A + B).sup.2].

PROOF. Each of the inequalities below is implied by the one that follows it:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and this last inequality follows from A + B [is greater than or equal to] 0. []

LEMMA 2.2.2.2. Let 0 [is less than or equal to] a [is less than or equal to] b. Then for all x and all [Lambda] such that 0 [is less than or equal to] [Lambda] [is less than or equal to] 1,

(5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

PROOF. Equality holds when a = b or [Lambda] = 1/2 and x = 0, so we can prove the inequality in general by showing that for fixed a and b with a [is less than] b the left-hand side L of (5) is minimized when [Lambda] = 1/2 and x = 0.

To do so we will take L through a sequence of transformations resulting in a rational function in [Lambda], tanh a, tanh b, and tanh x. Showing that this function is minimized when [Lambda] = 1/2 and x = 0 is equivalent to showing that a certain polynomial obtained by multiplying out denominators is never negative. This problem can in turned be reduced to showing that the polynomial is never negative for certain extreme cases, where its sign can easily be determined. Reversing these steps proves the original bound.

Step (1). Removing occurrences of [tanh.sup.-1] from L. The first step is to remove the inverse hyperbolic tangents that appear in L. To save space let us write [bar][Lambda] for 1 - [Lambda], yielding

L = [tanh.sup.-1] ([Lambda] tanh(x + a) + [bar][Lambda] tanh(x + b)) - [tanh.sup.-1] ([Lambda] tanh(x - b) + [bar][Lambda] tanh(x - a)).

This we can rewrite using the fact tanh and [tanh.sup.-1] are both odd functions to get:

L = [tanh.sup.-1] ([Lambda] tanh(a + x) + [bar][Lambda] tanh(b + x)) + [tanh.sup.-1] ([Lambda] tanh(b - x) + [bar][Lambda] tanh(a - x)).

Let s = [Lambda] tanh(a + x) + [bar][Lambda] tanh(b + x) and let t = [Lambda] tanh(b - x) + [bar][Lambda] tanh(a - x). Recall that for |z| [is less than] 1, [tanh.sup.-1] z = 1/2 ln(1 + x)/(1 - x). Thus,

L = [tanh.sup.-1] s + [tanh.sup.-1] t

= 1/2 ln 1 + s/1 - s + 1/2 ln 1 + t/1 - t

= 1/2 ln (1 + s) (1 + t)/(1 - s) (1 - t).

Thus, to minimize L we need to minimize

(1 + s) (1 + t)/(1 - s) (1 - t).

Step (2). Further expansion using the sum formula for tanh. To do so, we will first expand every occurrence of tanh in s and t using the identity tanh(x [+ or -] y) = (tanh x [+ or -] tanh y)/(1 [+ or -] tanh x tanh y). In order to give the resulting expressions even the slightest hope of readability, let us write X for tanh x, A for tanh a, and B for tanh b. We have

s = [Lambda] tanh(a + x) + [bar][Lambda] tanh(b + x) = [Lambda] A + X/1 + AX + [bar][Lambda] B + X/1 + BX.

Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A similar expansion shows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

from which it follows that

(6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Step (3). Transforming a rational function inequality to a polynomial inequality. The next step is to reduce the problem of showing that the rational function (6) is minimized at x = 0, [Lambda] = 1/2 to an inequality involving only polynomials.

This transformation will be less cumbersome if we can find a way to write (6) more compactly. We've already canceled all the terms that cancel easily; so to simplify it further we are going to need to exploit its internal symmetry. Let [Delta] = 2 [Lambda] - 1, so that [Lambda] = (1 + [Delta])/2 and [bar][Lambda] = 1 - [Lambda] = (1 - [Delta])/2. Let

R = (1 + [Delta]) (1 + A) (1 + BX) + (1 - [Delta]) (1 + B) (1 + AX)

S = (1 - [Delta]) (1 + A) (1 - BX) + (1 + [Delta]) (1 + B) (1 - AX)

T = (1 + [Delta]) (1 - A) (1 + BX) + (1 - [Delta]) (1 - B) (1 + AX)

U = (1 - [Delta]) (1 - A) (1 - BX) + (1 + [Delta]) (1 - B) (1 - AX).

So that (6) is (RS)/(TU) (we are canceling out a few factors of 2 here).

Let us now consider what happens if we set X = 0 and [Delta] = 0 (i.e., x = 0 and [Lambda] = [bar][Lambda] = 1/2). Then R, S, T, and U are all radically simplified and (6) becomes [P.sup.2]/[Q.sup.2] where P = 2 + A + B and Q = 2 - A - B. Since our goal is to show that (RS)/(TU) is minimized at X = 0, [Delta] = 0, we must demonstrate that for any values for X and [Delta] with |X| [is less than] 1 and |[Delta]| [is less than or equal to] 1,

(7) RS/TU [is greater than or equal to] [P.sup.2]/[Q.sup.2].

Observe that since |tanh z| [is less than] 1 for all z, we have |A| [is less than] 1, |B| [is less than] 1, and |X| [is less than] 1. It follows that both T and U are positive and thus the inequality (7) holds just in case RS[Q.sup.2] [is greater than or equal to] TU[P.sup.2] or RS[Q.sup.2] - TU[P.sup.2] [is greater than or equal to] 0.

Step (4). Constraining the coefficients of the polynomial. Consider f ([Delta], X) = [RSQ.sup.2] - [TUP.sup.2] as a polynomial in [Delta] and X. If possible, we'd like to show f is always nonnegative without having to multiply out its many terms. Fortunately, we can get quite a bit of information about its coefficients without such Herculean efforts.

Let [a.sub.ij] be the coefficient in f of [[Delta].sup.i][X.sup.j]. If [Delta] = X = 0, then [RSQ.sup.2] - [TUP.sup.2] = [P.sup.2][Q.sup.2] - [Q.sup.2][P.sup.2] = 0. Thus, [a.sub.00] = 0. By symmetry f([Delta], X) = f(-[Delta], -X) (changing both of these signs swaps R with S and T with U). Thus, [a.sub.ij] = 0 for any i, j such that i + j is odd. Finally, since the largest power of [Delta] or X in each of R, S, T, and U is 1, and neither [Delta] nor X appears in P or Q, we have that [a.sub.ij] = 0 whenever i or j is greater than 2. This leaves four possible nonzero coefficients, and so we can write f as [a.sub.11][Delta]X + [a.sub.20][[Delta].sup.2] + [a.sub.02][X.sup.2] + [a.sup.22][[Delta].sup.2][X.sup.2].

Step (5). Reduction to extreme cases. Now we wish to show that if f is negative anywhere in [[-1, 1].sup.2], it is negative for some point ([Delta], X) with either [Delta] = 1 or X = 1. To do so, we will show that any ([Delta], X) in the interior of [[-1, 1].sup.2] that yields a negative f can be replaced by t[Delta], tX for any t such that |t| [is greater than] 1, with the result that f(t[Delta], tX) will also give a negative f. If all of the terms in f had the same degree, this would be easy; since this is not the case, we must first show that the coefficient [a.sub.22] of the [[Delta].sup.2][X.sup.2] term is negative.

Fortunately, with not too much work [a.sub.22] is seen to be (B - A)(B - A)[Q.sup.2] - (B - A) (B - A)[P.sup.2] or [(B - A).sup.2][[(2 - (A + B)).sup.2] - [(2 + (A + B)).sup.2]] = [(B - A).sup.2][-8[(A + B).sup.2]] [is less than or equal to] 0. So if |t| [is greater than] 1,

(8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, if f is ever negative on [[-1, 1].sup.2], it is negative for some point in which [Delta] = 1 or X = 1, since we can choose whichever of [Delta] or X has larger absolute magnitude and set t = 1/[Delta] or t = 1/X.

Step (5a). [Delta] = 1, X [is not equal to] 1. Let us examine the [Delta] = 1 case first. We will assume that |X| [is less than] 1; the case [Delta] = 1, X = 1 will be covered by the X = 1 case below. Recall that f is negative if and only if the inequality (5) is violated. If [Delta] = 1, then [Lambda] = 1 and (5) becomes

(9) [tanh.sup.-1] tanh(x + a) - [tanh.sup.-1] tanh(x - b) [is greater than or equal to] 2 [tanh.sup.-1] (1/2 tanh a + 1/2 tanh b).

The left-hand side of this inequality simplifies to a + b, and so (9) holds just in case

tanh a+b/2 [is greater than or equal to] 1/2 tanh a + 1/2 tanh b,

which holds because tanh is concave on the positive real line.

Step (5b). X = 1. When X = 1, we have

R = (1 + [Delta])(1 + A)(1 + A)(1 + B) + (1 - [Delta])(1 + A)(1 + B) = 2(1 + A)(1 + B)

S = (1 - [Delta])(1 + A)(1 - B) + (1 + [Delta])(1 - A)(1 + B)

T = (1 + [Delta])(1 - A)(1 + B) + (1 - [Delta])(1 + A)(1 - B) =S

U = (1 - [Delta])(1 - A)(1 - B) + (1 + [Delta])(1 - A)(1 - B)

= 2(1 - A)(1 - B).

Thus, [RSQ.sup.2] - [TUP.sup.2] = 2S(1 + A)(1 + B)[(2 - A - B).sup.2] - 2S(1 - A)(1 - B) [(2 + A + B).sup.2] which is nonnegative by Lemma 2.2.2.1.

Wrap-up. In summary, we have that f([Delta], X) [is greater than or equal to] 0 whenever [Delta] = 1 or X = 1. Using (8), this implies that f([Delta], X) [is greater than or equal to] 0 for all points ([Delta], X) in the unit square [[-1, 1].sup.2], which, after reversing the translations from (5) to f, implies that (5) holds under the conditions stated in the lemma. []

LEMMA 2.2.2.3. If x [is greater than or equal to] 0, then for any a,

(10) tanh(x + a) + tanh(x - a) [is greater than or equal to] 2 tanh(x [sech.sup.2] 2a).

PROOF. The inequality above holds just in case

(11) tanh(x + a) + tanh(x - a) - 2 tanh(x [sech.sup.2] 2a)

is nonnegative for nonnegative x. To avoid unwieldy notation, let us write c for [sech.sup.2] 2a. Observe that

tanh x = [e.sup.2x] - 1/[e.sup.2x] + 1 = 1 - 2/[e.sup.2x] + 1.

So we can rewrite tanh(x + a) + tanh(x - a) - 2 tanh(xc) as

(1 - 2/[e.sup.2x+2a] + 1) + (1 - 2/[e.sup.2x-2a] + 1) - (2 + 2 2/[e.sup.2cx] + 1) = 4/[e.sup.2cx] + 1 - 2/[e.sup.2x+2a] + 1] - 2/[e.sup.2x-2a] + 1.

Note that each of these denominators is positive. Thus multiplying out the denominators and dividing by 2 does not change the sign, and the sign of the original expression is the same as the sign of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [e.sup.2x] [is greater than] 0, we can drop the first factor While preserving the sign. Writing z for [e.sup.2x], and noting that [e.sup.2a] + [e.sup.-2a] = 2 cosh 2a, the second factor becomes

2z - [2z.sup.c-1] + 2(1 - [z.sup.c])cosh 2a,

and now we can divide out 2 without changing the sign to obtain

(12) z - [z.sup.c-1] + (1 - [z.sup.c])cosh 2a.

To show that the inequality (10) holds when x [is greater than or equal to] 0, it is necessary to show that the sign of (12), and thus of (11), is nonnegative for z [is greater than or equal to] 1. Note that when x = 0, z = [e.sup.2x] = 1 and (12) reduces to 0. So if we can show that (12) is nondecreasing for z [is greater than or equal to] 1 we are done.

This we do by taking the derivative of (12) with respect to z and showing that it is non-negative when z [is greater than or equal to] 1. The derivative is 1 - (c - 1)[z.sup.c-2] - [cz.sup.c-1] cosh 2a. Observe that c = [sech.sup.2] 2a [is less than or equal to] 1 and z [is greater than or equal to] 1 implies both [z.sup.c-1] [is less than or equal to] 1 and [z.sup.c-2] [is less than or equal to] 1. Thus, we have

1 - (c - 1)[z.sup.c-2] - [cz.sup.c-1] cosh 2a [is greater than or equal to] 1 - (c - 1) - c cosh 2a = 1 - ([sech.sup.2] 2a - 1) - [sech.sup.2] 2a cosh 2a = 2 - [sech.sup.2] 2a - sech 2a [is greater than or equal to] 0. []

LEMMA 2.2.2.4. If a [is greater than or equal to] 0, then the function f(x) = tanh(a + [tanh.sup.-1] x) is monotone increasing and concave.

PROOF. That f is monotone follows immediately from the monotonicity of tanh and [tanh.sup.-1]. To show it is concave, observe that:

[d.sup.2]/[dx.sup.2] tanh(a + [tanh.sup.-1] x)

= d/dx [sech.sup.2](a + [tanh.sup.-1] x) 1/1 - [x.sup.2]

= 2 sech(a + [tanh.sup.-1] x)[- sech(a + [tanh.sup.-1] x)tanh(a + [tanh.sup.-1] x)] 1/[(1 - [x.sup.2]).sup.2]

+ [sech.sup.2](a + [tanh.sup.-1] x) -1/[(1 - [x.sup.2]).sup.2] 2x

= -2 [sech.sup.2](a + [tanh.sup.-1] x) 1/[(1 - [x.sup.2]).sup.2] [tanh(a + [tanh.sup.-1] x) - x]

[is less than or equal to] 0.

Note that, in the last step, we need the fact that f is monotone to know that the last factor is positive. []

2.2.3. Corollaries to Theorem 2.2.1. Theorem 2.2.1 assumes a coin-flipping game with [+ or -] 1 outcomes. For more general sets of outcomes it is more convenient to work with the minimum and maximum probabilities of some particular outcome rather than the expected outcome. A simple transformation of the theorem gives:

COROLLARY 2.2.3.1. Let G be a coin-flipping game and let x lie in the outcome set of G. Fix k, and let p = [min.sub.A] Pr[G ?? A = x] and q = [min.sub.A] Pr[G ?? A [is not equal to] x], where in each case A ranges over adversaries that can hide up to k local coins. Then

(13) ln 1 - p/p + ln 1 - q/q [is greater than or equal to] k/2 [square root of n].

PROOF. Consider the modification G' of G which replaces each x outcome with +1 and each non-x outcome with +1. Then [m.sub.k]G = [min.sub.A] E[G ?? A] = p - (1 - p) = 2p - 1 and [M.sub.k]G = [max.sub.A] E[G ?? A] = (1 - q) - q = 1 - 2q. Thus

[tanh.sup.-1]([M.sub.k]G) = [tanh.sup.-1](1 - 2q) = ln 1 + (1 - 2q)/1 - (1 - 2q)

= ln 2 - 2q/2q = ln 1 - q/q

and

-[tanh.sup.-1]([m.sub.k]G) = -[tanh.sup.-1](2p - 1) = [tanh.sup.-1](1 - 2p) = ln 1 - p/p.

Substituting into (3) in Theorem 2.2.1 then gives the desired result. []

If the bound on each side is the same, we can simplify even further:

COROLLARY 2.2.3.2. Let G be a coin-flipping game, let x be one of its outcomes, and let A range over adversaries that can hide up to k local coins. If for some [Epsilon] [is less than] 1/2, [min.sub.A] Pr[G ?? A = x] [is greater than or equal to] [Epsilon] and [min.sub.A] Pr[G ?? A [is not equal to] x] [is greater than or equal to] [Epsilon], then the maximum length n of G is at least

[k.sup.2]/16 [ln.sup.2] ((1/[Epsilon]) - 1)

PROOF. From the previous corollary, we have that

k/2 [square root of n] [is greater than or equal to] 2 ln 1 - [Epsilon]/[Epsilon] = 2 ln (1/[Epsilon] - 1).

Since [Epsilon] [is less than] 1/2, the logarithmic term is positive and we can rearrange this inequality to get the desired bound. []

2.3. LOWER BOUNDS FOR VARIABLE-LENGTH GAMES. In the preceding section, we considered the connection between the adversary's influence over the outcome and the maximum length of a game. Here we consider instead the connection between the adversary's influence and the worst-case expected length of a game. In principle, one could imagine low-expected-length games whose small bias was purchased by a high maximum length in rare executions; thus, the bounds on maximum length do not immediately imply bounds on expected length.

However, using a truncation argument, we can show that a bound similar to that given in Corollary 2.2.3.2 holds even if we are considering the expected length of G rather than its maximum length. The theorem below covers both the worst-case expected length (when the adversary is trying to maximize the running time of the protocol) and the best-case expected length (when the adversary is trying to minimize the running time of the protocol). The worst-case bound will be used later to get a lower bound on the work required for consensus.

THEOREM 2.3.1. Fix k, and let A range over adversaries that can hide up to k local coins. Let G be a coin-flipping game with an outcome x such that [min.sub.A] Pr[G ?? A = x] [is greater than or equal to] [Epsilon] and [min.sub.A] Pr[G ?? A [is not equal to] x] [is greater than or equal to] [Epsilon]. Then the worst-case expected length of G is at least

3/64 [multiplied by] [k.sup.2]/[ln.sup.2] (1/[Epsilon]/2 - 1).

and the best-case expected length is at least

1/32 [multiplied by] [Epsilon][k.sup.2]/[ln.sup.2] (1/[Epsilon]/2 - 1).

PROOF. The essential method is to show that if a game exists whose expected length is "too good" then a truncated version of this game exists that violates the requirements of Corollary 2.2.3.2.

Let us assume without loss of generality that G has outcomes x = 1 and 0. (We can justify this assumption by replacing all x outcomes with 1 and all non-x outcomes with 0.)

First, the worst-case bound. Let

m = [k.sup.2]/16 [ln.sup.2] (1/[Epsilon]/2 - 1).

Let [G.sub.m] be the game obtained by truncating G as follows. If G finishes in m or fewer steps, let [G.sub.m] = G. If G finishes in more than m steps, let [G.sub.m] = [perpendicular to]. The value of m is chosen such that for any outcome x of [G.sub.m], at least one of [min.sub.A] Pr[G ?? A [is not equal to] x] and [min.sub.A] Pr[G ?? A [is not equal to] x] is less than or equal to [Epsilon]/2 (using Corollary 2.2.3.2).

For each A and each execution of G ?? A that produces an outcome v, there is an execution of [G.sub.m] ?? A that produces either v or [perpendicular to]. It is given that [min.sub.A] Pr[G ?? A = 0] is at least [Epsilon]; thus it follows that [Epsilon] [is less than or equal to] [min.sub.A] Pr[[G.sub.m] ?? A [element of] {0, [perpendicular to]}] = [min.sub.A] Pr[[G.sub.m] ?? A [is not equal to] 1]. But then [min.sub.A] Pr[[G.sub.m] ?? A = 1] [is less than] [Epsilon]/2. Since for any A, Pr[[G.sub.m] ?? A [element of] {1, [perpendicular to]}] [is greater than or equal to] [Epsilon], we get [min.sub.A] Pr[[G.sub.m] ?? A = [perpendicular to]] [is greater than] [Epsilon]/2. But applying Corollary 2.2.3.2 a second time now implies that [min.sub.A] Pr[[G.sub.m] ?? A [is not equal to] [perpendicular to]] [is less than or equal to] [Epsilon]/2; in other words, that for some adversary A the probability that G ?? A does not finish after m steps is at least 1 - [Epsilon]/2. Since [Epsilon] [is less than] 1/2, this probability is at least 3/4 and so the worst-case expected length of G is at least (3/4)m.

The best-case bound is also obtained by considering a truncated game. Let T = [min.sub.A] E[length(G ?? A)]. Let n = 2T/[Epsilon], so that (using Markov's inequality) the probability that G ?? A has not finished by time n is at most [Epsilon]/2. Thus [min.sub.A] Pr[[G.sub.n] ?? A = [perpendicular to]] [is greater than or equal to] [Epsilon]/2. But [min.sub.A] Pr[[G.sub.n] ?? A [element of] {0, [perpendicular to]}] [is greater than or equal to] [min.sub.A] Pr[G ?? A = 0] [is greater than or equal to] [Epsilon], so [min.sub.A] Pr[[G.sub.n] ?? A = 0] [is greater than or equal to] [Epsilon]/2. By symmetry, we also have [min.sub.A] Pr[[G.sub.n] ?? A = 1] [is greater than or equal to] [Epsilon]/2. Corollary 2.2.3.2 then gives

n [is greater than or equal to] 1/16 [multiplied by] [k.sup.2]/[ln.sup.2] (1/[Epsilon]/2 - 1)

and thus

T = n [multiplied by] [Epsilon]/2 [is greater than or equal to] 1/32 [multiplied by] [Epsilon][k.sup.2]/ [ln.sup.2] (1/[Epsilon]/2 - 1). []

2.4. CONSEQUENCES FOR CONSTANT-BIAS COINS. For constant bias, Corollary 2.2.3.2 and Theorem 2.3.1 imply that we need [Omega]([t.sup.2]) local coin flips in both the worst and average cases. This is true even though the adversary's power is limited by the fact that (a) the local coin flips may have arbitrary ranges and distributions; (b) the adversary can hide coins, but cannot control them; (c) the adversary must decide which coins to hide or reveal immediately in an on-line fashion; and (d) the algorithm may observe and react to the choices of which coins to hide. These assumptions were chosen to minimize the power of the adversary while still capturing the essence of its powers in a distributed system with failures.

In contrast, it is not difficult to see that taking a majority of [Theta]([t.sup.2]) fair coins gives a constant bias even if (a) local coins are required to be fair random bits; (b) the adversary can replace up to t values with new values of its own choosing; (c) the adversary may observe the values of all the local coins before deciding which ones to alter; and (d) changes made by the adversary are invisible to the algorithm. So the [Omega]([t.sup.2]) lower bound for constant bias is tight for a wide range of assumptions about the powers of the algorithm and the adversary.(7)

2.5. CONNECTION TO RANDOMIZED DISTRIBUTED ALGORITHMS WITH FAILURES. The importance of coin-flipping games as defined above comes from the fact that they can often be found embedded inside randomized distributed algorithms. Let us discuss briefly how this embedding works.

Consider a randomized distributed algorithm in a model in which (a) all random events are internal to individual processes; and (b)all other nondeterminism is under the control of an adaptive adversary. Suppose further that the adversary has the power to kill up to k of the processes. Then given any randomized algorithm in which some event X that does not depend on the states of faulty processes occurs with minimum probability m and maximum probability M, we can extract a coin-flipping game from it as follows: Arbitrarily fix all the nondeterministic choices of the adversary except for the decision whether or not to kill each process immediately following each internal random event. (Since this step reduces the options of the adversary, it can only increase m and decrease M.) Each step of the coin-flipping game corresponds to an execution of the distributed algorithm up to some such random event, which we interpret as the local coin. The adversary's choice to hide or reveal this local coin corresponds to its power to kill the process that executes the random event (thus preventing any other process from learning its value) or to let it run (which may or may not eventually reveal the value). The outcome of the coin-flipping game is determined by whether or not X occurs in the original system.

3. Lower Bound for Randomized Consensus

Consensus is a problem in which a group of n processes must agree on a bit. We will consider consensus in models in which at most t processes may fail by halting. Processes that do not halt (i.e., correct processes) must execute infinitely many operations. (A more detailed description of the model is given in Section 3.2.)

It is assumed that each process starts with some input bit and eventually decides on an output bit and then stops executing the algorithm. Formally, consensus is defined by three conditions:

--Agreement. All correct processes decide the same value with probability 1.

--Nontriviality. For each value v, there exists a set of inputs and an adversary that causes all correct processes to decide v with probability 1.

--Termination. All correct processes decide with probability 1.

Nontriviality is a rather weak condition, and for applications of consensus protocols a stronger condition is often more useful:

--Validity. If all processes have input v, all correct processes decide v with probability 1.

As nontriviality is implied by validity, if we show a lower bound on the total work of any protocol that satisfies agreement, non-triviality, and termination, we will have shown a fortiori a lower bound on any protocol that satisfies agreement, validity, and termination. Thus, we will concentrate on consensus as defined by the first three conditions.

Since the agreement and termination conditions are violated only with probability zero, we can exclude all schedules in which they are violated without affecting the expected length of the protocol or the independence and unpredictability of local coin-flips. Thus, without loss of generality, we may assume that not only do agreement and termination apply to the protocol as a whole, but they also apply even if one conditions on starting with some particular finite execution [Alpha].

3.1. OVERVIEW OF THE PROOF. In a randomized setting, we are concerned with the cost of carrying out a consensus protocol in terms of the expected total work when running against a worst-case adversary. We show how the coinflipping lower bound can be used to show a lower bound on the worst-case expected cost of t-resilient randomized consensus in the standard asynchronous shared-memory model. As in the coin-flipping bound, we will measure the cost of a consensus protocol by the total number of local coin-flips executed by the processes. This measure is not affected by deterministic simulations, so any results we obtain for the shared-memory model will also apply to any model that can be simulated using shared memory, such as a t-resilient message-passing model.

For each adversary strategy and finite execution [Alpha] there is a fixed probability that the protocol will decide 1 conditioned on the event that its execution starts with [Alpha]. (We may speak without confusion of the protocol deciding 1, as opposed to individual processes deciding 1, because of the agreement condition.) For any set of adversaries, there is a range of probabilities running from the minimum to the maximum probability of deciding 1.

These ranges are used to define a probabilistic version of the bivalence and univalence conditions used in the well-known Fischer-Lynch-Paterson (FLP) impossibility proof for deterministic consensus [Fischer et al. 1985]. We will define an execution as bivalent if the adversary can force either outcome with high probability. A v-valent execution will be one after which only the outcome v can be forced with high probability. Finally, a null-valent execution will be one in which neither outcome can be forced with high probability. The notions of bivalence and v-valence (defined formally in Section 3.3) match the corresponding notions for deterministic algorithms used in the FLP proof; null-valence is new, as it cannot occur with a deterministic algorithm in which the probability of deciding each value v must always be exactly 0 or 1.

In outline, the proof that consensus is expensive for randomized algorithms retains much of the structure of the FLP proof. First, it is shown that with at least constant probability any protocol can be maneuvered from its initial state into either a bivalent or a null-valent execution. Once the protocol is in a bivalent execution, we show that there is a fair, failure-free extension that leads either to a local coin-flip or a null-valent execution. The result of flipping a local coin after a bivalent execution is, of course, random; but we can show that with high probability it leaves us with an execution that is either bivalent or null-valent or from which we are likely to return to a bivalent or a null-valent execution after additional coin-flips. If we do reach a null-valent execution, the coin-flipping bound applies.

Unlike a deterministic protocol, it is possible for a randomized protocol to "escape" through a local coin-flip into an execution in which it can finish the protocol quickly. But we will be able to show that the probability of escaping in this way is small, so that on average many local coin-flips will occur before it happens.

3.2. MODEL FOR CONSENSUS LOWER BOUND. This section describes in detail the model used for the consensus lower bound. It is included for completeness, as lower bounds are notoriously sensitive to features of the underlying model. However, the reader who is familiar with previous work on asynchronous shared-memory systems will find no surprises here, and may wish to skip ahead to the actual proof starting in Section 3.3.

3.2.1. Foundations. There are many ways to represent a distributed system; we will use the I/O automaton model as described in Lynch [1996]. In this model, an execution of a system is represented by a sequence [s.sub.0], [[Pi].sub.1], [s.sub.1], [[Pi].sub.2], ... of alternating states and actions, starting with an initial state. An execution may be finite or infinite; if finite, it ends with a state. The behavior of a deterministic system is described by a transition relation consisting of triples ([s.sub.0], [Pi], [s.sub.1]) specifying the prior state, the action that occurs during the transition, and the posterior state. For a randomized system, the third element is replaced by a probability distribution over new states. An action [Pi] is said to be enabled after a finite execution [Alpha] if there is a transition (s, [Pi], P) such that s is the last state in [Alpha].

We will assume that for any state s and action [Pi], there is at most one transition (s, [Pi], P). We will call an action [Pi] a deterministic action if for any s such that (s, [Pi], P) appears in the transition relation, P assigns probability 1 to a single state. Other actions are randomized actions. We will assume that a randomized action must be local: it can change the state of only one process.

Under the above assumptions, the effect of executing a deterministic action [Pi] after a finite execution [Alpha] is well-defined; we will write the resulting execution as [Alpha][Pi]. For a randomized action, suppose that C is a random variable representing its outcome; we will write [Alpha]C for the (random) execution that results from executing the randomized action after [Alpha]. In order to avoid dragging in too much measure-theoretic machinery, we will assume that there are only countably many possible outcomes of each local coin-flip. Among other things, this assumption means that we can exclude all outcomes whose probability is zero without having more than a probability-zero effect on the behavior of a system.

An execution [Beta] is an extension of [Alpha] if [Alpha] (considered formally as a sequence of states and actions) is a prefix of [Beta]. If the suffix of [Beta] after [Alpha] consists only of deterministic actions, we write that [Beta] is a deterministic extension of [Alpha].

Often there will be several actions that are enabled after some finite execution [Alpha]. The choice of which action to execute will be given to an adversary, a function mapping each finite execution to an action enabled in its final state. Letting the domain of the adversary function be the entire previous execution implies first that the adversary has total knowledge of the system's history and present state; but also that the adversary cannot base its choices on future events, such as the outcome of randomized actions that have not yet occurred. We will assume that the adversary does not itself use a randomized strategy; since we are in the lower-bound business this restriction on the adversary does not affect our results.

3.2.2. Shared-Memory Model. Re lower bound for randomized consensus will be given in the context of the standard asynchronous shared-memory model (see Lynch [1996] for a definition of the shared-memory model in terms of I/O automata). In this model, the processes communicate by reading and writing a set of shared atomic registers. It may be assumed without loss of generality that operations on the registers are in fact instantaneous; so even though a read or write operation may be modeled formally as more than one action (e.g., as a separate invocation and response), we can treat this sequence of actions as a single step.

We will define the property that a step x is enabled after an execution [Alpha], the result [Alpha]x of executing x after [Alpha], and so forth, in the obvious way. Thus, having secured the connection between our intuitive understanding and the underlying formal model, we will think of each process as carrying out a sequence of read, write, and local coin-flip steps, without worrying too much about the actual actions that make up these steps.

An additional property of the shared-memory model is that processes may fail. The failure of a process is a deterministic action that is always enabled, and its effect is to prevent the process from carrying out any more actions. We will usually assume a limit on the number of failures and require that any process that does not fail (or halt on its own) executes infinitely many steps. Both of these requirements are restrictions on the range of possible adversaries. The first forbids adversaries that cause too many failures. The second forbids adversaries that starve processes that have not failed.

An algorithm that operates in a model permitting up to t failures is called t-resilient.

3.3. BIVALENCE, UNIVALENCE, AND NULL-VALENCE. Formally, for each execution [Alpha] and adversary A, write Pr[v|[Alpha], A] for the probability that the protocol decides v after [Alpha] running under the control of adversary A. For each execution [Alpha] and set of adversaries A, let [r.sub.v,A] ([Alpha]) be the set of such probabilities ranging over all adversaries in A; that is, [r.sub.v,A] = {Pr[v|[Alpha], A]|A [element of] A}. Since the fact that the protocol terminates with probability 1 implies Pr[0|[Alpha], A] = 1 -- Pr[1|[Alpha], A], no additional information is gained by keeping track of [r.sub.0] and [r.sub.1] separately; thus, we will drop the v subscript and write [r.sub.A](Alpha]) for [r.sub.1,A]([Alpha]). In addition, when the set A is clear from context, we will drop it as well and just write r([Alpha]) for [r.sub.1,A]([Alpha]).

Fix [Epsilon] [is greater than] 0. We will classify executions using the maximum probabilities of deciding 0 or 1 according to the following table.

An execution that is either 0-valent or 1-valent will be called univalent. Note that this classification is exhaustive: every execution falls into exactly one of these classes.
Classification   min r([Alpha])       max r([Alpha])
of [Alpha]

bivalent         <[[Epsilon].sup.2]   [is greater than] 1
                                      - [[Epsilon].sup.2]

0-valent         <[[Epsilon].sup.2]   [is greater than or
                                      equal to] 1 -
                                      [[Epsilon].sup.2]

1-valent         [is greater than     [is greater than] 1
                 or equal to]         - [[Epsilon].sup.2]
                 [[Epsilon].sup.2]

null-valent      [is greater than     [is greater than or
                 or equal to]         equal to] 1 -
                 [[Epsilon].sup.2]    [[Epsilon].sup.2]


It is not hard to see that for deterministic algorithms these definitions reduce to the FLP definitions of a bivalent execution as one in which either outcome is possible (i.e., can occur with probability 1), and a v-valent execution is one in which only the outcome v is possible.

The FLP proof is based on the fact that for deterministic protocols, any extension of a v-valent execution is also v-valent. This fact is used to prove impossibility of deterministic consensus by showing that if a protocol can always extend a bivalent execution to either a 0-valent or 1-valent execution (necessary to reach a decision) it must have a 0-valent execution that is indistinguishable from a 1-valent execution (a contradiction).

We will not be deriving any contradictions from randomized protocols--randomized consensus is not impossible. Instead we will show that if a bivalent execution can be extended to either a 0-valent or a 1-valent execution through deterministic steps, then there exist deterministic extensions of these 0-valent and 1-valent executions that can be made indistinguishable. The resulting indistinguishable executions are not a contradiction; instead, they are null-valent.

The reason is that any deterministic extension of a v-valent execution may be either v-valent or null-valent. This fact is immediate from the lemma below:

LEMMA 3.3.1. Let [Alpha]' be a deterministic extension of [Alpha]. Then r(Alpha]') [subset or equal to] r([Alpha]).

PROOF. Let p be an element of r([Alpha]'). Then, there is some adversary A' in A such that Pr[1|[Alpha]', A'] = p. But then the adversary A which first executes the steps leading to [Alpha]' and then follows the strategy of A' gives Pr[1|[Alpha], A] = p, and thus p is in r(Alpha]). []

If only deterministic operations are enabled after some execution [Alpha], the converse holds:

LEMMA 3.3.2. Let [Alpha] be an execution after which only deterministic operations are enabled. Then r([Alpha]) is the union of r([Alpha]x) for each Operation x enabled after [Alpha].

PROOF. In proving the lemma, it is necessary to be a little careful about failures. Observe that for any adversary A that fails some process after [Alpha], there is an adversary A' that simulates A without failing this process, delaying it instead until some other process decides. Since no process can distinguish A from A' until the decision value is fixed, both give the same probability of deciding 1 starting from [Alpha]. Thus, in computing r(Alpha]), we need consider only adversaries that do not fail any processes as the first step after [Alpha].

For each operation x enabled after [Alpha], let [A.sub.x] be the set of adversaries that choose x. Then r([Alpha]) = [[union].sub.x] [r.sub.Ax]([Alpha]) = [[[union].sub.x] r([Alpha]x). []

In particular, if such an [Alpha] only has v-valent successors, it must be v-valent.

In contrast, the range after a local coin-flip may be arbitrary. However, the expected endpoints of the range after the flip will always be equal to the endpoints of the range before the flip. This fact is not immediately obvious but it is not too hard to prove.

LEMMA 3.3.3. Let [Alpha] be an execution and let C be a random variable that describes the outcome of some particular local coin-flip enabled after [Alpha]. Then the expected value of min r([Alpha]C) is equal to min r([Alpha]), and the expected value of max r([Alpha]C) is equal to max r([Alpha]).

PROOF. We will prove the lemma only for max r([Alpha]C); the case of min r([Alpha]C) is symmetric.

First, observe that max r(Alpha]) is at least E[max r([Alpha]C)], since E[max r([Alpha]C)] is the probability of deciding 1 starting from [Alpha] with an adversary that executes C and then follows the maximizing strategy in whatever execution results.

To show that max r([Alpha]) is at most E[max r([Alpha]C)], let A be any adversary such that Pr[1[[Alpha], A] = max r([Alpha]). We can modify A to get an adversary A' that executes C immediately after [Alpha], and then simulates A, ignoring the result of C until A chooses to execute C. Since a local coin-flip commutes with all operations of other processes, the executions produced by A and A' are indistinguishable and Pr[1|[Alpha], A'] = Pr[1|[Alpha], A ] = max r([Alpha]). But Pr[1|[Alpha], A'] is E[Pr[1|[Alpha]C, A'] [is less than or equal to] max r([Alpha]C). []

3.4. VALENCE OF INITIAL STATES. To get the proof off the ground, we will need to show that there exists an initial state with the appropriate properties. The following lemma does so.

LEMMA 3.4.1. For any t-resilient consensus protocol with t [is greater than] 0, there is an initial state [Alpha] such that min r([Alpha]) [is less than] 1/2 and max r([Alpha]) [is greater than or equal to] 1/2.

PROOF. The proof is essentially identical to the proof that a bivalent initial state exists for a deterministic protocol. First, observe that if two initial states a and [Alpha]' differ in only one input, then given any adversary that kills the process with that input as the first action, the resulting executions are indistinguishable to all live processes. Thus, r([Alpha]) and r([Alpha]') overlap at at least one point.

Now consider two states [Alpha] and [Beta] such that min r([Alpha]) = 0 and max r([Beta]) = 1. (These states, which are not necessarily distinct, exist by the nontriviality condition.) There exists a chain of initial states [[Alpha].sub.0] = [Alpha], [[Alpha].sub.1], [[Alpha].sub.2], ..., [[Alpha].sub.k] = [Beta] such that each adjacent pair of states differ in only one input. Let [[Alpha].sub.i] be the first state in the chain for which max r([[Alpha].sub.i]) [is greater than or equal to] 1/2. If i = 0, we are done: min r([[Alpha].sub.i]) = 0 [is less than] 1/2. Otherwise, max r([[Alpha].sub.i-1]) [is less than] 1/2, implying min r([[Alpha].sub.i]) [is less than] 1/2, since r([[Alpha].sub.i-1]) and r([[Alpha].sub.i]) must overlap. []

3.5. STRATEGY FOR UNIVALENT EXECUTIONS. Starting with a univalent execution, one of the outcomes can be forced with high probability. In this case the adversary's strategy will be to minimize the likelihood of that outcome in the hopes of getting back to a bivalent or null-valent execution. The likelihood of being able to do so is described by the following lemma:

LEMMA 3.5.1. Let [Alpha] be a failure-free 1-valent execution such that min r([Alpha]) = p. Then there is an adversary strategy that, with probability at least 1 - p, extends [Alpha] to a failure-free execution [Alpha][Beta] such that one of the following conditions holds:

(1) [Alpha][Beta] is null-valent;

(2) [Alpha][Beta] is bivalent and [Beta] contains at least one local coin-flip;

(3) [Alpha][Beta] is 0-valent, max r([Alpha][Beta]) [is greater than] 1 - [Epsilon], and [Beta] contains at least one local coin-flip; or

(4) [Beta] contains an expected 1/[Epsilon] local coin-flips.

PROOF

CLAIM 3.5.2. For any failure-free execution [Alpha] for which 0 [is less than] min r([Alpha]) [is less than] 1, there-exists some failure-free deterministic extension [Alpha]' of [Alpha] such that min r([Alpha]') = min r([Alpha]) and a local coin-flip is enabled after [Alpha]'.

PROOF. There is some adversary A for which Pr[1|[Alpha], A] - min r([Alpha]). Since Pr[1|[Alpha], A] is not 0 or 1, A must eventually cause the protocol to execute a coin-flip after some deterministic extension [Alpha]' or [Alpha]. (Otherwise, the protocol does not satisfy the termination condition). If A causes failures, it can be simulated by an adversary A' that simply delays "failed" processes until after the coin-flip. That min r([Alpha]') = min r([Alpha]) is immediate from Lemma 3.3.1.

Here is the full adversary strategy: carry out [Alpha]' as described above, and then execute a local coin-flip. Repeat until max r drops to 1 - [[Epsilon].sup.2], min r drops below [[Epsilon].sup.2], or a decision is reached.

Now let us show that this strategy works as advertised. We have min r([Alpha]') = min r([Alpha]) [is greater than or equal to] 1 - [[Epsilon].sup.2]; and from Lemma 3.3.1 the only other effect of executing deterministic steps can be to reduce max r([Alpha]'). If max r([Alpha]') is less than or equal to 1 - [[Epsilon].sup.2], [Alpha]' is null-valent and case (1) of the lemma holds. Otherwise, we must consider the possible outcomes of the local coin-flip.

Let C be the random variable whose values are the possible outcomes of the local coin-flip. From Lemma 3.3.3, E[max r([Alpha]' C)] -- max r([Alpha]) [is greater than] 1 - [[Epsilon].sup.2]. By Markov's inequality, the probability that max r([Alpha]' C) is less than or equal to 1 - [Epsilon] is less than [Epsilon]. So on average, we expect to execute at least 1/[Epsilon] local coin-flips before max r drops below 1 - [Epsilon]. This possibility accounts for case (4).

Suppose that max r([Alpha]C) does not drop below 1 - [Epsilon]. There are several possibilities. If min r([Alpha]C) [is less than] [[Epsilon].sup.2], case (2) or (3) holds, and we are done. If min r([Alpha]C) [is greater than or equal to] [[Epsilon].sup.2] and max r([Alpha]C) [is less than or equal to] 1 - [[Epsilon].sup.2], case (1) holds, and again we are done. If max r([Alpha]C) [is greater than] 1 - [[Epsilon].sup.2], then we may repeat the process described above until we reach a new local coin-flip, unless a decision of 1 is reached; but the probability that the protocol reaches a decision of 1 following this strategy is at most p. So with probability at least 1 - p, one of the other outcomes occurs. []

By symmetry, it is immediate that the lemma also holds if the decision values 0 and 1 are swapped.

3.6. STRATEGY FOR BIVALENT EXECUTIONS. Given a bivalent execution [Alpha], we wish to show that [Alpha] has a fair, failure-free deterministic extension that is either null-valent (so we can apply the coin-flipping bound) or permits a local coin-flip in its final state.

LEMMA 3.6.1. Let [Alpha] be a failure-free bivalent execution, and let x be a deterministic operation that is enabled after [Alpha]. Then there exists a finite deterministic extension [Beta] of [Alpha] such that one of the following conditions holds:

(1) [Beta] is failure-free, bivalent, and a local coin-flip is enabled after [Beta];

(2) [Beta] is failure-free, bivalent, and contains x; or

(3) [Beta] contains at most one failure and is null-valent.

PROOF. Consider the set S of all bivalent failure-free deterministic extensions [Gamma] of [Alpha]. If there is a [Gamma] in S after which a local coin-flip is enabled, we are done: case (a) holds with [Beta] = [Gamma]. If there is a [Gamma] in S containing x, we are done: case (2) holds with [Beta] = [Gamma]. If there is a [Gamma] in S such that [Gamma]y is null-valent for some y, we are done: case (3) holds with [Beta] = [Gamma]y.

Otherwise, let [Gamma] be a maximal execution in S, that is, one such that no extension of [Gamma] is in S. Such an execution exists because every execution in S must be finite by the termination condition. Under the assumption that none of the conditions above hold, we know that:

(1) No local coin-flip is enabled after [Gamma].

(2) For each operation y, [Gamma]y is univalent. (It cannot be null-valent; nor can it be bivalent, because then [Gamma] is not maximal.)

(3) The operation x is enabled after [Gamma]. (It is enabled after [Alpha]; for it not to be enabled after [Gamma] it must appear in [Gamma].)

Assume without loss of generality that [Gamma]x is 0-valent; the case where it is 1-valent is symmetric. Then there exists some y such that [Gamma]y is 1-valent, as otherwise [Gamma] would be 0-valent by Lemma 3.3.2, contradicting its membership in S. We will show by a case analysis that there are always deterministic extensions of [Gamma]x and [Gamma]y that are distinguishable by at at most one process. Killing this process thus leads to indistinguishable executions that deterministically extend 0-valent and 1-valent executions; these executions must both be null-valent and we can choose either one for [Beta] and satisfy condition (3).

There are several cases depending on the type of the operations x and y:

(1) x and y are operations on different registers. In this case x and y commute and the states resulting from [Gamma]xy and [Gamma]yx are the same. No killing is necessary; [Gamma]xy and [Gamma]yx are both null-valent.

(2) x is a read operation. If y is also a read operation, the operations commute and [Gamma]xy and [Gamma]yx are both null-valent as above. If y is a write operation, then only the process performing x can distinguish between [Gamma]yx and [Gamma]xy. Killing this process yields a pair of indistinguishable executions that are thus both null-valent.

(3) y is a read operation. This case is symmetric with the previous case.

(4) x and y are both write operations on the same register. Then [Gamma]yx is distinguishable from [Gamma]x only by the process performing y. Again, killing this process yields two indistinguishable executions that must both be null-valent. []

Iterating the lemma eliminates one of the cases:

LEMMA 3.6.2. Let [Alpha] be a failure-free bivalent execution. Then there exists a finite deterministic extension [Beta] of [Alpha] such that either

(1) [Beta] is failure-free and a local coin-flip is enabled after [Beta], or

(2) [Beta] contains at most one failure and is null-valent.

PROOF. Let [[Alpha].sub.0] = [Alpha]. For each [[Alpha].sub.i], let [x.sub.i] be the operation enabled after [[Alpha].sub.i] that has been enabled the longest and let [[Alpha].sub.i+1] be the finite deterministic extension of [[Alpha].sub.i] whose existence is implied by Lemma 3.6.1. If [[Alpha].sub.i+1] is failure-free and a local coin-flip is enabled after it, set [Beta] = [[Alpha].sub.i+1]. Similarly set [Beta] = [[Alpha].sub.i+1] if [[Alpha].sub.i+1] contains at most one failure and is null-valent. If [[Alpha].sub.i+1] is bivalent, contains [x.sub.i], and no coin-flip is enabled in [[Alpha].sub.i+1], continue with [[Alpha].sub.i+1] and a new [x.sub.i+1].

This process must eventually terminate with [Beta] equal to some [[Alpha].sub.i]. Otherwise, it would yield an infinite, fair, failure-free deterministic extension of [Alpha], violating the termination condition. []

The lemma above implies that we can always reach an execution that either is null-valent or permits a coin-flip. For this fact to be useful, coin-flips cannot be too destructive. The following lemma constrains their wrath:

LEMMA 3.6.3. Let [Alpha] be a bivalent execution and let C be a random variable corresponding to the possible outcomes of a local coin-flip enabled in [Alpha]. Then

Pr[min r([Alpha]C) [is greater than or equal to] [Epsilon] [disjunction] max r([Alpha]C) [is less than or equal to] 1 - [Epsilon]] [is less than] 2[Epsilon].

PROOF. Let X = min r([Alpha]C). Then X [is greater than or equal to] 0, and E[X] = min r([Alpha]) [is less than] [[Epsilon].sup.2]. So by Markov's inequality the probability that min r([Alpha]C) reaches [Epsilon] is less than [[Epsilon].sup.2]/[Epsilon] = [Epsilon]. Adding the probability of the symmetric event that max(r[Alpha]C) reaches 1 - [Epsilon] raises the bound to 2[Epsilon]. []

Thus, with high probability, the result of a local coin-flip after a bivalent execution is an execution that is either bivalent, null-valent, or univalent with a very wide range. In the case of a bivalent execution, the adversary may continue as above. In the case of a null-valent execution, the coin-flipping bound applies. The case of a univalent execution with a wide range is covered below.

3.7. THE FULL STRATEGY. Here is the full strategy used to prove the lower bound. It is divided into four cases corresponding to four conditions that could hold at the end of each partial execution:

(1) Start in an initial state whose range straddles 1/2. The existence of such a state is guaranteed by Lemma 3.4.1. If this state is bivalent or null-valent, skip to the appropriate condition below. Otherwise, the state must either be 0-valent with max r [is greater than or equal to] 1/2 or 1-valent with min r [is less than or equal to] 1/2. In either case, Lemma 3.5.1 or its symmetric equivalent applies, and with probability at least 1/2 we reach one of conditions (2), (3), or (4); or we execute an expected 1/[Epsilon] local coin-flips before deciding.

(2) From a 0-valent execution with max r [is greater than] 1 - [Epsilon] or a 1-valent execution with min r [is less than] 1 - [Epsilon], apply Lemma 3.5.1 or its symmetric equivalent. With probability 1 - [Epsilon]: one of the following occurs: we reach one of conditions (2) or (3) after executing at least one local coin-flip; we reach condition (4); or we execute an expected 1/[Epsilon] local coin-flips before deciding.

(3) From a bivalent execution, apply Lemma 3.6.2 to either reach a null-valent execution with at most one failure, or a bivalent execution after which a local coin-flip is enabled. If we reach a bivalent execution after which a local coin-flip is enabled, apply Lemma 3.6.3 to show that the result of this coin-flip lands us in condition (2), (3), or (4) with probability at least 1 - 2[Epsilon].

(4) From a null-valent execution with at most one failure, Theorem 2.3.1 applies, and there is an adversary strategy that forces an expected

3[(t - 1).sup.2]/64 [ln.sup.2](2/[Epsilon] - 1)

local coin-flips before termination.

With a suitable choice of [Epsilon], the existence of this strategy implies:

THEOREM 3.7.1. Against a worst-case adaptive adversary, any t-resilient consensus protocol for the asynchronous shared-memory model performs an expected

[Omega]([(t - 1/log (t - 1)).sup.2])

local coin-flips.

PROOF. Let I be the expected cost from the initial state in case (1); U the expected cost from the univalent execution in case (2); B the expected cost from the bivalent execution in case (3); and N the expected cost from the null-valent execution in case (4). Then we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Our goal is to work backwards from the lower bound on N to get a lower bound for I. Let M be the smallest of U, B, and N. There are three cases:

--M = U. Then U [is greater than or equal to] (1 - [Epsilon])min(1 + U, 1/[Epsilon]). This implies U is at least 1/[Epsilon] - 1; for if we assume that U [is less than or equal to] 1/[Epsilon] - 1, we get U [is greater than or equal to] (1 - [Epsilon])(1 + U) and thus [Epsilon]U [is greater than or equal to] 1 - [Epsilon] or U [is greater than or equal to] 1/[Epsilon] - 1.

--M = B. Then B [is greater than or equal to] (1 - 2[Epsilon])(1 + B), implying B [is greater than or equal to] (1/2[Epsilon]) - 1.

--M = N. Then M [is greater than or equal to] 3[(t - 1).sup.2]/64 [ln.sup.2](2/[Epsilon] - 1).

In each case, we have

(14) M [is greater than or equal to] min[1/2[Epsilon] - 1, 3[(t - 1).sup.2]/ 64 [ln.sup.2] (2/[Epsilon] - 1)].

Since I [is greater than or equal to] (1/2) min(M, 1/[Epsilon]), the right-hand side of (14), divided by 2, gives a lower bound on the number of local coin-flips executed by the consensus protocol. If we set [Epsilon] = [(t - 1).sup.-2], this expression reduces to the bound claimed in the theorem. []

The bound counts the number of local coin-flips. Because we allow coin-flips to have arbitrary values (not just 0 or 1), local coin-flips performed by the same process without any intervening operations can be combined into a single coin-flip without increasing the adversary's influence. Thus, the lower bound on local coin-flips immediately gives a lower bound on total work. Furthermore, because the coin-flip bound is not affected by changing the model to one that can be deterministically simulated by shared memory, we get the same lower bound on total work in any model that can be so simulated, no matter how powerful its primitives are. So, for example, wait-free consensus requires [Omega]([n.sup.2]/[log.sup.2] n) work even in a model that supplies counters or O(1)-cost atomic snapshots.

4. Discussion

For those of us who like working with an adaptive adversary, randomization has given only a temporary reprieve from the consequences of Fischer, Lynch, and Paterson's impossibility proof for deterministic consensus with faulty processes. Theorem 3.7.1 means that even though we can solve consensus using randomization, we cannot hope to solve it quickly without a small upper bound on the number of failures, built-in synchronization primitives, or restrictions on the power of the adversary.

Fortunately, there are a number of natural restrictions on the adversary that allow fast consensus protocols without eliminating the faults that we might reasonably expect to observe in real systems. One plausible approach is to limit the knowledge the adversary has of register contents, to prevent it from discriminating against coin-flips it dislikes. Various versions of this can be found in the consensus work of Chor et al. [1987] and Abrahamson [1988], and in the O(n [log.sup.2] n) total work protocol of Aumann and Bender [1996], the O([log.sup.2] n) work-per-process protocol of Chandra [1996], and the recent O(log n) work-per-process protocol of Aumann [1997]. Restrictions on the amount of asynchrony can also have a large effect [Alur et al. 1994; Saks et al. 1991].

A question that we have not completely answered is the following: Does the majority of n fair coin-flips give an optimal coin-flipping game (in the sense of having minimum bias) with an adversary that can censor up to k flips? Majority is optimal for similar models (e.g., in the fair-local-coin model studied by Lichtenstein et al. [1989]). Theorem 2.2.1 implies that it is not possible to achieve constant bias with more than k = O([square root of n]) faults, the amount tolerated by majority, but there is still a gap between the lower bound of Theorem 2.2.1 and the upper bound of the majority game when k is large relative to [square root of n]. It can be shown using the analysis in Section 2.1 that taking a majority of fair coins cannot be optimal in an absolute sense when biased local coins are allowed, as the optimal games characterized in that section generally do not use fair local coins. However, it is still possible that majority is close to optimal, and it might be possible to show (for example) that no game where the adversary was allowed to hide 2k local coins could have a smaller bias than majority with k hidden coins.

One possible approach to showing majority is close to optimal is suggested by the fact that the hyperbolic tangent function tanh in Theorem 2.2.1 essentially acts as an easier-to-manipulate approximation to the normal distribution function [Phi]. If we replace tanh by [Phi] and adjust the set of possible game outcomes to match the range of [Phi], we get the following conjecture:

CONJECTURE 4.1. Let G be a game of length n with outcome set {0, 1}. Then there exists a constant c [is greater than] 0 such that for any k [is greater than or equal to] 0, either [M.sub.k]G = 1, [m.sub.k]G = 0, or

(15) [[Phi].sup.-1][M.sub.k]G - [[Phi].sup.-1][m.sub.k]G [is greater than or equal to] ck/[square root of n].

If true, the conjecture would give a lower bound that would match (up to constant factors) the upper bound given by majority voting, and would improve by a factor of log n the lower bound for consensus given in Theorem 3.7.1.

A still more general question asked by Ben-Or and Linial [1989], also still open, is whether majority voting is optimal in a Byzantine model in which processes may vote more than once but in which the adversary controls all future votes of a process once it has been corrupted. Our work shows that the number of local coins flipped in this model must be large relative to the number of failures, but it does not exclude the possibility that the number of distinct processes might still be relatively small.

ACKNOWLEDGMENTS. The author is indebted to Russell Impagliazzo for many fruitful discussions of coin-flipping problems, Steven Rudich for a suggestion that eventually became the truncation argument used to prove Theorem 2.3.1, Mike Saks for encouragement and pointers to related work, and Faith Fich, Wai-Kau Lo, Eric Ruppert, and Eric Schenk for many useful comments on an earlier version of this work.

(1) See, for example, Chor et al. [1987], Dolev et al. [1987], Fischer et al. [1985], Herlihy [1991], and Loui and Abu-Amara [1987].

(2) See, for example, Aspnes and Herlihy [1990], Attiya et al. [1989], Saks et al. [1991], Aspnes [1993], Dwork et al. [1992], Bracha and Rachman [1990; 1991], and Aspnes and Waarts [1996].

(3) Some of the algorithms deviate slightly from the simple majority-voting approach described here. In the algorithm of Aspnes [1993], some votes are generated deterministically. In the algorithm of Saks et al. [1991], several coin-flipping protocols optimized for different execution patterns are run in parallel. In the algorithm of Aspnes and Waarts [1996], processes that have already cast many votes generate votes with increasing weights in order to finish the protocol quickly. However, none of these protocols costs less than simple majority voting in terms of the expected total number of local coin flips performed in the worst case.

(4) See, for example, Alon and Naor [1990], Cooper and Linial [1993], Ben-Or et al. [1987], and Saks [1979].

(5) An excellent survey of results for a wide variety of models involving fair or nearly fair two-valued local coins can be found in Ben-Or et al. [1987].

(6) We conjecture (Conjecture 4.1) that a slightly tighter lower bound could be proven using the curves given by [[Phi].sup.-1](y) - [[Phi].sup.-1](x) = c, where [Phi] is the normal distribution function. An analog of Theorem 2.2.1 using [Phi] instead of tanh would improve the consensus lower bound in Theorem 3.7.1 by a logarithmic factor.

(7) The theorem does not apply if the adversary cannot observe local coin-flips, and so it cannot be used with an oblivious (as opposed to the usual adaptive) adversary. However, the bound on best-case expected length does imply that it is impossible to construct a "hybrid" constant-bias coin-flipping protocol that adapts to the strength of the adversary, finishing quickly against an oblivious adversary but using additional work to prevent an adaptive adversary from seizing control. This is not the case for consensus; for example, Chandra's [1996] consensus algorithm for a weak adversary switches over to an algorithm that is robust against an adaptive adversary if it does not finish in its usual time.

REFERENCES

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.

ALON, N., AND NAOR, 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.

ALUR, 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.

ASPNES, J. 1993. Time- and space-efficient randomized consensus. J. Algorithms 14, 3 (May), 414-431.

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.

ASPNES, J., AND HERLIHY, M. 1990. Fast randomized consensus using shared memory. J. Algorithms 11, 3 (Sept.), 441-461.

ASPNES, J., AND WAARTS, O. 1996. Randomized consensus in O(n [log.sup.2] n) operations per processor. SIAM J. Comput. 25, 5 (Oct.), 1024-1044.

ATTIYA, H., 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.

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.

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.

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.

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.

BRACHA, G., AND RACHMAN, O. 1990. Approximated counters and randomized consensus. Tech. Rep. 662. Technion, Israel.

BRACHA, G., AND RACHMAN, O. 1991. Randomized consensus in expected O([n.sup.2] log n) operations. In Proceedings of the 5th Workshop on Distributed Algorithms. Springer-Verlag, New York, pp. 143-150.

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.

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.

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.

CLEVE, R., AND IMPAGLIAZZO, R. 1993. Martingales with Boolean final value must make jumps of O(1/[n.sup.1/2]) with constant probability. Unpublished manuscript.

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.

DOLEV, D., DWORK, C., AND STOCKMEYER, L. 1987. On the minimal synchronism needed for distributed consensus. J. ACM 34, 1 (Jan.), 77-97.

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.

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.

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.

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.

HARPER, L. H. 1966. Optimal numberings and isoperimetric problems on graphs. J. Combinat. Theory 1, 385-394.

HERLIHY, M. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1 (Jan.), 124-149.

LICHTENSTEIN, D., LINIAL, N., AND SAKS, M. 1989. Some external problems arising from discrete control processes. Combinatorica 9, 269-287.

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.

LYNCH, N. A. 1996. Distributed Algorithms. Morgan-Kaufmann, San Mateo, Calif.

SAKS, M. 1989. A robust non-cryptographic protocol for collective coin flipping. SIAM J. Disc. Math. 2, 2, 240-244.

SAKS, M., SHAVIT, N., AND WOLL, H. 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.

VAZIRANI, 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.

RECEIVED FEBRUARY 1997; REVISED AUGUST 1997; ACCEPTED JANUARY 1998

A preliminary version of this paper appeared in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, 1997, pp. 559-568.

J. Aspnes was supported by National Science Foundation (NSF) grants CCR 94-10228 and CCR 94-15410.

Author's address: Yale University, Department of Computer Science, 51 Prospect Street/P.O. Box 208285, New Haven, CT 06520-8285; e-mail: aspnes@cs.yale.edu.
COPYRIGHT 1998 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1998 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:ASPNES, JAMES
Publication:Journal of the Association for Computing Machinery
Geographic Code:1USA
Date:May 1, 1998
Words:17734
Previous Article:Efficient Descriptor-Vector Multiplications in Stochastic Automata Networks.
Next Article:Fault-Tolerant Wait-Free Shared Objects.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters