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 \((\varDelta ,d)\) -twins, as follows. A periodic undirected time-varying graph \(\mathcal G=(G_t)_{t\in \mathbb N}\) of period p is an infinite sequence of static graphs where \(G_t=G_{t+p}\) for every \(t\in \mathbb N\) . For \(\varDelta \) and d two integers, two distinct nodes u and v in \(\mathcal G\) are \((\varDelta ,d)\) -twins if, starting at some instant, their outside neighbourhoods \(N(u)\setminus \{u,v\}\) and \(N(v)\setminus \{u,v\}\) have non-empty intersection and differ by at most d elements for \(\varDelta \) consecutive instants. In particular when \(d=0\) , u and v can act during the \(\varDelta \) instants as substitutes for each other in order to maintain journeys of the same length in time-varying graph \(\mathcal G\) . It is known how to compute \((\varDelta ,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 \((\varDelta ,d)\) -twins in at most 2p rounds. We prove that the size of the messages used in our algorithm is at most \(O(\delta _\mathcal G\log n+\log p)\) , where n is the total number of nodes and \(\delta _\mathcal G\) is the maximum degree of the graphs \(G_t\) ’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)\) .