English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Efficient Counting with Optimal Resilience

Lenzen, C., & Rybicki, J. (2015). Efficient Counting with Optimal Resilience. Retrieved from http://arxiv.org/abs/1508.02535.

Item is

Files

show Files
hide Files
:
arXiv:1508.02535.pdf (Preprint), 489KB
Name:
arXiv:1508.02535.pdf
Description:
File downloaded from arXiv at 2015-09-24 12:38
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Lenzen, Christoph1, Author           
Rybicki, Joel2, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2015-08-112015
 Publication Status: Published online
 Pages: 17 pages, 2 figures
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1508.02535
URI: http://arxiv.org/abs/1508.02535
BibTex Citekey: LenzenarXiv2015
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show