## 2 Prior Work  
In this section, we survey some of the prior work in duplicate node detection in stationary sensor networks. While we outline some of the most important approaches and contributions in this area, this survey is not to be treated as an exhaustive overview of prior and related work. The first schemes to appear in the literature on detecting replica nodes in a wireless sensor network were centralized schemes [2]. In these schemes, all of the nodes in the network were required to send their neighbors' identities and claimed locations to a central base station. The base station would then check for replicas using these neighborhood lists and detect duplicates followed by broadcasting relevant revocation messages to the network. Clearly, such a solution, despite its simplicity and accuracy, is extremely expensive in terms of communication. Furthermore, it creates a central point of failure and leads to energy depletion of the nodes immediately surrounding the base station. Therefore, distributed solutions are strongly preferred to address this problem. Other variants of such centralized solutions are discussed in [9, 10, 11]. Another scheme that is almost a folklore distributed detection scheme outlined in the research literature is a naive distributed detection scheme called node-to-network broadcasting (N2 NB) [10]. Each node floods the network with an authenticated broadcast message containing its claimed location and stores the location claims of its neighbors. Upon receiving a conflicting claim (a node identity residing in multiple locations), this whistle-blower node signals the detection of a clone and alerts the rest of the network. Clearly, this scheme has a 100% detection rate, but incurs a high communication and storage cost. Wireless sensor motes have stringent memory and energy constraints, and thus, this solution is not satisfactory. Subsequently, other similar broadcast schemes were developed that trade detection accuracy for communication and storage costs [12]. Localized voting approaches were then proposed, which remedied some of these energy and memory issues. Using a voting mechanism, neighbors are required to reach a consensus on the legitimacy of a given node. However, these neighborhood voting protocols [1, 5] failed to detect replicas distributed in disjoint neighborhoods of the network. By deploying replicas at least two hops away from each other, an adversary can evade detection from such schemes. The first distributed and randomized replica detection schemes were proposed by [PERSON] _et al._[10]. Motivated by emergent algorithms [13], they proposed two related schemes. In these schemes, nodes broadcast their neighbors' identities and locations to other nodes in the network. They rely on special witness nodes in the network for duplicate detection. When a particular sensor node receives conflicting location claims and realizes that a specific node identity exists in more than one location, such a node becomes a witness for this duplicate. Once detected, the witness nodes broadcast this information to the rest of the network, and an appropriate revocation mechanism is triggered. The first scheme, called randomized-multicast, distributes location claims to a randomly-selected set of nodes in the network. With an appropriate choice of parameters, they show that the birthday paradox ensures that a collision occurs with high probability, thereby creating witness nodes. The second protocol, called line-selected multicast, takes advantage of the routing topology of the network to select witness nodes. They show that line-selected multicast is more efficient that randomized-multicast in terms of communication and storage requirements. Inspired by the emergent algorithmic approaches, [PERSON] _et al._[14, 15] proposed a randomized, efficient and distributed algorithm called REDthat improves upon the communication and storage costs and the detection accuracy of the line-selected multicast protocol proposed by [PERSON] _et al._[10].