# Network Size Estimation in Small-World Networks under Byzantine Faults

Soumyottam Chatterjee Department of Computer Science, University of Houston,
Houston, TX 77204, USA. Email<EMAIL_ADDRESS>Gopal Pandurangan
Department of Computer Science, University of Houston, Houston, TX 77204, USA.
Email<EMAIL_ADDRESS>Research supported, in part, by NSF grant
CCF-1527867. Peter Robinson Department of Computing & Software, McMaster
University, Hamilton, Ontario L8S 4L7, Canada. Email:
<EMAIL_ADDRESS>
###### Abstract

We study the fundamental problem of counting the number of nodes in a sparse
network (of unknown size) under the presence of a large number of Byzantine
nodes. We assume the full information model where the Byzantine nodes have
complete knowledge about the entire state of the network at every round
(including random choices made by all the nodes), have unbounded computational
power, and can deviate arbitrarily from the protocol. Essentially all known
algorithms for fundamental Byzantine problems (e.g., agreement, leader
election, sampling) studied in the literature assume the knowledge (or at
least an estimate) of the size of the network. In particular, all known
algorithms for fundamental Byzantine problems that can tolerate a large number
of Byzantine nodes in bounded-degree networks assume a sparse expander network
with nodes having knowledge of the network size. It is non-trivial to design
algorithms for Byzantine problems that work without knowledge of the network
size, especially in bounded-degree (expander) networks where the local views
of all nodes are (essentially) the same and limited, and Byzantine nodes can
quite easily fake the presence/absence of non-existing nodes. To design truly
local algorithms that do not rely on any global knowledge (including network
size), estimating the size of the network under Byzantine nodes is an
important first step.

Our main contribution is a randomized distributed algorithm that estimates the
size of a network under the presence of a large number of Byzantine nodes. In
particular, our algorithm estimates the size of a sparse, “small-world”,
expander network with up to $O(n^{1-\delta})$ Byzantine nodes, where $n$ is
the (unknown) network size and $\delta$ can be be any arbitrarily small (but
fixed) positive constant. Our algorithm outputs a (fixed) constant factor
estimate of $\log(n)$ with high probability; the correct estimate of the
network size will be known to a large fraction ($(1-\epsilon)$-fraction, for
any fixed positive constant $\epsilon$) of the honest nodes. Our algorithm is
fully distributed, lightweight, and simple to implement, runs in
$O(\log^{3}{n})$ rounds, and requires nodes to send and receive messages of
only small-sized messages per round; any node’s local computation cost per
round is also small.

##  1 Introduction

Motivated by the need for robust and secure distributed computation in large-
scale (sparse) networks such as peer-to-peer (P2P) and overlay networks, we
study the fundamental Byzantine counting problem in networks, where the goal
is to count (or estimate) the number of nodes in a network that can contain a
large number of Byzantine nodes that can exhibit malicious behaviour.

The Byzantine counting problem is challenging because the goal is to guarantee
that most of the honest (i.e., non-Byzantine) nodes obtain a good estimate of
the network size 111In sparse, bounded-degree networks, an adversary can
always isolate some number of honest nodes; hence “almost-everywhere”
knowledge is the best one can hope for in such networks (cf. [11]). despite
the presence of a large number of Byzantine nodes (which have full information
about all the nodes and can behave arbitrarily or maliciously) in the network.
Byzantine counting is related to, yet different, compared with other
fundamental problems in distributed computing, namely, Byzantine agreement and
Byzantine leader election. Similar to the latter two problems, it involves
solving a global problem under the presence of Byzantine nodes. However, it is
a different problem, since protocols for Byzantine agreement or leader
election do not necessarily yield a protocol for Byzantine counting. In a
sense, the Byzantine counting problem can be considered to be more fundamental
than Byzantine agreement and leader election, since many existing algorithms
for these two problems (discussed below and in Section 1.3) assume knowledge
of the number of nodes in the network $n$; some algorithms require at least a
reasonably good estimate of $n$, typically a constant factor estimate of $\log
n$. Indeed, one of the main motivations for this paper is to design
distributed protocols that can work with little or no global knowledge,
including the network size. In this sense, an efficient protocol for the
Byzantine counting problem can serve as a pre-processing step for protocols
for Byzantine agreement, leader election and other problems that either
require or assume knowledge of an estimate of $n$ [4].

Byzantine agreement and leader election have been at the forefront of
distributed computing research for several decades. The work of Dwork et. al.
[11] and Upfal [34] studied the Byzantine agreement problem in bounded-degree
expander networks under the condition of almost-everywhere agreement, where
almost all (honest) processors need to reach agreement as opposed to _all_
nodes agreeing as required in the standard Byzantine agreement problem. Dwork
et. al. [11] showed how one can achieve almost-everywhere agreement under up
to $\Theta(\frac{n}{\log{n}})$ of Byzantine nodes in a bounded-degree expander
network ($n$ is the network size). Subsequently, Upfal [34] gave an improved
protocol that can tolerate up to a linear number of faults in a bounded degree
expander of sufficiently large spectral gap (in fact, on Ramanujan graphs,
which have the asymptotically largest spectral graph possible [17] — our
protocol in this paper also works on a similar type of expander). These
algorithms required $O(\log n)$ rounds and polynomial (in $n$) number of
messages; however, the local computation required by each processor is
exponential. Both of the above algorithms require knowledge of the global
topology (including the knowledge of $n$), since at the start, nodes need to
have this information hardcoded. The work of King et. al. [24] was the first
to study scalable (polylogarithmic communication and number of rounds, and
polylogarithmic computation per processor) algorithms for Byzantine leader
election and agreement. Similar to Dwork et al.’s and Upfal’s algorithm, the
nodes require hardcoded information on the network topology — which is also an
expander graph — to begin with, including the network size. We note that
expansion property is crucially exploited in all the above works to achieve
Byzantine agreement and leader election. Furthermore, the expander networks
assumed in Dwork et al and Upfal works are bounded-degree (essentially,
regular) graphs, where without prior knowledge it is difficult for nodes to
have a knowledge of the network size.

The works of [6], [2], and [3] studied stable agreement, Byzantine agreement,
and Byzantine leader election (respectively) in dynamic networks (see also
[4]), where in addition to Byzantine nodes there is also adversarial churn.
All these works assume that there is an underlying bounded-degree regular
expander graph and all nodes are assumed to have knowledge of $n$. It was not
clear how to estimate $n$ without additional information under presence of
Byzantine nodes in such (essentially, regular and constant degree expander)
networks. In fact, the works of [4, 3] raised the question of designing
protocols in expander networks that work when the network size is not known
and may even change over time, with the goal of obtaining a protocol that
works when nodes have strictly local knowledge. This requires devising a
distributed protocol that can measure global network parameters such as size,
diameter, average degree, etc. under Byzantine nodes in sparse networks,
especially in sparse expander networks.

###  1.1 Our Contributions

We introduce and study the problem of Byzantine Counting. Our goal is to
design a distributed algorithm that guarantees, despite a large number of
Byzantine nodes, that almost all honest nodes know a good estimate of the
network size in a bounded degree, “small world” network. We are not aware of
any prior work that studies Byzantine counting in the setting addressed here.

Before stating our result, we briefly describe the key ingredients of our
network model (we refer to Section 2.1 for the full details). We assume a
sparse network that has constant bounded degree (essentially regular) and has
high expansion as well as large clustering coefficient. In other words, it is
a “small-world” network. Expander graphs have been used extensively as
candidates to solve the Byzantine agreement and related problems in bounded
degree graphs (e.g., as discussed earlier, see [11, 20, 21, 23, 34]); the
expander property proves crucial in tolerating a large number of Byzantine
nodes. The high expansion of such graphs have been exploited in previous works
as well, most notably by Upfal [34] to solve the Byzantine agreement (with
knowledge of $n$). For the Byzantine counting problem, which seems harder,
however, expansion by itself does not seem to be sufficient; our protocol also
exploits the high clustering coefficient of the network crucially (cf. Section
1.2).

We assume that up to $O(n^{1-\delta})$ nodes can be _Byzantine_ , where
$\delta>0$ can be an arbitrarily small (but fixed) positive constant. We
assume a strong adversarial full information model where the Byzantine nodes
(who have unbounded computational power) are adaptive, in the sense that they
know the entire states of all nodes at the beginning of every round (including
the messages sent by them), including the random choices made by the nodes up
to and including the current round as well as future rounds (in other words,
they are omniscient). However, we note that the Byzantine nodes can
communicate only using the edges of the network, i.e., they can send messages
directly only to their neighbors.

In our network model, where nodes have constant bounded degree, most nodes,
with high probability, see (essentially) the same local topological structure
even for a reasonably large neighborhood radius — cf. Section A, and hence
nodes do not have any a priori local information that can help them estimate
the network size. In this setting, Byzantine nodes can easily fake the
presence/absence of nodes — thus trying to foil the estimate of the honest
nodes.

Our main contribution is a distributed algorithm (cf. Section 3) that
estimates the size of the network, even under the presence of a large number
of Byzantine nodes. In particular, our algorithm estimates the size of a
sparse (constant degree) “small-world” network with up to $O(n^{1-\delta})$
(for any small positive constant $\delta$) Byzantine nodes, where $n$ is the
(unknown) network size. Our algorithm outputs a (fixed) constant factor
estimate of $\log{n}$ with high probability; 222“With high probability (whp)”
refers to a probability $\geq 1-n^{-c}$, for some constant $c>0$. the correct
estimate of the network size will be known to $(1-\epsilon)$-fraction (where
$\epsilon>0$ is a small constant, say 0.1) of the honest nodes. 333We call
$\epsilon$ _the error parameter_ — by changing its value (please refer to Line
LABEL:value-of-alpha-i in the pseudocode in Algorithm 1), we (the algorithm
designer) can control exactly how large a fraction of the honest nodes would
estimate $\log{n}$ correctly (i.e., get a constant-factor approximation of
$\log{n}$). Theorem 1, which is the main result of this paper, tells us that
at most $\epsilon$-fraction of the honest nodes would _fail_ to get a constant
factor approximation of $\log{n}$.

Our algorithm is the first known, decentralized Byzantine counting algorithm
that can tolerate a large amount of Byzantine nodes. It is fully-distributed,
localized (does not require any global topological knowledge), lightweight,
runs in $O(\log^{3}n)$ rounds, and requires nodes to send and receive “small-
sized messages” only. 444A “small-sized message” is one that contains a
constant number of IDs and $O(\log{n})$ additional bits. Any node’s
computation cost per round is also logarithmic.

The given algorithm is a basic ingredient that can be used for the design of
efficient distributed algorithms resilient against Byzantine failures, where
the knowledge of the network size (a global parameter) may not be known a
priori. It can serve as a building block for implementing other non-trivial
distributed computation tasks in Byzantine networks such as agreement and
leader election where the network size (or its estimate) is not known a
priori.

###  1.2 Technical Challenges

The main technical challenge that we have to overcome is designing and
analyzing distributed algorithms under the presence of Byzantine nodes in
networks where (honest) nodes only have local knowledge, i.e., knowledge of
their immediate neighborhood. It is possible to solve the counting problem
exactly in networks without Byzantine nodes by simply building a spanning tree
and converge-casting the nodes’ counts to the root, which in turn can compute
the total number of nodes in the network. A more robust and alternate way that
works also in the case of anonymous networks is the technique of support
estimation [6, 4] which uses exponential distribution (or alternately one can
use a geometric distribution, see e.g., [25]) to estimate accurately the
network size as described below.

Consider the following simple protocol for estimating the network size that
uses the geometric distribution. Each node $u$ flips an unbiased coin until
the outcome is heads; let $X_{u}$ denote the random variable that denotes the
number of times that $u$ needs to flip its coin. Then, nodes exchange their
respective values of $X_{u}$ whereas each node only forwards the highest value
of $X_{u}$ (once) that it has seen so far. We observe that $X_{u}$ is
geometrically distributed and denote its global maximum by $\bar{X}$. For any
$u$, $\Pr(X_{u}\geq 2\log n)=(\frac{1}{2})^{2\log{n}}$, and by taking a union
bound, $\Pr(\bar{X}\geq 2\log{n})\leq\frac{1}{n}$. Furthermore,
$\Pr(\bar{X}<\frac{\log{n}}{2})=(1-(\frac{1}{2})^{\frac{\log{n}}{2}})^{n}\leq
e^{-\sqrt{n}}$. It follows that each node forwards at most $O(\log{n})$
distinct values (w.h.p.). After $O(D)$ rounds (where $D$ is the network
diameter), each node knows the value of $\bar{X}$, and sets that as its
estimate of $\log{n}$. Due to the above bounds on $\bar{X}$ it follows that
(w.h.p.), it is a constant factor estimate of $\log{n}$. The support
estimation algorithm [6, 4] which uses the exponential distribution works in a
similar manner.

The geometric distribution protocol fails when even just one Byzantine node is
present. Byzantine nodes can fake the maximum value or can stop the correct
maximum value from spreading and hence can violate any desired approximation
guarantee. Hence a new protocol is needed when dealing with Byzantine nodes.

Prior localized techniques that have been used successfully for solving other
problems such as Byzantine agreement and leader election such as random walks
and majority agreement (e.g., [2, 3]) do not imply efficient (i.e., fast
algorithms that uses small message sizes) algorithms for Byzantine counting.
For instance, random walk-based techniques crucially exploit a uniform
sampling of tokens (generated by nodes) after $\Theta(\text{mixing time})$
number of steps. However, the main difficulty in this approach is that the
mixing time is unknown (since the network size is unknown) — and hence it is
unclear a priori how many random walk steps the tokens should take. Similar
approaches based on the return time of random walks fail due to long random
walks having a high chance of encountering a Byzantine node. One can also use
Birthday paradox ideas to try to estimate $n$ (e.g., these have been tried in
an non-Byzantine setting [14]); these also fail in the Byzantine case.

We note that one can possibly solve Byzantine counting if one can solve
Byzantine leader election; 555Informally, the idea is as follows. If one can
elect a honest leader, then it can initiate flooding by sending a message to
the entire network; any other node can set an estimate of $\log{n}$ as the
round number when it sees the message for the first time. It can be shown that
in a sparse expander, $n-o(n)$ nodes will have a constant factor estimate of
$\log n$. however, all known algorithms for Byzantine leader election (or
agreement) assume a priori knowledge (or at least a good estimate) of the
network size. Hence we require a new protocol that solves Byzantine counting
from “scratch.” In our random network model, where most nodes, with high
probability, see (essentially) the same local topological structure (and
constant degree) even for a reasonably large neighborhood radius (cf. Section
A), it is difficult for nodes to break symmetry or gain a priori knowledge of
$n$. 666We point out that with constant probability, in our network model, due
to the property of the $d$-regular random graph, an expected constant number
of nodes might have multi-edges — this can potentially be used to break ties;
however, this fails to work with constant probability. In any case, such
symmetry breaking will fail in symmetric regular graphs.

Another approach is to try to estimate the diameter of the network, which,
being $\Theta(\log{n})$ for sparse expanders, can be used to deduce an
approximation of the network size. Assuming that there exists a leader in the
network, one way to do this is for the leader to initiate the flooding of a
message and it can be shown that a large fraction of nodes (say a
$(1-\epsilon)$-fraction, for some small $\epsilon>0$) can estimate the
diameter by recording the time when they see the first token, since we assume
a synchronous network. However, this method fails since it is not clear, how
to break symmetry initially by choosing a leader — this by itself appears to
be a hard problem in the Byzantine setting without knowledge of $n$.

We now give a high-level intuition behind our protocol. The main idea is based
on using the geometric distribution, but there are several technical obstacles
that we need to tackle (cf. Section 3).

The algorithm operates in phases. In phase $i$, each honest node estimates the
number of nodes at distance $i$ (in particular, whether there are any nodes at
all) by observing the maximum (or near-maximum) value, generated according to
the geometric distribution, at distance $i$; this value can be propagated by
flooding for exactly $i$ steps. We only allow certain values to propagate in
phase $i$; this avoids congestion and hence our algorithm works using only
small message sizes. As $i$ increases, i.e., when it becomes $a\log n$, for
some small constant $0<a<1$, this provides a constant factor estimate of
$\log{n}$. Up to a distance of $i=a\log{n}$, most nodes (i.e., $n-o(n)$ nodes)
do not see any values from Byzantine nodes, since most nodes are a distance at
least $a\log n$ from any Byzantine node — this is due to the property of the
expander graph. However, as $i$ increases, the Byzantine nodes can introduce
fake values and hence can fool most of the nodes into believing that the
network is much larger than it actually is. To overcome this, the protocol
exploits the small-world property of the network, i.e., nodes have high
clustering coefficients — which implies that a node’s neighbors are well-
connected among themselves. Each (honest) node checks with its neighbors to
see if the value sent by the Byzantine node is consistent among the neighbor
set; if not, this (high) value is discarded.

There are some complications in implementing this idea, since Byzantine nodes
can lie about the identity of neighboring nodes; our protocol exploits the
fact that the network is a union of expander and small-world network to
overcome this. We refer to Section 3.3 for more details.

###  1.3 Other Related Works

There have been several works on estimating the size of the network, see e.g.,
the works of [14, 18, 27, 33, 32], but all these works do not work under the
presence of Byzantine adversaries. There have been some work on using network
coding for designing byzantine protocols (see e.g., [19]); but these protocols
have polynomial message sizes and are highly inefficient for problems such as
counting, where the output size is small. There are also some works on
topology discovery problems under Byzantine setting (e.g., [29]), but these do
not solve the counting problem.

Several recent works deal with Byzantine agreement, Byzantine leader election,
and fault-tolerant protocols in dynamic networks. We refer to [15, 6, 2, 1, 3]
and the references therein for details on these works. These works crucially
assume the knowledge of the network size (or at least an estimate of it) and
don’t work if the network size is not known.

There have been significant work in designing peer-to-peer networks that are
provably robust to a large number of Byzantine faults [12, 16, 28, 31]. These
focus only on (robustly) enabling storing and retrieving data items. The
problem of achieving almost-everywhere agreement among nodes in P2P networks
(modeled as expander graphs) is considered by King et al. in [24] in the
context of the leader election problem; essentially, [24] is a sparse
(expander) network implementation of the full information protocol of [23]. In
another recent work [22], the authors use a spectral technique to “blacklist”
malicious nodes leading to faster and more efficient Byzantine agreement. The
work of [15] presents a solution for maintaining a clustering of the network,
where each cluster contains more than two-thirds honest nodes with high
probability in a setting where the size of the network can vary polynomially
over time. All the above works assume an exact knowledge of or some good
estimate of the network size and do not solve the Byzantine counting problem.

The work of [8] shows how to implement uniform sampling in a peer-to-peer
system under the presence of Byzantine nodes where each node maintains a local
“view” of the active nodes. We point out that the choice of the view size and
the sample list size of $\Theta(n^{\frac{1}{3}})$ necessary for withstanding
adversarial attacks requires the nodes to have a priori knowledge of a
polynomial estimate of the network size. [18] considers a dynamically changing
network _without_ Byzantine nodes where nodes can join and leave over time and
provides a local distributed protocol that achieves a polynomial estimate of
the network size. In [35], the authors present a gossip-based algorithm for
computing aggregate values in large dynamic networks (but without the presence
of Byzantine failures), which can be used to obtain an estimate of the network
size. The work of [9] focuses on the consensus problem under crash failures
and assumes knowledge of $\log{n}$, where $n$ is the network size.

##  2 Preliminaries

###  2.1 Computing Model and Problem Definition

The distributed computing model: We consider a synchronous network represented
by a graph $G$ whose nodes execute a distributed algorithm and whose edges
represent connectivity in the network. The computation proceeds in synchronous
rounds, i.e., we assume that nodes run at the same processing speed (and have
access to a synchronized clock) and any message that is sent by some node $u$
to its neighbors in some round $r\geq 1$ will be received by the end of round
$r$.

Byzantine nodes: Among the $n$ nodes ($n$ or its estimate is not known to the
nodes initially), up to $B(n)$ can be _Byzantine_ and deviate arbitrarily from
the given protocol. Throughout this paper, we assume that
$B(n)=O(n^{1-\delta})$ (where $n$ is the unknown network size), for any
$\frac{3}{d}<\delta\leq 1$. We say that a node $u$ is _honest_ if $u$ is not a
Byzantine node and use Honest to denote the set of honest nodes in the
network. Byzantine nodes are “adaptive”, in the sense that they have complete
knowledge of the entire states of all nodes at the beginning of every round
(including random choices made by all the nodes), and thus can take the
current state of the computation into account when determining their next
action (they also can know the future random choices of honest nodes). The
Byzantine nodes have unbounded computational power, and can deviate
arbitrarily from the protocol. This setting is commonly referred to as the
_full information model_. We assume that the Byzantine nodes are randomly
distributed in the network.

Distinct IDs: We assume that nodes (including Byzantine) have distinct IDs and
they cannot lie about their ID while communicating with a neighbor. Note that
the $n$ distinct IDs (where $n$ is the unknown network size) are assumed to be
chosen from a large space (not known a priori to the nodes). Note that this
precludes (most) nodes from estimating $\log n$ by potentially looking at the
length of their IDs.

Network Topology: Let $G=(V,E)$ be the graph representing the network. We take
$G$ to be the union of two other graphs $H$ and $L$ (both defined below). That
is, $V(G)=V(H)=V(L)=V$, say, and $E(G)=E(H)\cup E(L)$. We take $H$ to be a
sparse, random $d$-regular graph that is constructed by the union of
$\frac{d}{2}$ (assume $d\geq 8$ is an even constant) random Hamiltonian cycles
of $n$ nodes. We call this random graph model the _$H(n,d)$ random graph
model_. 777We give more details on the model and analyze its properties in the
appendix (Section A). It is known that such a random graph is an expander with
high probability. The $H(n,d)$ random, regular graph model is a well-studied
and popular random graph model (see e.g., [37]). In particular, the $H(n,d)$
random graph model has been used as a model for Peer-to-Peer networks and
self-healing networks [26, 30].

$E(L)$ is defined as follows. For $u,v\in V$, $(u,v)\in E(L)$ if and only if
$dist(u,v)\leq k$ in $H$, where $k=\lceil\frac{d}{3}\rceil$ is a positive
integer. In other words, each node has direct connections (via edges of $L$)
to nodes that are within distance $k$. Note that adding the edges of $L$ makes
$H$ a “small-world” network, i.e., for each node $v$ in $G$, the neighbors of
$v$ within distance $\frac{k}{2}$ in $H$ are connected to each other (thus the
clustering coefficient is increased in $G$ compared to $H$). The small-world
property complements the expander property of the $d$-regular random graph,
since the clustering coefficient of the random regular graph is small. We
exploit both properties crucially in the protocol. Larger the degree $d$,
larger will be $k$, and large will be the robustness to Byzantine nodes, i.e.,
up to $O(n^{1-\delta})$ Byzantine nodes can be tolerated where
$\frac{3}{d}<\delta\leq 1$ (as defined earlier). Our small-world network is
inspired by and related to the Watts-Strogatz model [36, 7]. However, it is
important to note that the Watts-Strogatz model allows some nodes to have
$\Theta(\log n)$ degree and hence not constant bounded degree, unlike our
model.

It is important to note that nodes in $G$ do not know a priori which edges are
in $H$ and which are in $L$. However, as shown in Lemma 3, most (honest) nodes
can distinguish between the two types of edges using a simple protocol.

We point out although we assume a specific type of network model described
above — which, intuitively, is the worst case (most difficult) scenario for
the algorithm designer due to its (essentially) identical local topological
structure — our results can be extended to apply to potentially any (sparse)
graph that has high expansion and high clustering coefficient (e.g., one can
presumably take any bounded-degree expander rather than a $d$-regular graph as
$H$).

Problem and Goal: Our goal is to design a distributed protocol to estimate the
number of nodes in $G$, even under the presence of a large number of Byzantine
nodes. The problem is non-trivial, since each node has a local view and
knowledge that is independent of the network size. We would like our protocol
to run fast, i.e., in polylogarithmic (in the unknown network size $n$)
rounds, and use only “small-sized” messages. A “small-sized message” is one
that contains a constant number of IDs and $O(\log{n})$ additional bits.

We now present the formal definition of the Byzantine counting problem. Since
we assume a _sparse_ (constant bounded degree) network and a large number of
Byzantine nodes, it is difficult for an algorithm where every honest node
eventually knows the exact estimate of $n$. This motivates us to consider the
following “approximate, almost everywhere” variant of counting:

######  Definition 1 (Byzantine Counting).

Suppose that there are $B(n)$ Byzantine nodes in the network. We say that an
_algorithm $A$ solves Byzantine Counting in $T$ rounds_ if, in any run of $A$:

  1. 1.

all honest nodes terminate in $T$ rounds,

  2. 2.

all except $B(n)+\epsilon n$ honest nodes (for any arbitrarily small constant
$\epsilon>0$) have a constant factor estimate of $\log n$ (i.e., if
$\mathcal{L}$ is the estimate, then $c_{1}\log n\leq\mathcal{L}\leq c_{2}\log
n$, for some fixed positive constants $c_{1}$ and $c_{2}$), where $n$ is the
actual network size.

###  2.2 Notations and a Few Necessary Definitions

######  Definition 2.

For any two nodes $u$ and $v$ in $V$, the distance between them (in $G$) is
defined as $dist_{G}(u,v)\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}$ the
length of a shortest path between $u$ and $v$ in $G$. Similarly,
$dist_{H}(u,v)\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}$ the length of a
shortest path between $u$ and $v$ in $H$.

######  Remark 1.

For any node $v\in V(G)$, we follow the convention that
$dist_{G}(v,v)=dist_{H}(v,v)=0$.

######  Definition 3.

For any node $u$ and any set $V^{\prime}\subset V(G)=V$, the distance between
$u$ and $V^{\prime}$ (in $G$) is defined as
$dist_{G}(u,V^{\prime})\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\text{min}\left\\{dist_{G}(u,v)\
|\ v\in V^{\prime}\right\\}$.

######  Definition 4.

For any two subsets $V^{\prime}$ and $V^{\prime\prime}$ of $V(G)=V$, the
distance between $V^{\prime}$ and $V^{\prime\prime}$ (in $G$) is defined as
$dist_{G}(V^{\prime},V^{\prime\prime})\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\text{min}\left\\{dist_{G}(u,v)\
|\ u\in V^{\prime},v\in V^{\prime\prime}\right\\}$.

######  Remark 2.

In all our notations, the subscript $G$ or $H$ denotes the underlying graph.
We will, however, for the most part, talk about $H$. Thus to obtain notational
simplicity, we will omit the subscript $H$ from now on. If at any point, we
need to talk about $G$ instead, we will explicitly mention the subscript $G$.
For example, $dist(u,v)$ will denote the length of a shortest path between $u$
and $v$ in $H$, whereas $dist_{G}(u,v)$ will be used to denote the length of a
shortest path between $u$ and $v$ in $G$. And so on.

######  Definition 5.

For any $v\in V(H)$ and any positive integer $r$, $B(v,r)$ is defined as the
set of nodes within the ball of radius $r$ from $v$ (including at the
boundary), i.e,

$B(v,r)\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{w\in V(H)\ |\ 0\leq
dist(v,w)\leq r\right\\}$.

######  Definition 6.

For any $v\in V(H)$ and any positive integer $r$, $Bd(v,r)$ is defined as the
set of nodes at distance $r$ from $v$ (i.e., at the boundary), i.e,

$Bd(v,r)\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{w\in V(H)\ |\
dist(v,w)=r\right\\}$.

Next we introduce the “locally tree-like” property of an $H(n,d)$ random
graph: i.e., for most nodes $w$, the subgraph induced by $B(w,r)$ up to a
certain radius $r$ looks “like a tree”. This is stated more precisely as
follows.

######  Definition 7.

Let $G$ be an $H(n,d)$ random graph and $w$ be any node in $G$. Consider the
subgraph induced by $B(w,r)$ for $r=\frac{\log{n}}{10\log{d}}$. Let $u$ be any
node in $Bd(w,j)$, $1\leq j<r$. $u$ is said to be “typical” if $u$ has only
one neighbor in $Bd(w,j-1)$ and $(d-1)$-neighbors in $Bd(w,j+1)$; otherwise it
is called “atypical”.

######  Definition 8.

We call a node $w$ “locally tree-like” if no node in $B(w,r)$ is atypical. In
other words, $w$ is “locally tree-like” if the subgraph induced by $B(w,r)$ is
a $(d-1)$-ary tree.

It can be shown using properties of the $H(n,d)$ random graph model and
standard concentration bounds (cf. Section A) that most nodes in $G$ are
locally tree-like.

######  Lemma 1.

In an $H(n,d)$ random graph, with high probability, at least $n-O(n^{0.8})$
nodes are locally tree-like.

For the proof of this lemma, as well as for further details about the $H(n,d)$
random graph model, please refer to Section A.

######  Observation 1.

In a $d$-regular graph, for any vertex $v$, the number of vertices that are
within a $\tau$-distance of $v$ is bounded by $(d-1)^{\tau+1}$, i.e.,
$|B(v,\tau)|<(d-1)^{\tau+1}$.

Since any two vertices that are within $\tau$-distance of each other in $G$ is
within $k\tau$ distance of each other in $H$ (which is a $d$-regular graph),
we have that

######  Observation 2.

In the graph $G$, for any vertex $v$, the number of vertices that are within a
$\tau$-distance of $v$ is bounded by $(d-1)^{k\tau+1}$, i.e.,
$|B_{G}(v,\tau)|<(d-1)^{k\tau+1}$.

######  Definition 9.

We categorize the nodes in $V$ into the following distinct categories. Unlike
our usual convention, the distances referred to in this definition refer to
the respective distances in $G$ (not in $H$, as is usual).

  1. 1.

Byzantine nodes: The set of Byzantine nodes is denoted by Byz.

  2. 2.

Honest nodes: The set of honest nodes is defined to be
$\texttt{Honest}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}V\setminus\texttt{Byz}$.

  3. 3.

Locally tree-like nodes: Please refer to Definition 8. That is, the set of the
locally tree-like nodes is defined as
$\texttt{LTL}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{v\in V\ |\
v\text{ is locally tree-like}\right\\}$.

  4. 4.

Non-locally-tree-like nodes: The set of the non-locally-tree-like nodes is
defined as
$\texttt{NLT}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}V\setminus\texttt{LTL}$.

  5. 5.

Unsafe nodes: The set of nodes that have one or more NLT nodes within a
distance of $a\log{n}$, where
$a\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{\delta}{10k\log{(d-1)}}$.
If we denote the set of unsafe nodes by Unsafe, then

$\texttt{Unsafe}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{v\in V\ |\
dist_{G}(v,\texttt{NLT})\leq a\log{n}\right\\}$.

  6. 6.

Safe nodes: Nodes that are not unsafe. In other words, the set of nodes that
have no NLT nodes within a distance of $a\log{n}$. If we denote the set of
safe nodes by Safe, then

$\texttt{Safe}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{v\in V\ |\
dist_{G}(v,\texttt{NLT})>a\log{n}\right\\}$.

  7. 7.

Bad nodes: The set of bad nodes is defined to be
$\texttt{Bad}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\texttt{Byz}\cup\texttt{NLT}$.

  8. 8.

Byzantine-Unsafe nodes: The set of nodes that have one or more bad nodes
within a distance of $a\log{n}$, where
$a\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{\delta}{10k\log{(d-1)}}$.
If we denote the set of Byzantine-unsafe nodes by BUS, then

$\texttt{BUS}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{v\in V\ |\
dist_{G}(v,\texttt{Bad})\leq a\log{n}\right\\}$.

  9. 9.

Byzantine-Safe nodes: Nodes that are not Byzantine-unsafe. In other words, the
set of nodes that have no bad nodes within a distance of $a\log{n}$. If we
denote the set of Byzantine-safe nodes by Byz-safe, then

$\texttt{Byz-safe}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{v\in V\
|\ dist_{G}(v,\texttt{Bad})>a\log{n}\right\\}$.

######  Lemma 2.

The various node sets defined in Definition 9 have the following sizes,
respectively.

  1. 1.

$|\texttt{Byz}|=n^{1-\delta}$.

  2. 2.

$|\texttt{Honest}|=n-n^{1-\delta}$.

  3. 3.

$|\texttt{LTL}|\geq n-O(n^{0.8})$.

  4. 4.

$|\texttt{NLT}|\leq O(n^{0.8})$.

  5. 5.

$|\texttt{Unsafe}|\leq O(n^{0.8+\frac{\delta}{10}})=o(n)$.

  6. 6.

$|\texttt{Safe}|\geq n-O(n^{0.8+\frac{\delta}{10}})=n-o(n)$.

  7. 7.

$|\texttt{Bad}|\leq n^{1-\delta}+n^{0.8}\leq 2n^{1-\delta}$ (assuming
$\delta\leq 0.2$).

  8. 8.

$|\texttt{BUS}|\leq 2(d-1)n^{1-\frac{9\delta}{10}}=o(n)$.

  9. 9.

$|\texttt{Byz-safe}|\geq n-2(d-1)n^{1-\frac{9\delta}{10}}=n-o(n)$.

###### Proof.

  1. 1.

By definition.

  2. 2.

By definition.

  3. 3.

By Lemma 1.

  4. 4.

By Lemma 1.

  5. 5.

By Definition 9, Observation 2, and Lemma 1.

  6. 6.

By Definition 9, Observation 2, and Lemma 1.

  7. 7.

By definition.

  8. 8.

Follows from Observation 2 and the definition of BUS.

  9. 9.

By definition.

∎

######  Definition 10.

We call $u$ a child of $w$ with respect to $v$ (or $w$ the parent of $u$, with
respect to $v$) if $u$ is a child of $w$ in the BFS tree rooted at $v$.
Similarly, we call $u$ and $w$ siblings with respect to $v$ if they are
siblings in the BFS tree rooted at $v$. We note that, as is our usual custom,
this BFS tree is in the graph $H$ and not in $G$.

It is important to note that nodes in $G$ do not know a priori which edges are
in $H$ and which are in $L$. However, the following lemma assures us that most
(honest) nodes can distinguish between the two types of edges using a simple
protocol.

######  Lemma 3.

For any honest node $v$, if $v$ has no Byzantine neighbor in $G$ (that is, no
Byzantine neighbor in its $k$-distance neighborhood in $H$), then $v$ can
faithfully reconstruct the topology of its $k$-distance neighborhood in $H$
from the information it is provided by its $G$-neighbors.

###### Proof.

For any $x\in V(G)$, let $N_{G}(x)$ denote the set of $G$-neighbors of $x$.
Let $w$ and $u$ be two $G$-neighbors of $v$. Then we observe that

  * •

$w$ is a child of $u$ with respect to $v$ if and only if $N_{G}(w)\cap
N_{G}(v)\subset N_{G}(u)\cap N_{G}(v)$.

  * •

$u$ is a child of $w$ with respect to $v$ if and only if $N_{G}(u)\cap
N_{G}(v)\subset N_{G}(w)\cap N_{G}(v)$.

  * •

$u$ and $v$ are siblings if $u\in N_{G}(w)$ and $w\in N_{G}(u)$ but neither of
them is a child of the other.

∎

######  Remark 3.

Since $d$ and $k$ are constants, the list of neighbors is still $O(1)$, and
hence can be exchanged in a constant number of rounds (using small sized
messages).

##  3 The Algorithm and its analysis

For the sake of exposition, we first describe the algorithm and analyze its
behavior _free from_ the influence of any Byzantine nodes; in other words, we
will assume that all nodes (including Byzantine nodes) honestly execute the
protocol without malicious behavior. We will discuss any malicious effects the
Byzantine nodes may have in Section 3.3 and describe how to modify the
algorithm (and analysis) to counter the Bzyantine nodes.

###  3.1 Description of the algorithm (assuming no influence of Byzantine
nodes)

Phases and subphases: This is a distributed algorithm that runs in _phases_.
In the $i^{\text{th}}$ phase, the algorithm works with the current estimation
of $\log{n}$, which is $i$. We reserve the letter $i$ exclusively to denote
the phase that the algorithm is presently in. For $i\geq 1$, the
$i^{\text{th}}$ phase consists of several runs (repetitions) of the same
random experiment (the random experiment is described in the next few
paragraphs; also see Lines 10 through 18 of the pseudocode in Algorithm 1). We
call one such run a _subphase_ of the $i^{\text{th}}$ phase. We would usually
index the subphases by $j$, i.e., we will very frequently use the phrase “in
the $j^{\text{th}}$ subphase of the $i^{\text{th}}$ phase” in our description
and analysis of the algorithm. We note that in a synchronized network the
value of $i$ and $j$ are known to all nodes.

The $i^{\text{th}}$ phase consists of exactly $\alpha_{i}$ subphases
(repetitions), where
$\alpha_{i}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\lceil\frac{\log{(\frac{1}{\epsilon})}+i+1-\log{d}}{(i-2)\log{(d-1)}}\rceil$.
We call $\epsilon$ _the error parameter_ — by changing its value (please refer
to Line LABEL:value-of-alpha-i in the pseudocode in Algorithm 1), we (the
algorithm designer) can control exactly how large a fraction of the honest
nodes would estimate $\log{n}$ correctly (i.e., get a constant-factor
approximation of $\log{n}$). Theorem 1, which is the main result of this
paper, tells us that at most $\epsilon$-fraction of the honest nodes would
_fail_ to get a constant factor approximation of $\log{n}$.

Basic idea (see also Section 1.2): In one random experiment, i.e., in the
$j^{\text{th}}$ subphase of the $i^{\text{th}}$ phase, say, every node sends
out some tokens (these contain some information) that propagate through the
network (by flooding) for some (pre-determined) number of steps (rounds), at
the end of which every node takes stock of the tokens it has received over the
intermediate rounds.

Color of a token: Every token circulating in the network has a _color_
(defined next), which is passed down to a token from its generating node.
Every node $v$ tosses an unbiased coin until it gets its first head (see Line
10 of the pseudocode in Algorithm 1). If a node $v$ gets its first head at the
$r^{\text{th}}$ trial, we call $r$ to be the _color_ of $v$ (see Line 11 of
the pseudocode in Algorithm 1). Thus the _color_ of a node is always a
positive integer, which may be (but is not necessarily) different for
different nodes.

Estimating $\log{n}$: When $i$ is much smaller than $\log{n}$, most nodes will
receive their respective highest colored tokens in the last round. In
contrast, when $i$ is of the same order as $\log{n}$, most nodes will have
received their respective highest colored tokens much before the last round.
This provides a node with a way to determine when its estimate of $\log{n}$,
which is $i$, has reached close to the actual value of $\log{n}$.

1:Ask all the neighbors for their respective adjacency lists and distinguish
between the edges of $H$ and $L$ from that information.

2:for $i\leftarrow 1,2,\dots$ do $\triangleright$ $i$ denotes the phase node
$v$ is in

3: $FlagTerminate\leftarrow 1$

4: if $d(d-1)^{i-2}\leq\frac{2}{\epsilon}$ then

5:
$\alpha_{i}\leftarrow\lceil\frac{\log{(\frac{1}{\epsilon})}+i+1}{\log{d}+(i-2)\log{(d-1)}-1}\rceil$
$\triangleright$ $0<\epsilon<1$ is the error-parameter

6: else

7: $\alpha_{i}\leftarrow 1+\frac{i+1}{\log{(\frac{1}{\epsilon})}}$

8: end if

9: for $j\leftarrow 1,2,\dots,i\alpha_{i}$ do $\triangleright$ Phase $i$
consists of $\alpha_{i}$ subphases; the subphases are indexed by $j$

10: $v$ tosses a fair coin until the outcome is heads in the $r$-th trial, for
some $r\geq 1$.

11: $c_{v,i}\leftarrow r$

12: Flood the color $c_{v,i}$, along the edges of $H$ only, for exactly $i$
steps. $\triangleright$ This is possible by virtue of Lemma 3.

13: for time $t=1,2,\ldots,i$ do

14: In each round $t$, mark and store the highest color received. Let’s call
it $k_{t}$

15: end for

16: if $k_{i}>k_{t}$, $\forall 1\leq t<i$, and
$k_{i}>\log{(d(d-1)^{i-1})}-\log{\log{(d(d-1)^{i-1})}}$ then

17: $FlagTerminate\leftarrow 0$

18: end if

19: end for

20: if $FlagTerminate=1$ then

21: Decide $i$ and terminate all for-loops. $\triangleright$ $v$ accepts $i$
as the estimate of $\log{n}$

22: else

23: Continue to the next phase $i+1$.

24: end if

25:end for

Algorithm 1 The basic counting algorithm (in the absence of Byzantine nodes).
Code for node $v$.

###  3.2 Analysis of the algorithm (assuming Byzantine nodes behave honestly)

In this section we show that the algorithm gives a $(\frac{b}{a})$-factor
approximation of $\log{n}$ with high probability, where
$a\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{\delta}{10k\log{(d-1)}}$
and
$b\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{4}{\log{(1+\frac{h}{d})}}$,
where $h$ is the edge-expansion of $H$. Note that $0<a<b<1$. We recall that
$n^{1-\delta}$ is the number of Byzantine nodes in the network $G$, and $d$ is
the uniform degree of $H$. ($H$ is a subset of $G$. For the exact definition
of $H$, please refer to Section 2.1.)

######  Observation 3.

$b\log{n}\geq 2D(H)$, where $D(H)$ is the diameter of $H$.

##### High-level overview of the proof

We break our analysis up into two different stages of the algorithm. We show
that the following statements hold with high probability.

  1. 1.

For $i<a\log{n}$, at least $(1-\epsilon)$-fraction of the good nodes do not
accept $i$ to be the right estimate of $\log{n}$, and they continue with the
algorithm. The rest of the nodes — i.e., at most $\epsilon$-fraction of the
good nodes — even though they have stopped generating tokens, still continue
to forward tokens generated by other nodes. $0<\epsilon\leq 1$ is a constant
and we can make it arbitrarily small.

  2. 2.

If $i=b\log{n}$, all but $o(n)$ of the remaining active nodes accept $i$ to be
the estimate of $\log{n}$ and they stop producing tokens. They however
continue to forward tokens generated by other (if any) nodes.

We cannot say which way a node will decide when $a\log{n}\leq i<b\log{n}$. The
above two statements are, however, sufficient to give us an approximation
factor of $\frac{b}{a}=\frac{40k\log{(d-1)}}{\delta\log{(1+\frac{h}{d})}}$.

####  3.2.1 When $i$ is small: In particular, when $i<a\log{n}$

For the sake of the analysis in this subsection only, we will consider only
_safe nodes_ , i.e., only those nodes in the set Safe. Let us first take note
of a few properties of the geometric distribution though; these will be useful
later.

######  Observation 4.

For any node $v$ and any positive integer $r$,

  1. 1.

$Pr[c_{v}=r]=\frac{1}{2^{r}}$.

  2. 2.

$Pr[c_{v}\geq r]=\frac{1}{2^{r-1}}$.

  3. 3.

$Pr[c_{v}<r]=1-Pr[c_{v}\geq r]=1-\frac{1}{2^{r-1}}$.

  4. 4.

$Pr[c_{v}\leq r]=1-Pr[c_{v}\geq r+1]=1-\frac{1}{2^{r}}$.

  5. 5.

$Pr[c_{v}>r]=1-Pr[c_{v}\leq r]=\frac{1}{2^{r}}$.

For any non-empty $V^{\prime}\subset V(G)$, $c^{\text{max}}_{V^{\prime}}$ is
defined as
$c^{\text{max}}_{V^{\prime}}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{c_{v}\
|\ v\in V^{\prime}\right\\}$. Suppose $|V^{\prime}|=n^{\prime}$.

######  Observation 5.

For any positive integer $j$,

  1. 1.

$Pr[c^{\text{max}}_{V^{\prime}}<r]=(Pr[c_{v}<r])^{n^{\prime}}=(1-\frac{1}{2^{r-1}})^{n^{\prime}}$.

  2. 2.

$Pr[c^{\text{max}}_{V^{\prime}}\geq
r]=1-Pr[c^{\text{max}}_{V^{\prime}}<r]=1-(1-\frac{1}{2^{r-1}})^{n^{\prime}}$.

  3. 3.

$Pr[c^{\text{max}}_{V^{\prime}}\leq
r]=Pr[c^{\text{max}}_{V^{\prime}}<r+1]=(1-\frac{1}{2^{r}})^{n^{\prime}}$.

  4. 4.

$Pr[c^{\text{max}}_{V^{\prime}}>r]=Pr[c^{\text{max}}_{V^{\prime}}\geq
r+1]=1-(1-\frac{1}{2^{r}})^{n^{\prime}}$.

  5. 5.

$Pr[c^{\text{max}}_{V^{\prime}}=r]=Pr[c^{\text{max}}_{V^{\prime}}\geq
r]-Pr[c^{\text{max}}_{V^{\prime}}>r]=(1-\frac{1}{2^{r}})^{n^{\prime}}-(1-\frac{1}{2^{r-1}})^{n^{\prime}}$.

######  Lemma 4.

$Pr[c^{\text{max}}_{V^{\prime}}>2\log{n^{\prime}}]\leq\frac{1}{n^{\prime}}$.

###### Proof.

$\displaystyle
Pr[c^{\text{max}}_{V^{\prime}}>2\log{n^{\prime}}]=1-(1-\frac{1}{2^{2\log{n^{\prime}}}})^{n^{\prime}}=1-(1-\frac{1}{{n^{\prime}}^{2}})^{n^{\prime}}$
$\displaystyle\leq
1-(1-\frac{n^{\prime}}{{n^{\prime}}^{2}})=1-(1-\frac{1}{n^{\prime}})=\frac{1}{n^{\prime}}\text{.}$

∎

######  Lemma 5.

$Pr[c^{\text{max}}_{V^{\prime}}\leq\log{n^{\prime}}-\log{\log{n^{\prime}}}]<\frac{1}{n^{\prime}}$.

###### Proof.

$\displaystyle
Pr[c^{\text{max}}_{V^{\prime}}\leq\log{n^{\prime}}-\log{\log{n^{\prime}}}]=(1-\frac{1}{2^{\log{n^{\prime}}-\log{\log{n^{\prime}}}}})^{n^{\prime}}$
$\displaystyle=(1-\frac{\log{n^{\prime}}}{n^{\prime}})^{n^{\prime}}\leq\text{exp}(-\frac{(\log{n^{\prime}}).n^{\prime}}{n^{\prime}})=\text{exp}(-\log{n^{\prime}})<\frac{1}{n^{\prime}}\text{.}$

∎

For any node $v$ and any non-negative integer $r$, let us denote the set
$B(v,r)\setminus\left\\{v\right\\}$ by $B^{*}(v,r)$. We recall that from the
“locally tree-like property” (cf. Definition 8 and Lemma 1), for any _safe
node_ $v$,

$\displaystyle|B(v,r)|=1+d\cdot\textstyle{\sum_{j=1}^{r}}(d-1)^{j-1}\implies|B^{*}(v,r)|=d\sum_{j=1}^{r}(d-1)^{j-1}=\frac{d(d-1)^{r}}{d-2}\text{,
and}$ $\displaystyle|Bd(v,r)|=d(d-1)^{r-1}\text{.}$

For any positive integer $r$, let
$l_{r}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\log{d}+r\log{(d-1)}$. We
observe that $l_{r}=l_{r-1}+\log{(d-1)}$. Then

######  Lemma 6.

$\log{(|B^{*}(v,r)|)}=l_{r}-\log{(d-2)}$ and
$\log{(|Bd(v,r)|)}=l_{r}-\log{(d-1)}$.

######  Lemma 7.

$Pr[c^{\text{max}}_{B^{*}(v,r)}>2(l_{r}-\log{(d-2)})]\leq\frac{d-2}{d(d-1)^{r}}$.

###### Proof.

Follows from Lemma 4 and Lemma 6. ∎

######  Lemma 8.

$Pr[c^{\text{max}}_{Bd(v,r)}\leq
l_{r}-\log{(d-1)}-\log{(l_{r}-\log{(d-1)})}]<\frac{1}{d(d-1)^{r-1}}$.

###### Proof.

Follows from Lemma 5 and Lemma 6. ∎

Next we show that the probability that a _safe node_ decides to stop (when
$i<a\log{n}$) is bounded by a constant (any arbitrarily small, but fixed
constant).

######  Lemma 9.

$Pr[\text{a {\emph{safe}} node }v\text{ makes a wrong decision in the
}i^{\text{th}}\text{phase}]<\frac{\epsilon}{2^{i+1}}$.

We will use a series of other, smaller results to show the above. One subtle
issue to keep in mind is that since the “failure probability” for a safe node
is _not_ $0$ (zero), there may be some safe nodes that do decide wrongly.
Those safe nodes, in turn, will no longer generate tokens in the following
phases. Therefore, when we calculate the failure probability for a safe node
$v$, say, in phase $i$, we have to take into consideration the fact that there
may be some nodes in the $i$-hop neighborhood of $v$, i.e., in $B(v,i)$, that
made a wrong decision in some previous phase $j$, $j<i$, and is thus
_inactive_ in phase $i$.

We show this by induction on $i$, where $i$ is the phase-number. We note that
in the very first phase, all the nodes are active, thus there is no need to
consider inactive nodes. This helps us prove the basis of the induction. Next
we assume that for any $i<\log{n}$, the probability that a safe node $v$ went
inactive in some previous phase $i^{\prime}$, $i^{\prime}<i$, is at most
$\frac{\epsilon}{2^{i^{\prime}+1}}$, where $\epsilon$ is the error parameter.
This forms the inductive hypothesis. Assuming this, we go on to show that the
failure probability for a safe node in the $i^{\text{th}}$ phase is less than
$\frac{\epsilon}{2^{i+1}}$.

We defer the detailed, formal proof to the appendix — please refer to Section
B.

##### Translating the constant probability of error into a “low” probability
of error.

Lemma 9 promises us that any individual node has a small probability of error
when $i<a\log{n}$. So the expected number of nodes to make an error is also
small. We, however, want to show a high probability bound on the number of
nodes that make a mistake.

In order to show that, we proceed along the usual way of formulating an
indicator random variable and then computing the expectation of the sum of the
individual indicator random variables by using the principle of linearity of
expectation. We show the high probability bound by using the method of
_bounded differences_ (Azuma’s Inequality, more specifically).

Now to the formal description.

Let $Y^{v}_{i}$ be an indicator random variable which is $1$ if and only if
$v$ decides $i$ to be a correct estimate of $\log{n}$. Lemma 9 shows that
$Pr[Y^{v}_{i}=1]<\frac{\epsilon}{2^{i+1}}$. Now let

$Y_{i}=\sum_{v\in V}{Y^{v}_{i}}\text{.}$

That is, $Y_{i}$ denotes the number of nodes that decide _wrongly_ in the
$i^{\text{th}}$ phase. We recall once again that here we are interested only
in the case where $i<a\log{n}$. Then $Y_{i}$ cannot be too large, i.e., not
too many nodes can decide wrongly in one phase.

######  Lemma 10.

$Pr[Y_{i}>\frac{n\epsilon}{2^{i}}]<\frac{1}{n^{4}}$ if $i<a\log{n}$.

###### Proof.

$\displaystyle E[Y_{i}]=E[\sum_{v\in V}{Y^{v}_{i}}]=\sum_{v\in
V}E[{Y^{v}_{i}}]\text{ [by linearity of expectation]}$
$\displaystyle=\sum_{v\in V}{Pr[Y^{v}_{i}=1]}\text{ [since }Y^{v}_{i}\text{ is
an indicator random variable]}$ $\displaystyle<\sum_{v\in
V}{\frac{\epsilon}{2^{i+1}}}=\frac{n\epsilon}{2^{i+1}}$

Two vertices $v$ and $w$ are independent if their $i$-distance neighborhoods
do not intersect, i.e., if the distance between them is greater than $2i$. In
other words, $v$ going defective can affect only those vertices that are
within a distance of $2i$ to $v$. The number of vertices that are within a
$2i$ distance of $v$ is at most $(d-1)^{(2i+1)}$. By the Azuma-Hoeffding
Inequality [10],

$\displaystyle
Pr[Y_{i}-E[Y_{i}]\geq\frac{n\epsilon}{2^{i+1}}]\leq\text{exp}(-\frac{{(\frac{n\epsilon}{2^{i+1}})}^{2}}{2n\cdot(d-1)^{2(2i+1)}})=\text{exp}(-\frac{n\epsilon^{2}}{2^{2i+3}.(d-1)^{4i+2}})$
$\displaystyle=\text{exp}(-\frac{n\epsilon^{2}}{2^{k}})\text{, say, where
}k=2i+3+(4i+2)\log{(d-1)}\text{.}$

Since, $i<a\log{n}=\frac{\delta\log{n}}{10\log{(d-1)}}$,

$\displaystyle
k<\frac{\delta\log{n}}{5\log{(d-1)}}+3+2\log{(d-1)}+\frac{2\delta\log{n}}{5}$
$\displaystyle=\frac{\delta\log{n}}{5\log{(d-1)}}(2\log{(d-1)}+1)+2\log{(d-1)}+3$
$\displaystyle<\log{n}-\log{\log{n}}-2-2\log{(\frac{1}{\epsilon})}$
$\displaystyle\text{[assuming}\log{n}>\frac{5\log{(d-1)}(\log{\log{n}}+2\log{(d-1)}+3+2\log{(\frac{1}{\epsilon})}+2)}{(5-2\delta)\log{(d-1)}-\delta}\text{,}$
$\displaystyle\text{which is true for large enough values of }n\text{]}$

Thus

$\displaystyle
Pr[Y_{i}-E[Y_{i}]\geq\frac{n\epsilon}{2^{i+1}}]\leq\text{exp}(-\frac{n\epsilon^{2}}{2^{k}})\leq\text{exp}(-\frac{n\epsilon^{2}}{2^{\log{n}-\log{\log{n}}-2-2\log{(\frac{1}{\epsilon})}}})$
$\displaystyle=\text{exp}(-\frac{n\epsilon^{2}}{\frac{n}{4\log{n}\cdot\frac{1}{\epsilon^{2}}}})=\text{exp}(-4\log{n})<\frac{1}{n^{4}}$

But again $E[Y_{i}]<\frac{n\epsilon}{2^{i+1}}$. Hence
$Pr[Y_{i}>\frac{n\epsilon}{2^{i}}]\leq
Pr[Y_{i}-E[Y_{i}]\geq\frac{n\epsilon}{2^{i+1}}]<\frac{1}{n^{4}}$. ∎

Now this is true for one particular phase $i$. Summing over all the phases
(recall that we are concerned here only with the case $i<a\log{n}$), we get
that the fraction of nodes that make a wrong decision cannot be more than

$\sum_{i<a\log{n}}\frac{\epsilon}{2^{i}}<\epsilon\text{,}$

and this is true with probability

$>(1-\sum_{i<a\log{n}}\frac{1}{n^{4}})>(1-\frac{1}{n^{3}})\text{.}$

Thus we have

######  Lemma 11.

For Algorithm 1, the following holds with probability $>1-\frac{1}{n^{3}}$:
While $1\leq i<a\log{n}$, at most $\epsilon$-fraction of the nodes decide
wrongly, i.e., decide $i$ to be a correct estimate of $\log{n}$ (where
$\epsilon$ is any arbitrarily small but fixed positive constant).

###### Proof.

Follows from Lemma 10 and Lemma 2. ∎

####  3.2.2 When $i=\Theta(\log{n})$: In particular, when $i=b\log{n}$

Here we show that the following statement holds with probability at least
$1-\frac{1}{n^{2}}$: If a node $v$ is still active at the beginning of this
phase, by the end of this phase, it accepts the current value of $i$, i.e.,
$b\log{n}$, to be a correct estimate of $\log{n}$ and terminates.

######  Lemma 12.

The following holds with probability at least $1-\frac{1}{n^{2}}$: In all the
$i\alpha_{i}$ subphases of phase $i$ (where $i=b\log{n}$), it is always the
case that $c^{\text{max}}_{V}\leq 4\log{n}-1$, where
$c^{\text{max}}_{V}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\left\\{c_{v}\
|\ v\in V\right\\}$, i.e., the highest color generated in the network.

###### Proof.

From Observation 4, for any particular node $w$,
$Pr[c_{w}>4\log{n}-1]=\frac{1}{2^{4\log{n}-1}}=\frac{2}{n^{4}}$. Taking the
union bound over all $w\in V(G)$,

$Pr[c^{\text{max}}_{V}>4\log{n}-1]\leq\frac{2}{n^{3}}$ (1)

This is for one subphase of the $i^{\text{th}}$ phase. Since there are
$i\alpha_{i}$ subphases in the $i^{\text{th}}$ phase, we take the union bound
over all the subphases and get that with probability at least
$1-\frac{2i\alpha_{i}}{n^{3}}$, $c^{\text{max}}_{V}\leq 4\log{n}-1$ holds in
_all_ the $i\alpha_{i}$ subphases. But
$\frac{2i\alpha_{i}}{n^{3}}=\frac{\Theta(\log^{2}{n})}{n^{3}}<\frac{1}{n^{2}}$.
Thus with probability at least $1-\frac{1}{n^{2}}$, $c^{\text{max}}_{V}\leq
4\log{n}-1$ holds in _all_ the $i\alpha_{i}$ subphases. ∎

######  Lemma 13.

The following holds with probability at least $1-\frac{1}{n^{2}}$ for
Algorithm 1: If a node $v$ is still active at the beginning of phase $i$ (when
$i=b\log{n}$), by the end of this phase, it accepts the current value of $i$,
i.e., $b\log{n}$, to be a correct estimate of $\log{n}$ and terminates.

###### Proof.

We recall that in order for an honest node $v$ to continue after this phase,
the following criterion must be satisfied at least once in the $i\alpha_{i}$
subphases of the $i^{\text{th}}$ phase (Please see Line 17 of the pseudocode):

$k_{i}>\log{d}+(i-1)\log{(d-1)}-\log{(\log{d}+(i-1)\log{(d-1)})}$,

where $k_{i}$ is the highest color that $v$ receives after $i$ rounds, i.e.,
at the end of the $j^{\text{th}}$ subphase of the $i^{\text{th}}$ phase.
Substituting $i=b\log{n}=\frac{4\log{n}}{\log{(1+\frac{h}{d})}}>4\log{n}$, we
get that in order for an honest node $v$ to continue after this phase, the
following criterion must be satisfied at least once in the $i\alpha_{i}$
subphases of the $i^{\text{th}}$ phase:

$\displaystyle
k_{i}>\log{d}+(i-1)\log{(d-1)}-\log{(\log{d}+(i-1)\log{(d-1)})}$
$\displaystyle>\log{d}+(4\log{n}-1)\log{(d-1)}-\log{(\log{d}+(4\log{n}-1)\log{(d-1)})}$
$\displaystyle>\frac{1}{2}.(\log{d}+(4\log{n}-1)\log{(d-1)})>(4\log{n}-1).\frac{\log{(d-1)}}{2}$
$\displaystyle\geq 4\log{n}-1\text{, assuming }\log{(d-1)}\geq 2\text{, or
equivalently, }d\geq 5\text{.}$

By Lemma 12, with probability at least $1-\frac{1}{n^{2}}$, no node generates
a color $>4\log{n}-1$. Therefore $v$ will not receive any such color
($>4\log{n}-1$) either. So in all the $i\alpha_{i}$ subphases of phase $i$
(where $i=b\log{n}$), $k_{i}$ will always be $\leq 4\log{n}-1$ and therefore
$v$ will _not_ continue after this phase. ∎

###  3.3 The Byzantine Protocol: Modifications to Algorithm 1 and its analysis

We next discuss the modifications made to the Basic Counting Protocol
(Algorithm 1) to counter the effect of the Byzantine nodes — this gives us the
Byzantine Counting Protocol (Algorithm 2).

####  3.3.1 Description of the modifications in the algorithm

  1. 1.

At the very beginning (that is, even before phase $1$ starts), every honest
node $v$ asks its neighbors in $G$ for their own IDs and the IDs of their
respective neighbors. We observe that this takes a constant number of rounds.
From that neighborhood information of its neighbors, $v$ tries to reconstruct
the topology of its $k$-distance neighborhood in $H$. Lemma 3 tells us that
this is possible when there are no Byzantine nodes.

When there are Byzantine nodes, however, they can try to provide false
neighborhood data to $v$. The algorithm dictates that $v$ shuts itself down
(that is, goes into _crash failure_) if $v$ receives inconsistent or
conflicting data from two or more of its neighbors. Please refer to Line 2 of
the pseudocode in Algorithm 2.

  2. 2.

For every color that $v$ receives from a neighbor $w$, say, $v$ checks (via
the _lattice edges_ , i.e., the edges of $L$) with all the nodes in $B(w,k-1)$
(this ball $B$ is defined with respect to $H$) to verify that $w$ indeed
received that color via a legitimate path (up to a distance of $k-1$) from its
$(k-1)$-distance neighbors in $H$. Please refer to Line 15 of the pseudocode
in Algorithm 2.

We note a minor detail here: For colors received within the first $t$ time-
steps (in any $j^{\text{th}}$ subphase of any phase $i$), when $1\leq t\leq
k-1$, an honest node $v$ checks with nodes in the smaller ball $B(w,t)$
(instead of $B(w,k-1)$).

Lemma 15 guarantees that (for any honest node $v$) the Byzantine nodes cannot
fool $v$ into believing the existence of a $k$-length chain, composed purely
of Byzantine nodes, in its $k$-distance neighborhood in $H$. Thus it ensures
that a Byzantine node is _not_ able to push any arbitrary color into the
network without raising a flag.

####  3.3.2 The Pseudocode for the Byzantine counting algorithm

Lines 2 and 15 respectively indicate the changes from the previous algorithm
(please refer to Algorithm 1). These lines are shown in boldface. Suppose that
a node sends a message with some color $c$. We say that $c$ is a _legitimate
color_ if it was generated by an honest node. Note that some nodes might be
forwarding colors generated by Byzantine nodes.

1:Ask all the neighbors (in $G$) for their respective adjacency lists and
distinguish between the edges of $H$ and $L$ from that information.

2:If $v$ gets conflicting or contradictory information from two or more of its
neighbors in $G$, $v$ shuts down, i.e., $v$ goes into _crash failure_.

3:for $i\leftarrow 1,2,\dots$ do $\triangleright$ $i$ denotes the phase node
$v$ is in

4: $FlagTerminate\leftarrow 1$

5: if $d(d-1)^{i-2}\leq\frac{2}{\epsilon}$ then

6:
$\alpha_{i}\leftarrow\lceil\frac{\log{(\frac{1}{\epsilon})}+i+1}{\log{d}+(i-2)\log{(d-1)}-1}\rceil$
$\triangleright$ $0<\epsilon<1$ is the error-parameter

7: else

8: $\alpha_{i}\leftarrow 1+\frac{i+1}{\log{(\frac{1}{\epsilon})}}$

9: end if

10: for $j\leftarrow 1,2,\dots,i\alpha_{i}$ do

11: $v$ tosses a fair coin until the outcome is heads in the $r$-th trial, for
some $r\geq 1$.

12: $c_{v,i}\leftarrow r$

13: Flood the color $c_{v,i}$, along the edges of $H$ only, for exactly $i$
steps.

14: for time $t=1,2,\ldots,i$ do

15: In each round $t$, for every received color $c$, if $v$ got $c$ from its
neighbor (in $H$) $w$, say, $v$ checks with the $(k-1)$-distance neighbors (in
$H$) of $w$ to verify that $c$ is a legitimate color.

16: In each round $t$, mark and store the highest color received. Let’s call
it $k_{t}$

17: end for

18: if $k_{i}>k_{t}$, $\forall 1\leq t<i$, and
$k_{i}>\log{d}+(i-1)\log{(d-1)}-\log{(\log{d}+(i-1)\log{(d-1)})}$ then

19: $FlagTerminate\leftarrow 0$

20: end if

21: end for

22: if $FlagTerminate=1$ then

23: Decide $i$ and terminate all for-loops. $\triangleright$ $v$ accepts $i$
as the estimate of $\log{n}$

24: else

25: Continue to the next phase $i+1$.

26: end if

27:end for

Algorithm 2 The Byzantine counting algorithm. Code for an honest node $v$.

###  3.4 Analysis of the algorithm

####  3.4.1 Preliminaries — Some useful observations

Let Crashed be the set of honest nodes that shut themselves down at the very
beginning of the algorithm (please see Line 2 of the pseudocode in Algorithm
2). Let Core be the largest connected component in $H$ induced by Uncrashed,
where
$\texttt{Uncrashed}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\texttt{Honest}\setminus\texttt{Crashed}$.

######  Lemma 14 (See [5]).

Core has size at least $n-o(n)$. Moreover, Core is an expander with edge-
expansion at least $\gamma$, where $\gamma>0$ is a constant.

###### Proof.

Follows from Lemma $3$ in [5]. ∎

######  Observation 6.

In the graph $H$, with high probability, there is no chain of length $\geq k$
composed of Byzantine nodes only.

###### Proof.

We have that $k=\lceil\frac{d}{3}\rceil$ and $\delta>\frac{3}{d}$, implying
$k\delta>1$. We assume that $k\delta=1+\delta^{\prime}$ for a fixed positive
constant $\delta^{\prime}$.

The number of possible $k$-length chains is upper-bounded by $n\cdot d^{k-1}$.
We recall that the Byzantine nodes are randomly distributed in the network.
Therefore, for any one such chain, the probability that it is composed purely
of Byzantine nodes is $(\frac{n^{1-\delta}}{n})^{k}=n^{-k\delta}$. By union
bound, the probability that there is at least one chain made only of Byantine
nodes is upper-bounded by

$\displaystyle n\cdot d^{k-1}\cdot n^{-k\delta}=n\cdot d^{k-1}\cdot
n^{-(1+\delta^{\prime})}\text{ [since }k\delta=1+\delta^{\prime}\text{]}$
$\displaystyle=\frac{d^{k-1}}{n^{\delta^{\prime}}}\text{, which is low
probability for a fixed positive constant }k\text{.}$

∎

######  Lemma 15.

The following statement holds with high probability: $\forall
v\in\texttt{Honest}$, the Byzantine nodes cannot make $v$ believe that there
is a chain of length $\geq k$ composed entirely of Byzantine nodes, without
shutting $v$ down.

###### Proof.

Consider an honest node $v$. If $v$ has no Byzantine neighbors in $G$, then
$v$ gets true neighborhood information from all its neghbors in $G$, and is
thus able to accurately reconstruct the exact topology of its $k$-distance
neighborhood in $H$ (please refer to Observation 3). Since $H$ does not have
any $k$-length chain of Byzantine nodes (please see Observation 6), $v$’s
reconstruction will have none either.

So suppose $v$ has one or more Byzantine neighbors in $G$. Let
$\mathcal{C}_{1}$ be the final $k$-length chain whose existence the Byzantine
nodes are trying to “trick” $v$ into believing. Since, in truth,
$\mathcal{C}_{1}$ has at most $k-1$ Byzantine nodes (thanks to Observation 6),
there must be a _dummy_ node $b_{2}$, say, which the Byzantine nodes will try
to insert into $\mathcal{C}_{1}$ (that is, to make it look as such in $v$’s
eyes).

$v$$w_{1}$$w_{2}$$w_{i}$$x_{j}$$b_{3}$$u$$b_{2}$$w_{d}$ Figure 1:
$\mathcal{C}_{1}=(w_{i},x_{j},\ldots,b_{3},b_{2})$ is the $k$-length chain the
Byzantine nodes are trying to tamper with. In reality, $b_{2}$ is _not_ a
child of $b_{3}$ (even though $b_{2}$ is directly connected to $v$ in the
graph $G$). So $b_{3}$ must hide the existence of a real child $u$, say, in
order to concoct the existence of the fake, Byzantine child $b_{2}$.

Thus, $b_{3}$, the (fake) parent of $b_{2}$ in the chain $\mathcal{C}_{1}$,
must report to $v$ that it has $b_{2}$ as a child. While doing so, however,
$b_{3}$ will need to suppress the existence of a (real) child $u$ (which may
or may not be Byzantine) because $b_{3}$ will need to maintain its degree $d$
in $H$ (in $v$’s eyes).

But as $u$ is directly connected to $v$ in $G$, the Byzantine nodes cannot
disrupt the communication between $u$ and $v$. Since $u$ knows $b_{3}$ to be
its neighbor in $H$ (we recall that $b_{3}$, even though Byzantine, cannot lie
about its ID to $u$), the algorithm would dictate that $u$ let it be known to
$v$ (regardless of whether or not $u$ is Byzantine).

Therefore, $v$ will have two conflicting pieces of information: it will hear
from $b_{3}$ that $b_{3}$ and $u$ are not neighbors in $H$, and $v$ will hear
the exact opposite from $u$. Thus, as per the algorithm, $v$ will go into
_crash failure_ , i.e., will shut itself down (see Line 2 of the pseudocode in
Algorithm 2. ∎

####  3.4.2 A high-level overview of the analysis

In this section we show that the algorithm gives a $(\frac{b}{a})$-factor
approximation of $\log{n}$ with high probability, where
$a\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{\delta}{10k\log{(d-1)}}$
and
$b\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\frac{4}{\log{(1+\frac{\gamma}{d})}}$,
where $\gamma$ is the edge-expansion of Core. Note that $0<a<b<1$. We recall
that $n^{1-\delta}$ is the number of Byzantine nodes in the network $G$, and
$d$ is the uniform degree of $H$. ($H$ is a subset of $G$. For the exact
definition of $H$, please refer to Section 2.1.)

######  Observation 7.

$b\log{n}\geq 2D(\texttt{Core})$, where $D(\texttt{Core})$ is the diameter of
Core.

##### High-level overview of the proof

We break our analysis up into two different stages of the algorithm. We show
that the following statements hold with high probability.

  1. 1.

Then for $i<a\log{n}$, at least $(1-\epsilon)$-fraction of the good nodes do
not accept $i$ to be the right estimate of $\log{n}$, and they continue with
the algorithm. The rest of the nodes — i.e., at most $\epsilon$-fraction of
the good nodes — even though they have stopped generating tokens, still
continue to forward tokens generated by other nodes. $0<\epsilon\leq 1$ is a
constant and we can make it arbitrarily small.

  2. 2.

If $i=b\log{n}$, all but $o(n)$ of the remaining active nodes accept $i$ to be
the estimate of $\log{n}$ and they stop producing tokens. They however
continue to forward tokens generated by other (if any) nodes.

We cannot say which way a node will decide when $a\log{n}\leq i<b\log{n}$. The
above two statements are, however, sufficient to give us an approximation
factor of
$\frac{b}{a}=\frac{40k\log{(d-1)}}{\delta\log{(1+\frac{\gamma}{d})}}$. This
gives us our main result of the paper:

######  Theorem 1.

Algorithm 2, with high probability, solves the Byzantine counting problem with
up to $O(n^{1-\delta})$ (randomly distributed) Byzantine nodes (where
$\delta>0$ is a small fixed constant that depends on $d$) and runs in
$\Theta(\log^{3}{n})$ rounds with the guarantee that all but an
$\epsilon$-fraction of the nodes in the network (for any arbitrary small
positive constant $\epsilon$) have a constant factor approximation of
$\log{n}$, where $n$ is the number of nodes in the network.

The proof of the above Theorem is shown in the following Sections.

####  3.4.3 When $i$ is small: In particular, when $i<a\log{n}$

For the sake of the analysis in this subsection only, we will consider only
_Byzantine-safe nodes_ , i.e., only those nodes in the set Byz-safe.

We note that while $i<a\log{n}$, no token generated by a Byzantine node
reaches a Byzantine-safe node (by the very definition of a Byzantine-safe
node, as defined in Definition 9). Thus for any $v\in\texttt{Byz-
safe}\subset\texttt{Safe}$, the exact same analysis of Section 3.2.1 remains
valid. That is, we have the same result, i.e., Lemma 11, as in the Byzantine-
free setting.

####  3.4.4 When $i=\Theta(\log{n})$: In particular, when $i=b\log{n}$

We showed in Section 3.2.2 that the following statement holds with probability
at least $1-\frac{1}{n^{2}}$: If an honest node $v$ is still active at the
beginning of this phase, by the end of this phase, it accepts the current
value of $i$, i.e., $b\log{n}$, to be a correct estimate of $\log{n}$ and
terminates.

But the aforementioned analysis in Section 3.2.2 takes into account tokens
generated by the honest nodes only. The Byzantine nodes can generate
arbitratily high colors in any subphase of any phase. But we argue that they
too are restricted by the structure of the network $G$. In particular, we
argue that a Byzantine node can push a high-colored token (that is, a token
with color $>\log{(d(d-1)^{i-1})}-\log{\log{(d(d-1)^{i-1})}}$ in phase $i$)
into the network only at the beginning of a subphase, and not at some
arbitrary point in the middle of a subphase. More specifically we show (by
exploiting the structure of the network, i.e., of the graph $G$):

######  Lemma 16.

The following statement holds with high probability: If a _core node_ receives
a high-colored token (generated by some Byzantine node) in round $t$ in some
subphase $j$, $1\leq j\leq\alpha_{i}$, then $1\leq t\leq k-1$.

###### Proof.

Suppose not. Suppose that there is at least one core node that receives a
high-colored token in some subphase $j$, where $1\leq j\leq\alpha_{i}$. Let
$t\geq k$ be the earliest time-instant in that subphase when a core node
receives a high-colored token. That is, there is some core node $v$ that
receives a high-colored token from a neighbor $b$, say, in the $t^{\text{th}}$
round. Now $b$ has to pretend that it received the high-colored token from
somebody else (because $b$ is not allowed to generate a token itself in the
middle of a subphase). Since $v$ has edges (the edges in $L$) to all the nodes
in $B(b,k-1)$, $v$ can contact all those nodes directly and check the veracity
of $b$’s claim. Since $t\geq k$, and since there are no Byzantine chains of
length $\geq k$ (Please see Observation 6 and Lemma 15), there will be at
least one honest node on any chain in $B(b,k-1)$ who would testify against
$b$. ∎

######  Lemma 17.

For $v\in\texttt{Core}$, if $v$ is still active at the beginning of phase $i$
(when $i=b\log{n}$), then with high probability, by the end of this phase, it
accepts the current value of $i$, i.e., $b\log{n}$, to be a correct estimate
of $\log{n}$ and terminates.

###### Proof.

Lemma 16 says that the Byzantine nodes would not be able to push tokens into
Core after the first $(k-1)$-rounds of a subphase without getting caught. So
suppose that one or more Byzantine nodes introduce a sufficiently high color
(so as to satisfy Line 17 of the pseudocode) into Core within the first
$(k-1)$-rounds of some subphase $j$ of the $i^{\text{th}}$ phase, where
$i=b\log{n}$.

But once even one core node receives a high color — Core being an expander
(Please refer to Lemma 14) — that high color will start propagating through
the network by means of flooding and will therefore reach every uncrashed node
$v$ within $D(\texttt{Core})$ rounds, where $D(\texttt{Core})$ is the diameter
of Core. By Observation 7, this means that the highest color introduced by the
Byzantine nodes will reach every core node $v$ within
$(\frac{b\log{n}}{2}+k-1)$-rounds.

In other words, for any core node $v$, $v$ will receive no higher color in
round $i$ than what it has already received before. This will violate the
criterion for continuing, in particular, the variable $FlagTerminate$ will
_not_ be assigned the value $0$ (Please see Line 19 of the pseudocode in
Algorithm 2. Therefore $v$ will accept the current value of $i$, which is
$b\log{n}$, to be a correct estimate of $\log{n}$ and will terminate. ∎

Thus we have

######  Lemma 18.

If $i=b\log{n}$, after the $i^{\text{th}}$ phase, the following statement
holds with high probability: All but $o(n)$ of the nodes that were active at
the beginning of this phase accept $i$ to be the correct estimate of
$\log{n}$.

###### Proof.

Follows from Lemma 17 and Lemma 14. ∎

Lemma 18 together with Lemma 11 give us Theorem 1, which is the main result of
this paper.

##  4 Conclusion and Open Problems

In this paper, we take a step towards designing localized, secure, robust, and
scalable algorithms for large-scale networks. We presented a fast (running in
$O(\log^{3}{n})$ rounds) and lightweight (only simple local computations per
node per round) distributed protocol for the fundamental Byzantine counting
problem tolerating $O(n^{1-\delta})$ (for any constant $\delta>0$) Byzantine
nodes while using only small-sized communication messages per round. Our work
leaves many questions open.

A key open problem is to show a lower bound that is essentially tight with
respect to the amount of Byzantine nodes that can be tolerated, or show an
algorithm that can tolerate significantly more Byzantine nodes. Our protocol
works only when the Byzantine nodes are randomly distributed; it will be good
to remove this assumption and design a protocol that works under Byzantine
nodes that are adversarially distributed. Another interesting question is
whether one can improve the approximation factor of the estimate of $\log{n}$
to $1\pm o(1)$.

## References

  * [1] John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, and Eli Upfal.  Storage and search in dynamic peer-to-peer networks.  In Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’13, pages 53–62, New York, NY, USA, 2013. ACM.
  * [2] John Augustine, Gopal Pandurangan, and Peter Robinson.  Fast byzantine agreement in dynamic networks.  In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 74–83, New York, NY, USA, 2013. ACM.
  * [3] John Augustine, Gopal Pandurangan, and Peter Robinson.  Fast byzantine leader election in dynamic networks.  In Yoram Moses, editor, Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 276–291, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
  * [4] John Augustine, Gopal Pandurangan, and Peter Robinson.  Distributed algorithmic foundations of dynamic networks.  SIGACT News, 47(1):69–98, March 2016.
  * [5] John Augustine, Gopal Pandurangan, Peter Robinson, Scott T. Roche, and Eli Upfal.  Enabling robust and efficient distributed computation in dynamic peer-to-peer networks.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 350–369, 2015.
  * [6] John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal.  Towards robust and efficient computation in dynamic peer-to-peer networks.  In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, pages 551–569, Philadelphia, PA, USA, 2012. Society for Industrial and Applied Mathematics.
  * [7] Marc Barthélémy and Luís A. Nunes Amaral.  Small-world networks: Evidence for a crossover picture.  Physical Review Letters, 82:3180–3183, April 1999.
  * [8] Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer.  Brahms: Byzantine resilient random membership sampling.  Computer Networks, 53(13):2340 – 2359, 2009.  Preliminary version in PODC 2008.
  * [9] Bogdan S. Chlebus and Dariusz R. Kowalski.  Locally scalable randomized consensus for synchronous crash failures.  In Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures, SPAA ’09, pages 290–299, New York, NY, USA, 2009. ACM.
  * [10] Devdatt Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, New York, NY, USA, 1st edition, 2009.
  * [11] Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal.  Fault tolerance in networks of bounded degree.  SIAM Journal on Computing, 17(5):975–988, 1988.
  * [12] Amos Fiat and Jared Saia.  Censorship resistant peer-to-peer content addressable networks.  In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pages 94–103, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics.
  * [13] Joel Friedman.  On the second eigenvalue and random walks in random d-regular graphs.  Combinatorica, 11(4):331–362, 1991.
  * [14] A. J. Ganesh, A. M. Kermarrec, E. Le Merrer, and L. Massoulié.  Peer counting and sampling in overlay networks based on random walks.  Distributed Computing, 20(4):267–278, 2007.
  * [15] Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec.  Highly dynamic distributed computing with byzantine failures.  In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 176–183, New York, NY, USA, 2013. ACM.
  * [16] Kirsten Hildrum and John Kubiatowicz.  Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks, pages 321–336.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.
  * [17] Shlomo Hoory, Nathan Linial, and Avi Wigderson.  Expander graphs and their applications.  Bulletin of the American Mathematical Society, 43(4):439–561, 2006\.
  * [18] Keren Horowitz and Dahlia Malkhi.  Estimating network size from local information.  Information Processing Letters, 88(5):237–243, 2003.
  * [19] Sidharth Jaggi, Michael Langberg, Sachin Katti, Tracey Ho, Dina Katabi, Muriel Médard, and Michelle Effros.  Resilient network coding in the presence of byzantine adversaries.  IEEE Trans. Information Theory, 54(6):2596–2603, 2008.
  * [20] Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani.  Fast asynchronous byzantine agreement and leader election with full information.  ACM Transactions on Algorithms, 6(4):68:1–68:28, September 2010\.
  * [21] Valerie King and Jared Saia.  Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary.  Journal of the ACM, 58(4):18:1–18:24, July 2011.
  * [22] Valerie King and Jared Saia.  Faster agreement via a spectral method for detecting malicious behavior.  In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, pages 785–800, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics.
  * [23] Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee.  Scalable leader election.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, pages 990–999, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics.
  * [24] Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee.  Towards secure and scalable computation in peer-to-peer networks.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages 87–98, Washington, DC, USA, 2006. IEEE Computer Society.
  * [25] Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan.  On the complexity of universal leader election.  Journal of the ACM, 62(1):7:1–7:27, March 2015.
  * [26] Ching Law and Kai-Yeung Siu.  Distributed construction of random expander networks.  In Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003, pages 2133–2143, 2003.
  * [27] Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis.  Counting in anonymous dynamic networks under worst-case adversary.  In Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS ’14, pages 338–347, Washington, DC, USA, 2014. IEEE Computer Society.
  * [28] Moni Naor and Udi Wieder.  A Simple Fault Tolerant Distributed Hash Table, pages 88–97.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.
  * [29] Mikhail Nesterenko and Sébastien Tixeuil.  Discovering Network Topology in the Presence of Byzantine Faults, pages 212–226.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
  * [30] Gopal Pandurangan and Amitabh Trehan.  Xheal: a localized self-healing algorithm using expanders.  Distributed Computing, 27(1):39–54, February 2014.
  * [31] Christian Scheideler.  How to spread adversarial nodes?: Rotate!  In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 704–713, New York, NY, USA, 2005. ACM.
  * [32] Tallat M. Shafaat, Ali Ghodsi, and Seif Haridi.  A Practical Approach to Network Size Estimation for Structured Overlays, pages 71–83.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.
  * [33] Håkan Terelius, Damiano Varagnolo, and Karl Henrik Johansson.  Distributed size estimation of dynamic anonymous networks.  In Proceedings of the 51th IEEE Conference on Decision and Control, CDC 2012, December 10-13, 2012, Maui, HI, USA, pages 5221–5227, 2012.
  * [34] Eli Upfal.  Tolerating a linear number of faults in networks of bounded degree.  Information and Computation, 115(2):312 – 320, 1994.
  * [35] Ruud van de Bovenkamp, Fernando A. Kuipers, and Piet Van Mieghem.  Gossip-based counting in dynamic networks.  In NETWORKING 2012 - 11th International IFIP TC 6 Networking Conference, Prague, Czech Republic, May 21-25, 2012, Proceedings, Part II, pages 404–417, 2012.
  * [36] Duncan J. Watts and Steven H. Strogatz.  Collective dynamics of ‘small-world’ networks.  Nature, 393:440–442, June 1998.
  * [37] Nicholas Wormald.  Models of random regular graphs, pages 239–298.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1999.

##  Appendix A $H(n,d)$ random regular graph: definitions and properties

In this section, we formally define the $d$-regular random graph model that we
are assuming and also state and prove some crucial properties that we will use
in the analysis.

###  A.1 Definitions

We assume a random regular graph that is constructed by the union of $d$
random permutations as described below. Call such a random graph model, the
$H(n,d)$ model (or simply H-graphs). This model was also used by Law and Siu
[26] to model Peer-to-Peer networks. A random graph in this model can be
constructed by picking $\frac{d}{2}$ (assume $d$ is even) Hamilton cycles
independently and uniformly at random among all possible Hamilton cycles on
the set of $n$ vertices, and taking the union of these Hamilton cycles. This
construction yields a random $d$-regular graph (henceforth called as a
$H(n,d)$ graph) that can be shown to be an expander with high probability (cf.
Lemma 19). Note that a $H(n,d)$ graph is $d$-regular multigraph whose set of
edges is composed of the $\frac{d}{2}$ Hamilton cycles. Friedman’s [13] result
below (rephrased here for our purposes) shows that a $H(n,d)$ graph is an
expander (in fact, a Ramanujan Expander, i.e., the second smallest eigenvalue
for these random graphs is close to the best possible) with high probability.

######  Lemma 19 ([13, 26]).

A random $n$-node, $d$-regular $H(n,d)$-graph (say, for $d\geq 6$) is an
expander with high probability.

###  A.2 Properties

We next show some basic properties of the $H(n,d)$ random graph which are
needed in the analysis. We show some bounds on the sizes of $B(w,r)$ and
$Bd(w,r)$.

######  Lemma 20.

  1. [(1)]

  2. 1.

$|Bd(w,r)|\leq(d-1)|Bd(w,r-1)|$.

  3. 2.

W.h.p. $|Bd(w,r)|\geq(d-1-o(1))|Bd(w,r-1)|$, for
$1<r<\frac{\log{n}}{2\log{d}}$.

  4. 3.

For some constant $c$ and $c^{\prime}$, $c^{\prime}(d-1)^{r}\leq|B(w,r)|\leq
c(d-1)^{r}$, w.h.p.

  5. 4.

$|B(w,r)|=\Theta(|Bd(w,r)|)$.

###### Proof.

Since the degree of each node is $d$, (1) follows. From (1) it is easy to show
the upper bound on $|B(w,r)|$ in (3).

We next show (2).

We first bound the expected number of neighbours that a node $u\in Bd(w,r-1))$
has in $B(w,r-1)$. The expected number of neighbors of $u$ in $B(w,r)$ is
$\frac{(d-1)(n-|B(w,r-1)|)}{n}\leq(d-1)(1-\frac{\sqrt{n}}{n})$, since
$|B(w,r-1)|<d^{\frac{\log{n}}{2\log{d}}}=\sqrt{n}$. Hence the expected number
of nodes in $Bd(w,r)$ is $|Bd(w,r-1)|(d-1)(1-\frac{\sqrt{n}}{n})$. The high
probability bound can be obtained via a Chernoff bound (one can consider the
choices made by individual nodes as essentially independent if one regards the
“sampling without replacement” due to the permutations. This can be done if
one pretends that the sample is from a set of size $n-\sqrt{n}$ (instead of
$n$). This will not make a difference asymptotically.

The lower bound of (3) follows from (2) and (4) follows from (1), (2), and
(3). ∎

Next we establish the “locally tree-like” property of an $H(n,d)$ random
graph: i.e., for most nodes $w$, the subgraph induced by $B(w,r)$ up to a
certain radius $r$ looks “like a tree”. This is stated more precisely as
follows.

######  Definition 11.

Let $G$ be an $H(n,d)$ random graph and $w$ be any node in $G$. Consider the
subgraph induced by $B(w,r)$ for $r=\frac{\log{n}}{10\log{d}}$. Let $u$ be any
node in $Bd(w,j)$, $1\leq j<r$. $u$ is said to be “typical” if $u$ has only
one neighbor in $Bd(w,j-1)$ and $(d-1)$-neighbors in $Bd(w,j+1)$; otherwise it
is called “atypical”.

######  Definition 12.

We call a node $w$ “locally tree-like” if no node in $B(w,r)$ is atypical. In
other words, $w$ is “locally tree-like” if the subgraph induced by $B(w,r)$ is
a $(d-1)$-ary tree.

The following lemma shows that most nodes in $G$ are locally tree-like.

######  Lemma 21.

In an $H(n,d)$ random graph, with high probability, at least $n-O(n^{0.8})$
nodes are locally tree-like.

###### Proof.

Consider a node $w\in V$. We upper bound the probability that a node in
$B(w,r)$, where $r=\frac{\log{n}}{10\log{d}}$, is atypical. For any $1\leq
j<r$,

$\Pr(u\in B(w,j)\text{ is
atypical})\leq(d-1)\cdot\frac{|B(w,j)|}{n}=O(\frac{1}{n^{0.9}})$,

using the bound that $|B(w,j)|\leq d^{r}$ (the above upper bounds the
probability that $u$ has more than one neighbor in $B(w,j)$, in which case it
is atypical). Hence the probability that there is some node $u$ that is
atypical in $B(w,r)$ is $O(\frac{n^{0.1}}{n^{0.9}})=O(\frac{1}{n^{0.8}})$.
Hence the probability that node $w$ is not locally tree-like is at most
$O(\frac{1}{n^{0.8}})$.

Let the indicator random variable $X_{w}$ indicate the event that node $w$ is
locally tree-like. Let random variable $X=\sum_{w\in V}X_{w}$ denote the
number of nodes that are locally tree-like. By linearity of expectation, using
the above probability bound, it follows that the expected number of nodes in
$G$ that are not locally tree-like is at most $O(n^{0.2})$; in other words,
$E[X]\geq n-O(n^{0.2})$.

To show concentration of $X$, we use Azuma’s inequality ([10], Theorem $5.3$)
as follows. Changing the value of $X_{w}$ affects only the nodes within radius
$r^{\prime}=2r=\frac{2\log{n}}{10\log{d}}$, i.e., at most $n^{0.2}$ nodes and
hence affects $E[X]$ by at most $n^{0.2}$. Thus, we have

$\Pr(|X-E[X]|>n^{0.8})\leq 2\text{exp}(-\frac{n^{\frac{8}{5}}}{n\times
n^{\frac{2}{5}}})=2\text{exp}(-n^{\frac{1}{5}})$.

Hence, with high probability, at least $n-O(n^{0.8})$ nodes are locally tree-
like. ∎

We now show a property that will be useful in our analysis; this follows
immediately from the definition of locally-tree like and the regularity of the
graph.

######  Corollary 1.

Let $G$ be an $H(n,d)$ random graph and consider a node $w$ in $G$. Assume
that $w$ is locally tree-like, i.e., the subgraph induced by $B(w,r)$, where
$r=\frac{\log{n}}{10\log{d}}$ is a tree. For every neighbor $u$ of $w$, the
respective subtrees rooted at $u$ (in the subgraph induced by $B(w,r)$) are
isomorphic; in particular each is a $(d-1)$-ary tree.

##  Appendix B Proof of Lemma 9

We recall that phase $i$ consists of $\alpha_{i}$ subphases, and the subphases
are indexed by $j$.

######  Definition 13.

Let $Failure(i,j)$ be the event that in the $j^{\text{th}}$ subphase of the
$i^{\text{th}}$ phase, $\exists t<i$ such that $k_{t}\geq k_{i}$. That is,
$Failure(i,j)$ is the event that in the $j^{\text{th}}$ subphase of the
$i^{\text{th}}$ phase, the node $v$ receives the maximum color in some round
$t<i$.

In the same vein, we define

######  Definition 14.

$Failure(i)\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\bigcap_{j=1}^{\alpha_{i}}Failure(i,j)$,

######  Observation 8.

We observe that the variable $FlagTerminate$ in the pseudocode (please refer
to Algorithm 1) remains $1$ after all the $\alpha_{i}$ subphases if the event
$Failure(i)$ occurs (Please see Line 17 of Algorithm 1). In other words, a
node $v$ accepts $i$ as the estimate of $\log{n}$ (and thus makes a wrong
decision) if the event $Failure(i)$ occurs. Hence

$\Pr[\text{a {\emph{safe}} node }v\text{ makes a wrong decision in the
}i^{\text{th}}\text{ phase}]\leq\Pr[Failure(i)]$.

######  Observation 9.

$\Pr[Failure(1)]=0$.

##### Induction Hypothesis.

Let $i^{\prime}$ be a positive integer such that $1\leq i^{\prime}<i$. Then

$\Pr[\text{a {\emph{safe}} node }v\text{ makes a wrong decision in the
}{(i^{\prime})}^{\text{th}}\text{phase}]<\frac{\epsilon}{2^{i^{\prime}+1}}$,

where $\epsilon$ is the error parameter.

######  Remark 4.

Observation 9 serves as the basis of induction.

######  Lemma 22.

Let $E_{i,j,1}$ be the event that $k_{t}>2(l_{i-1}-\log{(d-2)})$ for some
$0<t<i$. Then $\Pr[E_{i,j,1}]\leq\frac{d-2}{d(d-1)^{i-1}}$.

###### Proof.

$E_{i,j,1}$ occurs if and only if
$c^{\text{max}}_{B^{*}(v,i-1)}>2(l_{i-1}-\log{(d-2)})$ (please see Line 14 and
Line 16 of Algorithm 1). Thus

$\displaystyle\Pr[E_{i,j,1}]$
$\displaystyle=\Pr[c^{\text{max}}_{B^{*}(v,i-1)}>2(l_{i-1}-\log{(d-2)})]$
$\displaystyle\leq\frac{d-2}{d(d-1)^{i-1}}$ (by Lemma 7)

∎

######  Lemma 23.

Let $E_{i,j,2}$ be the event that $k_{i}\leq
l_{i}-\log{(d-1)}-\log{(l_{i}-\log{(d-1)})}$. Then

$\Pr[E_{i,j,2}]<\frac{\epsilon}{2}+\frac{1}{d(d-1)^{i-1}}$.

###### Proof.

$E_{i,j,2}$ occurs if and only if $c^{\text{max}}_{Bd(v,i)}\leq
l_{i}-\log{(d-1)}-\log{(l_{i}-\log{(d-1)})}$ (please see Line 14 and Line 16
of Algorithm 1).

Let $v^{\text{max}}\in Bd(v,i)$ be the node that generates (or _any_ one of
the nodes that generate) the color $c^{\text{max}}_{Bd(v,i)}$. Let
$E^{\text{bad}}_{i,v^{\text{max}}}$ be the event that $v^{\text{max}}$ went
inactive (i.e., took a wrong decision) in some phase $i^{\prime}<i$. Then

$\displaystyle\Pr[E^{\text{bad}}_{i,v^{\text{max}}}]$
$\displaystyle=\sum_{i^{\prime}=1}^{i-1}\Pr[v^{\text{max}}\text{ went inactive
in phase }i^{\prime}]$
$\displaystyle<\sum_{i^{\prime}=1}^{i-1}\frac{\epsilon}{2^{i^{\prime}+1}}$ (by
the induction hypothesis)
$\displaystyle<\sum_{i^{\prime}=1}^{\infty}\frac{\epsilon}{2^{i^{\prime}+1}}=\frac{\epsilon}{2}\text{.}$

That is,

$\Pr[E^{\text{bad}}_{i,v^{\text{max}}}]<\frac{\epsilon}{2}$ (2)

If $v^{\text{max}}$ is still active in the current phase, i.e.,
$v^{\text{max}}$ did _not_ go inactive in some previous phase $i^{\prime}<i$,
then in order to calculate $\Pr[E_{i,j,2}]$, it is enough to consider
$Bd(v,i)$ _in its entirety_ along with the properties of the geometric
distribution. That is,

$\displaystyle\Pr[E_{i,j,2}\ |\ (E^{\text{bad}}_{i,v^{\text{max}}})^{c}]$
$\displaystyle=\Pr[c^{\text{max}}_{Bd(v,i)}\leq
l_{i}-\log{(d-1)}-\log{(l_{i}-\log{(d-1)})}]]$
$\displaystyle<\frac{1}{d(d-1)^{i-1}}$ (by Lemma 8)

That is,

$\Pr[E_{i,j,2}\ |\
(E^{\text{bad}}_{i,v^{\text{max}}})^{c}]<\frac{1}{d(d-1)^{i-1}}$ (3)

Combining Equations 2 and 3, we get that

$\displaystyle\Pr[E_{i,j,2}]$
$\displaystyle\leq\Pr[E^{\text{bad}}_{i,v^{\text{max}}}]+\Pr[E_{i,j,2}\ |\
(E^{\text{bad}}_{i,v^{\text{max}}})^{c}]$ (thanks to Fact LABEL:fact-standard-
probabilistic-inequality)
$\displaystyle<\frac{\epsilon}{2}+\frac{1}{d(d-1)^{i-1}}\text{.}$

∎

######  Lemma 24.

Let $Success(i,j)$ be the event that

  1. 1.

the maximum color received by node $v$ until the $(i-1)^{\text{th}}$ round of
the $j^{\text{th}}$ subphase of the $i^{\text{th}}$ phase is strictly less
than the maximum color received by node $v$ in the $i^{\text{th}}$ round of
the same subphase of the same phase. That is, in terms of the pseudocode
(please refer to Line 14 and Line 16 of the pseudocode), $k_{t}<k_{i}$,
$\forall t<i$.

And

  2. 2.

$k_{i}>l_{i}-\log{(d-1)}-\log{(l_{i}-\log{(d-1)})}$.

Then $\Pr[Success(i,j)]>1-(\frac{1}{d(d-1)^{i-2}}+\frac{\epsilon}{2})$.

###### Proof.

One of the ways $Success(i,j)$ can happen is if $k_{t}\leq
2(l_{i-1}-\log{(d-2)})$, $\forall t<i$, _and_
$k_{i}>l_{i}-\log{(d-1)}-\log{(l_{i}-\log{(d-1)})}$. Thus

$\displaystyle Success(i,j)\supset(E_{i,j,1}^{c}\cap E_{i,j,2}^{c})$
$\displaystyle\implies\Pr[Success(i,j)]\geq\Pr[E_{i,j,1}^{c}\cap
E_{i,j,2}^{c}]$ $\displaystyle=\Pr[(E_{i,j,1}\cup E_{i,j,2})^{c}]$ (by De
Morgan’s Theorem) $\displaystyle=1-\Pr[E_{i,j,1}\cup E_{i,j,2}]$
$\displaystyle\geq 1-\Pr[E_{i,j,1}]-\Pr[E_{i,j,2}]$
$\displaystyle>1-\frac{d-2}{d(d-1)^{i-1}}-\frac{1}{d(d-1)^{i-1}}-\frac{\epsilon}{2}$
(From Lemma 22 and Lemma 23)
$\displaystyle=1-(\frac{1}{d(d-1)^{i-2}}+\frac{\epsilon}{2})\text{.}$

∎

######  Lemma 25.

$\Pr[Failure(i,j)]<\frac{1}{d(d-1)^{i-2}}+\frac{\epsilon}{2}$.

###### Proof.

We observe that $Failure(i,j)=(Success(i,j))^{c}$ and the result immediately
follows from Lemma 24. ∎

######  Lemma 26.

$\Pr[\text{a {\emph{safe}} node }v\text{ makes a wrong decision in the
}i^{\text{th}}\text{phase}]<\frac{\epsilon}{2^{i+1}}$.

###### Proof.

$\displaystyle\Pr[Failure(i)]=\prod_{j=1}^{\alpha_{i}}\Pr[Failure(i,j)]$
[since the subphases are independent from each other]
$\displaystyle<\prod_{j=1}^{\alpha_{i}}\frac{1}{d(d-1)^{i-2}}\text{ [since
}\Pr[Failure(i,j)]<\frac{1}{d(d-1)^{i-2}}\text{from Lemma \ref{lemma-lower-
end-probability-of-failure-in-phase-i-and-subphase-j}]}$
$\displaystyle=(\frac{1}{d(d-1)^{i-2}})^{\alpha_{i}}$

If we set
$\alpha_{i}\stackrel{{\scriptstyle{\mathsf{def}}}}{{=}}\lceil\frac{\log{(\frac{1}{\epsilon})}+i+1-\log{d}}{(i-2)\log{(d-1)}}\rceil$,
then

$\displaystyle\alpha_{i}\geq\frac{\log{(\frac{1}{\epsilon})}+i+1-\log{d}}{(i-2)\log{(d-1)}}$
$\displaystyle\implies(\frac{1}{d(d-1)^{i-2}})^{\alpha_{i}}\leq\frac{\epsilon}{2^{i+1}}$
$\displaystyle\implies\Pr[Failure(i)]<(\frac{1}{d(d-1)^{i-2}})^{\alpha_{i}}\leq\frac{\epsilon}{2^{i+1}}$

Thanks to Observation 8,

$\Pr[\text{a {\emph{safe}} node }v\text{ makes a wrong decision in the
}i^{\text{th}}\text{ phase}]\leq\Pr[Failure(i)]<\frac{\epsilon}{2^{i+1}}$.

∎