## 5 Our Epidemic Algorithm
### Discard Duplicate Detection Scheme
1 Active Thread n.active() whiletruedo
2 wait\(\delta\) time units if\(n\) is safe, i.e., within its home zonethen
3 // pick a peer neighbor \(p\) repeat
4\(p=n.getRandomHomeNber()\);
5 until\(p\
otin n.DCache\);
6 // send caches to peer
7 send\(<NC,n,n.NCache>\) to \(p\);
8 on receive\(<NC_{rep},p,p.NCache>\)\(n.detectAndUpdateDCache()\);
9\(merge(n.NCache,p.NCache)\);
10 send\(<DC,n,n.DCache>\) to \(p\);
11
12 on receive\(<DC_{rep},p,p.DCache>\)\(merge(n.DCache,p.DCache)\);
13
14
15 end if
16 ifnode\(n\) is unsafethen
17 Random seed \(rs\leftarrow\)baseStation;
18 for\(i\gets 1\)to\(v\)do
19\(verifier_{i}\leftarrow\)\(\{n\)'s home zone\(\}\);
20 // \(n\) contacts \(v\) verifiers
21 send\(<verify,n>\) to \(verifier_{i}\);
22
23
24
25 end if
26
27 end for
28
29 end for
```  
**Algorithm 1**Discard duplicate detection protocol: active thread. Now that both nodes have exchanged each others neighborhood caches (primary epidemic), they each run the routine \(detectAndUpdateDCache()\). This subroutine, as its name implies, traverses both the caches and detects if there are nodes in their home zone with the same ID, but different locations. If found, this node is clearly a duplicate, and this node's ID and location information is inserted into their duplicate cache stores. Both \(n\) and \(p\) now merge each others neighborhood caches using the subroutine \(merge(\cdot,\cdot)\) as indicated in Line \(11\) and Line \(6\) of the active and passive threads in Algorithms 1 and 2, respectively. This is merely an independent, shuffling process as described here: for a neighborhood cache of size \(c\), first, \(c-1\) randomly chosen entries from the collection of both caches (of size \(2c\)) are chosen to populate each participating node's \(NCache\) repository. Next, each node also inserts its own ID and location into this cache. This step is important to ensure that the cache gets populated with each node's own entry prior to cache exchanges and also essential to bootstrap this exchange process. Next, a similar cache exchange and merge procedure for the duplicate caches is performed by \(n\) and \(p\), as indicated in Lines 12-14 and 8-12 of the active and passive threads respectively (secondary epidemic). We now discuss the procedure when node \(n\) is located outside its home zone. Since the above cache exchange process was limited to interactions among genuine nodes within the home zone, nodes outside their home zone will need to provide evidence of their authenticity in order to participate in network activities. As noted earlier, node \(n\) is aware that it is located outside its home zone and follows the procedure discussed in this paragraph, listed in Lines 16-22 of the active thread in Algorithm 1. In each time period, the base station broadcasts a random seed that is unique for every time period. Once node \(n\) receives this seed, it determines which nodes in its home zone act as verifiers at this time instant and contacts them. Having determined the identities of the verifier nodes, node \(n\) sends its signed \(<verify,n>\) message to these verifier nodes and awaits their response. The \(verify\) message contains the ID and the \((x,y)\) location of the sender node. Having received this message, the verifier checks to see if this sender at this location is a duplicate. This is accomplished by simply checking if this sender is an element of its \(DCache\), the duplicate cache. The verifier nodes also check to ensure that they are indeed chosen to be the verifier for this time period. In our algorithm, we require that each node outside its home zone approaches \(v\) verifiers, which is a parameter to be determined later to balance security and communication cost. Upon receiving the \(<verify,n>\) message (Lines 13-21 of the passive thread), \(p\) checks if it is a verifier, then responds to \(n\) with the appropriate signed response. If node \(n\) is not an element of the verifier's duplicate cache, a signed \(genuine\) response is sent; otherwise, a signed \(duplicate\) response is sent.