Coordination Through Stochastic Channels

We describe algorithms minimizing the expected discrepancy, showing several interesting, surprising behaviors.

• $\mathrm{■}$

  We first study the case of two processes in detail, proving tight upper and lower bounds on the expected discrepancy. In particular, we prove a lemma, referred to as the Integrality Lemma, stating that, for optimal algorithms, it is sufficient to assume that the processes always decide integral values, either $0$ or $1$. We present two algorithms, one that is optimal for $p\le 1/2$, and one that is optimal for $p\ge 1/2$. Our lower bound technique shows that stochastic settings can be analyzed by following the algebraic topology approach although the latter was initially designed for analyzing protocols in non-stochastic settings [12].

• $\mathrm{■}$

  When one considers executions conditioned on the event that at least one message is delivered, it is intuitively clear that, when $p$ is large, i.e., when the probability of message delivery is high, it should be possible to obtain small expected discrepancy, namely, going down to $0$ as $p$ gets closer to $1$. We confirm this intuition with our algorithms. However, we additionally show that this is also the case when $q=1-p$ is large, i.e. when the probability of message loss is high. As $q$ gets closer to $1$, the expected discrepancy of our algorithms also goes down to $0$. In particular, when we discuss the application to randomized consensus, we will see that the probability of error goes down to $0$, both when the probability of message loss is either very low or very high (conditioned on the event that at least one message is delivered).

• $\mathrm{■}$

  We then move on to the case of $n>2$ processes. We show that the Integrality Lemma does not hold anymore, even for three processes. That is, an optimal algorithm must decide fractional values. As for the case of two processes, we show that there are thresholds for the values of $p$ such that, depending on whether the value of $p$ is smaller or larger than each threshold, a different algorithm minimizes the expected discrepancy. As mentioned above, for two processes, there is a unique threshold $\theta =1/2$, but we show that, for three processes, there are two thresholds ${\theta }_1\approx 0.35$ and ${\theta }_2=1/2$. We provide optimal algorithms for three processes, one for each interval $[0,{\theta }_1]$, $[{\theta }_1,{\theta }_2]$, and $[{\theta }_2,1]$ of message delivery probability $p$.

• $\mathrm{■}$

  For the case of a large number of processes $n$, we design a 1-round algorithm which guarantees an expected discrepancy that goes to $0$ when $n$ grows to infinity, except for highly unbalanced input configurations, i.e., when the number of 0s is $\omega (\log n)$, or when the number of 1s is $\omega (\log n)$. We however show how to adapt our 1-round algorithm for handling all possible input configurations, at the mere expense of one additional round.

• $\mathrm{■}$

  Finally, to support our claim that minimizing the expected discrepancy could be useful in applications where processes must decide values within a small $ϵ$ from each other in most executions, and tolerate few executions with large discrepancy – as for clock synchronization, sensor replication, among others (see, e.g. [9]) – we provide some concrete applications. Specifically, we design algorithms solving randomized binary consensus, and randomized approximate agreement, with small error probability. In fact, for two processes, our randomized approximate agreement algorithm also applies to the case of arbitrary inputs in $[0,1]$, or even in $ℝ$, and we can also prove corresponding lower bounds.

Alon et al. [1] consider a model similar to ours, from the information theoretic perspective. They assume binary symmetric channels (BSC), i.e each message is a bit that may be flipped with some constant probability $\epsilon >0$. Their concern is computing a function (while ours is computing a task). Roughly, they show that for $n\to \mathrm{\infty }$, any computation over failure-free channels can be emulated, with high probability, over BSC channels with a constant multiplicative overhead. These results are asymptotic and are not applicable to small $n$ values, but they inspired our Theorem 15.

In a single round, Alice and Bob send one message each, and hence there are four possible executions, according to whether each message was delivered or not. Remark 2 states that a player who did not receive a message must output its input value. So a single-round protocol can be completely characterized by the outputs made by the players as a response to the reception of a message containing a value different than their input (in all other cases, the output must be equal to the input).

Let us denote by $y_A\in [0,1]$ the output of Alice (with input 0) after receiving a message with value 1 from Bob, and similarly $y_B\in [0,1]$ denote the output of Bob (with input 1) after receiving value 0 from Alice. Each message is delivered with probability $p$, and dropped with probability $q=1-p$.

We consider two types of 1-round algorithms, which as we shall prove, are optimal, each one on its own range of $p$.

Agreed Meeting Point $y$ (AMP$(y)$):

The algorithm specifies an arbitrary meeting point $y\in [0,1]$, and sets $y_A=y_B=y$. That is, if a player receives a value different than its input value, then it outputs $y$; otherwise it outputs its input value.

Flip Value (FV):

The protocol is the following. If a player receives a value $x^{\prime }$ different from its input value, then it outputs $x^{\prime }$; otherwise it outputs its input value.

Figure 3(3(a)) shows the expected discrepancy of the two algorithms as a function of $p$, as stated in the following theorem. If $p=q=1/2$, either AMP or FV can be used, so long as both players use the same algorithm.

Consider now an algorithm running for $k$ rounds, for any fixed $k\in \mathbb{N}$, known by both processes. Given a single-round algorithm, one simple strategy is replication, i.e., sending the 1-round algorithm message $k$ times, so as to decrease the probability that the message is not received from $q$ to $q^k$. We shall see that the replication strategy is optimal only for $p\ge 1/2$. Instead, we use any of our single-round algorithms recursively. That is, we used the output of round $i\ge 1$ as the input of round $i+1$. For simplicity, we can force the inputs to always be in $\{0,1\}$, by using algorithm AMP with meeting point either at $0$ or at $1$ (algorithm FV satisfies the requirement in any case).

To analyze the expected discrepancy of multiple rounds, we note that the discrepancy of round $i+1$ is a random function (because the execution is stochastic) of a random variable, namely, the discrepancy of round $i$. The main part of the argument is stated as follows.

The result in Theorem 6 is illustrated in Figure 3(3(b)).

A recursive algorithm for the case where it is assumed that at least one message is delivered in each round can be derived in a similar way, from Theorem 4 and Lemma 5.

We already discussed briefly the notion of protocol complex, only for one round, in Figure 1. We explain it in more detail and generalize it to multiple rounds in Section 4.1.1, and then define the notion of an algorithm for a protocol complex in Section 4.1.2.

In Section 3.1 we analyzed single round algorithms, and showed that there always exists an optimal algorithm whose only possible output values are $0$ and $1$. In this section we consider the general case of two player, $r$-rounds algorithms, and show that the same integrality property holds as well. The idea is the following. For every given input assignment, the discrepancy of an approximate agreement algorithm is a random variable which we wish to minimize. We shall formalize the problem as an optimization problem, which we then convert into a linear program. The result will follow from the fact that the optimal solution is at a vertex of the polytope defined by the constraints.

We have now all the ingredients to prove a lower bound on the expected discrepancy of any $r$-round protocol. To this end, fix an algorithm $𝒜$ and a number of rounds $r$. We focus on the instance where Alice gets input $x_A=0$, and Bob gets input $x_B=1$.

We study the protocol complex $𝒫$ of $𝒜$ after $r$ rounds. In this complex, each edge is associated with some probability (depending on the message deliveries in that execution), and a certain discrepancy (depending on the output values defined by the decision function $\delta$ of the protocol, in the local states at the edge endpoints). By Lemma 8 we may assume w.l.o.g. that the output values are only $0$ and $1$. We can therefore partition the vertices of the protocol complex into the set of vertices whose output is 0 and the set of vertices whose output is 1. All edges within a set correspond to executions with discrepancy $0$, and all edges that connect vertices in different sets correspond to executions with discrepancy $1$. The expected discrepancy is therefore simply the sum of the probabilities of the edges that connect the different sets. In graph theoretic terms, if we view the probability of an execution as the weight of the corresponding edge in the protocol complex, the expected discrepancy is the weight of the edges in the cut defined by the output values. Our goal of obtaining a lower bound on the expected discrepancy can be restated as bounding from below the weight of cuts in the protocol complex.

Let $s,t$ denote the two nodes in the 0-round protocol complex $G_0$ (see Figure 4(a)). These nodes correspond to the local states of $A$ and $B$, respectively, where no message is ever received. With these local states, by the validity requirement (Remark 2), $A$ and $B$ are forced to output their input values, namely $0$ and $1$, respectively. We are thus interested in bounding from below the weight of $s$-$t$ cuts in the $r$-round protocol complex $G_r$.

Let $G=(V,E,w)$ be a graph with edge weights, and let $s,t\in V$ be two distinct nodes in $G$. Recall that an $s$-$t$ cut of $G$, denoted $(S,\overline{S})$ is a partition of $V$ into two subsets $S$ and $\overline{S}=V\setminus S$ where $s\in S$ and $t\in \overline{S}$. The weight of $(S,\overline{S})$, denoted by $w(S;\overline{S})$, is the sum of weights of edges with one endpoint in $S$ and another in $\overline{S}$.

Recall from Section 4.1.1 that $T(e)$ is the protocol complex graph of one round executions starting in $e$.

The linear program of Section 4.2 can be extended to any number of players as follows. While the constraints of Eq. (5) must always be maintained, the target function of Eq. (4) changes. In Eq. (4), we are minimizing the expected discrepancy of a single input assignment. This is fine for the two-party case, because there is only one non-trivial input in this case (namely $\overline{x}=(0,1)$). However, this is no longer true for more than two players: For example, if there are $3$ parties, there are two non-isomorphic nontrivial input assignments: $(0,0,1)$ and $(0,1,1)$. This means that our goal is to minimize the maximum of the discrepancies of the different inputs.

To deal with this, we introduce a new variable, say $v$ (the goal of the linear program is to minimize $v$), and a new constraint for each input assignment. Specifically, for each input assignment $\overline{x}$, let $\mathrm{\Gamma }(\overline{x})$ denote the set of all executions with input assignment $\overline{x}$, and for any execution $\mathrm{\Gamma }$, let $𝖣(\mathrm{\Gamma })$ be the discrepancy of the outputs in $\mathrm{\Gamma }$. Then, for each input assignment $\overline{x}$, we introduce the constraint $v\ge {\sum }_{\mathrm{\Gamma }\in \mathrm{\Gamma }(\overline{x})}\mathrm{Pr}[\mathrm{\Gamma }]𝖣(\mathrm{\Gamma })$ (similarly to the expression in the r.h.s. of Eq. (4).) Since the goal is to minimize $v$, the program will find the outputs which minimize the worst-case discrepancy, over all inputs.

However, the new constraints change the polytope and create vertices in non-integral coordinates. Indeed, we have computed the optimal 1-round for 3 players using the linear program formulation. The optimal protocol sometimes decides $1/2$: see Figure 6 for a specification of the optimal protocol according to the value of $p$. Interestingly, the output value $1/2$ is not used when $p$ is small. The expected discrepancy for the three strategies is plotted in Figure 7.

We have seen that already for three players the optimal expected discrepancy behaves differently than for two players. At the extreme end of the spectrum we have the case of $n$ players, with $n\to \mathrm{\infty }$. It turns out that 2 rounds suffice in this case to guarantee 0 discrepancy with high probability. In fact, 0 discrepancy can also be guaranteed w.h.p. in 1 round, if the minority is not too small.

Let us start with the case of one round. We use AMP with any meeting point. Note that the probability that a process does not receive a value decreases exponentially with the number of times that value is sent. Therefore, when one of the values (say 1) is held by a sublogarithmic number of players, there is non-negligible probability that at least one of the other players (with input 0) does not receive any 1 message. Formally, for any $n\ge 2$ and $0\le m\le n$, let

Consensus in the case of $n=2$ synchronous reliable processes when messages can be lost is called coordinated attack since [10] (also two generals’ problem). The randomized coordinated attack [22], or for arbitrary number of processes, randomized consensus, see, e.g., [2, p.66], for a given desired upper bound error probability , is defined by the following conditions, for processes starting with binary input values, and agreeing on binary output values.

Randomized Consensus

Termination:

All processes terminate in a bounded number of rounds, $r$.

Validity:

If all processes start with the same value, that is the only value that can be decided.

Randomized agreement:

The probability that some process decides $0$ and some other process decides $1$ is at most $\rho$.

A straightforward application of Markov-like inequality gives the following result, for any number of players.

Since our 2-party algorithms produce discrepancy either $0$ or $1$, we have the following result.

The usual $ϵ$-approximate agreement problem requires processes to decide values at most $ϵ$ apart. Here we define a relaxed version, allowing an error of $\rho$. Formally, it requires the following to hold.

$(ϵ,\rho )$-Approximate Agreement

Termination:

All processes terminate in a bounded number of rounds, $r$.

Validity:

The value decided by every processor is in the range spanned by all input values.

Randomized $ϵ$-Agreement:

The probability that the discrepancy is larger than $ϵ$ is at most $\rho$.

In the classic version of approximate agreement [6], the input values are arbitrary real numbers. Input values in a bounded region such as $[0,1]$, have also been considered e.g. [19]. The number of rounds $r$ depends on $ϵ$. In fact, it may depend also on the discrepancy of the input values (the maximal distance between inputs) or even their magnitude, see e.g. [3]. The relative discrepancy agreement optimization can be defined as its discrepancy normalized by the discrepancy of the input values.

We have the following consequence of our lower bound on the expected discrepancy of agreement optimization. It is stated for inputs in $[0,1]$ (it could be rephrased in terms of the discrepancy of the inputs)

We can also derive upper bounds on $(ϵ,\rho )$-Approximate Agreement using agreement optimization, for the case of 2 players with arbitrary real input values, as follows.

First, note that non-binary inputs may be a problem for algorithms such as AMP: where should the meeting point be located? If we fix the location in advance, validity may be violated. And if a process computes it based on the values it has seen, the meeting point may be different at different processes because their views may be different. However, this is easily solvable in the case of two processes. The point is that the agreed meeting point is used only when two values are known, and in the case of two processes, if both their views contain two values, they must contain the same two values, so it is possible to specify a common meeting point.

Specifically, consider the following algorithm for $a\in [0,1]$.

Algorithm Scaled AMP$(a)$ (2 players, arbitrary input values in $ℝ$)

• $\mathrm{■}$

  If no value is received, output the input value.

• $\mathrm{■}$

  Otherwise, denote the local input and the 4 value by $x$ and $y$. Output $\min \{x,y\}+a\cdot |y-x|$.

Clearly, scaled AMP is a generalization of AMP to any input values, assuming there are only two players. Since Algorithm FV also works with arbitrary input values, we arrive at the following result.

We note that we have not attempted to optimize the constants. For the case of $p\le 1/2$, we use the recursive FV algorithm and the following similar statement holds.

The nice property of scaled AMP is that it allows us to use AMP$(a)$ with in the recursive version, thus obtaining a “continuous” algorithm, i.e., an algorithm in which the discrepancy shrinks (probabilistically) in each round, rather than algorithms in which the discrepancy is either 0 or 1.