论文标题
网络中的拜占庭的弹性计数
Byzantine-Resilient Counting in Networks
论文作者
论文摘要
我们为{\ em byzantine计数问题}提供了两种分布式算法，这与在存在大量拜占庭节点的情况下估算网络的大小有关。 在$ n $ node网络（$ n $是未知的）中，我们的第一个算法是{\ em确定性}，以$ o（\ log {n}）$ rounds结束，并且是时间 - 最佳。该算法可以（n^{1 -γ}）$最高可忍受（对抗性），以放置拜占庭节点的任何任意小（但固定）的正常数$γ$。它输出了$ \ log {n} $的（固定）恒定因子估计，除$ o（1）$的良好节点的分数（1）$。该算法适用于\ emph {Any}有限度扩展器网络。但是，该算法假定好节点可以在一轮中发送任意的大型消息。 我们的第二个算法是{\ em随机}，大多数好节点仅发送小型消息（在本文中，将小型消息定义为包含$ o（\ log {n}）$ lits的消息，除了最多可恒定的节点ID。该算法在\ emph {几乎全部} $ d $ -REGRACH图中起作用。它最多可容忍$ b（n）= n^{\ frac {1} {2} - ξ} $（请注意$ n $和$ n $和$ b（n）$是任意放置（对抗性）拜能定义的算法（算法）未知的，而$ξ$是任何任意的（固定的）正常数。该算法采用$ O（b（n）\ log^2 {n}）$ rounds，并输出A（固定的）常数因子估计为$ \ log {n} $，概率至少为$ 1- o（1）$。大多数节点（即$ \ geq（1 -β）n $ nodes对于任何任意小（但固定的）正常常数$β$，该估计值是已知的。 为了补充我们的算法，我们还提出了一个不可能的结果，表明如果网络没有足够的顶点扩展，则不可能以任何合理的近似值来估计网络大小，并以任何非平凡的成功概率。
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 - γ})$ arbitrarily (adversarially) placed Byzantine nodes for any arbitrarily small (but fixed) positive constant $γ$. 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} - ξ}$ (note that $n$ and $B(n)$ are unknown to the algorithm) arbitrarily (adversarially) placed Byzantine nodes, where $ξ$ 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 - β)n$ nodes for any arbitrarily small (but fixed) positive constant $β$. 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.
