# Tight bounds on the size of 2-monopolies

Jean-Claude Bermond, Johny Bond, David Peleg, Stéphane Perennes

► To cite this version:

Jean-Claude Bermond, Johny Bond, David Peleg, Stéphane Perennes. Tight bounds on the size of 2-monopolies. Conference SIROCCO96, International Informatics Series 6, Carleton University, Jun 1996, Siena, Italy. pp.170-179. hal-03832700

HAL Id: hal-03832700

https://hal.science/hal-03832700

Submitted on 27 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Tight Bounds on the Size of 2-Monopolies

(Extended abstract)

J-C. Bermond¹

J. Bond¹

D. Peleg²

S. Perennes¹

¹ I3S CNRS, Université de Nice-Sophia Antipolis, Bât ESSI, 930 Route des Colles, BP 145, F-06903 Sophia-Antipolis, France. E-mail: {bermond,bond,sp}@unice.fr. This work was done during the different visits of the authors at the Weizmann Institute, and has been partially supported by a French-Israeli cooperation (AFIRST).

² Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel. E-mail: peleg@wisdom.weizmann.ac.il. Part of this work was done while this author was visiting the Université de Nice-Sophia Antipolis. Supported in part by a grant from the Israel Science Foundation and by a grant from the Israel Ministry of Science and Art (via the French-Israeli cooperation).

**Abstract.** This paper deals with the question of the influence of a *monopoly* of vertices, seeking to gain the majority in local neighborhoods in a graph. Say that a vertex $v$ is *r-controlled* by a set of vertices $M$ if the majority of its neighbors at distance $r$ are from $M$. We ask how large must $M$ be in order to *r-monopolize* the graph, namely, *r-control every vertex*. Tight upper and lower bounds are provided for this problem. For any even $r \ge 2$, an *r-monopoly* $M$ in an $n$-vertex graph must be of size $\Omega(n^{3/5})$, and there exist $n$-vertex graphs with *r-monopolies* of size $O(n^{3/5})$. As for odd $r$ values, we show that for every odd $k \ge 1$, a $3k$-monopoly $M$ in an $n$-vertex graph must be of size $\Omega(n^{6/11})$ and that for any odd $r$ there exist $n$-vertex graphs with *r-monopolies* of size $O(n^{4/7})$. This settles a problem left open in $[L^{+}93, BP95]$.

# 1 Introduction

## 1.1 The problem

Majority voting, in one form or another, is used as a component of fault-tolerant algorithms in a wide variety of contexts, including agreement and consensus problems (cf. [LSP82, Br87, D+88]), quorum system applications (cf. [G79, GMB85, SB94, JRT91]), self-stabilization and local mending [KP95a, KP95b], and more.

In the context of distributed network algorithms, the majority ruling method must be used in a restricted and local fashion, by replicating the data of a processor $v$ only among processors in $v$'s *local vicinity*. The chief reason for this focus on locality is that in the distributed network model, computations are local in nature, namely, the accessibility of data to a processor is greatly affected by its distance from it.

On the other hand, the potential risk in limiting ourselves to local neighborhoods is that it makes it possible for a sufficiently large set of faults to *corrupt*
the majority in some of these neighborhoods. Generally speaking, the ability of failed vertices to influence the voting process is not only a function of their number but also a function of their location in the network, namely, strategically positioned vertices may have greater influence.

This observation naturally leads to the fundamental problem of characterizing the potential power of a set of failures in a network of processors. In particular, previous work has focused on the notion of monopolies in graphs. This notion is defined as follows.

**Definition 1.** A vertex $v$ in a network $G(V, E)$ is said to be controlled by the vertex set $M$ if at least half of its neighbors are in $M$.

The set $M$ is called a *monopoly* if it controls every vertex in the graph.

The question of bounds for the size of monopolies in the graph was addressed in [L+93], and the following tight answers were provided.

**Proposition 2.** [L+93]

1. In every $n$-vertex graph, a monopoly must be of size $\Omega(\sqrt{n})$.

2. There exist (infinitely many) $n$-vertex graphs with monopolies of size $O(\sqrt{n})$.

A graph $G$ with a monopoly of size $O(\sqrt{n})$ as in Prop. 2(2) is depicted in Fig. 1. The graph consists of a coalition $M$ of $\sqrt{n}+1$ vertices, connected by a clique, plus a set of $\sqrt{n}$ leaves attached to each vertex of $M$.

<figure><img src="image_2.png" /><figcaption>Fig. 1. A graph $G$ with a monopoly $M$ of size $O(\sqrt{n})$.</figcaption></figure>

The above results may be interpreted as the result of the limited scope of our majority voting. Indeed, one may hope to strengthen the quality of the voting by querying vertices to larger distances. Let $\Gamma_r(v)$ denote the $r$-neighborhood of $v$ in $G$, i.e., the set of vertices at distance $r$ or less from $v$. A variant of the above question, in which neighborhoods are replaced by $r$-neighborhoods for some fixed $r$, was also discussed in [L+93].

**Definition 3.** A vertex $v$ in a network $G(V, E)$ is said to be $r$-controlled by the vertex set $M$ if at least half of the vertices in $\Gamma_r(v)$ are in $M$.

The set $M$ is called an *$r$-monopoly* if it $r$-controls every vertex in the graph.
It is shown in [L+93] that for any fixed $r \ge 1$ there exist (infinitely many) $n$-vertex graphs with $r$-monopolies of size $O(n^{2/3})$. However, the question of tight bounds for $r$-monopolies was left open.

In this paper we improve this bound on the size of $r$-monopolies, and show a bound that is tight for even $r$.

**Proposition 4.**

1. In every $n$-vertex graph, an $r$-monopoly for even $r \ge 2$ must be of size $\Omega(n^{3/5})$.

2. For any fixed $r \ge 2$ there exist (infinitely many) $n$-vertex graphs with $r$-monopolies of size $O(n^{3/5})$.

3. In every $n$-vertex graph, a 3k-monopoly for odd $k \ge 1$ must be of size $\Omega(n^{6/11})$.

4. For any fixed odd $r$ there exist (infinitely many) $n$-vertex graphs with $r$-monopolies of size $O(n^{4/7})$.

In what follows we prove the above claims 1 and 2, and illustrate claim 4. The proof of claim 3 is deferred to the full paper.

**1.2 Related work**

The variant of a self-ignoring $r$-monopoly, namely, a set $M$ that $r$-controls every vertex in $V \setminus M$ was studied in [BP95]. That paper also studied the influence of an arbitrary coalition $M$ (that is not a monopoly) as a function of its size.

Certain dynamic variants of majority voting problems were studied in the literature, in the context of discrete time dynamical systems. These variants dealt with a setting in which the nodes of the system operate in discrete time steps, and at each step, each node computes the majority in its neighborhood, and adapts the resulting value as its own. Typical problems studied in this setting concern the behavior of the resulting sequence of global states (represented as a vector $\bar{x}^t = (x_1^t, \dots, x_n^t)$, where $x_i^t$ represents the value at node $v_i$ after time step $t$). For instance, the fact that the period of such sequences is either one or two is proved (in various contexts) in [GO80, PS83, PT86]. The problem was studied further in [M94c, M94b, M94a]. Also, the applicability of majority voting as a tool for fault-local mending was investigated in [KP95a, KP95b].

For a review of recent results in the area, see [P96].

**2 Lower Bounds**

Given a graph $G = (V, E)$ and a set $S \subset V$, let $\Gamma_r(S, G)$ denote the $r$-neighborhood of $S$ in $G$, i.e., the set of vertices at distance $r$ or less from some node of $S$ in $G$. (We omit the parameter $G$ when it is clear from the context.) Given a graph $G = (V, E)$, a vertex $x \in V$, and a set $S \subset V$, we denote by $\deg_G(x, S)$ the number of neighbors of $x$ in $G$ belonging to $S$, namely, $|\Gamma_1(x, G) \cap S|$. (We omit the parameter $S$ when it is the entire vertex set of $G$; we omit the subscript
G when it is clear from the context.) $D_G(x, y)$ denotes the distance in G between $x$ and $y$. Given a subset $S$ of $V$, define the distance from $x$ to $S$ in G as $D_G(x, S) = \min_{y \in S}(D_G(x, y))$.

## 2.1 The case of 2-monopoly

In this section we concentrate on the case of 2-monopolies. For notational convenience, we will refer to the pair $(G, M)$ as a “2-monopoly” whenever $G$ is a graph $(V, E)$ and $M \subseteq V$ is 2-monopoly for $G$.

For $i = 1, 2$, let $S_i$ denote the set of vertices at distance $i$ from $M$, that is, $S_i = \{v \in V | D_G(v, M) = i\}$, and let $s_i = |S_i|$. Also let $m = |M|$. Note that if $(G, M)$ is a 2-monopoly then $V = M \cup S_1 \cup S_2$ and $|V| = m + s_1 + s_2$.

The influence of a subset $S \subset V$ on a vertex $v$ in the graph $G$ is defined by

$$ \mathcal{I}_G(S, v) = |\{w \in S | D_G(v, w) \le 2\}|. $$

(We omit the subscript $G$ whenever clear from the context.) More generally, the influence of a set $S$ on a set $S'$ is $\mathcal{I}_G(S, S') = \sum_{x \in S'} \mathcal{I}_G(S, x)$.

Using the $\mathcal{I}$ notation, a vertex $v$ is 2-controlled by $M$ if $\mathcal{I}(M, v) \ge \mathcal{I}(S_1 \cup S_2, v)$, and a subset $S$ of $V$ is 2-controlled if every vertex $x \in S$ is.

In what follows we make frequent use (sometimes without mention) of the following three immediate properties of $\mathcal{I}$.

**Proposition 5.**

1. $\mathcal{I}$ is a symmetric function, i.e., $\mathcal{I}(S, S') = \mathcal{I}(S', S)$ for every $S, S' \subseteq V$.

2. $\mathcal{I}(S, S) \le |S|^2$ for every $S \subseteq V$, and

3. $\mathcal{I}$ is monotone nonincreasing in the size of $E$, namely, if $G' = (V, E')$ for $E' \subseteq E$, then $\mathcal{I}_{G'}(S, S') \le \mathcal{I}_G(S, S')$ for every $S, S' \subseteq V$.

**Lemma 6.** If $(G, M)$ is a 2-monopoly, then $\mathcal{I}(S_1 \cup S_2, M) \le m^2$ and $\mathcal{I}(S_1 \cup S_2, S_1 \cup S_2) \le m^2$.

**Proof** As all the nodes are 2-controlled, we have for every $v \in V$,

$$ \mathcal{I}(S_1 \cup S_2, v) \le \mathcal{I}(M, v). \qquad (1) $$

By summing (1) on all $v \in M$ we get

$$ \mathcal{I}(S_1 \cup S_2, M) \le \mathcal{I}(M, M) \le m^2, \qquad (2) $$

proving the first claim. On the other hand, by summing (1) on all $v \in S_1 \cup S_2$ we get

$$ \mathcal{I}(S_1 \cup S_2, S_1 \cup S_2) \le \mathcal{I}(M, S_1 \cup S_2) = \mathcal{I}(S_1 \cup S_2, M), \qquad (3) $$

and combining (2) and (3), the lemma follows.

Our main two lemmas bound the size of $S_1$ and $S_2$ with respect to $M$.

**Lemma 7.** If $(G, M)$ is a 2-monopoly, then $s_1 \le m^{3/2}$.
**Proof** For every vertex $y \in S_1$, we assign a unique neighbor $p(y)$ in $M$ as its parent. For every $x \in M$, let $\alpha(x)$ denote the number of children assigned to it. Note that $s_1 = \sum_{x \in M} \alpha(x)$. Also note that for every vertex $y \in S_1$, $\alpha(p(y)) \le I(y, S_1) \le I(y, M)$. Therefore

$$ \sum_{x \in M} \alpha^2(x) = \sum_{y \in S_1} \alpha(p(y)) \le \sum_{y \in S_1} I(y, M) = I(S_1, M) \le m^2. $$

By convexity, this sum is minimal when all the values of $\alpha(x)$ are equal; that happens when $\alpha(x) = s_1/m$ as $s_1 = \sum_{x \in M} \alpha(x)$. Hence $m(s_1/m)^2 \le m^2$, yielding the claim.

Consider a graph $G$ and a set of vertices $M$ with $S_1$ and $S_2$ defined as above. Let $E_1$ denote the set of edges connecting $M$ and $S_1$. The following lemma holds even if $M$ is not a 2-monopoly.

**Lemma 8.** If $S_2$ is 2-controlled by $M$, then $|E_1| \ge s_2$.

**Proof** Construct a bipartite graph $B = (S_2, E_1, E')$ by defining the edge set $E'$ as follows. For $z \in S_2$, $y \in S_1$ and $x \in M$ such that $(x, y) \in E_1$, we connect $z$ to $(x, y)$ in $B$ if $z$ is adjacent to $y$ in $G$. (See Fig. 2(a) and 2(b)).

<figure><img src="image_3.png" /><figcaption>Fig. 2. Proof of Lemma 8.</figcaption></figure>

We prove the lemma by showing that $B$ admits a matching saturating $S_2$. This is proved by relying on Hall's Lemma (cf. [Be76]). By Hall's Lemma, $B$ admits a matching touching every vertex of $S_2$ if and only if $|\Gamma_1(U, B)| \ge |U|$ for every subset $U \subseteq S_2$.

This property is proved by contradiction. Suppose that this property does not hold, namely, there exists a "deficit" set $U$, such that $|\Gamma_1(U, B)| < |U|$. Let $U_0$ be a minimal size deficit set. Note that $U_0$ is not a singleton (since no singletons in $S_2$ are in deficit). Let $F = \Gamma_1(U_0, B)$. Pick an arbitrary node $z_0 \in U_0$, and let $Z = U_0 \setminus \{z_0\}$. The bipartite graph $B'$ induced by $Z$ and $\Gamma_1(Z, B)$ obeys the
condition of Hall's Lemma, hence it admits a matching saturating the vertices of Z. Moreover, note that

$$|Z| + 1 = |U_0| > |\Gamma_1(U_0, B)| \geq |\Gamma_1(Z, B)| \geq |Z|,$$

so $|F| = |Z|$, and hence $B'$ admits a perfect matching $\mathcal{M}$ between $Z$ and $F$. Now let $Q = \Gamma_1(z_0, B) \subseteq F$, and let $H$ be the set of nodes in $Z$ matched by $\mathcal{M}$ with the edges of $Q$ (see Fig. 2(c)). Note that

$$|\Gamma_2(z_0, G) \cap M| \leq |Q| = |H| \leq |\Gamma_2(z_0, G) \cap S_2| - 1$$

(counting $z_0$ itself, and possibly more $S_2$ vertices currently not in $U_0$). This implies that $z_0$ is not 2-controlled, leading to contradiction.

Consequently, $B$ admits a matching saturating $S_2$, and hence $s_2 \leq |E_1|$. ■

**Lemma 9.** If $(G, M)$ is a 2-monopoly, then $s_2 \leq O(m^{5/3})$.

**Proof** Consider a 2-monopoly $(G, M)$. Let $\delta(y) = \deg_G(y, M)$ for each node $y \in S_1$. Let $d_0$ be an integer to be fixed later. Let $A_1$ (resp. $B_1$) be the set of vertices $y \in S_1$ with $\delta(y) < d_0$ (resp. $\delta(y) \geq d_0$). Let $B_2$ be the set of nodes in $S_2$ adjacent to some node in $B_1$, and $A_2 = S_2 \setminus B_2$. Let $a_2 = |A_2|$ and $b_2 = |B_2|$.

First, we note that $m^2 \geq \mathcal{I}(B_2, M) \geq b_2 \cdot d_0$, leading to

$$b_2 \leq \frac{m^2}{d_0} \qquad (4)$$

Secondly, let $t$ be the number of edges between $M$ and $A_1$. Note that a vertex $z \in A_2$ has all its $S_1$ neighbors in $A_1$, and consequently, $A_2$ is 2-controlled by $M$ in the subgraph of $G$ induced by $M \cup A_1 \cup A_2$. Therefore $t \geq a_2$ by Lemma 8. These edges form paths of length 2 from $A_1$ to $A_1$ via $M$. The number of such paths is $K = \sum_{x \in M} \deg(x, A_1)^2$. By convexity, this number is minimal when the degrees $\deg(x, A_1)$ are equal, in which case $\deg(x, A_1) = \frac{t}{m} \geq \frac{a_2}{m}$ for any $x \in M$. Hence

$$K \geq \left(\frac{a_2}{m}\right)^2 \cdot m = \frac{a_2^2}{m}.$$

As we want to compute the influence $\mathcal{I}(A_1, A_1)$, we have to take into account the fact that a vertex in $A_1$ may influence another vertex in $A_1$ via more than one 2-path. But as for any $y \in A_1$ we have $\deg(y, M) \leq d_0$, the number of different 2-paths via $M$ that can contribute the (same) influence of some $y' \in A_1$ on $y$ is at most $d_0$. Consequently

$$m^2 \geq \mathcal{I}(S_1, S_1) \geq \mathcal{I}(A_1, A_1) \geq \frac{K}{d_0} \geq \frac{a_2^2}{md_0}.$$

and we get

$$a_2 \leq \sqrt{d_0 \cdot m^{3/2}}. \qquad (5)$$
The bounds specified by inequalities (4) and (5) are optimized by fixing $d_0 = \Theta(m^{\frac{1}{3}})$ (more exactly $d_0 = (4m)^{\frac{1}{3}}$), where we get

$$a_2 = O(m^{\frac{2}{3}}), \quad b_2 = O(m^{\frac{1}{3}}).$$

$$\text{So } s_2 = a_2 + b_2 = O(m^{5/3}).$$

Since $|V| = s_1 + s_2 + m$, by Lemmas 7 and 9 we have the following.

**Proposition 10.** Every 2-monopoly $(G, M)$ satisfies $m = \Omega(|V|^{3/5})$.

## 2.2 Lower Bound for $2k$-Monopolies

The generalization to $2k$-monopolies is straightforward.

**Proposition 11.** If $(G, M)$ is a $2k$-monopoly then $m = \Omega(|V|^{3/5})$.

*Proof* Define $G^k$, as the graph on vertex set $V$ with an edge between $x$ and $y$ if and only if $D_G(x, y) \le k$. Then clearly $(G, M)$ is a $2k$-monopoly only if $(G^k, M)$ is a $2$-monopoly.

The lower bound proof for the case of $3k$-monopolies for odd $k$ is deferred to the full paper.

## 3 Upper Bounds

**Proposition 12.** There exist $r$ monopolies $(G, M)$ with $m = O(|V|^{3/5})$.

*Proof* To prove this we construct a $2$-monopoly associated to a parameter $t$ with $m = \Theta(t^3)$, $s_1 = \Theta(t^4)$, and $|V| = \Theta(t^5)$, that is, $|V| = \Theta(m^{\frac{2}{3}})$. The nodes $x \in S_1$ also satisfy $\delta(x) = O(t) = O(m^{1/3})$. Clearly these parameters ensure the lower bound. An outline of the construction is given in figure 3. The construction technique can be extended to the case of $r$-monopolies for $r > 2$; this extension is deferred to the full version of the paper.

- $V = M_2 \cup M_1 \cup S_1 \cup S_2$.

- $M_2$ is a clique of size $t^3$, composed of $t$ sets of $t^2$ vertices.

- $M_1$ is an independent set of size $t^3$ composed of $t$ sets of $t^2$ vertices. The $i$th set in $M_1$ is connected to the $i$th set in $M_2$ by a complete bipartite graph. Each set of size $t^2$ is decomposed into subsets of size $t$.

- $S_1$ is an independent set of size $t^4$, composed of $t^2$ sets of size $t^2$. The $i$th set in $S_1$ (of size $t^2$) is connected to the $i$th subset in $M_1$ (of size $t$) by a complete bipartite graph.

- $S_2$ is an independent set of size $t^5 - t^4$, composed of $t^4$ sets of size $t-1$. The nodes of the $i$th set in $S_2$ are connected to the $i$th node of $S_1$.

In order to show that the construction gives a $2$-monopoly achieving the lower bound it is enough to count the influences for the four types of vertices (in $M_2$, $M_1$, $S_1$, $S_2$). The following table summarizes the counts.
<figure><img src="image_4.png" /><figcaption>Fig. 3. A 2-monopoly achieving the upper bound.</figcaption></figure>

<table><thead><tr><th></th><th>x &isin; M<sub>2</sub></th><th>x &isin; M<sub>1</sub></th><th>x &isin; S<sub>1</sub></th><th>x &isin; S<sub>2</sub></th></tr></thead><tbody><tr><td>I(x, M)</td><td>2t<sup>3</sup></td><td>t<sup>3</sup> + t<sup>2</sup></td><td>t<sup>2</sup> + t</td><td>t</td></tr><tr><td>I(x, S)</td><td>t<sup>3</sup></td><td>t<sup>3</sup></td><td>t<sup>2</sup> + t - 1</td><td>t</td></tr></tbody></table>

<figure><img src="image_5.png" /></figure>

**Proposition 13.** There exist 3-monopolies $(G, M)$ with $m = O(|V|^{4/7})$.

**Proof** To prove this we construct a 3-monopoly associated to a parameter $t$ with $m = \Theta(t^4)$, $s_1 = \Theta(t^5)$, and $|V| = \Theta(t^7)$, that is, $|V| = \Theta(m^{1/2})$. Clearly these parameters ensure the lower bound. An outline of the construction is given in figure 4), and the details are deferred to the full version of the paper.

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /><figcaption>Fig. 4. A 3-monopoly achieving the upper bound.</figcaption></figure>
References

[Be76] C. Berge. *Graphs and Hypergraphs*. 1976.

[BP95] J-C. Bermond and D. Peleg. The Power of Small Coalitions in Graphs. 2nd SIROCCO, 1995.

[Br87] G. Bracha. An $o(\log n)$ expected rounds randomized Byzantine generals algorithm. *J. of the ACM*, pages 910–920, 1987.

[D⁺88] C. Dwork, D. Peleg, N. Pippenger and E. Upfal. Fault tolerance in networks of bounded degree. *SIAM J. on Comput.*, 17:975–988, 1988.

[GMB85] H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. *J. ACM*, 32(4):841–860, 1985.

[G79] D. K. Gifford. Weighted voting for replicated data. In *Proc. 7th Symp. Oper. Sys. Princip.*, pages 150–159, 1979.

[GO80] E. Goles and J. Olivos. Periodic behaviour of generalized threshold functions. *Discrete Mathematics*, 30:187–189, 1980.

[JRT91] P. Jalote, S. Rangarajan and S. K. Tripathi. Capacity of voting systems. Technical Report UMIACS-TR-91-118, University of Maryland, 1991.

[KP95a] S. Kutten and D. Peleg. Fault-local distributed mending. In *Proc. 14th ACM Symp. on Principles of Distributed Computing*, August 1995.

[KP95b] S. Kutten and D. Peleg. Tight fault-locality. In *Proc. 36th IEEE Symp. on Foundations of Computer Science*, October 1995.

[LSP82] L. Lamport, R. Shostak and M. Pease. The Byzantine generals problem. *ACM Transactions on Programming Languages and Systems*, 4(3):382–401, July 1982.

[L⁺93] N. Linial, D. Peleg, Y. Rabinovich and M. Saks. Sphere packing and local majorities in graphs. In *2nd ISTCS*, pages 141–149. IEEE Computer Soc. Press, June 1993.

[M94a] G. Moran. On the period-two-property of the majority operator in infinite graphs. Manuscript, 1994.

[M94b] G. Moran. Parametrization for stationary patterns of the r-majority operators on 0-1 sequences. *Discrete Mathematics*, 132:175–195, 1994.

[M94c] G. Moran. The r-majority vote action on 0-1 sequences. *Discrete Mathematics*, 132:145–174, 1994.

[P96] D. Peleg. Local Majority Voting, Small Coalitions and Controlling Monopolies in Graphs: A Review. These proceedings.

[PS83] S. Poljak and M. Sura. On periodical behaviour in societies with symmetric influences. *Combinatorica*, 3:119–121, 1983.

[PT86] S. Poljak and D. Turzik. On an application of convexity to discrete systems. *Discrete Applied Mathematics*, 13:27–32, 1986.

[SB94] M. Spasojevic and P. Berman. Voting as the optimal static pessimistic scheme for managing replicated data. *IEEE Trans. on Parallel & Distr. Systems*, 5(1):64–73, 1994.