## 5 Our Epidemic Algorithm
### Discard Duplicate Detection Scheme  
In this section, we describe the functionality of the **Discard** algorithm in detail. The pseudocode presented in Algorithms 1 and 2 is modeled by two distinct threads executed at each sensor node. For the sake of exposition, we describe the algorithm as an interaction between two sensor nodes \(n\) and \(p\). In particular, we will discuss the interaction between the active thread of node \(n\) and the passive thread of node \(p\). The primary distinction between these two threads is captured by the fact that while the active thread actively takes the initiative to communicate, the passive thread merely responds to incoming messages. The active thread repeats itself periodically, denoted by \(\delta\) time units in the algorithm. Each sensor node maintains two caches, the neighborhood cache and the duplicate cache. For instance, the neighborhood cache of node \(n\) contains information about \(n\)'s neighbors and their location, _i.e._, their \((x,y)\) coordinates. Node \(n\)'s duplicate cache contains information (ID and no more than two distinct locations) about the duplicate nodes in \(n\)'s home zone that \(n\) is aware of at a particular time instant. The structure of these caches and the interaction between two sensor nodes \(n\) and \(p\) is depicted in Figure 2. The neighborhood cache is of size \(c\), and the duplicate cache is of size \(d\). The effect of the interaction between these two threads is essentially a continuous random shuffling of the caches of the sensor nodes within the home zones of the sensor network, with requests and replies exchanged between the nodes. Here, we discuss the algorithm in terms of the parameters \(\delta,c,\text{ and }d\) and relegate the discussion of the choice of these parameters to Section 6. Let us now discuss the interaction between the two threads: the active thread of node \(n,\ \ n.active()\) and the passive thread of node \(p,\ \ p.passive()\), the two nodes that are involved in the cache exchange and duplicate detection process. In this paragraph, we discuss the procedure where node \(n\) is located within its home zone. We use \(NCache\) and \(DCache\) to refer to the neighborhood and duplicate cache of a sensor node. Furthermore, we use the dotted notation, borrowed from object-oriented programming, to refer to membership. Hence, \(n.Ncache\) and \(p.Dcache\) refer to the neighborhood cache of node \(n\) and the duplicate cache of node \(p\), respectively. At every \(\delta\) time interval, the active thread of node \(n\) seeks out an immediate, genuine (non-duplicate) neighbor \(p\) in its home zone with which to interact. By an immediate neighbor, we mean a sensor node \(p\) that is within the communication radius of node \(n\) and is also within \(n\)'s home zone. Furthermore, it is important to note that \(n\) will ensure that the chosen node \(p\) is genuine (not a duplicate), _i.e._, \(p\) is not contained in \(n\)'s duplicate cache. Our reason for enforcing nodes to interact only with immediate, in-home-zone nodes stems not only from the fact that we need to conserve energy during the cache exchange process, but also because each home zone is tasked with the responsibility of detecting duplicate nodes from their territory in the entire network. This division of labor, as we will show, has a profound effect on the communication cost. Having chosen a peer node \(p\), \(n\) sends its neighborhood cache \(<NC,n,n.NCache>\) to \(p\) (Line \(8\) of \(n.active()\) in Algorithm 1). The passive thread of node \(p\) responds to this message with its own neighborhood cache \(<NC_{rep},p,p.NCache>\) after ensuring that \(n\) is not a duplicate, as indicated by its duplicate cache records, (Line \(4\) of \(p.passive()\) in Algorithm 2). The message format \(<NC,n,n.NCache>\) follows the structure \(<\) type of message, sender, content \(>\), and the subscript \(rep\) stands for reply. ```
Data: Protocol run by sensor nodes \(n\) and \(p\). Result: Caches updated and duplicates detected.