Communication cost of consensus for nodes with limited memory

Abstract

Motivated by applications in wireless networks and the Internet of Things, we consider a model ofnnodes trying to reach consensus with high probability on their majority bit. Each nodeiis assigned a bit at time 0 and is a finite automaton withmbits of memory (i.e.,2mstates) and a Poisson clock. When the clock ofirings,ican choose to communicate and is then matched to a uniformly chosen nodej. The nodesjandimay update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that, whenm>3⁡log⁡log⁡log(n), consensus can be reached with linear communication cost, but this is impossible ifmlog⁡log⁡log(n). A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.

Document Details

• Document Type: Pub Defense Publication
• Publication Date: Mar 04, 2020
• Source ID: 10.1073/pnas.1912980117

Entities

People

• Gireeja Ranade
• Giulia Fanti
• Nina Holden
• Yuval Peres

Organizations

• Army Research Office
• Carnegie Mellon University
• ETH Zurich
• ETH Zurich Foundation
• Microsoft Research
• National Science Foundation

Tags

Fields of Study

• Computer science

Readers

• Distributed Systems and Data Platform Development
• Mathematical Modeling and Probability Theory.
• Systems Analysis and Design

Technology Areas

• 5G
• 5G - Internet of Things