Title:Byzantine-Resilient Counting in Networks

Abstract:We present two distributed algorithms for the {\em Byzantine counting problem}, which is concerned with estimating the size of a network in the presence of a large number of Byzantine nodes.
In an $n$-node network ($n$ is unknown), our first algorithm, which is {\em deterministic}, finishes in $O(\log{n})$ rounds and is time-optimal. This algorithm can tolerate up to $O(n^{1 - \gamma})$ arbitrarily (adversarially) placed Byzantine nodes for any arbitrarily small (but fixed) positive constant $\gamma$. It outputs a (fixed) constant factor estimate of $\log{n}$ that would be known to all but $o(1)$ fraction of the good nodes. This algorithm works for \emph{any} bounded degree expander network. However, this algorithms assumes that good nodes can send arbitrarily large-sized messages in a round.
Our second algorithm is {\em randomized} and most good nodes send only small-sized messages (Throughout this paper, a small-sized message is defined to be one that contains $O(\log{n})$ bits in addition to at most a constant number of node IDs.). This algorithm works in \emph{almost all} $d$-regular graphs. It tolerates up to $B(n) = n^{\frac{1}{2} - \xi}$ (note that $n$ and $B(n)$ are unknown to the algorithm) arbitrarily (adversarially) placed Byzantine nodes, where $\xi$ is any arbitrarily small (but fixed) positive constant. This algorithm takes $O(B(n)\log^2{n})$ rounds and outputs a (fixed) constant factor estimate of $\log{n}$ with probability at least $1 - o(1)$. The said estimate is known to most nodes, i.e., $\geq (1 - \beta)n$ nodes for any arbitrarily small (but fixed) positive constant $\beta$.
To complement our algorithms, we also present an impossibility result that shows that it is impossible to estimate the network size with any reasonable approximation with any non-trivial probability of success if the network does not have sufficient vertex expansion.