Technical Report CS-2006-19

Title: RAPID: Reliable Probabilistic Dissemination in Wireless Ad-Hoc
Authors: Vadim Drabkin, Roy Friedman, Gabriel Kliot, and Marc Segal
Abstract: Reliable broadcast is a basic service for many collaborative applications as it provides reliable dissemination of the same information to many recipients. In this paper we propose a novel ReliAble ProbabIlistic Dissemination protocol, called RAPID, for mobile wireless ad-hoc networks that tolerates message omissions, node crashes, and selfish behavior.

The protocol employs a combination of probabilistic forwarding with deterministic corrective measures. The forwarding probability is set based on the observed number of nodes in each one-hop neighborhood, while the deterministic corrective measures include deterministic gossiping as well as timer based corrections of the probabilistic process. These aspects of the protocol are motivated by a theoretical analysis that is also presented in the paper, which explains why this unique protocol design is inherent to ad-hoc networks environments. Since the protocol only relies on local computations and probability, it is highly resilient to mobility and failures. By adding authentication, it can even be made malicious tolerant.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2006
To the main CS technical reports page

Computer science department, Technion