I have a doubt about how we update the entries of the cache: I understand that after selecting a peer, the two nodes exchange their caches, merge them, and then remove the oldest entries such that the cache has a predefined size c.
My question is: when updating, should we overwrite the previous entries from the same peer, if there was already one in the cache? Or should we just add another entry and maybe have multiple entries from the same peer?
I ask this question because it seems that, if c = 20 ~ 50, after some simulation steps, a grid graph becomes disconnected (in other words, more than 1 connected components). Allowing multiple entries of the same peer cause each node to exploit circa half of its cache to get its neighbors, since the observed average degree of the nodes is ~c/2 (not allowing multiple edges between two nodes).
The paper "Newscast Computing" by Jelasity et al. is not very clear about this, but it states that
"The graph Dt is c-regular, that is, all correspondents have cache size c and therefore c
outgoing edges (provided the number of correspondents is larger than c)."
and also
"[...] there is a directed edge from correspondent c1 to c2 if and only if the address of c2 is contained in the cache of c1."
so the c outgoing edges in the Dt graph should connect to c distinct nodes, which is highly improbable if we allow repetitions.
My implementation may be wrong, but I want to specify that:
- the random selection of the nodes is not biased by the number of entries from the same peer (each peer is counted as 1 and selected uniformly at random;
- the random selection exclude the possibility that a peer selects itself;
- at each simulation step, the nodes are sorted by the instant in which they were last updated (from the oldest to the most recently updated), and then re-updated in that order (sequentially).
