Treffer: Distributed Computation of Temporal Twins in Periodic Undirected Time-Varying Graphs

Twin nodes in a static network capture the idea of being substitutes for each other for maintaining paths of the same length anywhere in the network. In dynamic networks, we model twin nodes over a time-bounded interval, noted (∆, d)-twins, as follows. A periodic undirected time-varying graph G = (Gt)t∈N of period p is an infinite sequence of static graphs where Gt = Gt+p for every t ∈ N. For ∆ and d two integers, two distinct nodes u and v in G are (∆, d)-twins if, starting at some instant, their outside neighbourhoods N (u) \ {u, v} and N (v) \ {u, v} have non-empty intersection and differ by at most d elements for ∆ consecutive instants. In particular when d = 0, u and v can act during the ∆ instants as substitutes for each other in order to maintain journeys of the same length in time-varying graph G. It is known how to compute (∆, 0)twins in polynomial time by a centralized algorithm. In this paper we propose the first distributed deterministic algorithm enabling each node to enumerate its (∆, d)-twins in at most 2p rounds. We prove that the size of the messages used in our algorithm is at most O(δG log n + log p), where n is the total number of nodes and δG is the maximum degree of the graphs Gt's. Additionally, we prove that using randomized techniques borrowed from distributed hash function sampling the message size can be reduced w.h.p. down to O(log n + log p).