## 1 Introduction  
A sensor network is composed of a number of low-cost nodes typically scattered in a sensor field. The purpose of these nodes is to sense the parameters of interest and report their findings, either to the base station or to share this information with their neighbors. Nodes join the network by initiating simple neighbor discover protocols [1; 2; 3; 4] without requiring any registration procedure with a base station. Sensor nodes, by design, are low-cost devices and, to this end, are built and deployed without any tamper-resistant features. This implies that an adversary can obtain access to the contents of a sensor node and subsequently duplicate the node and deploy the replicas back in the network with reasonable ease. If left undetected, such duplicate nodes can defeat or subvert the goals of the network. For instance, with a sufficient number of duplicates in the network, an adversary can inject false data into the network, suppress legitimate data, partition or disconnect the network and subsequently launch other malicious attacks. Clearly, detection of these replicated nodes in the network is of paramount importance and has garnered significant interest from the research community. In this paper, we study the problem of detecting these replica nodes in a group-deployed, two-dimensional, stationary wireless sensor network and present a duplicate detection scheme, which respects the constraints imposed by the sensor nodes and the wireless sensor network. Hence, in our protocol, we aim to minimize the communication, storage and computation costs incurred by individual nodes and the network as a whole, while achieving robust detection and security against the adversary, whose objective is to thwart detection. One of our goals in this paper is to study the fitness of epidemic algorithms in detecting replica nodes in a sensor network. To this end, we propose a novel distributed, randomized sensor duplicate detection algorithm called **Discard** to detect node replicas in group-deployed wireless sensor networks. Our scheme is built using an epidemic message propagation paradigm. We show that our epidemic-gossip-based scheme exhibits emergent properties, _i.e._, characteristic properties that are manifested only as a consequence of interactions among members of a group and absent otherwise. We designed **Discard** in a very organic manner: our idea was to design a protocol that emulates the natural workings of a sensor network. As noted above, sensor nodes communicate with each other periodically, sending and receiving heart-beat messages, membership messages, neighbor discovery messages and the sensed data from the environment. Our scheme is designed in harmony with the natural processes already at play in the network. This ensures that **Discard** can be integrated into a sensor network in a seamless fashion. Epidemic schemes have found diverse applications in distributed computing: load balancing, topology management, audio and video streaming, computing aggregate functions, failure detection, network and resource monitoring, to name a few. To the best of our knowledge, our algorithm is the first attempt at exploring the potential of this paradigm to detect replicas in a wireless sensor network. Through analysis and simulation, we show that our scheme achieves robust replica detection with substantially lower communication, computational and storage requirements than prior schemes in the literature. Our goal is to test the potential of using epidemic algorithms in sensor network duplicate node detection, and we show that this technique is very naturally suited not only for sensor networks, but several other classes of networks, as well. At this point, we would like to note that our work is focused only on detecting duplicates in the network. To make this clear, in this paragraph, we mention a couple of problems that are (in spirit) related to node replica detection. The Sybil attack in sensor networks refers to the ability of a sensor node to claim multiple identities.