#  The Topology of Randomized Symmetry-Breaking Distributed Computing

Pierre Fraigniaud Université de Paris and CNRS<EMAIL_ADDRESS>Ran
Gelles Bar-Ilan University<EMAIL_ADDRESS>Zvi Lotker Bar-Ilan
University<EMAIL_ADDRESS>
###### Abstract

Studying distributed computing through the lens of algebraic topology has been
the source of many significant breakthroughs during the last two decades,
especially in the design of lower bounds or impossibility results for
_deterministic_ algorithms. In a nutshell, this approach consists of capturing
all the possible states of a distributed system at a certain time as a
simplicial complex $\mathcal{P}(t)$, called _protocol complex_ , and viewing
computation as a _simplicial_ map from that complex to the so-called _output
complex_ , $\mathcal{O}$, that captures all possible legal output states of
the system. The topological properties (e.g., homotopy) of the protocol
complex depends on the properties of the _input complex_ $\mathcal{I}$ (i.e.,
the complex $\mathcal{P}(0)$ of all possible initial states), and on the
communication model. Studying these properties lead to proving or disproving
the existence of a simplicial map from $\mathcal{P}(t)$ to $\mathcal{O}$.

This paper aims at studying _randomized_ synchronous distributed computing
through the lens of algebraic topology. We do so by studying the wide class of
(input-free) _symmetry-breaking_ tasks, e.g., leader election, in synchronous
fault-free anonymous systems, that is, when the absence of IDs prevents the
processing nodes from breaking symmetry in a deterministic manner. We show
that it is possible to redefine solvability of a task “locally”, i.e., for
each simplex of the protocol complex _individually_ , without requiring any
global consistency. However, this approach has a drawback: it eliminates the
topological aspect of the computation, since a single facet has a trivial
topological structure. To overcome this issue, we introduce a “projection”
$\pi$ of both protocol and output complexes, where every _simplex_ $\sigma$ is
mapped to a _complex_ $\pi(\sigma)$; the later has a rich structure that
replaces the structure we lost by considering one single facet at a time.

We show that a facet of $\mathcal{P}(t)$ solves the task if and only if there
exists a simplicial map from the projection of that facet to the projection of
some facet of the output complex. This approach allows us to use topological
arguments to establish which facets of the protocol complex solve the task,
and which do not. By doing so, one can compute the probability to solve a task
at time $t$ by analyzing each facet independently, and summing the
probabilities of all facets that solve the task. An application of
Kolmogorov’s zero–one law establishes which symmetry-breaking tasks are
_eventually_ solvable when $t\to\infty$.

To show the significance and applicability of our approach, we derive
necessary and sufficient conditions for solving leader election in synchronous
fault-free anonymous shared-memory and message-passing models. In both models,
we consider scenarios in which there might be correlations between the random
values provided to the nodes. In particular, different parties might have
access to the same randomness source so their randomness is not independent
but equal. Interestingly, we find that solvability of leader election relates
to the number of parties that possess correlated randomness, either directly
or via their greatest common divisor, depending on the specific communication
model.

##  1 Introduction

There are two main categories of distributed algorithms: deterministic and
randomized. The difference between them is stark as some tasks are solvable
when randomness is present but cannot be solved deterministically. Further,
randomness often yields faster and more efficient algorithms for tasks
solvable deterministically. A main example is the task of electing a leader in
anonymous systems [LL77, GHS83], where $n>1$ identical computing nodes need to
designate a single node as their leader. For any deterministic algorithm
running in symmetric systems where all nodes are identical, all nodes return
exactly the same output. This is known as the impossibility of deterministic
algorithms to break symmetry [Ang80]. On the other hand, if each node has
access to an independent source of randomness, then symmetry can be broken,
allowing electing a leader [ASW88].

It is widely agreed that the major breakthrough of computer science is the
invention of the Turing machine [Tur36], which abstracts all possible
realistic computing machines into a single _universal_ model. With this
abstraction, researchers can ignore the system’s specific properties and focus
on the computational aspect of the problem rather than on its manifestation in
a specific environment. In the distributed world, while each node is still a
Turing machine, the environment plays a large role in setting the relevant
model: nodes and communication links may be reliable or subject to various
forms of failures. The system may be synchronous or experience arbitrary large
communication delays. Also, all nodes might be connected as a single hop or
connected in an arbitrary manner. This large variety of models required
focusing on each model and analyzing each task and algorithm separately. In
the early 1990s, a unifying framework was developed that captures all the
above distributed models: distributed computing via _algebraic topology_
[BG93, HS93, SZ93]. Similar to the Turing model, this framework enables
analyzing the complexity of distributed tasks under a unique umbrella in which
the same tools and methodologies apply, independently from the details of the
actual distributed model of distributed computing. However, these pioneering
works and the numerous subsequent work that followed them (see [HKR14], and
the references therein) mostly treated deterministic algorithms, and
randomized algorithms remain so far excluded.

The usual topology-analysis of deterministic distributed algorithms [HKR14]
involves a simplicial complex $\mathcal{P}(t)$, called _protocol_ complex,
that captures all the possible global states of the distributed system at time
$t\geq 0$, where each global state is modeled as a simplex of that
complex.111See Appendix  The Topology of Randomized Symmetry-Breaking
Distributed Computing for a summary of the topological notions used in this
paper. Initially $\mathcal{P}(0)=\mathcal{I}$, the so-called input complex
that captures all initial global states of the system. The evolution of the
system with time translates to the evolution of the complex $\mathcal{P}(t)$,
$t\geq 0$. An algorithm solving a task in time $t$ is then modeled as a
simplicial map $\delta:\mathcal{P}(t)\to\mathcal{O}$ from the protocol complex
to the output complex $\mathcal{O}$, where the latter captures all legal final
global states of the system. This mapping may need to satisfy some additional
requirements in the case of input-output tasks (e.g., consensus) where the
legality of the output depends on the input. It turns out that, for many
distributed models, certain properties of a topological space, such as
connectivity or homotopy type, are preserved during the evolution of the
protocol complex with time. Comparing the topological properties of the
protocol complex with those of the output complex is a fruitful approach for
establishing impossibility results, that is, proving that the mapping $\delta$
cannot exist. A typical example is the task of consensus in the crash-prone
asynchronous shared-memory model in which the protocol complex remains
connected throughout time while the output complex is disconnected, preventing
the simplicial map $\delta$ from existing.

Extending this approach to the analysis of randomized algorithms requires
overcoming several difficulties. In particular, for a large class of tasks
that are not solvable deterministically in anonymous systems, including
symmetry breaking tasks such as leader election, the solvability of these
tasks using a randomized algorithm is only _eventual_. That is, there is no
fixed $t\geq 0$ for which there exists a simplicial map
$\delta:\mathcal{P}(t)\to\mathcal{O}$, even if we allow $t$ to be as large as
we wish. Nevertheless, the task is eventually solvable, meaning that when $t$
goes to infinity, the probability for solving the task approaches 1. One may
argue that, for a fixed $t\geq 0$, one can still compute the probability of
solving the task at time $t$ by considering a mapping
$\delta_{t}:V(\mathcal{P}(t))\to V(\mathcal{O})$ (not necessarily simplicial),
then considering only the facets of $\sigma\in\mathcal{P}(t)$ such that
$\delta_{t}(\sigma)\in\mathcal{O}$, and finally computing the sum of the
probability of each of these facets to occur as a function of the outcomes of
the random bits used in the protocol. This argument is valid. However, it may
not be of practical use. Indeed, one is losing the whole point of using
topology, as it might be difficult to analyze what topological properties
(e.g., homotopy type) are preserved by such an arbitrary map $\delta_{t}$.
Additionally, it might be difficult to relate the topological properties of
the “best” map $\delta_{t}$ (i.e., the one that maximizes the probability of
solving the task at time $t$) with the properties of the best map
$\delta_{t+1}$ at time $t+1$.

In this paper, we give the first stab at developing a topological framework
that captures synchronous randomized algorithms of certain types, which we now
describe.

###  1.1 A Topological Approach for Randomized Algorithms

We consider input-free symmetry-breaking tasks: tasks solely defined by their
output complex $\mathcal{O}$, which we require to be symmetric (i.e., stable
to permutation of the processing nodes names). For instance, this is the case
of leader election in which there are no constraints on which node may be the
leader. In this context, a crucial observation is that the solvability of a
task at a time $t$ can be analyzed for each facet $\sigma\in\mathcal{P}(t)$
separately. For each facet $\sigma\in\mathcal{P}(t)$, we can say that $\sigma$
solves the task $\mathcal{O}$ whenever there exists a simplicial map
$\delta:\sigma\to\mathcal{O}$ which maps the state of each node to its output,
such that the output value is independent of the actual name of the node. The
interest of that observation is that it decouples the map
$\delta:\sigma\to\mathcal{O}$ from the map
$\delta^{\prime}:\sigma^{\prime}\to\mathcal{O}$ that may exist for another
facet $\sigma^{\prime}$ of $\mathcal{P}(t)$. The significant drawback of this
approach is that, as the aforementioned general approach consisting of
considering arbitrary maps $\delta_{t}:V(\mathcal{P}(t))\to V(\mathcal{O})$,
one is losing connection with topology. Indeed, the facet $\sigma$ has a
trivial topological structure, as it is just a simplex of $\mathcal{P}(t)$.
Our approach, on the other hand, provides a structure to each simplex of
$\mathcal{P}(t)$; this allows us to keep analyzing the system using
topological tools.

To provide the simplices of $\mathcal{P}(t)$ with a structure, we “project”
each simplex $\sigma\in\mathcal{P}(t)$ to a sub-complex $\pi(\sigma)$ of
$\sigma$, the latter being viewed as a complex.222To be precise, this complex
is the induced subcomplex of $\mathcal{P}(t)$ on $V(\sigma)$. Roughly, a set
of nodes forms a simplex in $\pi(\sigma)$ if they have an identical individual
state in $\sigma$, where the individual state of a node results from the
outcomes of its source of randomness and from its knowledge about the outcomes
of the other nodes (acquired during the communications up to time $t$). In a
sense, a simplex in $\pi(\sigma)$ bears the meaning that the algorithm up to
time $t$ did not break symmetry for the nodes associated with this simplex
vertices. The sub-complex $\pi(\sigma)$ captures the internal state of each
one of the parties in a specific execution and portrays similarity in the
knowledge of the parties. The projection $\pi$ is called _consistency
projection_. Thanks to the consistency projection, we have regained structure,
which we can now utilize to determine the ability of a facet
$\sigma\in\mathcal{P}(t)$ to solve a task $\mathcal{O}$. A facet $\sigma$
solves the task $\mathcal{O}$ whenever there exists a (name-preserving)
simplicial map $\delta:\pi(\sigma)\to\pi(\tau)$ for some facet
$\tau\in\mathcal{O}$, where $\pi(\tau)$ is the projection of $\tau$, that is,
the sub-complex of $\tau$ in which a set of vertices of $\tau$ forms a simplex
in $\pi(\tau)$ if they have identical individual output value in $\tau$.

Granted with the notion of solvability for each facet of the protocol complex
at time $t$, we show how to define the _eventual_ solvability of the task.
Specifically, let us define the probability $p(t)$ that $\mathcal{P}(t)$
solves $\mathcal{O}$ as the sum, taken over all facets of $\mathcal{P}(t)$
that solve $\mathcal{O}$, of the probability of each of these facets. Eventual
solvability is then based on Borel-Cantelli’s Lemma and on Kolmogorov’s
zero–one law stating that any _tail event_ occurs with probability zero or
one. As a consequence, we can show that $\lim_{t\to\infty}p(t)\in\\{0,1\\}$,
and to forbid mixed answers where tasks are “solvable” with some probability
$p\in(0,1)$. Therefore, this provides us with a complete (deterministic)
characterization of eventual solvability, namely, an input-free symmetry-
breaking task $\mathcal{O}$ is eventually solvable if
$\lim_{t\to\infty}p(t)=1$.

To sum up this part, given an input-free symmetry-breaking task, i.e., a task
represented by a symmetric output complex $\mathcal{O}$, we say that a global
state $\sigma\in\mathcal{P}(t)$ solves $\mathcal{O}$ if there exists a name-
preserving simplicial map $\delta:\pi(\sigma)\to\pi(\tau)$ for some
$\tau\in\mathcal{O}$, where $\pi$ is the consistency projection. For any
$t\geq 1$, let $\mathcal{S}(t)$ be the set of all the global states
$\sigma\in\mathcal{P}(t)$ that solves the task $\mathcal{O}$, and let us
define $\Pr[\mathcal{S}(t)]=\sum_{\sigma\in\mathcal{S}(t)}\Pr[\sigma]$. We say
that $\mathcal{O}$ is eventually solvable if and only if
$\lim_{t\to\infty}\Pr[\mathcal{S}(t)]=1$.

###  1.2 Application to Leader Election in Anonymous Models

To demonstrate the interest and usability of the topological approach of
randomized algorithms sketched in the previous section, we study the arguably
most prominent symmetry-breaking task, namely _leader election_ , in two
important models for anonymous computing, that is, the blackboard model and
the message-passing model with port-numbers. While in this paper we focus on
leader election, we note that the vast majority of other symmetry-breaking
tasks in anonymous message-passing networks are trivially solvable once a
leader can be elected; see [EPSW14], for instance.333Another reason to focus
on leader election is that many other important tasks, such as reaching
consensus or $k$-set agreement, are _deterministically_ solvable in the fault-
free setting. See also Appendix  The Topology of Randomized Symmetry-Breaking
Distributed Computing . Moreover, we consider an exhaustive range of
randomness source assignments to the nodes, from private randomness (each node
has its own independent source of randomness) to shared randomness (all nodes
get their random bits from the same source). Indeed, in many real-life
situations, we observe dependencies and correlations between the different
randomness sources, and this is in particular noticeable in distributed
systems as the parties are all deterministic machines that obtain their
randomness via pseudo-random generators, which might cause the randomness of
some (or all) parties to be correlated or even identical. This is not just a
theoretical whim: recent work showed that the same random SSH keys were
generated by more than 250,000 “independent” devices [Mat15] and that 1 out of
172 RSA-based certificates found online (i.e., about 450,000 certificates)
have a random RSA key that shares a factor with the key of another
“independent” certificate, allowing the complete factorization of these RSA
keys and breaking the security of these certificates [KV19].

Specifically, we model our setting as follows. The system is composed of $n$
parties, where all parties are connected to each other either via an anonymous
broadcast channel (blackboard model) or via private point-to-point channels
(message-passing model). In the latter model, each private channel of a party
is locally identified by an index in $\\{1,\dots,n-1\\}$, called port-number
[JS85]. Other than that, the $n$ parties are identical and anonymous (they
have no IDs). There are $k$, $1\leq k\leq n$, independent sources of
randomness $\mathbf{R}_{1},\ldots,\mathbf{R}_{k}$, where each randomness
source generates an infinite sequence of i.i.d random bits, each bit being
picked uniformly at random. Each party is connected to a single randomness
source. However, different parties may be connected to the same source, hence,
their randomness is completely dependent (i.e., identical). This modeling is
simple, but it allows us to capture both the case where all parties have
independent randomness as well as the case where all parties share the same
randomness source, or any situation in between—where some parties are
correlated and others are not.

One can easily verify that the correlations between parties bring up
interesting questions. In particular, under which assumption on the
correlations between the parties is leader election possible? There are
trivial answers under specific scenarios. For instance, if each party is
connected to a private source of randomness, then leader election is
eventually solvable, even in the weak blackboard model (e.g., whenever one
party gets a bit 1 while all the other parties get bits 0). Instead, if all
parties are connected to the same randomness source, then symmetry cannot be
broken in the blackboard model, and leader election is impossible. But what
about intermediate cases? And what about the message-passing model in which
the port-numbers may assist in breaking symmetry?

We show that, in the blackboard model, leader election is eventually solvable
if and only if there exists a randomness source $\mathbf{R}_{i}$,
$i\in\\{1,\dots,k\\}$, that is connected to a single party (Theorem 4.1). In
the message-passing model, we show that whenever $n_{i}\geq 1$ parties are
connected to the randomness source $\mathbf{R}_{i}$, $i\in\\{1,\dots,k\\}$,
leader election is eventually solvable if and only if
$\gcd(n_{1},n_{2},\ldots,n_{k})=1$ (Theorem 4.2). The latter result must be
read as follows. If $\gcd(n_{1},n_{2},\ldots,n_{k})=1$, then leader election
is eventually solvable for every assignment of the port-numbers to the
channels, and if $\gcd(n_{1},n_{2},\ldots,n_{k})>1$, then there is an
assignment of the port-numbers to the channels such that leader election is
not eventually solvable. The intuition behind these two theorems is somewhat
immediate. In the blackboard model, if two processes (or more) possess the
same randomness source, then their states will be identical throughout the
computation, hence none of them can be elected a leader. On the other hand, if
there is a single process with a unique source of randomness, then with
probability 1 this process eventually arrives at a state distinct from all
other processes. In the next round, every process will see that this has
happened and elect the distinct process as a leader. In the message-passing
model, the GCD condition guarantees that processes with the same randomness
source $\mathbf{R}_{i}$ can “match” themselves with processes that have a
different randomness source $\mathbf{R}_{j}$. At the end of this step, any
process in the smaller set will have a match from the other set. The key
observation is that if we deactivate all the matched-processes that belong to
the _larger_ set, then the GCD condition still holds. Thus, we can repeat this
matching process recursively, similar to Euclid’s GCD algorithm [Euc], until
we reach a set with a size of 1. That process will be the leader. One can
verify that this idea cannot work when the GCD is not 1, since eventually one
of the sets will have a size of 0, while the size of the other set will be a
multiple of the GCD. Indeed, if the GCD is $g$, we show that every process
belongs to a set (of size $c\cdot g$ for some $c\in\mathbb{N}$) such that all
processes within the same set share the exact same state.

While the above intuition could lead to a direct proof for leader election
solvability, it is almost straightforward to derive some of the above insights
by applying our topological framework. The above intuition might seem trivial
in hindsight, but such insights might not be simple to come up with a priori.
As an example, consider the conditions for the solvability of 2-leader
election, i.e., obtaining exactly two leaders. The topological framework
immediately leads to the correct characterization of this problem and many
others. We encourage the reader to find a direct characterization in both the
blackboard and message-passing models, and then compare it with the
characterization obtained via the topological framework.

In order to establish the above characterization, we apply the topological
approach described in the previous sub-section. Leader election is represented
by the output complex $\mathcal{O}_{\mathsf{LE}}$ defined as follows. A set
$\\{(i,x_{i}):i\in\\{1,\dots,n\\}\\}$ is a facet of
$\mathcal{O}_{\mathsf{LE}}$ if $\\{x_{1},\dots,x_{n}\\}=\\{0,1\\}$, and there
is a unique $i\in\\{1,\dots,n\\}$ such that $x_{i}=1$. See Figure 3 for an
illustration of $\mathcal{O}_{\mathsf{LE}}$ and its consistency projection.
First, we characterize the global states $\sigma\in\mathcal{P}(t)$ that solve
$\mathcal{O}_{\mathsf{LE}}$, that is, the states for which there exists a
name-preserving simplicial map $\delta:\pi(\sigma)\to\pi(\tau)$ for some
$\tau\in\mathcal{O}_{\mathsf{LE}}$, where $\pi$ is the consistency projection.
Then, given the set $\mathcal{S}(t)$ of the global states
$\sigma\in\mathcal{P}(t)$ that solves leader election, we compute
$\Pr[\mathcal{S}(t)\mid\alpha]=\sum_{\sigma\in\mathcal{S}(t)}\Pr[\sigma\mid\alpha]$
for every configuration $\alpha$ of the connections between the parties and
the randomness sources. Finally, we compute
$\lim_{t\to\infty}\Pr[\mathcal{S}(t)\mid\alpha]$ for figuring out under which
condition this limit is 1, which establishes eventual solvability.

Computing the probability of a global state $\sigma\in\mathcal{P}(t)$ to occur
(i.e., computing $\Pr[\sigma\mid\alpha]$) is, however, non-trivial. So, we
introduce another complex, called the _realization_ complex at time $t$,
denoted by $\mathcal{R}(t)$. The vertices of $\mathcal{R}(t)$ are pairs
$(i,x_{i})$ where $i\in\\{1,\dots,n\\}$, and $x_{i}\in\\{0,1\\}^{t}$. Each set
of vertices $\\{(i,x_{i}):i\in I\\}$ is a simplex of $\mathcal{R}(t)$, for
every non-empty set $I\subseteq\\{1,\dots,n\\}$. The interest of
$\mathcal{R}(t)$ is that given an assignment $\alpha$ of the randomness
sources to the nodes and given a facet $\rho$ of $\mathcal{R}(t)$, it is easy
to compute $\Pr[\rho\mid\alpha]$. Interestingly, it turns out that the facets
of $\mathcal{R}(t)$ are isomorphic to the facets of $\mathcal{P}(t)$. That is,
we show that a specific realization at time $t$ of the randomness sources
fully and uniquely defines the states of the parties at time $t$ in the
protocol complex $\mathcal{P}(t)$. This makes the computation of
$\Pr[\sigma\mid\alpha]$ easier for each facet $\sigma$ of $\mathcal{P}(t)$, by
computing the probability $\Pr[\rho\mid\alpha]$ of the corresponding facet
$\rho$ of $\mathcal{R}(t)$.

Thanks to the isomorphism between the facets of $\mathcal{P}(t)$ and
$\mathcal{R}(t)$, we can focus on determining whether a given facet $\rho$ of
$\mathcal{R}(t)$ solves leader election. For this purpose, we introduce a
variant of the consistency projection, denoted by $\tilde{\pi}$, that applies
to facets of $\mathcal{R}(t)$. Then we study the existence of a name-
preserving simplicial map $\delta:\tilde{\pi}(\rho)\to\pi(\tau)$ for some
facet $\tau\in\mathcal{O}_{\mathsf{LE}}$ for determining whether the facet
$\rho$ of $\mathcal{R}(t)$ solves leader election or not. Since for any facet
$\tau\in\mathcal{O}_{\mathsf{LE}}$, $\pi(\tau)$ contains an isolated vertex,
for any realization $\rho$ that potentially solves leader election,
$\tilde{\pi}(\rho)$ must contain an isolated vertex as well. In the blackboard
model, the dimension of the smallest facet in $\tilde{\pi}(\rho)$ is
$\min\\{n_{1},n_{2},\ldots,n_{k}\\}-1$, and thus the presence of an isolated
node in $\tilde{\pi}(\rho)$ requires that
$\min\\{n_{1},n_{2},\ldots,n_{k}\\}=1$. In the message-passing model, we prove
that there exists some way to assign port-numbers to the channels such that,
for any facet $\gamma\in\tilde{\pi}(\rho)$ with dimension $d$, it holds that
$\gcd(n_{1},n_{2},\ldots,n_{k})\mid d+1$. Therefore, if
$\gcd(n_{1},n_{2},\ldots,n_{k})>1$, then there are no isolated nodes in
$\tilde{\pi}(\rho)$, and the task cannot be solved. In order to prove the
other direction, i.e., that if $\gcd(n_{1},n_{2},\ldots,n_{k})=1$ then leader
election is eventually solvable, we describe an algorithm that imitates
Euclid’s algorithm [Euc] for computing the greatest common divisor of the
dimensions of the facets in $\tilde{\pi}(\rho)$, until reaching an isolated
vertex.

###  1.3 Related Work

As mentioned above, the pioneering work [BG93, HS93, SZ93] formulated
distributed computations in the language of algebraic topology in order to
show impossibility results in the presence of failures. A tremendous amount of
subsequent work is described in the book of Herlihy, Kozlov, and Rajsbaum
[HKR14] (see also dozens of citations therein). We mention that the language
of algebraic topology was found useful to analyze systems both in the
_message-passing_ model as well in the _shared-memory_ model, and it can even
be extended to capture non-benign faults, like Byzantine failures [MTH14].

Leader election has been extensively studied as an interesting special case of
symmetry-breaking between nodes, usually in anonymous systems. Angluin [Ang80]
showed that no deterministic algorithm could elect a leader in anonymous
networks (usually, in a ring) while it is possible to elect a leader non-
deterministically or probabilistically. A long line of leader election
algorithms, as well as lower bounds, were developed for certain special cases
[AAG+89, AM94, ASW88, DMR08, IR90, KPP+15, Pel90, SS94]. Mostly related to
this paper is the work of Yamashita and Kameda [YK96], which fully
characterize the solvability of deterministic leader election over general
graphs in the message-passing model; their characterization follows from
considering various types of _symmetries_ in the graph. Boldi et al. [BSV+96]
also give a full characterization of solvability for leader election in
networks with and without port-numbers, using a method of graph-homomorphisms
known as graph covering or fibrations. This was later extended by Chalopin et
al. [CGM12] to families of graphs. (Codenotti et al. [CGPS97] mention that
leader election in $K_{m,n}$ is possible if and only if $\gcd(m,n)=1$). In
contrast to [BSV+96, CGM12, YK96], which require a complicated analysis of the
structure of the network, our characterization is much more straightforward
and intuitive, and is based only on the greatest common divisor of the sizes
of the subsets of parties connected to the same randomness source — however,
this clean characterization applies only for the clique. There is plenty of
other work on leader election in various models and settings. We surveyed
above only the most relevant work to our model. No prior work considered the
interesting case of symmetry-breaking in correlated randomness settings to the
best of our knowledge. We stress again that the analysis of leader election is
merely a single example of our framework and machinery for topological
analysis of randomized distributed algorithms.

##  2 The Model

###  2.1 Communication and Randomness

#### Communication model.

We consider $n\geq 1$ identical fault-free processing nodes with no
identifiers (i.e., they are anonymous) running the same algorithm. The nodes
perform computation and communication in lockstep, that is, we assume
synchronous rounds. For $r\geq 1$, the $r$-th round occurs between time $r-1$
and time $r$. During each round every node can send a message to each other
node, and can receive messages from the other nodes. The size of the messages
is finite but unbounded. Without loss of generality, we can assume that each
node sends its entire history to the other nodes at every round, which is a
complete description of all the information accumulated by the node during the
previous rounds, including its inputs, the content of the messages that were
sent and received, when these messages were sent and received, etc. We
consider two sub-models regarding the way each node communicates with the
other nodes in the system.

  * •

_The blackboard model:_ There is a shared memory called _blackboard_ , and
each node can send information to the other nodes by appending a message to
the blackboard. Every message written on the blackboard by a node at the
beginning of a round can be seen by all the other nodes at the end of the
round. However, there are no indications about which node is the origin of a
message written on the board. Furthermore, the order in which the messages
appear on the blackboard during a single round is arbitrary; without loss of
generality we will assume all the messages written to the board in a single
round appear on it in a lexicographic order.

  * •

_The message-passing model:_ The nodes are connected as a clique $K_{n}$, and
they communicate by passing messages through the edges of $K_{n}$. A message
sent by a node $u$ through its incident edge $e$ at the beginning of a round
is received by the other extremity of $e$ at the end of the round. The $n-1$
edges incident to every node $u$ are labeled by $n-1$ distinct integers in
$\\{1,\ldots,n-1\\}$. The label given to an edge $e$ incident to node $u$ is
called the port number of $e$ at $u$. The port numbers are arbitrary, and
there are no correlations between the two port numbers of an edge at its two
extremities. Our results hold for the worst case assignment of port numbers,
that is, they can be assumed to be assigned by an adversary.

In both cases, there are no restrictions on the amount of information that can
be transmitted during a round, that is, there are no restrictions on the size
of the messages to be written on the blackboard or to be sent through the
links of the network. In other words, we assume _full information_ protocols.

#### Randomness.

Given a positive natural number $m$ we denote by $[m]$ the set
$\\{1,\ldots,m\\}$. We assume that the system has access to $k$ independent
sources of randomness, denoted by $\mathbf{R}_{1},\ldots,\mathbf{R}_{k}$, for
$k\in[n]$. During every round, each source $\mathbf{R}_{i}$, $i\in[k]$,
generates a single bit whose value is chosen uniformly at random in
$\\{0,1\\}$. The random variable equal to the infinite binary string generated
by $\mathbf{R}_{i}$ is denoted by $R_{i}$. Each node is connected to one of
the $k$ sources $\mathbf{R}_{i}$, $i\in[k]$, and it may be the case that
several nodes are connected to the same source of randomness (this necessarily
happens whenever $k<n$). The random variable equal to the infinite binary
string received by node $i\in[n]$, is denoted by $X_{i}$. At time $t$, node
$i$ has received a prefix of length $t$ of $X_{i}$, i.e., a $t$-bit string
$x_{i}(t)\in\\{0,1\\}^{t}$.

Throughout the paper, random variables are denoted by uppercase letters (e.g.,
$R_{i},X_{i}$), and their realizations are denoted by lowercase letters (e.g.,
$r_{i},x_{i}$). A random variable $Z$ at round $t$ is denoted by $Z(t)$, and
for a string $S$, we let $S(t,\dots,t^{\prime})$ denote the sub-string
$S(t)\,S(t+1)\dots S(t^{\prime})$; the same holds for realizations of random
variables, etc.

###  2.2 Knowledge

For $t\geq 0$, let $K_{i}(t)$ be the _knowledge_ of node $i\in[n]$ at time
$t$, defined recursively as follows. For every $i\in[n]$, $K_{i}(0)=v_{i}$,
where $v_{i}$ is the input value given to node $i$. If there are no inputs,
then $K_{i}(0)=\bot$. In the blackboard model, for $t\geq 1$, we set

$K_{i}(t)=\Big{(}K_{i}(t-1),X_{i}(t),\big{\\{}K_{j}(t-1):j\in[n]\smallsetminus\\{i\\}\big{\\}}\Big{)}.$
(1)

where the knowledge $\\{K_{j}(t-1):j\in[n]\smallsetminus\\{i\\}\\}$ received
from the other nodes is a multi-set; this multiset corresponds to the entire
content of the blackboard, up to the order which is lexicographic by
assumption. In the message-passing model, we set

$K_{i}(t)=\Big{(}K_{i}(t-1),X_{i}(t),\big{(}K_{\pi_{i}(1)}(t-1),\dots,K_{\pi_{i}(n-1)}(t-1)\big{)}\Big{)},$
(2)

where $\pi_{i}(j)\in[n]$ denotes the node connected to node $i$ by the edge
with port-number $j$ at $i$. Note that node $i$ does not know $i$, nor does it
know $\pi_{i}(j)$ for $j=1,\dots,n-1$. Note also that, at time $t$, a node
knows the $t$ random bits it received from its source of randomness during the
first $t$ rounds, but only the $t-1$ bits received by every other node from
its source of randomness during the first $t-1$ rounds.

##  3 Topological Description of Randomized Symmetry-Breaking Distributed
Algorithms

In this section, we describe the topological framework that enables the
analysis of distributed algorithms, and extends it to capture the analysis of
randomized algorithms. In Section 4 we will later show how to actually use
this framework for analyzing the solvability of leader election as a function
of the randomness given to each node, for both blackboard and message-passing
models. The reader is referred to Appendix  The Topology of Randomized
Symmetry-Breaking Distributed Computing for some basic topological
definitions. Further information can be found, e.g., in [HKR14].

###  3.1 Topological Setting

We recall the notion of tasks, and of solvability of tasks in fixed time,
within the topological framework.

#### Tasks.

A _task_ is described by a triple $\Pi=(\mathcal{I},\mathcal{O},\Delta)$,
where $\mathcal{I}$ is the input complex, $\mathcal{O}$ is the output complex,
and $\Delta:\mathcal{I}\to 2^{\mathcal{O}}$ is the input-output specification
of the task (see, e.g., [HKR14]). All the complexes are “colored”, in the
sense that their vertices have the form $(i,x)$ with color $i\in[n]$, for some
value $x$, and their simplices include vertices with different colors. We
rather refer to the color $i$ of a vertex $(i,x)$ as its _name_ , i.e., the
node named $i$ holds value $x$; we denote $\mathsf{name}((i,x))=i$, which can
be extended to a set of nodes in a straightforward manner.

In this paper, we focus on input-free symmetry breaking tasks, so
$\mathcal{I}$ is the trivial complex with a single facet
$\\{(i,\bot):i\in[n]\\}$. For input-free tasks, the input-output specification
is trivial, that is, given any input simplex $\sigma\in\mathcal{I}$, this
simplex is mapped to all simplices of $\mathcal{O}$ with same set of names as
$\sigma$. A symmetry-breaking task is thus simply defined by its output
complex $\mathcal{O}$. We only require that the output complex must be stable
by permutation of the colors of the processes. That is, if $\\{(i,v_{i}):i\in
I\\}$ is a simplex of $\mathcal{O}$, with $\varnothing\neq I\subseteq[n]$,
then, for every permutation $\pi:I\to I$, it must be the case that
$\\{(i,v_{\pi(i)}):i\in I\\}\in\mathcal{O}$. For instance, the output complex
$\mathcal{O}_{\mathsf{LE}}$ for leader election (LE) has $n$ facets

$\tau_{i}=\\{(1,0),\dots,(i-1,0),(i,1),(i+1,0),\dots,(n,0)\\},$

for $i=1,\dots,n$. That is, $\tau_{i}$ is the legal output state in which node
$i$ is elected, and the $n-1$ other nodes are defeated. Note that
$\mathcal{O}_{\mathsf{LE}}$ is symmetric.

#### Communication and randomness configuration.

The exchanges of information between the nodes occurring throughout the
execution is captured by the protocol complexes. The vertices of the protocol
complex at time $t$, denoted by $\mathcal{P}(t)$, are pairs $(i,K_{i}(t))$,
$i\in[n]$, where $K_{i}(t)$ denotes the knowledge acquired by node $i$ at time
$t$. See Figure 1 for a demonstration of $\mathcal{P}(t)$ for $t=0,1,2$ for a
computation with two parties.

$\bot$$\bot$$\bot,0,(\bot)$$\bot,0,(\bot)$$\bot,1,(\bot)$$\bot,1,(\bot)$$k_{0},0,(k_{0})$$k_{0},0,(k_{0})$$k_{0},1,(k_{0})$$k_{0},1,(k_{0})$$k_{1},0,(k_{1})$$k_{1},0,(k_{1})$$k_{1},1,(k_{1})$$k_{1},1,(k_{1})$$k_{0},0,(k_{1})$$k_{1},0,(k_{0})$$k_{0},1,(k_{1})$$k_{1},1,(k_{0})$$k_{1},0,(k_{0})$$k_{0},0,(k_{1})$$k_{1},1,(k_{0})$$k_{0},1,(k_{1})$$\mathcal{P}(0)$$\mathcal{P}(1)$$\mathcal{P}(2)$
Figure 1: The evolution of a 2-party algorithm for time steps $t=0,1,2$. The
knowledge of each party at a given time, written next to the respective node,
consists of the party’s previous knowledge, the random bit it has achieved in
that round, and the knowledge of the other party sent to it in the previous
round. In this figure, $k_{0}=(\bot,0,(\bot))$, $k_{1}=(\bot,1,(\bot))$. Each
edge is a possible state of the system, whose probability is determined by the
specific randomness configuration $\alpha\in\mathcal{A}$ in a given execution.
An edge at time $t$ (i.e., a facet of $\sigma\in\mathcal{P}(t)$) evolves into
$4$ possible facets (edges) of $\mathcal{P}(t+1)$. These correspond to the 4
possible values of the random bits obtained by the two parties at time $t+1$.

The knowledge acquired by the nodes however depends the randomness they obtain
and on the way the $k$ randomness sources are assigned to the $n$ nodes. We
also use a complex to formalize all possible assignments. This complex,
denoted by $\mathcal{A}$ (for “assignment”) is the pure $(n-1)$-dimensional
complex whose facets are of the form

$\alpha=\\{(1,j_{1}),\ldots,(n,j_{n})\\},$

where $\bigcup_{i=1}^{n}\\{j_{i}\\}=[k]$ for some $k\in[n]$; that is, without
loss of generality we rename the $k$ different sources to be contiguous in
$\\{1,\ldots,k\\}$. For every $i\in[n]$, a pair $(i,j)$ means that node $i$ is
connected to the randomness source $\mathbf{R}_{j}$. Every facet $\alpha$ of
$\mathcal{A}$ is called a randomness-_configuration_ , that is, a
configuration determines which node is connected to which randomness source,
for all the nodes. For a given configuration $\alpha$ we denote by
$k=k(\alpha)$ the number of different sources actually connected to the
systems. Note that our restriction on $\mathcal{A}$’s facets means that the
$k$ sources actually connected to the system are exactly
$\mathbf{R}_{1},\ldots,\mathbf{R}_{k}$. A set

$\\{(i,K_{i}(t)):i\in[n]\\}$

forms a facet of $\mathcal{P}(t)$ whenever there exists a configuration
$\alpha\in\mathcal{A}$ such that, with non-zero probability, each node $i$
acquires knowledge $K_{i}(t)$, $i=1,\dots,n$, after $t$ rounds of
communication.

#### Solvability in fixed time.

Recall that a map $\delta$ between the vertex sets of two complexes is
_simplicial_ if it preserves simplices. A simplicial map between two chromatic
complexes is _name-preserving_ if it preserves the names of the vertices
(i.e., for every vertex $(i,x)$, $\delta(i,x)=(i,y)$ for some $y$ that may
depend on $i$ and $x$), and it is _name-independent_ if it is oblivious to the
names (i.e., if $\delta(i,x)=(i,y)$, then $\delta(j,x)=(j,y)$ for every $j$,
that is, $y$ depends solely on $x$). In this work all our complexes are
chromatic and all the maps are name-preserving.

In the standard topological setting, a task $(\mathcal{I},\mathcal{O},\Delta)$
is solvable in $t$ rounds if there exists a name-preserving and name-
independent simplicial map

$\delta:\mathcal{P}(t)\to\mathcal{O}.$

This notion of solvability is not appropriate to our randomized setting, for
two reasons. First, we want to discuss solvability as a function of the
randomness-configuration $\alpha\in\mathcal{A}$ of the randomness sources.
Second, and more importantly, there might be no $t$, even arbitrarily large,
enabling such a simplicial map $\delta:\mathcal{P}(t)\to\mathcal{O}$ to exist.
This holds even when the task is eventually solvable under the configuration
$\alpha$. To better illustrate this point, assume two processes, each with its
private and independent source of randomness. There is no $t$ for which one
can guarantee that the two processes have received two different bits at some
round $r\in\\{1,\dots,t\\}$. Yet, leader election is almost surely solvable in
this context as, eventually, the two processes will receive two different bits
at some round.

###  3.2 Eventual Solvability

A global state of the system at time $t$ is a facet $\sigma$ of
$\mathcal{P}(t)$.

######  Definition 3.1.

A global state $\sigma\in\mathcal{P}(t)$ solves a symmetry-breaking task
$\mathcal{O}$ if there exists $\tau\in\mathcal{O}$ and a _name-preserving_ and
_name-independent_ simplicial map $\delta:\sigma\to\tau.$

This definition of solvability for a facet of $\mathcal{P}(t)$ is motivated by
the following observation. Let us assume that, for a facet
$\sigma=\\{(i,K_{i}(t)):i\in[n]\\}$ of $\mathcal{P}(t)$, there is a name-
preserving and name-independent simplicial map $\delta:\sigma\to\tau$. This
map can be written as $\delta(i,K_{i}(t))=(i,f(K_{i}(t))$, $i=1,\dots,n$, for
some function $f$ of the knowledge. Since the output complex $\mathcal{O}$ is
symmetric, the map $\delta$ yields the existence of a simplicial map
$\delta^{\prime}:\sigma^{\prime}\to\tau^{\prime}$ for every simplex
$\sigma^{\prime}=\\{(i,K_{\pi(i)}(t)):i\in[n]\\}$ of $\mathcal{P}(t)$ where
$\pi:[n]\to[n]$ is a permutation, letting
$\tau^{\prime}=\\{(i,v_{\pi(i)}):(i,v_{i})\in\tau\\}\in\mathcal{O}$ and
defining $\delta^{\prime}(i,K_{\pi(i)}(t))=(i,f(K_{\pi(i)}(t)))$. From this
observation, we derive an algorithm solving $\mathcal{O}$ whenever the global
state of the system is of the form
$\sigma^{\prime}=\\{(i,K_{\pi(i)}(t)):i\in[n]\\}$ for some permutation
$\pi:[n]\to[n]$. Indeed, at time $t$, the knowledge accumulated by nodes
during the first $t$ rounds results in some global state
$\sigma^{\prime}\in\mathcal{P}(t)$ of the system. Each node may not be aware
of $\sigma^{\prime}$ as its individual knowledge may also be compatible with
other global states. Nevertheless, after one more round, the nodes receives
the knowledge of the other nodes in $\sigma^{\prime}$. This enables each node
to reconstruct $\sigma^{\prime}$ up to a permutation of the names of the other
nodes. By applying $f$ on its knowledge, every node can then compute its
output such that the collection of all outputs truly solves the task at time
$t+1$ whenever the processes were in global state $\sigma^{\prime}$ at time
$t$.

Given an assignment $\alpha\in\mathcal{A}$ of the randomness sources to the
nodes, every global state $\sigma\in\mathcal{P}(t)$ has some probability to
occur at a given time. One can thus compute the probability of solving the
task at time $t$ given $\alpha$ as

$\Pr[\mbox{$\mathcal{P}(t)$ solves
$\mathcal{O}$}\mid\alpha]=\sum_{\mbox{\small$\sigma$ solves
$\mathcal{O}$}}\Pr[\sigma\mid\alpha].$

Observe that whenever $\sigma\in\mathcal{P}(t)$ solves $\mathcal{O}$ via some
$\delta_{\sigma}:\sigma\to\tau$, every global state
$\sigma^{\prime}\in\mathcal{P}(t^{\prime})$ for $t^{\prime}\geq t$ that
results from $\sigma$ after $t^{\prime}-t$ additional rounds also solves
$\mathcal{O}$. This is simply because the knowledge is cumulative, and one can
discard all the additional information obtained by the nodes during the
$t^{\prime}-t$ additional rounds for defining
$\delta_{\sigma^{\prime}}:\sigma^{\prime}\to\tau$ using $\delta_{\sigma}$.
More importantly, the following holds.

######  Lemma 3.2.

For every input-free symmetry-breaking task $\mathcal{O}$, and every
randomness-configuration $\alpha\in\mathcal{A}$,

$\lim_{t\to\infty}\Pr[\mbox{$\mathcal{P}(t)$ solves
$\mathcal{O}$}\mid\alpha]\in\\{0,1\\}.$

###### Proof.

Let us assume that
$\Pr[\mathcal{P}(t)\;\mbox{solves}\;\mathcal{O}\mid\alpha]>0$. Therefore,
there exists a global state $\sigma\in\mathcal{P}(t)$ that solves
$\mathcal{O}$, where $\Pr[\sigma\mid\alpha]>0$. This means that there exists a
set of nodes’ knowledge $K=\\{K_{i}(t)\\}_{i\in[n]}$ that yields a solution to
the task. Note that in an input-free task, knowledge (at time $t$) stems only
from the randomness and messages sent by time $t$. That is, there exists $k$
realizations of randomness, each of length $t$, that induce the set $K$, and
these realizations have non-zero probability to occur, given $\alpha$. Denote
these realizations by $R$. For every $s\geq 0$, let $E_{s}$ be the event “$R$
occurred during rounds $s+1$ to $s+t$”. Since knowledge is cumulative, the
occurrence of $E_{s}$ implies that, at time $s+t$, the nodes hold a knowledge
$\\{K_{i}(s+t)\\}_{i\in[n]}$ where, for every $i\in[n]$, $K_{i}(t)$ is
included in $K_{i}(s+t)$. Thus, for any $s\geq 0$, if $E_{s}$ holds, the
system reaches a global state that solves the task. Furthermore, note that two
events $E_{s}$ and $E_{s^{\prime}}$ are independent whenever
$|s-s^{\prime}|>t$, since our sources are i.i.d across time.

Recall that, given an infinite sequence $(X_{i})_{i\geq 1}$ of independent
random variables, a _tail event_ for $(X_{i})_{i\geq 1}$ is an event based on
the realization of the $X_{i}$’s, $i\geq 1$, which is probabilistically
independent of any _finite_ subset of $\\{X_{i}:i\geq 1\\}$. Kolmogorov’s
zero–one law [FT14] states that, for any tail event $E$ over $(X_{i})_{i\geq
1}$, either

$\displaystyle\Pr[E]=0,\quad\text{or}\quad\Pr[E]=1.$

Let $E=\bigcup_{s=0}^{\infty}E_{st}.$ We have
$\Pr[E\mid\alpha]\leq\lim_{t\to\infty}\Pr[\mbox{$\mathcal{P}(t)$ solves
$\mathcal{O}$}\mid\alpha].$ Moreover, $E$ is a tail event, and therefore its
probability is either 0 or 1. Since $\Pr[E_{0}\mid\alpha]>0$, it follows that
$\Pr[E\mid\alpha]=1$. We conclude that if $\Pr[\mathcal{P}(t)$ solves
$\mathcal{O}\mid\alpha]>0$, then $\lim_{t\to\infty}\Pr[\mbox{$\mathcal{P}(t)$
solves $\mathcal{O}\mid\alpha$}]=1,$ as claimed. ∎

This result motivates the following definition.

######  Definition 3.3.

A task $\mathcal{O}$ is _eventually solvable_ given the randomness-
configuration $\alpha\in\mathcal{A}$ if and only if

$\lim_{t\to\infty}\Pr[\mbox{$\mathcal{P}(t)$ solves
$\mathcal{O}$}\mid\alpha]=1.$

###  3.3 Realization and Consistency Complexes

We now introduce new complexes, which are essentially reformulations of the
protocol and output complexes $\mathcal{P}(t)$ and $\mathcal{O}$, more
suitable for the analysis of input-free symmetry-breaking tasks.

#### Realization complex.

In the setting of this paper, namely the anonymous blackboard and message-
passing models, the protocol complex is entirely determined by the values of
the random bits produced by the $k$ sources of randomness. The realization
complex at time $t$ is denoted by $\mathcal{R}(t)$, for any $t\geq 1$. The
vertices of $\mathcal{R}(t)$ are pairs $(i,x_{i})$ where
$x_{i}\in\\{0,1\\}^{t}$ is a binary string of length $t$ (the random bits
received by node $i$ during the first $t$ rounds). Specifically,
$\mathcal{R}(t)$ has vertex-set

$V(\mathcal{R}(t))=\\{(i,x_{i}):i\in[n],x_{i}\in\\{0,1\\}^{t}\\}.$

For $I\subseteq[n]$, a set $\rho=\\{(i,x_{i}):i\in I\\}\subseteq
V(\mathcal{R}(t))$ is a simplex of $\mathcal{R}(t)$ if there exists a
randomness-configuration $\alpha\in\mathcal{A}$ such that, with non-zero
probability, each node $i\in I$ may receive the random bit-string $x_{i}$. See
Figure 2 for an illustration with three parties.

$\mathcal{R}(0)$$\mathcal{R}(1)$$(\bot,\bot,\bot)$(2,0)(1,0)(3,0)(2,1)(1,1)(3,1)$(1,0,1)$$(0,0,1)$$(1,0,0)$
Figure 2: A demonstration of $\mathcal{R}(0)$ and $\mathcal{R}(1)$ in a system
with 3 processes. Each facet represents a possible state of the system
described via the randomness received by the parties up to that time. The
notation $(w,b,r)$ with $w,b,r\in\\{0,1\\}$ describes the randomness of the
white, black, and red nodes accordingly, i.e., the simplex
$\\{(1,w),(2,b),(3,r)\\}$; $\bot$ is the empty string.

We observe relations between $\mathcal{P}(t)$ and $\mathcal{R}(t)$ that allow
us to analyze the algorithm via the more intuitive $\mathcal{R}(t)$. For any
time $t\geq 0$ there exists a simplicial map
$h:\mathcal{P}(t)\to\mathcal{R}(t)$ that takes each vertex
$(i,K_{i})\in\mathcal{P}(t)$ to $(i,x_{i})\in\mathcal{R}(t)$, where
$x_{i}\in\\{0,1\\}^{t}$ is the randomness received by party $i$ according to
$K_{i}(t)$; recall that $K_{i}(t)$ indeed contains $x_{i}(t)$ by its
definition (Eqs. (1) and (2) for the blackboard and message-passing models,
respectively). Note that $K_{i}(t)$ contains also randomness received by all
the other parties up to round $t-1$, hence, $h$ maps multiple vertices to
$(i,x_{i})$. Note that $h$ is name-preserving by construction.

We observe that the simplicial map $h$ induces an isomorphism between _facets_
of $\mathcal{P}(t)$ and facets of $\mathcal{R}(t)$. Indeed, a facet
$\\{(i,K_{i}(t)):i\in[n]\\}\in\mathcal{P}(t)$ uniquely determines the
randomness $(x_{1},\ldots,x_{n})$ received by all parties up to round $t$, and
is mapped to the facet $\\{(i,x_{i}):i\in[n]\\}$ of $\mathcal{R}(t)$.
Similarly, if one determines the randomness by time $t$,
$(x_{1},\ldots,x_{n})$, this uniquely defines the knowledge every party holds
up to time $t$, since each $K_{i}(t)$ consists of $x_{i}$ and $K_{j}(t-1)$ for
$j\in[n]$, and these, by induction, are deterministic function of
$(x_{1},\ldots,x_{n})$. With a slight abuse of notation we will commonly refer
to $h$ as an _isomorphism_ , implicitly restricting it to act on facets.

#### Consistency complexes.

We now consider two general “consistency-projections” $\pi$ and $\tilde{\pi}$
that apply on chromatic complexes. Let $\mathcal{K}$ be a pure chromatic
complex of dimension $n-1$, that is, a complex whose vertices are pairs of the
form $(i,v)$, with $i\in[n]$, and $v$ a value. Let
$\sigma=\\{(i,v_{i}):i\in[n]\\}$ be a facet of $\mathcal{K}$. We define the
complex $\pi(\sigma)$ as the complex on vertex-set $\\{(i,v_{i}):i\in[n]\\}$
such that, for every non-empty $I\subseteq[n]$,

$\\{(i,v_{i}):i\in I\\}\in\pi(\sigma)\iff\forall(i,j)\in I\times
I,v_{i}=v_{j}.$ (3)

The projection $\pi$ applied simultaneously to all the facets of $\mathcal{K}$
results in the complex

$\pi(\mathcal{K})=\bigcup_{\sigma\in\mathcal{K}}\pi(\sigma),$

where the union is taken on the facets of $\mathcal{K}$. We note that
$\pi(\mathcal{K})$ is a subcomplex of $\mathcal{K}$.

As a simple illustrative example, in the case of leader election (LE), the
complex $\pi(\mathcal{O}_{\mathsf{LE}})$ has facets

$\displaystyle\\{(i,1)\\}\quad\text{and}\quad\\{(j,0):j\in[n]\smallsetminus\\{i\\}\\}$

for every $i\in[n]$. See also Figure 3.

$\tau_{2}$$\tau_{1}$$\tau_{3}$$\mathcal{O}_{\mathsf{LE}}$$(1,0)$$(2,0)$$(3,0)$$(1,1)$$(2,1)$$(3,1)$

$\pi(\mathcal{O}_{\mathsf{LE}})$$(1,0)$$(2,0)$$(3,0)$$(1,1)$$(2,1)$$(3,1)$$\pi(\tau_{1})$

Figure 3: $\mathcal{O}_{\mathsf{LE}}$ and $\pi(\mathcal{O}_{\mathsf{LE}})$.
The facet $\tau_{1}\in\mathcal{O}_{\mathsf{LE}}$ is mapped to the subcomplex
$\pi(\tau_{1})\subseteq\pi(\mathcal{O}_{\mathsf{LE}})$ that contains the edge
$\\{(2,0),(3,0)\\}$ and the isolated node $\\{(1,1)\\}.$

The second consistency-projection, $\tilde{\pi}$, is more specific and applies
only to the realization complexes $\mathcal{R}(t)$, for $t\geq 1$. It is not
using equality between values, but an equivalence relation between the
vertices of $\mathcal{R}(t)$, defined as follows. Given specific realizations
$x_{i}\in\\{0,1\\}^{t}$ for the randomness of party $i\in[n]$ at time $t$, we
say that nodes $i$ and $j$ are _consistent_ at time $t$, denoted by

$i\overset{t}{\sim}j$ (4)

if $K_{i}(t)=K_{j}(t)$. Note that once the randomness obtained by the parties
up to round $t$, $x_{1},\ldots,x_{n}\in\\{0,1\\}^{t}$, are fixed, the event
$K_{i}(t)=K_{j}(t)$ is deterministic (it has probability either 0 or 1). In
the blackboard model, this equality depends solely on the random bits received
by nodes $i$ and $j$ during the first $t$ rounds. However, in the message-
passing model, this equality also depends on the actual assignment of parties’
port numbers. Also, it is worth observing that once $K_{i}(t)\neq K_{j}(t)$ in
a specific instance of randomness, the two nodes $i$ and $j$ become
inconsistent for the rest of the execution. However, they become aware of this
fact only at the next round, where knowledge is exchanged (in both the
blackboard and the message-passing model)[FMHV03].

Let $\rho=\\{(i,x_{i}):i\in[n]\\}$ be a facet of $\mathcal{R}(t)$. We define
the complex $\tilde{\pi}(\rho)$ as the complex on vertex-set
$V(\rho)=\\{(i,x_{i}):i\in[n]\\}$ such that, for every non-empty $I\in[n]$,

$\\{(i,x_{i}):i\in I\\}\in\tilde{\pi}(\rho)\iff\forall(i,j)\in I\times I,\
i\overset{t}{\sim}j.$ (5)

The consistency complex captures all the possible relations of consistency for
all possible generations of random strings. The consistency-projection
$\tilde{\pi}$ applied simultaneously to all the facets of $\mathcal{R}(t)$
results in the complex

$\tilde{\pi}(\mathcal{R}(t))=\bigcup_{\rho\in\mathcal{R}(t)}\tilde{\pi}(\rho),$
(6)

where the union is taken on the facets of $\mathcal{R}(t)$. Note that
$\tilde{\pi}(\mathcal{R}(t))$ is a subcomplex of $\mathcal{R}(t)$; its
topological structure will be vital for our analysis.

###  3.4 Randomized Solvability of Tasks Revisited

A facet of $\mathcal{R}(t)$ is called a _realization_ of the system at time
$t$. By definition, there are $2^{nt}$ different realizations at time $t$.
Also, since each source of randomness generates a single bit uniformly at
random at each round, we have

$\Pr[R_{i}(1,\dots,t)=x]=2^{-t}$

for every $x\in\\{0,1\\}^{t}$. It directly follows that the probability that a
node $i\in[n]$ receives random string $x\in\\{0,1\\}^{t}$ during the first $t$
rounds is $2^{-t}$, regardless to which randomness source node $i$ is
connected. However, there might be correlations between different nodes,
whenever they are connected to the same randomness source (an information that
is not given to the nodes a priori). Let
$\rho=\\{(1,x_{1}),\ldots(n,x_{n})\\}\in\mathcal{R}(t)$ be a realization of
the system at time $t$, and let $\alpha\in\mathcal{A}$ be a randomness-
configuration of the system. We have

$\Pr[\rho\mid\alpha]=\Pr\Big{[}\bigwedge_{(i,j)\in\alpha}R_{j}(1,\dots,t)=x_{i}\Big{]}.$

We introduce a novel definition for solvability. This definition will be shown
to be equivalent to the definition using facets of $\mathcal{P}(t)$.

######  Definition 3.4.

A realization $\rho\in\mathcal{R}(t)$ solves a symmetry-breaking task
$\mathcal{O}$ if there exists $\tau\in\mathcal{O}$ and a name-preserving
simplicial map $\delta:\tilde{\pi}(\rho)\to\pi(\tau).$

Note that, in this definition, the map $\delta$ is not asked to be name-
independent, since this property will be provided by the structure the
projections impose. Since every realization $\rho\in\mathcal{R}(t)$ has some
probability to occur at a given time, one can compute the probability of
solving the task at time $t$ by summing up the probabilities of the
realizations that solve the task at time $t$. For any $t\geq 1$, let
$\mathcal{S}(t)$ be the set of all the realizations of the system after $t$
rounds that solves the task $\mathcal{O}$, and let us define the probability
of $\mathcal{S}(t)$ given some randomness-configuration $\alpha\in\mathcal{A}$
as the sum of the probability of its facets, that is,

$\Pr\left[\mathcal{S}(t)\mid\alpha\right]=\sum_{\sigma\in\mathcal{S}(t)}\Pr\left[\sigma\mid\alpha\right].$

Again, by Kolmogorov’s zero–one law, the limit when $t$ goes to infinity of
the probability of $\mathcal{S}(t)$ is equal to 0 or 1. Moreover, this new
notion of solvability is equivalent to the (algorithmic) notion of solvability
of Definition 3.3.

######  Lemma 3.5.

An input-free symmetry-breaking task $\mathcal{O}$ is eventually solvable
given a randomness-configuration $\alpha\in\mathcal{A}$ if and only if

$\lim_{t\to\infty}\Pr\left[\mathcal{S}(t)\mid\alpha\right]=1,$ (7)

where $\mathcal{S}(t)$ is the set of all the realization
$\sigma\in\mathcal{R}(t)$ that solve $\mathcal{O}$ at time $t$.

###### Proof.

First, assume $\sigma\in\mathcal{P}(t)$ solves $\mathcal{O}$. We show that
$h(\sigma)\in\mathcal{R}(t)$ solves $\mathcal{O}$ for
$h:\mathcal{P}(t)\to\mathcal{R}(t)$ the name-preserving simplicial map defined
in Section 3.3. Fix $t$ and $\sigma\in\mathcal{P}(t)$ that solves the task,
and set $\rho=h(\sigma)$. According to Definition 3.1, there is a name-
preserving name-independent simplicial map $\delta:\sigma\to\tau$. where
$\tau=\delta(\sigma)$ is a facet of $\mathcal{O}$.

Given $\sigma$ and $\rho$, we can define a name-preserving simplicial map (in
fact, an isomorphism) $\tilde{h}:\rho\to\sigma$ (being viewed as complexes)
that for any $i\in[n]$ takes $(i,x_{i})\in\rho$ to $(i,K_{i})\in\sigma$; note
that $\tilde{h}$ is the uniqe name-preserving simplicial map between $\rho$
and $\sigma$.

We claim that $\lambda\triangleq\delta\circ\tilde{h}=\delta(\tilde{h}(\cdot))$
is a name-preserving simplicial map $\lambda:\tilde{\pi}(\rho)\to\pi(\tau)$.
Indeed, (1) $\lambda$ is name preserving: this follows immediately since
$\tilde{h},\delta$ are both name-preserving. (2) $\lambda$ preserves
simplices: fix a realization $\rho=\\{(i,x_{i}):i\in[n]\\}\in\mathcal{R}(t)$
and let $K_{i}(t)$ be the knowledge of party $i$ at time $t$ given the
realization $\rho$. Then $\sigma=\tilde{h}(\rho)=\\{(i,K_{i}(t)):i\in[n]\\}$;
in particular $\tilde{h}((i,x_{i}))=(i,K_{i}(t))$, since $\tilde{h}$ preserves
names. Let $\rho^{\prime}$ be a facet in $\tilde{\pi}(\rho)$. By the
definition of $\tilde{\pi}$, for any two vertices
${(i,x_{i}),(j,x_{j})}\in\rho^{\prime}$ it holds that $i\overset{t}{\sim}j$.
Thus, by the definition of the $\sim$ relation, $K_{i}(t)=K_{j}(t)$ and thus
$\\{(i,K_{i}(t)),(j,K_{j}(t))\\}\in\pi(\sigma)$. Since the consistency
relation $\sim$ is transitive, the same argument holds for any subset of
vertices in $\rho^{\prime}$. Hence, $\lambda(\rho^{\prime})$ is a simplex in
$\pi(\sigma)$. We conclude that, if $\Pr[\sigma\mid\alpha]>0$, and $\sigma$
solves $\mathcal{O}$ by Definition 3.1 via the map $\delta$, then for
$\rho=h(\sigma)$ and $\tau=\delta(\sigma)$ we have $\Pr[\rho\mid\alpha]>0$,
and $\rho$ solves $\mathcal{O}$ by Definition 3.4 via the map
$\lambda:\tilde{\pi}(\rho)\to\pi(\tau)$.

Conversely, assume that $\rho\in\mathcal{R}(t)$ solves $\mathcal{O}$. We show
that the facet $h^{-1}(\rho)\in\mathcal{P}(t)$ solves $\mathcal{O}$ for
$h:\mathcal{P}(t)\to\mathcal{R}(t)$ the name-preserving simplicial map from
Section 3.3 (recall that $h$ induces an isomorphism on facets, thus it has a
unique inverse for $\rho$). Let $\tau\in\mathcal{O}$ and
$\delta:\tilde{\pi}(\rho)\to\pi(\tau)$ be given for $\rho$ by Definition 3.4.
Let $\sigma=h^{-1}(\rho)$ be given by the isomorphism. We claim that $\sigma$
solves $\mathcal{O}$ via the map $\lambda=\delta\circ h$. First, note that
$\lambda:\sigma\to\tau$ is a name-preserving simplicial map, which follows
since $h$ and $\delta$ are both name-preserving simplicial maps. This also
implies that $\lambda(\sigma)=\delta(h((\sigma))=\tau$ is a facet of
$\mathcal{O}$. Next, we argue that $\lambda$ is name-independent, namely, that
any two parties with the same knowledge give the same output. Let
$(i,K_{i}(t)),(j_{,}K_{j}(t))$ be two vertices in $\sigma$, such that
$K_{i}(t)=K_{j}(t)$. By definition, $i\overset{t}{\sim}j$. If so, then
$\\{(i,x_{i}),(j,x_{j})\\}$ is a simplex in $\tilde{\pi}(\rho)$, where
$(i,x_{i})=h((i,K_{i}(t)))$ and $(j,x_{j})=h((j,K_{j}(t)))$. This simplex must
be mapped by the simplicial map $\delta$ to some simplex
$\\{(i,v),(j,v)\\}\in\pi(\tau)$ (recall that simplices in $\pi(\tau)$ consist
of nodes with similar outputs, Eq. (3)). Since the argument holds for
arbitrary two nodes, it easily extends to any subset of nodes in $\sigma$ that
have identical knowledge, which proves that $\lambda$ is a name-independent. ∎

In Figure 4 we illustrate the relations between the different complexes of
this work.

${\mathcal{R}(t)}$${\mathcal{P}(t)}$${\mathcal{O}}$${\displaystyle\bigcup_{\mathclap{\rho\in\mathcal{R}(t)}}\tilde{\pi}(\rho)}$${\displaystyle\bigcup_{\mathclap{\tau\in\mathcal{O}}}\pi(\tau)}$$\delta:\sigma\to\tau$(Def.
3.1)$\pi$$h$$\tilde{\pi}$(Def. 3.4)$\delta:\tilde{\pi}(\rho)\to\pi(\tau)$
Figure 4: A summary of our topological complexes and the relations between
them.

##  4 Solvability of Leader Election via Topology

In the remainder of this paper we will consider the task of leader election,
$\mathcal{O}_{\mathsf{LE}}$. In this section we will discuss the conditions on
randomness-configurations $\alpha\in\mathcal{A}$ that make
$\mathcal{O}_{\mathsf{LE}}$ eventually solvable. We begin in Section 4.1 with
the blackboard model. In Section 4.2 we will consider the message-passing
model. Recall that the leader election task is defined by
$\mathsf{LE}=(\mathcal{I},\mathcal{O}_{\mathsf{LE}},\Delta)$ with
$\mathcal{I}=\\{(i,\bot):i\in[n]\\}$ and $\Delta:\mathcal{I}\to
2^{\mathcal{O}_{\mathsf{LE}}}$ that maps the single facet of $\mathcal{I}$ to
the entire complex $2^{\mathcal{O}_{\mathsf{LE}}}$. Further recall that
$\mathcal{O}_{\mathsf{LE}}$ has facets

$\tau_{i}=\\{(1,0),\dots,(i-1,0),(i,1),(i+1,0),\dots,(n,0)\\},$

for any $i\in[n]$, and thus
$\pi(\mathcal{O}_{\mathsf{LE}})=\bigcup_{\tau\in\mathcal{O}}\pi(\tau)$ has
facets

$\\{(i,1)\\}\quad\text{and}\quad\\{(j,0):j\in[n]\smallsetminus\\{i\\}\\}$

for any $i\in[n]$. To ease readability, we will denote
$\mathcal{O}_{\mathsf{LE}}$ simply by $\mathcal{O}$ from this point and on, as
the task is clear from context.

Intuitively, leader election is eventually solvable, in either model, if the
algorithm can break symmetry, which in our topological view amounts to
reaching some $\rho\in\mathcal{R}(t)$ with positive probability, such that
$\tilde{\pi}(\rho)$ has an isolated vertex—that process will be the leader.
Impossibility is obtained when for any time $t$, for any
$\rho\in\mathcal{R}(t)$ with positive probability $\tilde{\pi}(\rho)$ does not
contain an isolated vertex and thus cannot be mapped to any $\pi(\tau)$ for
$\tau\in\mathcal{O}$.

In the blackboard model (Section 4.1) we show that processes with the same
randomness will always be connected in $\tilde{\pi}(\rho)$. Then, the only way
to solve leader election is if there exists a process with its unique
randomness source—eventually, the randomness will distinguish this node from
any other node (with probability 1) so this node will be isolated in
$\tilde{\pi}(\rho)$ for any $\rho\in\mathcal{R}(t)$ for which the realization
of randomness that node obtained by time $t$ differs form all the realizations
of all other nodes.

In the message-passing model (Section 4.2), we show that one plus the
dimension of any facet in $\tilde{\pi}(\rho)$ is a multiple of $g$, the GCD of
$n_{1},n_{2},\ldots$, where $n_{i}$ is the number of processors connected to
source $\mathbf{R}_{i}$. Then, an isolated vertex $\tilde{\pi}(\rho)$ cannot
exist unless the GCD is 1. On the other hand, if the GCD is 1, we show an
algorithm that leads to reducing the dimensions of certain facets (i.e., when
looking on the evolution of $\rho\in\mathcal{R}(t)$ as time goes by, that is,
considering states $\rho^{\prime}\in\mathcal{R}(t^{\prime})$ for
$t^{\prime}>t$ with $\Pr[\rho^{\prime}\mid\rho]>0$) until reaching a facet
with dimension 0, that is, an isolated node.

###  4.1 The Blackboard Model

With the above formulation we can determine the solvability of leader election
in the blackboard model as a function of the specific configuration
$\alpha\in\mathcal{A}$ of the system:

######  Theorem 4.1.

Assume $k\leq n$ distinct randomness sources are available to $n$ parties,
where for any $i\in[k]$, there are exactly $n_{i}$ parties connected to
$\mathbf{R}_{i}$. Then, leader election in the blackboard model is eventually
solvable if and only if there exists a source $i\in[k]$ such that $n_{i}=1$.

###### Proof.

We prove the theorem separately for $k=1$ and for $k>1$. For each case we show
that Eq. (7) holds if and only if $n_{i}=1$.

_Base case ( $k=1$):_ Let the randomness-configuration be such that $k=1$,
that is, all the parties are connected to $\mathbf{R}_{1}$ and see exactly the
same stream of randomness. In particular, any realization that gives two
different parties different randomness strings, has zero probability.

‘if’ direction:

Since there is only a single source in the system ($\mathbf{R}_{1})$, if
$n_{1}=1$ then the entire network contains a single party, $n=1$. In this case
leader election is trivial: For any time $t>0$, the complex $\mathcal{R}(t)$
has only 0-dimension facets: $\\{(1,x_{1})\\}$ for any
$x_{1}\in\\{0,1\\}^{t}$. For any $\rho\in\mathcal{R}(t)$ it holds that
$\tilde{\pi}(\rho)=\rho$. Further, $\mathcal{O}$ reduces to a single isolated
node $\tau=\\{(1,1)\\}$, and thus $\pi(\mathcal{O})=\pi(\tau)=\\{(1,1)\\}$. It
then follows that, for any $\rho=\\{(1,x_{i})\\}\in\mathcal{R}(t)$ there
exists a name-preserving simplicial map
$\delta:\tilde{\pi}(\rho)\to\pi(\tau)$, i.e., the map that takes $(1,x_{i})$
to $(1,1)$.

Thus, for every $t$, it holds that $\mathcal{S}(t)$ contains _all_ the facets
of $\mathcal{R}(t)$, because any such realization solves the task
$\mathsf{LE}$. For any $t$, as well as in the limit $t\to\infty$,
$\Pr\left[\mathcal{S}(t)\mid\alpha\right]=1.$

‘only if’ direction:

For the other direction, let $\alpha^{\prime}\in\mathcal{A}$ be a randomness-
configuration in which there is no source $i$ with $n_{i}=1$. Since there is
only a single source ($k(\alpha^{\prime})=1$) we have $n_{1}=n>1$ and we need
to show that leader election is not eventually solvable. Towards
contradiction, assume that $\rho\in\mathcal{R}(t)$ is a realization that
solves LE, say, via a map $\delta:\tilde{\pi}(\rho)\to\pi(\tau_{j})$ for some
$j\in[n],\tau_{j}\in\mathcal{O}$. By definition, any simplicial map $\delta$
must preserve simplices. Let $(i,x_{i})\in\tilde{\pi}(\rho)$ be the vertex
that is mapped to $(j,1)\in\pi({\tau_{j}})$. Since $\\{(j,1)\\}$ is a facet in
$\pi({\tau_{j}})$, the vertex $(i,x_{i})$ must be isolated in
$\tilde{\pi}(\rho)$.

However, this implies that $\Pr[\rho\mid\alpha^{\prime}]=0$, since
$\alpha^{\prime}$ dictates that all parties share the same randomness source
and their views (randomness and blackboard content) are identical. Therefore,
for any realization $\rho^{\prime}$ that has a non-zero probability (given
$\alpha^{\prime}$), the projection $\tilde{\pi}(\rho^{\prime})$ must be a
single facet of dimension exactly $n-1$, that is, $\\{(i,x):{i\in[n]}\\}$, for
some value $x\in\\{0,1\\}^{t}$. On the other hand, $\tilde{\pi}(\rho)$ has a
0-dimension facet, and since $n>1$ its probability is zero given
$\alpha^{\prime}$.

It follows that for any $t$, as well as in the limit,
$\lim_{t\to\infty}\Pr\left[\mathcal{S}(t)\mid\alpha^{\prime}\right]=0.$

_General case ( $k>1$):_ Assume we are given a randomness-configuration
$\alpha\in\mathcal{A}$ with $k=k(\alpha)>1$ distinct randomness sources.
Without loss of generality assume $0<n_{1}\leq n_{2}\leq\dotsb\leq n_{k}$.

‘if’ direction:

Assume $\alpha\in\mathcal{A}$ satisfies $n_{1}=1$. At any time $t$ there are
exactly $2^{kt}$ unique realizations $\rho\in\mathcal{R}(t)$ with positive
probability conditioned on $\alpha$, and recall that all such realizations are
equiprobable (Lemma .1). Let us define

$\displaystyle\mathcal{S}_{1}(t)\overset{\text{def}}{=}\Big{\\{}\rho=\\{(1,x_{1}),\ldots,(n,x_{n})\\}\in\mathcal{R}(t)\
\Big{|}\ \forall i>1,x_{i}\neq x_{1}\Big{\\}}$

to be the set of all the realizations $\rho\in\mathcal{R}(t)$ in which the
randomness obtained by the first party is unique, $x_{1}\neq x_{i}$ for all
$i>1$. There are $2^{t}\cdot(2^{t}-1)^{k-1}$ such realizations with positive
probability given $\alpha$. Note that each such realization solves the task
$\mathsf{LE}$ via the (unique) name-preserving map
$\delta:\tilde{\pi}(\rho)\to\pi(\tau_{1})$, thus
$\mathcal{S}_{1}(t)\subseteq\mathcal{S}(t)$. Since all the positive-probable
realizations are equiprobable we have,

$\displaystyle\Pr\left[\mathcal{S}(t)\mid\alpha\right]$
$\displaystyle\geq\Pr\Big{[}\bigcup_{\rho\in\mathcal{S}_{1}(t)}\rho\mid\alpha\Big{]}=2^{t}(2^{t}-1)^{k-1}\cdot
2^{-kt}=\frac{(2^{t}-1)^{k-1}}{2^{t(k-1)}}$ $\displaystyle\geq
1-\frac{(k-1)2^{t(k-2)}}{2^{t(k-1)}}=1-\frac{k-1}{2^{t}}.$

From the above, $\lim_{t\to\infty}\Pr\left[\mathcal{S}(t)\mid\alpha\right]=1$
as required.

‘only if’ direction:

Assume a randomness-configuration $\alpha^{\prime}$ (with
$k(\alpha^{\prime})>1$) in which $n_{1}>1$ (hence, there exists no $i$ with
$n_{i}=1$). Let us fix a time $t$, and let $\rho\in\mathcal{R}(t)$ be a
realization that solves the task $\mathsf{LE}$ via
$\delta_{j}:\tilde{\pi}(\rho)\to\pi(\tau_{j})$. In order for $\delta_{j}$ to
be a name-preserving simplicial-map, it is required that $(j,x_{j})\in
V(\tilde{\pi}(\rho))$ is isolated in $\tilde{\pi}(\rho)$, since the vertex
with name $j$ is a 0-dimensional facet of $\pi(\tau_{j})$.

On the other hand, let $\rho^{\prime}\in\mathcal{R}(t)$ be a realization with
positive probability given $\alpha^{\prime}$, namely,
$\Pr[\rho^{\prime}\mid\alpha^{\prime}]>0$. Since in $\alpha^{\prime}$ we have
that $\forall i,n_{i}>1$, for any party $j$ there must exist another party
$j^{\prime}\neq j$ that is connected to the same randomness source as $j$.
Hence, for any time $t$, the randomness $j$ and $j^{\prime}$ see is identical,
$x_{j}=x_{j^{\prime}}$. Furthermore, in the blackboard model, equality of
randomness is equivalent to equality of knowledge, since the knowledge of a
party is just its randomness along with the content of the blackboard.
Therefore, regardless of the realizations
$\\{x_{i}\\}_{i\notin\\{j,j^{\prime}\\}}$ of the other parties, it holds that
$j\overset{t}{\sim}j^{\prime}$ and
$\\{(j,x_{j}),(j^{\prime},x_{j^{\prime}})\\}$ is a simplex in
$\tilde{\pi}(\rho^{\prime})$. So, for any $\rho^{\prime}$ with
$\Pr[\rho^{\prime}\mid\alpha^{\prime}]>0$ and any party $j$, we get that
$(j,x_{j})$ is _not_ isolated in $\tilde{\pi}(\rho)$.

These two arguments imply that for any facet $\rho\in\mathcal{R}(t)$ that
solves the task $\mathsf{LE}$ it holds that $\Pr[\rho\mid\alpha^{\prime}]=0.$
If we let $\mathcal{S}(t)$ denote all the realizations the solve leader
election at time $t$, the above proves that for any $t$, as well in the limit,

$\Pr\left[\mathcal{S}(t)\mid\alpha^{\prime}\right]=0.$

In particular, leader election is not eventually solvable in this case. ∎

###  4.2 The Message-Passing Model

We now turn to the message-passing model where nodes are indistinguishable and
connected by point-to-point channels as a clique. Each node (privately) labels
its $n-1$ neighbours with unique labels from $\\{1,\ldots,n-1\\}$ in an
arbitrary way, which we refer to as the node’s port-numbers. Then, when a node
sends a message to some port $p$ it always reaches the same party; however, if
a different node sends a message to (its own) port $p$, it might reach a
different party according to that node’s private labeling. The main difference
from the blackboard model is that a party’s knowledge might be affected by its
port-numbering in addition to its randomness. Unlike the blackboard model,
where similar randomness means similar knowledge, here parties may have
different knowledge while observing the same randomness (however, if their
randomness is different, their knowledge will be different as well).

We recall that the numbering of the ports is arbitrary. In the following we
ask which configurations lead to solving leader-election _regardless_ of the
specific port numbers. Alternatively, we ask which configurations prevent any
protocol from solving leader-election for at least one port-numbers labeling.
That is, given a randomness-configuration, we look at the _worst case_ for
setting the port numbers and ask whether or not leader-election is eventually
solvable. We term this question _worst-case leader election_.

The following Theorem 4.2, which is this section’s main theorem, shows that
_worst-case_ eventual solvability of leader election depends on the greatest
common divisor (GCD) of the number of parties connected to each randomness
source.

######  Theorem 4.2.

Assume $k\leq n$ distinct randomness sources are available to $n$ parties,
where for any $i\in[k]$, exactly $n_{i}\geq 1$ parties are connected to
$\mathbf{R}_{i}$. Worst-case leader election is eventually solvable if and
only if $\gcd(n_{1},n_{2},\ldots,n_{k})=1.$

We start by showing the following technical lemma that explains how the
consistency-projected complex $\tilde{\pi}(\mathcal{R}(t))$ changes with time.

######  Lemma 4.3.

For any $\alpha\in\mathcal{A}$ such that $\gcd(n_{1},\ldots,n_{k})=g$ there
exists a way to number ports so that for any realization
$\rho\in\mathcal{R}(t)$ that has positive probability $\Pr[\rho\mid\alpha]>0$,
the dimension $\dim(\gamma)$ of any facet $\gamma\in\tilde{\pi}(\rho)$
satisfies $g\mid\dim(\gamma)+1.$

Note that the above suggests that worst-case leader election is not eventually
solvable when the GCD is larger then one, proving the “only if” direction of
Theorem 4.2.

######  Corollary 4.4.

Assume $\alpha^{\prime}\in\mathcal{A}$ such that $\gcd(n_{1},\ldots,n_{k})=g$
and $g>1$, then there exists a way to assign port-numbers to channels so that
leader election is impossible.

###### Proof.

From Lemma 4.3 we know that there exists a way to number ports such that any
realization $\rho\in\mathcal{R}(t)$ for which
$\Pr[\rho\mid\alpha^{\prime}]>0$, has facets of dimension at least $g-1>0$. In
particular, there is no isolated vertex in $\tilde{\pi}(\rho)$, as this will
imply a facet $\gamma$ with $\dim(\gamma)=0$, but $g\nmid\dim(\gamma)+1$,
which is a contradiction. Since there is no isolated vertex in
$\tilde{\pi}(\rho)$, there exists no simplicial map from $\tilde{\pi}(\rho)$
to $\pi(\tau_{j})$ for any facet $\tau_{j}\in\mathcal{O}$ and thus $\rho$ does
not solve leader election. We get that for any $t$, no realization that solves
leader election has positive probability,
$\Pr\left[\mathcal{S}(t)\mid\alpha^{\prime}\right]=0$. ∎

###### Proof of Lemma 4.3..

Let $\alpha\in\mathcal{A}$ be a randomness-configuration in which
$\gcd(n_{1},\ldots,n_{k})=g$. Split the $n$ parties into $g$ disjoint subsets
of nodes where subset $i\in\\{1,\ldots,g\\}$ holds exactly $n_{j}/g$ parties
which are connected to $\mathbf{R}_{j}$ (for all $j\in[k]$). For this part
only rename the parties as $0,1,\ldots,n-1$ where the first $n_{1}$ parties
are connected to the first source and the next $n_{2}$ parties are connected
to the second one, etc. We assign the $j$-th port ($j\in[n-1]$) of party
$i\in\\{0,1,\ldots,n-1\\}$ to be connected to party number

$\big{(}(i+j)\text{mod }g+\lceil i/g\rceil\cdot g+\lceil j/g\rceil\cdot
g\big{)}\mod n.$

There exists an isomorphism $f:\\{0,\dotsc,n-1\\}\to\\{0,\dotsc,n-1\\}$ that
takes any party $i\in\\{0,1,\ldots,{n-1}\\}$ written as $i=r+m\cdot g$ for
$r<g$, $m\in\mathbb{N}$, to the party $f(i)=(r+1\mod g)+mg$. This isomorphism
preserves the assignment of randomness source and it preserves port numbers.
Thus, fixing any realization of randomness $(x_{1},\ldots,x_{n})$ at round
$t$, for any party $i$ we get that $i\overset{t}{\sim}f(i)$: they are
connected to the same source and thus have the same randomness
($x_{i}=x_{f(i)}$). Moreover, every message that party $i$ receives from port
$j$, is also received by $f(i)$ from its own port $j$, due to the way we
number ports. This can be seen by induction; it trivially holds for round $0$;
now assume it holds for round $t-1$. Note that if $i$ is connected to $p$ at
its port $j$, then $f(i)$ is connected to $f(p)$ in its port $j$; furthermore,
if $p$ sees $i$ in its $j^{\prime}$ port, then $f(p)$ sees $f(i)$ it its
$j^{\prime}$ port. Since $p,f(p)$ hold the same information at round $t-1$ by
the induction hypothesis, $i$ and $f(i)$ will receive the same information
from $p,f(p)$ respectively, and the claim will hold for time $t$ as well. Let
us denote the equivalence class of party $i$ by

$\displaystyle\llbracket i\rrbracket=\\{f^{(c)}(i)\mid c\in[g]\\}.$

where $f^{(c)}=f(f(\ldots))$ denotes the $c$-th composition of $f$ with
itself, and $f^{(0)}$ is the identity function (also note that
$f^{(g)}=f^{(0)}$). Let $\rho\in\mathcal{R}(t)$ be a realization such that
$\Pr[\rho\mid\alpha]>0$, and let $\gamma\in\tilde{\pi}(\rho)$ be a facet.

######  Claim 4.5.

If $(i,y_{i})\in\gamma$, then for any $j\in\llbracket i\rrbracket$ we have
that $(j,y_{i})\in\gamma$.

Proof of claim. Suppose $(j,y_{i})\not\in\rho$. Then there exists $y_{j}\neq
y_{i}$ such that $(j,y_{j})\in\rho$ which implies that $\Pr[\rho\mid\alpha]=0$
since $i$ and $j$ are connected to the same randomness source in $\alpha$
according to the way we numbered parties and the definition of $f()$.
Therefore, $(j,y_{i})$ is a node of $\tilde{\pi}(\rho)$, and we are left to
show that $(j,y_{i})\in\gamma$. As argued above, we know that, for any time
$t$, $i\overset{t}{\sim}f(i)$ and thus (for the realization $\rho$)

$i\overset{t}{\sim}f(i)\overset{t}{\sim}\dotsb\overset{t}{\sim}f^{(g-1)}(i).$

Since the $\overset{t}{\sim}$ relation is transitive, all these vertices are
consistent with one another. In particular, note that $i\overset{t}{\sim}j$
since $j\in\llbracket i\rrbracket$. Further, for any vertex $(x,y)\in\gamma$,
we have that $x\overset{t}{\sim}i$ by the definition of the projection
$\tilde{\pi}$ (Eq. (5)) and the fact that $\gamma\in\tilde{\pi}(\rho)$. Now,
by the transitivity of the consistency operator and the fact that
$i\overset{t}{\sim}j$, we get that also $x\overset{t}{\sim}j$. Finally, since
$\gamma$ is a facet of $\tilde{\pi}(\rho)$, the above implies that
$(j,y_{i})\in\gamma$, which completes the proof of Claim 4.5. $\diamond$

Finally, we conclude the proof of the lemma. Let $\gamma\in\tilde{\pi}(\rho)$
be a facet. For any $(i,y_{i})\in\gamma$, Claim 4.5 proves that also
$(j,y_{i})\in\gamma$ for any $j\in\llbracket i\rrbracket$. Since the sets
$\llbracket i\rrbracket$ form a partition of $\\{0,...,n-1\\}$ and since
$|\llbracket i\rrbracket|=g$ for any $i$, we conclude that
$g\mid\dim(\gamma)+1$, which completes the proof of Lemma 4.3. ∎

We now move to proving the other direction of Theorem 4.2, that is, showing
that if the GCD of the size of subsets that are assigned the same randomness
source equals one, then leader election is solvable, _regardless_ of the
specific port numbers. Towards this goal, we show the following technical
lemma that once again considers the structure of the projected complex
$\tilde{\pi}(\mathcal{R}(t))$ over time. The lemma suggests that facets in
$\tilde{\pi}(\mathcal{R}(t))$ (that stem from realizations with positive
probability) eventually “split” into smaller facets. The change in their
dimension is always a multiple of the GCD.

######  Definition 4.6.

We say that a realization $\rho^{\prime}\in\mathcal{R}(t^{\prime})$ _succeeds_
a realization $\rho\in\mathcal{R}(t)$ and denote $\rho\prec\rho^{\prime}$ if
(i) $t^{\prime}>t$ and (ii) for any $i\in[n]$, if $(i,x_{i})\in\rho^{\prime}$
then $(i,x_{i}(1,\ldots,t))\in\rho$.

######  Lemma 4.7.

Fix a randomness-configuration $\alpha\in\mathcal{A}$. Assume a realization
$\rho\in\mathcal{R}(t)$ with $\Pr[\rho\mid\alpha]>0$. Let
$\gamma_{1},\gamma_{2}\in\tilde{\pi}(\rho)$ be two facets, where without loss
of generality we assume $\dim(\gamma_{1})\leq\dim(\gamma_{2})$. For any
$t^{\prime}>t$, let $\Gamma(t^{\prime})$ be the set of realizations
$\rho^{\prime}\in\mathcal{R}(t^{\prime})$ that satisfy the following three
conditions: (1) $\rho\prec\rho^{\prime}$; (2)
$\Pr[\rho^{\prime}\mid\rho,\alpha]>0$ and (3) if $\gamma$ is the largest facet
in $\rho^{\prime}$ that contains a node with name from
$\textsf{names}(V(\gamma_{2}))$, then
$\dim(\gamma)\leq\max\\{\dim(\gamma_{1}),\dim(\gamma_{2})-\dim(\gamma_{1})-1\\}$.
It holds that

$\lim_{t^{\prime}\to\infty}\Pr\left[\Gamma(t^{\prime})\ \middle|\
\alpha,\rho\right]=1.$

###### Proof.

Let $V_{1}=\mathsf{names}(V(\gamma_{1}))$ and
$V_{2}=\mathsf{names}(V(\gamma_{2}))$ be the names of all nodes in the
respective set. Note that if at each round, parties send all their information
to each other, this information can simulate any randomized protocol the
network can run, in the sense that the parties can output the same output of
any other protocol. In particular, it simulates the CreateMatching() procedure
depicted in Algorithm 1, that essentially creates a matching between $V_{1}$
and $V_{2}$. The matching is performed as follows: each party in $V_{1}$
randomly picks a node in $V_{2}$, and sends a message to that node, asking to
be matched with it. If a node in $V_{2}$ received only a single matching-
request message, it accepts it. If it received more than a single request, it
accepts just one request and rejects the others. This process continues with
the remaining unmatched nodes until all the nodes in $V_{1}$ are matched
(assuming $|V_{1}|\leq|V_{2}|$).

Algorithm 1 The CreateMatching Procedure

1:Input: $n$ identical parties, connected as a clique, where $n_{1}$ parties
connected to $\mathbf{R}_{i}$ and $n_{2}$ parties connected to
$\mathbf{R}_{j}$ with $j\neq i$, and $\gcd(n_{1},n_{2})=1$.

2:

3:Initially: $V_{1}$ is the set of all nodes connected to $\mathbf{R}_{i}$ and
$V_{2}$ is the set of all parties connected to $\mathbf{R}_{j}$. The procedure
assumes that this separation is already known to all the participating
parties. Ignore any other parties in the network, if they exist.

4:

5:procedure CreateMatching($V_{1},V_{2}$) $\triangleright$ Assuming (without
loss of generality) $|V_{1}|\leq|V_{2}|$

6: All nodes in $V_{1},V_{2}$ set themselves as active.

7: repeat

8: Each active node in $V_{1}$ randomly picks an active neighbour from $V_{2}$
and sends a messages to that selected neighbour.

9: Each node in $V_{2}$ that have received at least one message, selects the
minimal port from which a message has arrived, and sends an ACK message to
that origin node (in $V_{1}$).

10: Nodes from $V_{1}$ that received an ACK message in the previous step set
themselves to done and broadcasts this event to all their neighbours. Nodes in
$V_{2}$ that _sent_ an ACK message in the previous step, set themselves to
done and broadcast this event to all their neighbours.

11: until all $V_{1}$ nodes are done

12:end procedure

######  Lemma 4.8.

Let $n$ identical nodes be connected as a clique where $n_{1}$ ($n_{2}$) nodes
are connected to the randomness source $\mathbf{R}_{i}$ ($\mathbf{R}_{j}$,
$j\neq i$). At the end of CreateMatching(), there exists a matching $M$
between all the $n_{1}$ parties connected to $\mathbf{R}_{i}$ and $n_{1}$
parties connected to $\mathbf{R}_{j}$, and every party outputs whether it is
matched or not.

###### Proof.

The proof is rather straightforward. Call $V_{1}$ ($V_{2}$) the set of parties
connected to $\mathbf{R}_{i}$ ($\mathbf{R}_{j}$). Consider the state after the
first time the procedure reaches Line 8. At this point, every node in $V_{1}$
has selected a single node in $V_{2}$, which we consider as throwing $|V_{1}|$
balls into $|V_{2}|$ bins. In Line 9 each non-empty bin selects exactly a
single ball and “ignores” the other balls in it. Since each ball is uniquely
identified with a node in $V_{1}$, this creates a matching between all the
non-empty bins (nodes) in $V_{2}$ to some nodes in $V_{1}$. Nodes that belong
to the matching now become done, and the matching continues recursively with
the remaining nodes. Since in every iteration there must be at least one non-
empty bin, every iteration increases the size of the matching by at least one.
Eventually, all the parties in $V_{1}$ will be matched (since
$|V_{1}|\leq|V_{2}|$ by our assumption). At this point, all the parties that
are done participate in the matching and all the remaining active parties are
unmatched. Note that all the parties learn when CreateMatching() has
terminated (e.g., by counting the number of done parties in $V_{1}$ when
reaching Line 11). ∎

After the execution of CreateMatching(), the nodes whose names belong to
$V_{2}$ has split into two subsets, $V_{2}=V_{m}\cup V_{um}$ of “matched” and
“un-matched” nodes, of sizes $|V_{m}|=n_{1}$ and $|V_{um}|=n_{2}-n_{1}$,
respectively. Let $t^{\prime}$ be a time after this split happens, and let
$\rho^{\prime}$ be the realization that corresponds this execution, so
$\rho\prec\rho^{\prime}$. Note that the knowledge of nodes in these two
subsets must be different444I.e., their state
$\in\\{\mathsf{matched},\mathsf{unmatched}\\}$ is function of their knowledge,
hence their knowledge must be different in order to obtain different state..
By the definition of the projection $\tilde{\pi}$, no facet in
$\tilde{\pi}(\rho^{\prime})$ can contain nodes from both $V_{m}$ and $V_{um}$,
as they are inconsistent. Hence, the maximal dimension of any facets of
$\tilde{\pi}(\rho^{\prime})$ that contain some nodes with name from $V_{2}$ is
at most $\max\\{n_{1}-1,n_{2}-n_{1}-1\\}$. Note that CreateMatching() requires
that the participating parties know their partition into $V_{1},V_{2}$. This
holds in our case since $\gamma_{1},\gamma_{2}$ are two different facets and
parties that belong to different facets have different knowledge (and in a
single rounds they can be aware of this). ∎

With the above lemma in hand, we can prove the ‘if’ direction of Theorem 4.2.
The intuition is that any realization $\rho$ with positive probability whose
projection $\tilde{\pi}(\rho)$ has a facet of dimension $d\geq 1$ is
eventually succeeded by $\rho^{\prime}$ whose projection
$\tilde{\pi}(\rho^{\prime})$ has facets with maximal dimension strictly less
than $d$. At the beginning of the computation, each set of parties that are
connected to the same randomness source, are consistent in their
knowledge555To be more precise, the knowledge already might be different due
to differences in parties’ port numbers. This can only help us in reaching a
leader. In the discussion we ignore this option and assume that knowledge
differences only come from the randomness and its affect on being matched or
unmatched., and form a facet in the projection of the relevant realization.
The fact that the GCD of the sizes of these subsets is 1 implies that we can
reduce the dimension of the (largest) facet again and again until we reach
facets of dimension 0.

To illustrate the above in an algorithmic manner, if we start with two sets of
sizes $n_{1}<n_{2}$, we can perform a matching between the sets, and turn off
all the nodes that belong to $V_{m}$ in the matching. This leaves us with two
new sets of parties, $V_{1}$ and $V_{um}$ of sizes $a=n_{1},b=n_{2}-n_{1}$,
respectively, where parties that belong to the same set connect to the same
randomness source. Repeating this process again and again yields a subset of
size $\gcd(n_{1},n_{2})$. The fact that $\gcd(n_{1},n_{2},\ldots,n_{k})=1$ and
that $\gcd()$ is an associative function, $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$,
means we can repeat the above process on different subsets of parties (in a
similar way to the Euclidean algorithm) until the dimension of the maximal
facet becomes $0$.

###### Proof of Theorem 4.2, ‘if’ direction.

We just need to show that for any $\alpha\in\mathcal{A}$ with
$\gcd(n_{1},n_{2},\ldots,n_{k})=1$ there exists a realization
$\rho\in\mathcal{S}$ with positive probability given $\alpha$. Then, by
Kolmogorov’s zero–one Eq. (7) holds. We will assume, without loss of
generality, that at the onset of the analysis shown here,
$\tilde{\pi}(\mathcal{R}(t))$ contains facets of dimensions
$n_{1}-1,n_{2}-1,\ldots,n_{k}-1$. This can easily be achieved by letting the
parties exchange their randomness until $k$ differences appear (if $k$ is
known), or until the parties’ randomness distinguish $k^{\prime}$ subsets
whose sizes’ GCD is 1 (if $k$ is unknown, restarting the protocol whenever
future randomness exhibits new differences among parties that previously
belonged to the same set). This step eventually succeeds with probability 1.
We set time $0$ to be after this step has completed, and below consider only
$t>0$. Let $\alpha\in\mathcal{A}$ be a randomness-configuration with
$k=k(\alpha)$ in which $\gcd(n_{1},n_{2},\ldots,n_{k})=1$. Let

$\mathcal{S}^{*}(t)=\\{\rho\in\mathcal{R}(t)\mid\dim(\tilde{\pi}(\rho))=0\\}$

be the set of realizations whose consistency-projection has dimension 0, that
is, it is composed of $n$ isolated vertices. Clearly any realization in
$\mathcal{S}^{*}$ solves leader election,
$\mathcal{S}^{*}\subseteq\mathcal{S}(t)$, so finding a realization in
$\mathcal{S}^{*}$ with positive probability given $\alpha$ suffices to
complete the proof. Assume a realization $\rho\notin\mathcal{S}^{*}(t)$ with
positive probability, $\Pr[\rho\mid\alpha]>0$. Let $d_{1},d_{2},\ldots$ be the
dimensions of $\tilde{\pi}(\rho)$’s facets. Since
$\rho\notin\mathcal{S}^{*}(t)$ we know that $d=\max(d_{1},d_{2},\ldots)>0$. We
argue that $\gcd(d_{1}+1,d_{2}+1,\ldots)=1$. This will follow from the
following lemma

######  Lemma 4.9.

For any $\alpha\in\mathcal{A}$, $t^{\prime}>t$ and realizations
$\sigma\in\mathcal{R}(t),\sigma^{\prime}\in\mathcal{R}(t^{\prime})$, such that
$\sigma\prec\sigma^{\prime}$, the (unique) name-preserving map
$\delta:\tilde{\pi}(\sigma^{\prime})\to\tilde{\pi}(\sigma)$ is a simplicial
map.

###### Proof.

Let $\tau^{\prime}\in\tilde{\pi}(\sigma^{\prime})$ be a facet. By the
properties of $\tilde{\pi}$ we have that for any two nodes
$(i,x_{i}),(j,x_{j})\in V(\tau^{\prime})$ we have
$i\overset{t^{\prime}}{\sim}j$, with respect to the realization
$\sigma^{\prime}$. Note that $(i,x_{i}(1,\ldots,t)),(j,x_{j}(1,\ldots,t))\in
V(\sigma)$ since $\sigma\prec\sigma^{\prime}$. It thus also holds that
$i\overset{t}{\sim}j$ with respect to the realization $\sigma$ since knowledge
is cumulative (i.e., if the knowledge in time $t$ makes them inconsistent,
this holds also for any time $t^{\prime}>t$). Thus, $\delta(\tau^{\prime})$ is
a simplex in $\tilde{\pi}(\sigma)$. ∎

Assume, towards contradiction, that $\gcd(d_{1}+1,d_{2}+1,\ldots)=g>0$, and
let $\sigma_{1},\sigma_{2},\ldots,\sigma_{t}=\rho$ be the sequence of
realizations that correspond to the computation, $\sigma_{i}\prec\sigma_{i+1}$
for any $i<t$. Note that due to the above lemma, facets in
$\tilde{\pi}(\sigma_{t-1})$ have dimension $\in\\{(-1)+\sum D\mid D\in
2^{\\{d_{1}+1,d_{2}+1,\ldots\\}}\\}$ (where a sum of a set is the sum of the
elements in the set), since facets in $\tilde{\pi}(\sigma_{t-1})$ must be
composed of one or more facets of $\tilde{\pi}(\sigma_{t})$. Let
$d^{\prime}_{1},d^{\prime}_{2},\ldots$ be the dimensions of the facets of
$\tilde{\pi}(\sigma_{1})$. The above implies that
$\gcd(d^{\prime}_{1}+1,d^{\prime}_{2}+1,\ldots)=g>0$, which is a
contradiction. Therefore, unless all the facets of $\tilde{\pi}(\rho)$ are of
dimension $0$, there must exist a facet $\gamma_{1}$ with dimension strictly
less than $d$ (otherwise, if all facets have dimension $d$, then
$\gcd(d_{1}+1,d_{2}+1,\ldots)=d+1>1$). Now, we apply Lemma 4.7 on $\rho$,
where $\gamma_{1}$ is as defined above (i.e., the fact with
$\dim(\gamma_{1})<d$), and $\gamma_{2}$ is any facet with maximal dimension
$\dim(\gamma_{2})=d$. The lemma suggests that there exists a time $t^{\prime}$
and a realization $\rho^{\prime}\in\mathcal{R}(t^{\prime})$ that succeeds
$\rho$, $\Pr[\rho^{\prime}\mid\rho,\alpha]>0$, where the maximal facet in
$\tilde{\pi}(\rho^{\prime})$ has dimension strictly less than $d$, that is,
$\dim(\tilde{\pi}(\rho^{\prime}))<d$.666Note that multiple applications of
Lemma 4.7 might be needed, e.g., when multiple facets in $\tilde{\pi}(\rho)$
are of dimension $d$. Note that,

$\displaystyle\Pr[\rho^{\prime}\mid\alpha]\geq\Pr[\rho^{\prime}\mid\alpha,\rho]\Pr[\rho\mid\alpha]>0.$

Hence, $\rho^{\prime}$ is a realization with positive probability, where
facets in $\tilde{\pi}(\rho^{\prime})$ have dimension strictly less than the
ones in $\tilde{\pi}(\rho)$ we began with. We can now apply the same reasoning
on $\rho^{\prime}$ and keep reducing the dimension of the projected complex,
until we reach a realization $\rho^{*}$ with $\Pr[\rho^{*}\mid\alpha]>0$, for
which all facets of $\tilde{\pi}(\rho^{*})$ are of dimension $0$. ∎

##  5 Conclusion

This paper focuses on input-free symmetry-breaking tasks, and presents a
topological framework for studying the solvability of such tasks by
_randomized_ algorithms. The applicability of this framework was demonstrated
by studying the solvability of leader election in environments where
correlations may exist between the randomness sources assigned to the
processing nodes. Thus, the paper is expected to help move the study of
randomized algorithms under the umbrella of algebraic topology.

Our analysis resulted in a complete characterization of the solvability of
leader election by randomized algorithms. In Appendix  The Topology of
Randomized Symmetry-Breaking Distributed Computing we show that the same
conditions required for solving leader election also suffice for solving any
_name-independent_ task (but they are not necessary). Extending this work to
_any_ task $(\mathcal{I},\mathcal{O},\Delta)$ is an appealing research
direction. A first step may consist of extending this paper’s framework to
input-free tasks for which the output complex $\mathcal{O}$ is not symmetric.
An intriguing example is electing a leader and a deputy leader (where the
latter is to be used as an immediate backup in case the leader fails), under
the constraint that some nodes may only be leaders, some nodes may only be
deputy leaders, some nodes may be either of the two, and some nodes may be
neither. Another compelling direction is extending the communication model to
networks with arbitrary structure.

## Acknowledgements

The authors would like to thank Ami Paz for fruitful discussions and
insightful explanations on topology in distributed computations. P. Fraigniaud
is supported in part by ANR projects DESCARTES and FREDDA. R. Gelles is
supported in part by ISF grant 1078/17.

## References

  * [AAG+89] K. Abrahamson, A. Adler, R. Gelbart, L. Higham, and D. Kirkpatrick.  The bit complexity of randomized leader election on a ring.  _SIAM Journal on Computing_ , 18(1):12–29, 1989.
  * [AM94] Y. Afek and Y. Matias.  Elections in anonymous networks.  _Information and Computation_ , 113(2):312 – 330, 1994.
  * [Ang80] D. Angluin.  Local and global properties in networks of processors (extended abstract).  _Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing_ , STOC ’80, p. 82–93, Association for Computing Machinery, New York, NY, USA, 1980.
  * [ASW88] H. Attiya, M. Snir, and M. K. Warmuth.  Computing on an anonymous ring.  _J. ACM_ , 35(4):845–875, 1988.
  * [BSV+96] P. Boldi, S. Shammah, S. Vigna, B. Codenotti, P. Gemmell, and J. Simon.  Symmetry breaking in anonymous networks: Characterizations.  _Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996_ , pp. 16–26, IEEE Computer Society, 1996.
  * [BG93] E. Borowsky and E. Gafni.  Generalized FLP impossibility result for t-resilient asynchronous computations.  _Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing_ , STOC ’93, p. 91–100, Association for Computing Machinery, New York, NY, USA, 1993.
  * [CGM12] J. Chalopin, E. Godard, and Y. Métivier.  Election in partially anonymous networks with arbitrary knowledge in message passing systems.  _Distributed Computing_ , 25(4):297–311, 2012.
  * [CGPS97] B. Codenotti, P. Gemmell, P. Pudlák, and J. Simon.  On the amount of randomness needed in distributed computations.  _OPODIS ’97_ , 1997.
  * [DMR08] Y. Dinitz, S. Moran, and S. Rajsbaum.  Bit complexity of breaking and achieving symmetry in chains and rings.  _J. ACM_ , 55(1), 2008.
  * [EPSW14] Y. Emek, C. Pfister, J. Seidel, and R. Wattenhofer.  Anonymous networks: Randomization = 2-hop coloring.  _Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing_ , PODC ’14, p. 96–105, Association for Computing Machinery, New York, NY, USA, 2014.
  * [Euc] Euclid.  _(Ελεμεντς)__._ _300(;) Β῝. Βοοϰ 7._
  * [FMHV03] _Ρ. Φαγιν, Ψ. Μοςες, Θ. Ψ. Ηαλπερν, ανδ Μ. Ψ. ῞αρδι._ _Ρεαςονινγ αβουτ ϰνοωλεδγε_ _._ _ΜΙΤ πρεςς, 2003._
  * [FT14] _Ι. Φλορεςςυ ανδ ῝. Τυδορ, εδς._ _Ηανδβοοϰ οφ Προβαβιλιτψ_ _, ςηαπ. Τωο: Προβαβιλιτψ Μεαςυρε, ππ. 15–62._ _Θοην Ωιλεψ & Σονς, Λτδ, 2014. _
  * [GHS83] _Ρ. Γ. Γαλλαγερ, Π. Α. Ηυμβλετ, ανδ Π. Μ. Σπιρα._ Α διςτριβυτεδ αλγοριτημ φορ μινιμυμ-ωειγητ ςπαννινγ τρεες _._ _Α῝Μ Τρανς. Προγραμ. Λανγ. Σψςτ.__, 5(1):66–77, 1983._
  * [HKR14] _Μ. Ηερλιηψ, Δ. Κοζλο, ανδ Σ. Ραϑςβαυμ._ _Διςτριβυτεδ ῝ομπυτινγ Τηρουγη ῝ομβινατοριαλ Τοπολογψ_ _._ _Μοργαν Καυφμανν, Βοςτον, 2014._
  * [HS93] _Μ. Ηερλιηψ ανδ Ν. Σηαιτ._ Τηε αςψνςηρονους ςομπυταβιλιτψ τηεορεμ φορ τ-ρεςιλιεντ ταςϰς _._ _Προςεεδινγς οφ τηε Τωεντψ-Φιφτη Αννυαλ Α῝Μ Σψμποςιυμ ον Τηεορψ οφ ῝ομπυτινγ_ _, ΣΤΟ῝ ´93, π. 111–120, Αςςοςιατιον φορ ῝ομπυτινγ Μαςηινερψ, Νεω Ψορϰ, ΝΨ, ϒΣΑ, 1993._
  * [IR90] _Α. Ιται ανδ Μ. Ροδεη._ Σψμμετρψ βρεαϰινγ ιν διςτριβυτεδ νετωορϰς _._ _Ινφορματιον ανδ ῝ομπυτατιον_ _, 88(1):60 – 87, 1990._
  * [JS85] _Ρ. Ε. Θοηνςον ανδ Φ. Β. Σςηνειδερ._ Σψμμετρψ ανδ ςιμιλαριτψ ιν διςτριβυτεδ ςψςτεμς _._ _Προςεεδινγς οφ τηε Φουρτη Αννυαλ Α῝Μ Σψμποςιυμ ον Πρινςιπλες οφ Διςτριβυτεδ ῝ομπυτινγ_ _, ΠΟΔ῝ ´85, π. 13–22, Αςςοςιατιον φορ ῝ομπυτινγ Μαςηινερψ, Νεω Ψορϰ, ΝΨ, ϒΣΑ, 1985._
  * [KV19] _Θ. Κιλγαλλιν ανδ Ρ. ῞αςϰο._ _Φαςτορινγ ΡΣΑ ϰεψς ιν τηε ΙοΤ ερα._ _2019 Φιρςτ ΙΕΕΕ Ιντερνατιοναλ ῝ονφερενςε ον Τρυςτ, Πριαςψ ανδ Σεςυριτψ ιν Ιντελλιγεντ Σψςτεμς ανδ Αππλιςατιονς (ΤΠΣ-ΙΣΑ)__, ππ. 184–189, 2019._
  * [KPP+15] _Σ. Κυττεν, Γ. Πανδυρανγαν, Δ. Πελεγ, Π. Ροβινςον, ανδ Α. Τρεηαν._ Ον τηε ςομπλεξιτψ οφ υνιερςαλ λεαδερ ελεςτιον _._ _Θ. Α῝Μ_ _, 62(1), 2015._
  * [LL77] _Γ. Λε Λανν._ _Διςτριβυτεδ ςψςτεμς-τοωαρδς α φορμαλ αππροαςη._ _Προςεεδινγς οφ τηε 7τη ΙΦΙΠ ςονγρεςς_ _, ππ. 155–160, Ιντερνατιοναλ Φεδερατιον φορ Ινφορματιον Προςεςςινγ, 1977._
  * [Mat15] _Θ. Ματηερλψ._ _Δυπλιςατε ΣΣΗ Κεψς Εερψωηερε_ _, 2015._ _[ονλινε] ηττπς://βλογ.ςηοδαν.ιο/δυπλιςατε-ςςη-ϰεψς-εερψωηερε/._
  * [MTH14] _Η. Μενδες, ῝. Ταςςον, ανδ Μ. Ηερλιηψ._ Διςτριβυτεδ ςομπυταβιλιτψ ιν βψζαντινε αςψνςηρονους ςψςτεμς _._ _Προςεεδινγς οφ τηε Φορτψ-Σιξτη Αννυαλ Α῝Μ Σψμποςιυμ ον Τηεορψ οφ ῝ομπυτινγ_ _, ΣΤΟ῝ ´14, π. 704–713, Αςςοςιατιον φορ ῝ομπυτινγ Μαςηινερψ, Νεω Ψορϰ, ΝΨ, ϒΣΑ, 2014._
  * [Pel90] _Δ. Πελεγ._ Τιμε-οπτιμαλ λεαδερ ελεςτιον ιν γενεραλ νετωορϰς _._ _Θουρναλ οφ Παραλλελ ανδ Διςτριβυτεδ ῝ομπυτινγ_ _, 8(1):96 – 99, 1990._
  * [SZ93] _Μ. Σαϰς ανδ Φ. Ζαηαρογλου._ Ωαιτ-φρεε ϰ-ςετ αγρεεμεντ ις ιμποςςιβλε: Τηε τοπολογψ οφ πυβλις ϰνοωλεδγε _._ _Προςεεδινγς οφ τηε Τωεντψ-Φιφτη Αννυαλ Α῝Μ Σψμποςιυμ ον Τηεορψ οφ ῝ομπυτινγ_ _, ΣΤΟ῝ ´93, π. 101–110, Αςςοςιατιον φορ ῝ομπυτινγ Μαςηινερψ, Νεω Ψορϰ, ΝΨ, ϒΣΑ, 1993._
  * [SS94] _Β. Σςηιεβερ ανδ Μ. Σνιρ._ ῝αλλινγ ναμες ον ναμελεςς νετωορϰς _._ _Ινφορματιον ανδ ῝ομπυτατιον_ _, 113(1):80–101, 1994._
  * [Tur36] _Α. Μ. Τυρινγ._ Ον ςομπυταβλε νυμβερς, ωιτη αν αππλιςατιον το τηε εντςςηειδυνγςπροβλεμ _._ _Θ. οφ Ματη_ _, 58(345-363):5, 1936._
  * [YK96] _Μ. Ψαμαςηιτα ανδ Τ. Καμεδα._ ῝ομπυτινγ ον ανονψμους νετωορϰς. Ι. ῝ηαραςτεριζινγ τηε ςολαβλε ςαςες _._ _ΙΕΕΕ Τρανςαςτιονς ον Παραλλελ ανδ Διςτριβυτεδ Σψςτεμς_ _, 7(1):69–89, 1996._

##  Αλγεβραις Τοπολογψ: Βαςις Δεφινιτιονς

_Ωε γιε ηερε α βριεφ ςυρεψ οφ τηε τοπολογιςαλ τερμς υςεδ ιν τηις παπερ, ανδ
ρεφερ τηε ρεαδερ το_ _[_HKR14] φορ α μορε ςομπλετε τρεατμεντ οφ τηε ςυβϑεςτ.

_Αν_ _αβςτραςτ ςιμπλιςιαλ ςομπλεξ_ $\mathcal{K}$ ις α νονεμπτψ ςετ οφ ςετς
(ςιμπλιςες) $\mathcal{K}=\\{\sigma_{i}\\}_{i}$ ανδ ιτ ηολδς τηατ ιφ $\sigma$
ις α ςιμπλεξ τηεν ανψ νον εμπτψ ςυβςετ $\rho\subseteq\sigma$ ις αλςο α
ςιμπλεξ, $\rho\in\mathcal{K}$. Τηε ελεμεντς οφ α ςιμπλεξ $\sigma$ αρε ςαλλεδ
_νοδες_ ορ _ερτιςες_ , ανδ αρε δενοτεδ βψ $V(\sigma)$. Τηε ςετ οφ αλλ νοδες,
$V(\mathcal{K})=\bigcup_{\sigma\in\mathcal{K}}V(\sigma)$ ις ςαλλεδ τηε _νοδε-
ςετ_ οφ τηε ςομπλεξ. Τηε διμενςιον οφ α ςιμπλεξ ις
$\dim(\sigma)=|V(\sigma)|-1$. Ιν παρτιςυλαρ, α ςινγλε νοδε $\sigma=\\{v\\}$
ηας διμενςιον $0$. Α _φαςετ_ οφ $\mathcal{K}$ ις α ςιμπλεξ τηατ ις νοτ
ςονταινεδ ιν ανψ οτηερ ςιμπλεξ οφ $\mathcal{K}$. Νοτε τηατ τηε ςετ οφ φαςετς
φυλλψ δεφινες τηε ςομπλεξ. Α φαςετ οφ διμενςιον $0$ ις ςαλλεδ αν _ιςολατεδ_
νοδε. Τηε διμενςιον οφ α ςομπλεξ ις τηε μαξιμαλ διμενςιον οφ ιτς φαςετς. Α
ςομπλεξ ωηοςε αλλ φαςετς ηαε τηε ςαμε διμενςιον ις ςαλλεδ _πυρε_.

_Φορ τωο ςομπλεξες,_ $\mathcal{K}$ ανδ $\mathcal{L}$, ωε ςαψ τηατ
$\mathcal{K}$ ις α ςυβςομπλεξ οφ $\mathcal{L}$ ιφ
$\mathcal{K}\subseteq\mathcal{L}$. Φορ α ςετ $X\subseteq V(\mathcal{K})$, τηε
_ινδυςεδ ςομπλεξ οφ $\mathcal{K}$ ον $X$_ ις τηε ςομπλεξ
$\\{\sigma\in\mathcal{K}\mid V(\sigma)\subseteq X\\}$. Α ερτεξ μαπ φρομ
$\mathcal{K}$ το $\mathcal{L}$ ις ανψ φυνςτιον $f:V(\mathcal{K})\to
V(\mathcal{L})$. Α _ςιμπλιςιαλ μαπ_ $\delta:\mathcal{K}\to\mathcal{L}$ ις α
ερτεξ μαπ ςυςη τηατ φορ ανψ $\sigma\in\mathcal{K}$ ιτ ηολδς τηατ
$\delta(\sigma)=\\{\delta(v)\mid v\in\sigma\\}\in\mathcal{L}$, τηατ ις, ιτ
μαπς ςιμπλιςες ιν $\mathcal{K}$ το ςιμπλιςες ιν $\mathcal{L}$ (ι.ε., ιτ
πρεςερες ςιμπλιςες). ῝ομπλεξες $\mathcal{K}$ ανδ $\mathcal{L}$ αρε ςαιδ το βε
ιςομορπηις ιφ τηερε εξιςτ ςιμπλιςιαλ μαπς $f:\mathcal{K}\to\mathcal{L}$ ανδ
$f^{-1}:\mathcal{L}\to\mathcal{K}$, ςυςη τηατ φορ ανψ $\sigma\in\mathcal{K}$,
$\sigma=f^{-1}(f(\sigma))$, ανδ φορ ανψ $\rho\in\mathcal{L}$,
$\rho=f(f^{-1}(\rho))$. Α _ςηροματις_ ςομπλεξ $\mathcal{K}$ ις α ςομπλεξ
αυγμεντεδ ωιτη α ναμινγ φυνςτιον $\mathsf{name}:V(\mathcal{K})\to C$ ωηερε $C$
ις ςαλλεδ τηε ςετ οφ ναμες (ςολορς). Α ερτεξ μαπ $f:V(\mathcal{K})\to
V(\mathcal{L})$ _πρεςερες ναμες_ ιφ $\mathcal{K}$ ανδ $\mathcal{L}$ αρε
ςηροματις, ανδ φορ ανψ $v\in V(\mathcal{K})$ ωε ηαε
$\mathsf{name}(v)=\mathsf{name}(f(v))$. Ιν τηις παπερ αλλ ςομπλεξες αρε
ςηροματις ανδ αλλ μαπς αρε ναμε-πρεςερινγ.

##  Τεςηνιςαλ Λεμμας

_Τηε φολλοωινγ λεμμα ςηοως τηατ, φορ α γιεν τιμε ανδ ρανδομνεςς-ςονφιγυρατιον,
αλλ τηε γλοβαλ ςτατες ωιτη ποςιτιε προβαβιλιτψ αρε εχυιπροβαβλε._

######  _Λεμμα .1_.

Γιεν $t>0$ ανδ $\alpha\in\mathcal{A}$ ωηερε εξαςτλψ $k=k(\mathcal{A})$
διφφερεντ ρανδομνεςς ςουρςες αρε ςοννεςτεδ το τηε παρτιες ιν $\alpha$, δεφινε
τηε ςετ οφ $\alpha$-ινςονςιςτεντ ρανδομνεςς,

$\textsf{B}_{\alpha}=\Big{\\{}(x_{1},\ldots,x_{n})\in(\\{0,1\\}^{t})^{n}\
\Big{|}\ \exists i,j\in[n],c\in[k]\text{ s.t. }x_{i}\neq x_{j}\text{ but
}(i,c),(j,c)\in\alpha\Big{\\}}.$

Φορ ανψ φαςετ $\sigma\in\mathcal{R}(t)$ ωιτη νοδες $V(\sigma)=\\{(i,x_{i})\mid
i\in[n]\\}$,

$\Pr[\sigma\mid\alpha]=\begin{cases}0&(x_{1},\dotsc,x_{n})\in\textsf{B}_{\alpha}\\\
2^{-tk}&(x_{1},\dotsc,x_{n})\notin\textsf{B}_{\alpha}\end{cases}.$

_Τηε προοφ φολλοως διρεςτλψ φρομ τηε δεφινιτιον ςινςε_
$\Pr[\sigma\mid\alpha]=\Pr[(R_{1},\ldots,R_{n})(1,\ldots,t)=(x_{1},\ldots,x_{n})\mid\alpha]$.
Ρεςαλλινγ τηατ τηε μαππινγ $h$ δεφινεδ ιν Σεςτιον 3.3 ινδυςες α ναμε-πρεςερινγ
ιςομορπηιςμ ον τηε φαςετς οφ $\mathcal{P}(t)$ ανδ $\mathcal{R}(t)$, ωε
ςονςλυδε:

######  _῝ορολλαρψ .2_.

Γιεν $t>0$ ανδ $\alpha\in\mathcal{A}$ ωιτη εξαςτλψ $k=k(\mathcal{A})$
ρανδομνεςς ςουρςες ςοννεςτεδ το τηε παρτιες, φορ ανψ $\sigma\in\mathcal{P}(t)$
ωε ηαε

$\Pr[\sigma\mid\alpha]=\Pr[h(\sigma)\mid\alpha]\in\\{0,2^{-tk}\\}.$

##  Ναμε-ινδεπενδεντ Ινπυτ-Ουτπυτ Ταςϰς Ρεδυςε το Λεαδερ Ελεςτιον

_Ας α ςονςεχυενςε οφ τηε αβοε, ανψ_ _ναμε-ινδεπενδεντ_ ταςϰ ςαν βε ςολεδ ιν
ουρ μοδελ ας λονγ ας λεαδερ ελεςτιον ις ποςςιβλε. Α ταςϰ
$(\mathcal{I},\mathcal{O},\Delta)$ ις ναμε-ινδεπενδεντ ιφ $\Delta$ μαπς ινπυτς
το ουτπυτς ιν α ναμε-οβλιιους ωαψ. Ναμελψ, φορ ανψ ποςςιβλε ινπυτ φορ τηε
ςψςτεμ, $\sigma\in\mathcal{I}$, παρτιες ωιτη τηε ςαμε ινπυτ-αλυε ςομπυτε τηε
ςαμε ουτπυτ-αλυε, ι.ε.,
$(i,x),(j,x)\in\sigma\Rightarrow(i,o),(j,o)\in\Delta(\sigma)$.

_βψ ρεδυςινγ τηε ταςϰ το ςηοοςινγ α λεαδερ, ωηο ιν τυρν ςομπυτες τηε ουτπυτ ιν
α ςεντραλιζεδ ωαψ._

######  _Τηεορεμ .3_.

Ιφ Λεαδερ ελεςτιον ις ςολαβλε βψ αν ανονψμους νετωορϰ ιν τηε βλαςϰβοαρδ ορ
μεςςαγε-παςςινγ μοδελ, τηεν ανψ διςτριβυτεδ ναμε-ινδεπενδεντ ινπυτ-ουτπυτ ταςϰ
ςαν βε ςολεδ οερ τηε ςαμε μοδελ.

###### Προοφ.

Γιεν α ταςϰ $(\mathcal{I},\mathcal{O},\Delta)$, τηε παρτιες περφορμ λεαδερ
ελεςτιον. Εερψ παρτψ τηεν ςενδς τηε λεαδερ ιτς ινπυτς, ειτηερ διρεςτλψ ορ ια
τηε βλαςϰβοαρδ. Τηε λεαδερ ςολλεςτς αλλ τηε ινπυτς (ανδ ρεςορδς τηε ρεςπεςτιε
πορτ-νυμβερ φορ εαςη ιν τηε μεςςαγε παςςινγ μοδελ). Τηεν, τηε λεαδερ ςολες τηε
ταςϰ $(\mathcal{I},\mathcal{O},\Delta)$ βψ ηιμςελφ ανδ διςτριβυτες τηε ουτπυτς
το ιτς νειγηβουρς, ειτηερ βψ πυβλιςηινγ τηε ρεςπεςτιε ουτπυτ οφ εαςη ινπυτ ον
τηε βλαςϰβοαρδ ορ βψ ςενδινγ τηε αππροπριατε ουτπυτ το τηε ςορρεςπονδινγ πορτ.
∎

_Ιτ ις οβιους τηατ τηε οτηερ διρεςτιον ις ιναλιδ, ας τηερε αρε ταςϰς τηατ ςαν
βε δετερμινιςτιςαλλψ ςολεδ ιν βοτη τηεςε μοδελς, ρεγαρδλεςς οφ τηε ςολαβιλιτψ
οφ λεαδερ ελεςτιον._