Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC

Résumés déjà disponibles dans d'autres langues : en

Auteurs : Kokouvi Hounkanli, Avery Miller, Andrzej Pelc

Résumé : Consensus is one of the fundamental tasks studied in distributed computing. Processors have input values from some set $V$ and they have to decide the same value from this set. If all processors have the same input value, then they must all decide this value. We study the task of consensus in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the $\mathit{beeping\ model}$. Communication proceeds in synchronous rounds. Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i.e., stay silent, or beep, i.e., emit a signal. In each round, a fault can occur in the channel independently with constant probability $0<p<1$. In a fault-free round, an awake processor hears a beep if it listens in this round and if one or more other processors beep in this round. A processor still dormant in a fault-free round in which some other processor beeps is woken up by this beep and hears it. In a faulty round nothing is heard, regardless of the behaviour of the processors. An algorithm working with error probability at most $\epsilon$, for a given $\epsilon>0$, is called $\epsilon$-$\mathit{safe}$. Our main result is the design and analysis, for any constant $\epsilon>0$, of a deterministic $\epsilon$-safe consensus algorithm that works in time $O(\log w)$ in a fault-prone MAC, where $w$ is the smallest input value of all participating processors. We show that this time cannot be improved, even when the MAC is fault-free. The main algorithmic tool that we develop to achieve our goal, and that might be of independent interest, is a deterministic algorithm that, with arbitrarily small constant error probability, establishes a global clock in a fault-prone MAC in constant time.

Soumis à arXiv le 26 Aoû. 2015

Posez des questions sur cet article à notre assistant IA

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

La licence de l'article ne nous permet pas de nous appuyer sur son contenu et l'assistant IA ne peut se servir que des métadonnées de l'article plutôt que de l'article complet.

Instructions pour utiliser l'assistant IA ?

Résultats du processus de synthèse de l'article arXiv : 1508.06583v1

La licence de cet article ne nous permet pas de nous appuyer sur son contenu et le processus de synthèse est ici effectué avec les métadonnées de l'article plutôt qu'avec l'article en tant que tel.

Le résumé n'est pas encore prêt
Créé le 22 Sep. 2023
Disponible dans d'autres langues : en

Évaluez la qualité du contenu généré par l'IA en votant

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Le résumé précédent a été créé il y a plus d'un an et peut être réexécuté (si nécessaire) en cliquant sur le bouton Exécuter ci-dessous.

La licence de cet article spécifique ne nous permet pas de nous appuyer sur son contenu et les outils de synthèse seront exécutés en utilisant les métadonnées de l'article plutôt que l'article complet. Cependant, l'outil produira quand même un bon résultat, et vous pouvez également essayer nos outils sur des papiers avec des licences plus ouvertes.

Articles similaires résumés avec nos outils d'IA

Naviguez à travers encore plus d'articles similaires en utilisant une

représentation arborescente

Recherchez des articles similaires (en version bêta)

En cliquant sur le bouton ci-dessus, notre algorithme analysera tous les articles de notre base de données pour trouver le plus proche en fonction du contenu des articles complets et pas seulement des métadonnées. Veuillez noter que cela ne fonctionne que pour les articles pour lesquels nous avons généré des résumés et que vous pouvez le réexécuter de temps en temps pour obtenir un résultat plus précis pendant que notre base de données s'agrandit.

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.