This disclosure describes a noise-tolerant gossip protocol suitable for a network of nodes communicating via noisy channels such as radio frequency or ultrasonic waves. The probability of error between two nodes is modeled as increasing with inter-node distance, mirroring the decay of electromagnetic or acoustic energy with distance. A node with information to transmit randomly selects one or more nearby nodes for reception, with the selection weighted towards lower error probability (geographically closer) nodes. A node that receives information retransmits the information to other nodes after confirming the veracity of the information by performing redundancy correction, e.g., by performing a majority vote over multiple receptions of the same information. The described gossip protocol achieves rapid, accurate, and stable convergence, e.g., each node of a network with geographically separated nodes rapidly receives the same, true information, even though the inter-node channels are of varying, possibly low, reliabilities.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.