9
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Efficient counting with optimal resilience

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In the synchronous \(c\)-counting problem, we are given a synchronous system of \(n\) nodes, where up to \(f\) of the nodes may be Byzantine, that is, have arbitrary faulty behaviour. The task is to have all of the correct nodes count modulo \(c\) in unison in a self-stabilising manner: regardless of the initial state of the system and the faulty nodes' behavior, eventually rounds are consistently labelled by a counter modulo \(c\) at all correct nodes. We provide a deterministic solution with resilience \(f<n/3\) that stabilises in \(O(f)\) rounds and every correct node broadcasts \(O(\log^2 f)\) bits per round. We build and improve on a recent result offering stabilisation time \(O(f)\) and communication complexity \(O(\log^2 f /\log \log f)\) but with sub-optimal resilience \(f = n^{1-o(1)}\) (PODC 2015). Our new algorithm has optimal resilience, asymptotically optimal stabilisation time, and low communication complexity. Finally, we modify the algorithm to guarantee that after stabilisation very little communication occurs. In particular, for optimal resilience and polynomial counter size \(c=n^{O(1)}\), the algorithm broadcasts only \(O(1)\) bits per node every \(\Theta(n)\) rounds without affecting the other properties of the algorithm; communication-wise this is asymptotically optimal.

          Related collections

          Author and article information

          Journal
          2015-08-11
          Article
          1508.02535
          fd72a080-6eb4-4f47-824e-5b40ed7261df

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          17 pages, 2 figures
          cs.DC

          Networking & Internet architecture
          Networking & Internet architecture

          Comments

          Comment on this article