What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?

The typical leader election algorithm for anonymous networks (see Table 1 for a detailed comparison) has nodes first select some identity randomly and then proceed like deterministic ones. With this approach, it is difficult to get below $O(\log n)$ random bits per node. Our algorithm for general graphs manages to provide every node with an identity that is unique with high probability, even though each node generates only one random bit. Hence, in some sense, this algorithm performs the task of a “distributed pseudorandom generator” by turning $n$ bits into $n$ numbers of length $\mathrm{\Omega }(\log n)$ each, such that each of them is unique with a sufficiently high probability.

A different idea was used in [2]; in the first step, a node uses a geometric random process to decide how long the node’s random ID would be, and in the second step, tosses additional coins to compose that ID. The total number of random bits is $4n+o(n)$ in expectation. In the algorithm of [17] for a ring, the candidates collaborate to find $a$, the total number of candidates. Each candidate then tosses a non-symmetric coin and decides with probability $1/a$ to remain a candidate. This is repeated until there remains precisely one candidate. The number of unfair coin tosses is $2.441716n$ in expectation. That is, the approach of the two papers that saved on random bits (versus those that used $O(n\log n)$) was to separate candidates for leadership into two sets: winners and losers, that is, one of two different identities: either $0$ or $1$, using one coin per node. Then those algorithms recur. This approach (even after we improve it in Algorithm Splt$\frac{1}{2}$ below) seems doomed to use more than just one random bit at each node. Intuitively, our main algorithm for complete networks generates more than two different identities using one random bit per node. Again, in a sense, this does the work of a “distributed pseudorandom generator.”

The following simple algorithm (described informally) Splt$\frac{1}{2}$ also has nodes toss again. However, the total number of fair coin tosses is reduced to $2n+o(n)$. Nevertheless, the main reason we present it is that it allows us to point out where we want to push the impact of the first bit a little further. Consider a set of $n$ candidates for leadership. Very informally, if each draws one bit at random, the set splits into two: those who drew $1$ and those who drew $0$. If both sets are non-empty, have the larger of these two subsets stop being candidates, breaking symmetry by preferring those who drew $1$ if the sizes are equal. We apply the algorithm recursively on the remaining subset until one node remains. It is easy to see that the total expected number of random bits used is $2n+o(n)$, since nodes who stop being candidates stop using random coins.

Speaking intuitively, Algorithm Splt$\frac{1}{2}$ performs a binary search. The main technical contribution in Algorithm Splt2Many, described next, is that we use a single bit per node to convert this search into a $k$-ary search for values of $k$ that are larger than $2$. For that, a node also uses random bits from other nodes. On one hand, a complete network is highly symmetric, thus it looks as if two nodes $u,v$ use the random bit of some third node $w$, this should not help them in eliminating one of them. Surprisingly, we show that it does.

Algorithm Splt2Many manages to split the set of remaining candidates into more than two subsets on one coin flip per node, thus eliminating more than half of the candidates. We demonstrate this by first presenting a simpler analysis of the algorithm (Theorem 5 in Section 3.1), showing that tossing one bit per node can split the candidates into $3$ subsets (so only those in the smallest subsets remain candidates). Theorem 7 in Section 3.2 takes this much further and shows the analogous property for values of $k$ (chosen later) larger than $3$ using more involved methods. We also show how to bound the maximum number of tokens generated by each node, see Section 3.3. Consider any integer value $k\ge 3$. Intuitively, we manage the above $k$-ways split by extracting information from the commonly assumed structure of ports [4, 34, 15]. Surprisingly, our algorithm manages to do that even in highly symmetric networks and even though the structure is assumed to be set by an adversary. In some more detail (see Section 2), the standard network models are graphs. The edges $(v,x)$ that $v$ is an endpoint of are numbered at $v$ (the numbers range between $1$ to $v$’s degree $\delta (v)$). This numbering may be, in general, not consistent between $v$ and the other endpoint $x$ or any other node, as we allow the numbering to be chosen by an adversary. To emphasize this possible inconsistency, it is usually assumed that a node $v$ does not send (or receive) messages over the edge numbered $i$ (at node $v$), but instead over $v$’s port number $i$, which is connected by an edge to some node that the adversary chose at the beginning of the execution.

In a complete network, the adversarial decision of which edge of a node $v\in [n-1]=\{1,\mathrm{\dots },n-1\}$ leads to which node, implies a permutation on the set of nodes, once we add $v$ itself at the first position of the permutation. Let $M$ be an $n\times n$ matrix containing these permutations as its columns, and let matrix $M$ be decided by the adversary (observing the above rule of the first position). We term the technique by which we extract information from this structure, strongly-separable blocks. It may be of independent interest.

Given matrix $M$ of permutations and a parameter $k\ll n$, our approach is to find in $M$ a collection of $b(n,k)=2^{k^2}$ disjoint submatrices $B_1,\mathrm{\dots },B_{b(n,k)}$, each of size $k\times k$, where each submatrix $B_i$ contains as its entries elements from a unique subset $V(B_i)\subset [n]$ of size $|V(B_i)|=k$; that is, for any $i\ne j$, $V(B_i)\cap V(B_j)=\mathrm{\varnothing }$.

We present an algorithm to constructively prove the existence of a collection of strongly separable blocks using a careful combination of the probabilistic method (Section 5.1) and a greedy recursive approach (Section 5.2). The consecutive blocks are constructed one by one considering “dominated and diverse” rows of $M$. A row of $M$ is dominated roughly, if it contains a value $v\in [n]$ that occurs in a relatively large fraction of positions in this row. A row is diverse if it contains at least two distinct values $u,v\in [n]$, $u\ne v$. We first prove, roughly, that if Matrix $M$ (in fact, the remaining sub-matrix $M^{\prime }$ of $M$), has no dominated and diverse rows and $M^{\prime }$ is sufficiently large, we can find at least $2^{k^2}$ strongly-separable blocks in $M^{\prime }$ by using the probabilistic method.

Our main algorithm for constructing strongly-separable blocks uses a multi-stage recursion, see Section 5.2. We formulate an appropriate inductive assumption which, whenever it holds, allows us to keep choosing strongly-separable blocks within epochs, until $2^{k^2}$ blocks are chosen or all rows in the remaining sub-matrix $M^{\prime }$ are not dominated. If, during this recursive process, the remaining sub-matrix does not have any dominated and diverse rows, we finish up constructing the blocks by the above probabilistic argument.

For each $i\in [n]$, we define $X_i$ as a $0/1$ fair coin random variable and study $n$-dimensional $0/1$ vectors $(X_1,\mathrm{\dots },X_n)\in {\{0,1\}}^n$ in the vector space over the field $GF(2)$. By disjointness of the sets $V(B_i)$, there exists a $0/1$ assignment to variables $X_j$ that implies existence of $b(n,k)$ linearly independent vectors in this vector space. Each such vector corresponds to a submatrix $B_i$ and has $X_j=1$ for $j\in V(B_i)$ and $X_j=0$ for $j\in [n]\setminus V(B_i)$. Thus, by the fact that there are many, $2^{k^2}$, submatrices $B_i$, we know the following: If we now sample each $X_j$, for $j\in [n]$, independently, then with probability at least $1-{\left(\frac{2^k-1}{2^k}\right)}^{b(n,k)}$, there exists at least one block whose $k$ $0/1$ column vectors are pairwise distinct. These vectors will define $k$ distinct IDs to perform the $k$-way recursive split in our algorithm for computing the leader. Section 3.1 contains a warm-up analysis of Algorithm Splt2Many, and Section 3.2 – analysis of Algorithm Splt2ManyIDs, for any $k$, using the existence of strongly-separable blocks.

Our second algorithm, in Section 4.3, works in any graph and uses only one random bit per node. It also builds IDs, but this time, by using competing tokens (originally anonymous). Each token traverses the graph using deterministic universal exploration sequences [29] and simultaneously “builds up” its uniqueness by (a) accumulating random bits met at each traversed node and (b) eliminating competing tokens that arrive simultaneously at the same node. Although the algorithm is polynomial for time and communication complexities, this polynomial is of a high degree, so the upper bounds are much higher than those for Algorithm Splt2Many from Section 3, described earlier (which uses nearly $n$ random bits in complete graphs). (Moreover, the polynomial is not in $n$ but rather in an upper bound $N$ on $n$.) See also Section 6 for a discussion about the complexity.

In certain graphs, there are local port numberings which enforce every node to draw at least one random bit, in order to elect a leader, see Section 4. Our first proof is for complete graphs, exploiting only adversarial point numbering. Our second proof uses a novel definition of shared coloring of edges, which generalizes the classic edge coloring in graphs and “colors” edges in some classes of graphs more effectively than the classic chromatic index would suggest (in the sense that it may result in using fewer colors). It shows that some colorable classes of graphs require $n$ random bits to solve LE. We believe that this technique can prove useful for solving various problems in anonymous networks. It may also be interesting on its own. The proofs have to account for the distributed nature of leader election algorithms, for instance, nodes can communicate before drawing random bits and gather different “views”; as a consequence, only some of them may decide to draw random bits or may do it at different times.

Section 2 introduces the anonymous CONGEST model and the LE problem. Section 3 gives the main Splt2Many algorithm on cliques, and analyzes it using the technical tool studied in Section 5. Section 4 presents the lower bounds and Section 4.3 presents Algorithm TokenID for general networks. Missing proofs from Sections 3 and 4.3 are deferred to the full version. Finally, Section 6 concludes the paper.

Suppose there are some $x_i$ nodes participating in recursion level $i$ of Algorithm Splt2Many, where $x_1=n$. By Lemma 4, the number of nodes $x_{i+1}$ participating in level $i+1$ is at most $max\{1,x_i/3\}$ with probability at least $1-{\left(\frac{31}{32}\right)}^{x_i/5}\ge 1-{\left(\frac{31}{32}\right)}^{f(n)/5}$.

Since only a node that participates in a recursion level draws a random bit (and it draws only one at that level), this is also the number of bits drawn in level $i+1$. Let $s$ be the number of levels (recursive calls) after which we have at most $f(n)$ remaining nodes. The number of nodes $x_{i+1}$ participating in level $i+1$ is larger than $x_i/3$ with probability at most ${\left(\frac{31}{32}\right)}^{f(n)/5}$. Therefore, by union bound, the total number of random bits used in all recursive calls is, at most with probability at least $1-s{\left(\frac{31}{32}\right)}^{f(n)/5}$. Conditioned on this random event, we have that $n/3^s\le f(n)$, which gives that $s\ge {\log }_3(n/f(n))$. Taking $s={\log }_3(n/f(n))$ as the number of recursion levels, the probability of success of the recursive part of our algorithm is at least $1-s{\left(\frac{31}{32}\right)}^{f(n)/5}\ge 1-\frac{{\log }_3(n/f(n))}{n^{\mathrm{\Theta }(\log (n))}}.\text{(*)}$

In the remainder of the analysis, we condition on the random event above. We now look at steps (6-7), in which each of at most $f(n)$ remaining nodes independently chooses $g(n)$ random bits and uses them to define its ID. Let us estimate the probability that all such $f(n)$ random IDs are pairwise distinct. Given any two remaining nodes, the probability that their IDs are the same is at most ${(1/2)}^{g(n)}$. Therefore, by union bound, the probability that all random IDs of all $f(n)$ remaining nodes are distinct is at least $1-\frac{{(f(n))}^2}{2^{g(n)}}=1-\frac{{(f(n))}^2}{n^{\log (n)}}.\text{(**)}$

By combining the two success probabilities above, (*) and (**) by union bound, the final success probability of the overall algorithm is $1-\frac{f{(n)}^2+{\log }_3(n/f(n))}{n^{\mathrm{\Theta }(\log (n))}}.$ The total number of random bits used in steps (6-7) is at most $f(n)g(n)=f{(n)}^2=o(n)$. $◀$

Let us comment that the general method described in Section 3.3 can be applied to this algorithm at the cost of increasing the time and the message complexity. This means that the bound on the maximum number of bits used by a single node can be made $2$ while the total number of bits drawn will remain $1.5n+o(n)$.

Suppose that we are given an $n\times n$ matrix $M$, whose each column contains a permutation of numbers from $[n]=\{1,2,\mathrm{\dots },n\}$ such that column $i\in [n]$ contains the permutation $(a_1,a_2,\mathrm{\dots },a_n)$ with $a_1=i$, i.e. the first number in the permutation is the column number. We call $B$ a submatrix of size $k^{\prime }$ of matrix $M$ if $B$ contains cells of $M$ induced by a subset of $k^{\prime }$ rows and subset of $k^{\prime }$ columns of matrix $M$. Below we will also call elements of matrix $M$ variables because they will play a role of random variables which will independently draw a random bit with equal probability. Note that each such (random) variable $i\in [n]$ has exactly one occurrence in each column of $M$, but occurs exactly $n$ times in the whole matrix $M$.

A collection of strongly-separable blocks with parameter in matrix $M$ is a set of $2^{k^2}$ row- and column-disjoint submatrices of matrix $M$, each of size $k\times k$, such that: (1) each $k\times k$ submatrix $B$ in the collection has a unique set of variables, denoted $V(B)\subset [n]$, with occurrences only in $B$ (i.e., these variables do not occur in any other submatrices of the collection); and (2) there exists at least one mapping $\tau :V(B)\to \{0,1\}$ such that all $k$ column 0/1 vectors in $B$ are pair-wise distinct under mapping $\tau$. To explain condition (2) formally, let $\overline{\tau }:[n]\to \{0,1\}$ be an extension of mapping $\tau$ to the full set of variables $[n]$, such that $\overline{\tau }(i)=\tau (i)$ if $i\in V(B)$ and $\overline{\tau }(i)=0$ if $i\in [n]\setminus V(B)$. Then, condition (2) means that the set $\{(\overline{\tau }(B_{1,i}),\overline{\tau }(B_{2,i}),\mathrm{\dots },\overline{\tau }(B_{k,i})):i\in [k]\}$ of 0/1 vectors contains $k$ distinct vectors; note that we assume that the consecutive columns (and rows) of submatrix $B$ are numbered $1,2,\mathrm{\dots },k$.

We use our main technical tool – Lemma 17 from Section 5.2 – that implies an existence of a collection of $b(n,k)$ strongly-separable blocks in matrix $M$. We will use this lemma in two cases. In the first case, we will assume that $b(n,k)=2^{k^2}$ for any $k\le c\sqrt{\log \log n}$; in this case we will take in fact $k=c\sqrt{\log \log n}$. In the second case, we will take $b(n,k)=\frac{{\log }^{1-\epsilon }(n)}{4k}$ for any fixed constant $k\le c\sqrt{\log \log n}$ and any fixed constant $\epsilon \in (0,1)$. Note that in the second case, $k$ can be an arbitrarily large fixed constant and thus, in that case $n$ will need to be large enough. In this case, it can easily be checked that $b(n,k)=\frac{{\log }^{1-\epsilon }(n)}{4k}$ fulfills Lemma 16. In Lemma 16, we prove the existence of $b(n,k)=2^{k^2}$ strongly-separable blocks. But because constant $c\in (0,1)$ can be arbitrarily close to $1$ and $1-\epsilon$ can be chosen to be (asymptotically) close to $c^2$, we have that for $k=c\sqrt{\log \log n}$, $2^{k^2}\approx {\log }^{1-\epsilon }(n)$, and so $\frac{{\log }^{1-\epsilon }(n)}{4k}\le 2^{k^2}$. Therefore Lemma 16 also implies in particular the existence of $\frac{{\log }^{1-\epsilon }(n)}{4k}$ strongly-separable blocks.

Let us now consider the first step (1) of Algorithm Splt2Many, where each node independently draws a random bit and its random IDs are created. Our probabilistic reasoning here will use this probabilistic space and experiment. By Lemma 17 and by the definition of strongly-separable blocks, for any such block $B$ in matrix $M$, there exists at least one 0/1 assignment to its variables in $V(B)$ that makes all its 0/1 column vectors distinct, using their coordinates that correspond to the rows of $B$ and therefore also the corresponding rows of $M$. We show in Lemma 17 that $|V(B)|=k$ and therefore there are a total of $2^k$ 0/1 assignments to the variables in $V(B)$. This means that in the considered probabilistic space with probability at least $1/2^k$ there are $k$ distinct vectors in block $B$ and therefore also in the whole matrix $M$ – the column vectors of $M$ which correspond to the columns of submatrix $B$. Therefore, with probability at most $(2^k-1)/2^k$, the $k$ 0/1 column vectors in $B$ are not distinct. But we have $b(n,k)$ strongly-separable blocks $B$ in matrix $M$ and their sets of variables $V(B)$ are pair-wise disjoint, meaning that the events of distinguishing the column vectors in any two blocks are probabilistically independent. This implies that with probability at least $1-{\left(\frac{2^k-1}{2^k}\right)}^{b(n,k)}$, there exists at least one block $B$ whose $k$ 0/1 column vectors are pair-wise distinct. This is exactly the probabilistic event that we need for Algorithm Splt2Many; please compare with such an analogous event for Algorithm Splt2Many. This proves the following lemma.

Let $x_i$ be the number of nodes participating in the recursion level $i$ of Algorithm Splt2Many, where $x_1=n$. Then, by Lemma 6, the number of nodes $x_{i+1}$ participating in iteration $i+1$ is at most $max\{1,x_i/k\}$ with probability at least $1-{\left(\frac{2^k-1}{2^k}\right)}^{b(n,k)}$. Here, $b(n,k)=2^{k^2}$ for $k=c\sqrt{\log \log n}$ in part (A) of the theorem. In part (B), we will take $b(n,k)=\frac{{\log }^{1-\epsilon }(n)}{4k}$ for any fixed constant $k\le c\sqrt{\log \log n}$ and any fixed constant $\epsilon \in (0,1)$. Note, that constant $c\in (0,1)$ can be arbitrarily close to $1$ and $1-\epsilon$ is (asymptotically) close to $c^2$, so $\epsilon$ can be chosen arbitrarily close to $0$ – see Lemma 16 with $2^{k^2}$ replaced by $b(n,k)$.

Since only a node that participates in a recursion level draws a random bit (and it draws only one at that recursion level), this is also the number of bits drawn in recursion level $i+1$. Let $s$ be the number of recursive calls after which we have $f(n)$ remaining nodes. The number of nodes $x_{i+1}$ participating in recursion level $i+1$ is larger than $x_i/k$ with probability at most ${\left(\frac{2^k-1}{2^k}\right)}^{b(n,k)}$. Therefore, by union bound, the total number of random bits used in all recursive calls is at most with probability at least $1-s{\left(\frac{2^k-1}{2^k}\right)}^{b(n,k)}$. Conditioned on this random event, we have that $n/k^s\le f(n)$, which gives that $s\ge {\log }_k(n/f(n))$. Taking $s={\log }_k(n/f(n))$ as the number of recursion levels, the probability of success of the recursive part of our algorithm is at least

In part (A), we have that this probability is

where $h(n)=e^{2^{k(k-1)}}/\log (n)$. This estimate follows because $b(n,k)=2^{k^2}$, $\log (n/f(n))=(1-\gamma )\log (n)$, $k=k(f(n))$, where $k(n)=c\sqrt{\log \log n}$, and then we obtain that

It is also easy to check that the above inequality holds when we take $h(n)=\log (n)$.

In part (B), we take $b(n,k)=\frac{{\log }^{1-\epsilon }(n)}{4k}$, and we have that the above probability is

so this is almost with high probability, because $e^{{\log }^{1-\epsilon }(n)}=n^{\mathrm{\Theta }(1)}$ when $\epsilon =0$ (but remember $\epsilon$ is any fixed constant $\epsilon >0$) and $k$ is an arbitrarily large fixed constant.

In the remaining analysis, we condition on the above random event. We will now look at steps (6-7) of the algorithm, in which each of the $f(n)$ remaining nodes independently chooses $g(n)$ random bits and uses them to define its ID. We will estimate the probability that all such $f(n)$ random IDs are pairwise distinct. Given any two remaining nodes, the probability that their IDs are the same is at most ${(1/2)}^{g(n)}$. Thus, by union bound, the probability that all random IDs of all $f(n)$ remaining nodes are distinct is at least

In part (A), the probability (3) is $1-\frac{{(f(n))}^2}{2^{g(n)}}=1-\frac{1}{f(n)}$, and by combining it with probability (1) using union bound, the final success probability of the algorithm is indeed $1-O\left(\frac{1}{h(n)}\right)$.

In part (B), the probability (3) is $1-\frac{{(f(n))}^2}{2^{g(n)}}=1-\frac{1}{f(n)}=1-{\left(\frac{1}{e^{{\log }^{1-\epsilon }(n)}}\right)}^{\frac{1}{4k{2}^k}}$, and by combining it with probability (2), the final success probability of the overall algorithm is at least $1-\log (n){\left(\frac{1}{e^{{\log }^{1-\epsilon }(n)}}\right)}^{\frac{1}{4k{2}^k}}$.

The total number of random bits used in steps (6-7) is at most $f(n)g(n)=f(n)\log (f{(n)}^3)=o(n)$. Thus, the total number of random bits the algorithm uses in part (A) is at most $\frac{k}{k-1}n+f(n)\log (f{(n)}^3)=n+\frac{n}{k-1}+f(n)\log (f{(n)}^3)=n+o(n)$, because $f(n)=n^{\gamma }$ and $k=k(n)=c\sqrt{\log \log n}$, where $\gamma \in (0,1/3)$. The total number of random bits in part (B) is at most $\frac{k}{k-1}n+f(n)\log (f{(n)}^3)=n+\frac{n}{k-1}+f(n)\log (f{(n)}^3)=n+\frac{n}{k-1}+o(n)$. $◀$

This result follows from the following property, which we will prove in the remainder: there is a local port numbering in the clique such that until some node draws the first (over all the nodes) random bit, in each round, all histories (and thus, states and messages sent/received by certain ports) are the same across all nodes. Indeed, if $t$ is the first round when someone draws a random bit, because of the same histories at nodes by that time, the next action at all nodes will be the same by Proposition 9, and since one of them will be drawing a random bit eventually (otherwise, leader election is impossible in the anonymous clique [4, 35]) so will all of them. So, the total number of drawn random bits is (at least) $n$.

The proof of the above property is by contradiction. Consider the following local port numbering, depending on whether $n$ is even or odd.

Case 1: $n$ is even. It implies that the node degree of each node in the cliques is odd, and thus, the edges could be partitioned into $n-1$ perfect matchings. The adversary can assign a unique number in $\{1,\mathrm{\dots },n-1\}$ to each matching in the partition, and we say that the $i$th matching has ports on both sides locally numbered $i$.

Case 2: $n$ is odd. It implies that the node degree is even, and thus we could partition all edges into $(n-1)/2$ hamiltonian cycles. We assign a unique number from $\{1,\mathrm{\dots },(n-1)/2\}$ to each of the Hamiltonian cycles in the partition. Local ports are assigned as follows. For each $i$th Hamiltonian cycle, the adversary directs the cycle in an arbitrary direction and assigns port number $2i$ to the port via which the $i$th cycle leaves the node, and number $2i-1$ to the port via which the cycle enters the node.

Now, by the contradictory assumption, for the defined local port numbering, there is a round $t$ such that by the beginning of that round, no node draws any random bit. Still, there are some two nodes, call them $v,w$,⁷⁷7As emphasized earlier, in the analysis, we use names only to distinguish nodes when applying mathematical arguments. This does not violate the anonymity of nodes and algorithms. such that their histories (and thus, their states) are different at the beginning of round $t$. Without loss of generality, let $t$ be the first round with such a property. Observe that $t\ge 2$, because, at the beginning of round $1$, all nodes have the same (empty, or containing only the same number $n$) history and no distinguishing IDs. From the definition of round $t$, it follows that all nodes had the same history at the beginning of round $t-1$. Therefore, all nodes make the same decisions about what message to send via each port. There are two cases to consider, as the defined local port labeling depends on it.

Ad Case 1: $n$ is even. It follows that if nodes decide to send the same message via port $i$, all nodes receive this particular message via port $i$. Since there was no randomness in round $t-1$, the history is the same at all nodes at the end of round $t-1$ and, hence, at the beginning of round $t$. This is a contradiction, finishing the proof of the invariant (and thus the theorem) in Case 1.

Ad Case 2: $n$ is odd. It follows that if nodes decide to send same message via port $2i-1$, for some number $i\in \{1,\mathrm{\dots },(n-1)/2\}$, all nodes receive this particular message via their local port $2i$, and vice versa. Since there was no randomness in round $t-1$, the history is the same at all nodes at the end of round $t-1$, and, hence, the beginning of round $t$. This contradiction finishes the proof of the invariant (and thus the theorem) in Case 2. $◀$

The proof is by a probabilistic argument. W.l.o.g., we may restrict to diverse rows, i.e., we may assume that $M^{\prime }$ contains only diverse rows.⁹⁹9Otherwise, we could remove from $M^{\prime }$ non-diverse rows, as they are not needed for this proof, and once we show the existence of strongly-separable blocks, we do not need matrix $M^{\prime }$ anymore. We assume a local numbering of rows and columns in $M^{\prime }$, that is, from $1$ to the number of rows in $M^{\prime }$ and from $1$ to the number of columns in $M^{\prime }$, respectively. Let $\alpha$ be the minimum between the number of rows and the number of columns in $M^{\prime }$. Let us choose, independently at random, a sequence of $k\cdot b(n,k)$ numbers in $\{1,\mathrm{\dots },\alpha \}$, where $b(n,k)=2^{k^2}$ is the required number of blocks; call them $r_1,\mathrm{\dots },r_{k\cdot b(n,k)}$. Let $M^{\prime \prime }$ be the sub-matrix of $M^{\prime }$ induced by rows and columns $r_1,\mathrm{\dots },r_{k\cdot b(n,k)}$. Define an $i$-th block of $M^{\prime \prime }$, for $i\le b(n,k)$, as induced by rows and columns $1+(i-1)k,\mathrm{\dots },ik$.

We first prove that any block $i$ is strongly-separable from any block . We proceed by induction on $i$.

Consider a block $i$ and any variable stored outside of its diagonal; call the coordinates of this variable $x,y\in \{1+(i-1)k,\mathrm{\dots },ik\}$, where $x\ne y$. Let $X_{x,y}$ be a random variable equal to $1$ if the variable stored in $M^{\prime \prime }[x,y]$ occurs on the diagonal of $M^{\prime \prime }$ or in any previous blocks, and equal to $0$ otherwise.

We now argue that the probability that $X_{x,y}=1$ is smaller than $b(n,k)\psi k^2$ Indeed, there are at most $b(n,k)\cdot k^2$ variables on different positions of the $b(n,k)$ blocks, while by the fact that row $r_x$ of $M^{\prime }$ is not dominated (and diverse), these variables occupy less than

positions in row $r_x$ of $M^{\prime }$ in total. Hence, the probability that $M^{\prime }[r_x,r_y]$ is one of them is smaller than $\frac{b(n,k)\cdot k^2\cdot \alpha \cdot \psi }{\alpha }=b(n,k)\psi k^2$, by the random choice of $r_y$.

Using this above upper bound on the probability that $X_{x,y}=1$, we get:

by the definition of $\psi$. By a probabilistic argument, using the fact that all variables $X_{x,y}$ are binary, with a positive probability all of them have to be $0$ (otherwise, with probability $1$ their sum would be at least $1$, and so the expected value of the sum – which would be a contradiction with our above sharp estimate). Consequently, there is a selection of $r_1,\mathrm{\dots },r_{k\cdot b(n,k)}$, and thus matrix $M^{\prime \prime }$, such that each non-diagonal position in any block of $M^{\prime \prime }$ contains a unique variable. Hence, in such selection of matrix $M^{\prime \prime }$, its blocks are strongly-separable in $M^{\prime \prime }$, and thus also in $M^{\prime }$. $◀$