## 4 Epidemic Diffusion  
Our goal in this paper is to explore the potential of emergent, epidemic algorithms on detecting duplicate nodes in a wireless sensor network and to design an appropriate detection algorithm using these algorithmic techniques for this problem setting. Epidemic algorithms and their applications to distributed computing were popularized by [PERSON] _et al._[35] as applied to the problem of maintaining distributed, replicated databases. These algorithms have been recognized by the distributed computing community as a robust, reliable and scalable means to disseminate information among the distributed computing nodes, similar to the manner in which an epidemic spreads through a distributed, connected population of people. They have also been applied in several other areas of distributed computing, such as load balancing, topology management protocols, audio and video streaming, computation of a large set of aggregate functions, network and resource monitoring, failure detection, to name a few. A survey of epidemic algorithms and their applications to distributed computing can be found in the work presented in [36, 37]. Of interest to note is the fact that our problem setting may be viewed as the dual problem of efficient rule collection of network coded data that has been studied extensively in the literature [38]. In the efficient data rule collection problem over sensor networks, one tries to improve data resilience to node failures and data collection by mobile sensor mules by employing erasure coding, such that a small subset of the sensor nodes stores some linear combination of all of the network data. In contrast, we attempt to disseminate sensed network data among many sensor nodes using epidemic gossip so as to enhance duplicate detection. In this paper, to the best of our knowledge, we initiate the study of using these techniques to detect duplicate nodes in a wireless sensor network and show that epidemic algorithmic techniques offer a very natural approach to solve this problem. To this end, we design our duplicate detection scheme, which we call **Disccard**, as a variant of a couple of interesting epidemic algorithms discussed below. Furthermore, we designed our scheme to ensure that it has an effective and robust replica detection capability with low communication, computation and storage overheads, as this is imperative in a wireless sensor network to conserve node energy and make efficient use of limited node storage and processing power. In our problem setting of detecting replicas in a wireless sensor network, our aim is to design schemes that enable sensor nodes to identify the duplicate nodes in the network by gossiping and exchanging information with each other. To this end, we have identified two primary tasks that need to be accomplished through the design of appropriate epidemic mechanisms. We list these two tasks below and discuss them briefly below. 1. Primary epidemic: Sensor nodes should detect a duplicate node in their midst by exchanging neighborhood information with each other. 2. Secondary epidemic: Once a duplicate node has been detected by a sensor node, this information should be disseminated to the rest of the nodes in the network as soon as possible. We call the above two epidemics primary and secondary merely to reflect the fact that the secondary epidemic (identity of the duplicate nodes) can be spread only after the primary epidemic algorithm has been successful in detecting a duplicate node by exchanging the neighborhood information. In this paragraph, we discuss, very briefly, the goals of each of these epidemic mechanisms and relegate the details to Section 5. Each sensor node maintains a neighborhood cache of a particularsize. This cache reflects the nodes' knowledge of its neighbors. This cache not only maintains information about the nodes' immediate neighbors, but also of the nodes beyond its communication radius.