About
Contact
Help
Sending publications
How to publish
Advanced Search
View Item 
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse byCommunities and CollectionsDateAuthorsTitlesSubjectsThis CollectionDateAuthorsTitlesSubjects

My Account

Login to my accountRegister
Biblioteca Digital - Universidad de Chile
Revistas Chilenas
Repositorios Latinoamericanos
Tesis LatinoAmericanas
Tesis chilenas
Related linksRegistry of Open Access RepositoriesOpenDOARGoogle scholarCOREBASE
My Account
Login to my accountRegister

Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory

Artículo
Thumbnail
Open/Download
IconBecker_Florent.pdf (185.5Kb)
Publication date
2009
Metadata
Show full item record
Cómo citar
Becker, Florent
Cómo citar
Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory
.
Copiar
Cerrar

Author
  • Becker, Florent;
  • Rajsbaum, Sergio;
  • Rapaport Zimermann, Iván;
  • Rémila, Eric;
Abstract
Consider a system composed of n sensors operating in synchronous rounds. In each round an input vector of sensor readings x is produced, where the i-th entry of x is a binary value produced by the i-th sensor. The sequence of input vectors is assumed to be smooth: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging consensus function f. This function returns, in each round, a representative output value v of the sensor readings x. Assuming that at most t entries of the vector can be erroneous, f is required to return a value that appears at least t + 1 times in x. The instability of the system is the number of output changes over a random sequence of input vectors. Our first result is to design optimal instability consensus systems with and without memory. Roughly, in the memoryless case, we show that an optimal system is D0, that outputs 1 unless it is forced by the faulttolerance requirement to output 0 (on vectors with t or less 1’s). For the case of systems with memory, we show that an optimal system is D1, that initially outputs the most common value in the input vector, and then stays with this output unless forced by the fault-tolerance requirement to change (i.e., a single bit of memory suffices). Our second result is to quantify the gain factor due to memory by computing cn(t), the number of decision changes performed by D0 per each decision change performed by D1. If t = n 2 the system is always forced to decide the simple majority and, in that case, memory becomes useless. We show that the same type of phenomenon occurs when n 2 − t is constant. Nevertheless, as soon as n 2 − t pn, memory plays an important stabilizing role because the ratio cn(t) grows like (pn). We also show that this is an upper bound: cn(t) = O(pn) for every t. Our results are average case versions of previous works where the sequence of input vectors was assumed to be, in addition to smooth, geodesic: the i-th entry of the input vector was allowed to change at most once over the sequence. It thus eliminates some anomalies that ocurred in the worst case, geodesic instability setting.
Patrocinador
Partially supported by Programs Conicyt “Anillo en Redes”, Instituto Milenio de Dinámica Celular y Biotecnología and Ecos-Conicyt, and IXXI (Complex System Institute, Lyon).
Identifier
URI: https://repositorio.uchile.cl/handle/2250/125340
Collections
  • Artículos de revistas
xmlui.footer.title
31 participating institutions
More than 73,000 publications
More than 110,000 topics
More than 75,000 authors
Published in the repository
  • How to publish
  • Definitions
  • Copyright
  • Frequent questions
Documents
  • Dating Guide
  • Thesis authorization
  • Document authorization
  • How to prepare a thesis (PDF)
Services
  • Digital library
  • Chilean academic journals portal
  • Latin American Repository Network
  • Latin American theses
  • Chilean theses
Dirección de Servicios de Información y Bibliotecas (SISIB)
Universidad de Chile

© 2020 DSpace
  • Access my account