Analysis of an epidemic dissemination protocol for ad hoc networks

We have worked on an epidemic dissemination protocol to maintain soft-state in a decentralized, peer-to-peer fashion, in ad hoc networks. This protocol is an enhancement of passive distributed indexing (PDI) method proposed by Lindemann and Waldhorst. We have enhanced PDI in order to reduce the number of broadcast messages when the search for an item may span several hops. Three enhancements are proposed: (i) lazy query propagation to delay the propagation of query messages such that local responses can inhibit unnecessary search. (ii) Quench waves to stop an already initiated query propagation when still possible. Decision rules based solely on local information determine whether to start a quench wave or not. (iii) The use of multi-point relay (MPR) or similar protocol and algorithm, to reduce redundant broadcast messages.