  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.
  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.
