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

**Authors:** Kokouvi Hounkanli, Avery Miller, Andrzej Pelc  
**arXiv:** [1508.06583](https://arxiv.org/abs/1508.06583)  
**Date:** 2015-08-26  
**Summary page:** https://www.summarizepaper.com/en/paper/1508.06583v1/

## Key points

- Consensus is a fundamental task in distributed computing
- Focus on achieving consensus in a Multiple Access Channel (MAC) susceptible to faults
- Communication model used is the "beeping model" operating in synchronous rounds
- Awake processors can listen silently or emit a beep during each round
- Constant probability of experiencing a fault in the channel during each round
- Awake processor hears a beep if it listens and if other processors emit beeps in the same round
- Dormant processor can be awakened by a beep from another processor during a fault-free round
- Goal is to design and analyze deterministic consensus algorithm with error probability not exceeding threshold ε (>0)
- Algorithm should work within time complexity O(log w), where w represents smallest input value among all participating processors
- Time complexity cannot be improved even when MAC is fault-free
- Researchers develop algorithmic tool for global synchronization with small constant error probability within constant time in fault-prone MAC
- Tool may have independent applications beyond achieving consensus
- Research contributes to understanding efficient and reliable consensus in distributed systems under weak communication models with potential faults.

## Summary

In the field of distributed computing, consensus is a fundamental task that involves processors reaching an agreement on a common value. In this study, the focus is on achieving consensus in a Multiple Access Channel (MAC) that is susceptible to faults. The communication model used in this scenario is known as the "beeping model," which operates in synchronous rounds. In the beeping model, processors can wake up spontaneously in different rounds determined by an adversary. During each round, an awake processor has two options: it can either listen silently or emit a signal known as a beep. However, there is a constant probability of experiencing a fault in the channel during each round. If a round is fault-free, an awake processor will hear a beep if it listens and if one or more other processors emit beeps in that same round. Additionally, if a dormant processor is still inactive during a fault-free round where another processor emits a beep, it will be awakened by that beep and hear it. The goal of this study is to design and analyze a deterministic consensus algorithm that ensures error probability does not exceed a given threshold ε (>0). This algorithm should work within time complexity O(log w), where w represents the smallest input value among all participating processors. Notably, even when the MAC is fault-free, it has been shown that this time complexity cannot be improved. To achieve their objective, the researchers develop an algorithmic tool capable of establishing global synchronization with arbitrarily small constant error probability within constant time in a fault-prone MAC. This tool may have independent applications beyond its use in achieving consensus. Overall, this research contributes to understanding how consensus can be achieved efficiently and reliably in distributed systems operating under weak communication models with potential faults.