Related Experiment Video
Updated: Sep 29, 2025
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
675
Simple Majority Consensus in Networks with Unreliable Communication
Ran Tamir1, Ariel Livshits2, Yonatan Shadmi2
1Signal and Information Processing Laboratory, ETH Zürich, 8092 Zürich, Switzerland.
Entropy (Basel, Switzerland)
|March 25, 2022
Summary
The Simple Majority Protocol (SMP) efficiently solves binary majority consensus in distributed systems, even with message loss. It guarantees consensus in three rounds, or fewer with faster opinion divergence.
Area of Science:
- Computer Science
- Distributed Systems
- Theoretical Computer Science
Background:
- Coordination problems are fundamental in distributed systems.
- Binary majority consensus is a key coordination challenge.
- Message loss complicates consensus protocols.
Purpose of the Study:
- Analyze the performance of the Simple Majority Protocol (SMP) for binary majority consensus.
- Evaluate SMP's resilience to probabilistic message loss.
- Determine the number of communication rounds required for consensus.
Main Methods:
- Probabilistic analysis of a fully-connected network of 2n agents.
- Mathematical modeling of message loss impact.
- Asymptotic analysis as the network size (n) approaches infinity.
Main Results:
- SMP achieves consensus in three rounds with probability approaching 1 for large networks.
- Consensus on the majority opinion is reached in two rounds if opinion difference grows at rate n.
- Consensus is achieved in one round if opinion difference grows faster than n, with exponentially fast convergence.
Conclusions:
- The Simple Majority Protocol is highly efficient for binary majority consensus.
- The number of rounds depends on the initial opinion distribution.
- The identified round requirements are both sufficient and necessary.
Related Concept Videos
01:25Multimachine Stability
243
Multimachine stability analysis is crucial for understanding the dynamics and stability of power systems with multiple synchronous machines. The objective is to solve the swing equations for a network of M machines connected to an N-bus power system.
In analyzing the system, the nodal equations represent the relationship between bus voltages, machine voltages, and machine currents. The nodal equation is given by:
In analyzing the system, the nodal equations represent the relationship between bus voltages, machine voltages, and machine currents. The nodal equation is given by:
243
00:59Propagation of Uncertainty from Random Error
1.2K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.2K
01:10Propagation of Uncertainty from Systematic Error
956
The atomic mass of an element varies due to the relative ratio of its isotopes. A sample's relative proportion of oxygen isotopes influences its average atomic mass. For instance, if we were to measure the atomic mass of oxygen from a sample, the mass would be a weighted average of the isotopic masses of oxygen in that sample. Since a single sample is not likely to perfectly reflect the true atomic mass of oxygen for all the molecules of oxygen on Earth, the mass we obtain from this...
956
01:25Distribution Reliability and Automation
169
Distribution reliability in electrical power systems is critical for ensuring an uninterrupted power supply to consumers at minimal cost. According to IEEE Standard Terms, reliability is the probability that a device will function without failure over a specified time period or amount of usage. For electric power distribution, this translates to maintaining continuous power supply and addressing customer concerns over power outages. Several indices, as defined by IEEE Standard 1366-2012, are...
169
00:52Social Proof
29.0K
Social proof is a form of persuasion based on comparison and conformity. People compare their behavior and actions to what others are doing and will change to conform to do what their peers do.
29.0K
01:21Pilot and Numeric Relaying
148
Pilot relaying is a type of differential protection used in power systems. It compares electrical quantities at the terminals of equipment via a communication channel instead of direct relay interconnection. This method is essential for transmission lines where the terminals are far apart, typically up to 80 km for lines with 69 to 115 kV ratings. Four types of communication channels are used for pilot relaying:
148