In this paper we study the diculty of counting nodes in a synchronous dynamic network where nodes share the same identier, they communicate by using a broadcast with unlimited bandwidth and, at each synchronous round, network topology may change. To count in such setting, it has been shown that the presence of a leader is necessary. We focus on a particularly interesting subset of dynamic networks, namely Persistent Distance -G(PD)h, in which each node has a xed distance from the leader across rounds and such distance is at most h. In these networks the dynamic diameter D is at most 2h. We prove the number of rounds for counting inG(PD)2 is at least logarithmic with respect to the network sizejVj. Thanks to this result, we show that counting on any dynamic anonymous network with D constant w.r.t. jVj takes at least D+(log jVj) rounds where (log jVj) represents the additional cost to be payed for handling anonymity. At the best
The question concerning what can be computed on top of static anonymous networks, has been pioneered by Angluin in @cite_13 and by Yamashita and Kameda @cite_1 . In the domain of non-anonymous dynamic networks the counting problem has been addressed in the following contexts: (i) dynamicity governed by node churn in the context of distributed query execution @cite_17 @cite_15 , (ii) dynamicity governed by random adversary in the context of peer-to-peer networks @cite_8 and (iii) dynamicity governed worst-case adversary in the context of @math -interval connectivity @cite_7 @cite_10 .
@cite_7 @cite_8 @cite_10 @cite_1 @cite_15 @cite_13 @cite_17
2172782997 2025284419 1857402595 2782823532
Contribution. We study the fundamental naming and counting problems in networks that are anonymous, unknown, and possibly dynamic. Network dynamicity is modeled by the 1-interval connectivity model [KLO10]. We first prove that on static networks with broadcast counting is impossible to solve without a leader and that naming is impossible to solve even with a leader and even if nodes know n. These impossibilities carry over to dynamic networks as well. With a leader we solve counting in linear time. Then we focus on dynamic networks with broadcast. We show that if nodes know an upper bound on the maximum degree that will ever appear then they can obtain an upper bound on n. Finally, we replace broadcast with one-to-each, in which a node may send a different message to each of its neighbors. This variation is then proved to be computationally equivalent to a full-knowledge model with unique names. In this paper we investigate the problem of counting the size of a network where processes are anonymous (i.e., they share the same identifier) and the network topology constantly changes controlled by an adversary able to look internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. It is easy to show that, if the adversary can generate graphs without any constraint on the connectivity (i.e. it can generate topologies where there exist nodes not able to influence the others), counting is impossible. In this paper we consider a synchronous round based computation and the dynamicity is governed by a worst-case adversary that generates a sequence of graphs, one for each round, with the only constraint that each graph must be connected (1-interval connectivity property). It has been conjectured that counting in a finite time against such adversary is impossible and the existing solutions consider that each process has some knowledge about network topologies generated by the adversary, i.e. at each round, each node has a degree lesser than D. Along the path of proving the validity (or not) of the conjecture, this paper presents an algorithm that counts in a finite time against the worst-case adversary assuming each process is equipped with an oracle. The latter provides a process at each round r with an estimation of the process degree in the graph generated by the adversary at round r. To the best of our knowledge, this is the first counting algorithm (terminating in a finite time) where processes exploit the minimal knowledge about the behavior of the adversary. Interestingly, such oracle can be implemented in a wide range of real systems. This paper addresses the problem of counting the size of a network where i processes have the same identifiers anonymous nodes and ii the network topology constantly changes dynamic network. Changes are driven by a powerful adversary that can look at internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. The paper proposes two leader-based counting algorithms. Such algorithms are based on a technique that mimics an energy-transfer between network nodes. The first algorithm assumes that the adversary cannot generate either disconnected network graphs or network graphs where nodes have degree greater than D. In such algorithm, the leader can count the size of the network and detect the counting termination in a finite time i.e., conscious counting algorithm. The second algorithm assumes that the adversary only keeps the network graph connected at any time and we prove that the leader can still converge to a correct count in a finite number of rounds, but it is not conscious when this convergence happens. Time varying problems usually have complex underlying structures represented as dynamic networks where entities and relationships appear and disappear over time. The problem of efficiently performing dynamic link inference is extremely challenging due to the dynamic nature in massive evolving networks especially when there exist sparse connectivities and nonlinear transitional patterns. In this paper, we propose a novel deep learning framework, i.e., Conditional Temporal Restricted Boltzmann Machine (ctRBM), which predicts links based on individual transition variance as well as influence introduced by local neighbors. The proposed model is robust to noise and have the exponential capability to capture nonlinear variance. We tackle the computational challenges by developing an efficient algorithm for learning and inference of the proposed model. To improve the efficiency of the approach, we give a faster approximated implementation based on a proposed Neighbor Influence Clustering algorithm. Extensive experiments on simulated as well as real-world dynamic networks show that the proposed method outperforms existing algorithms in link inference on dynamic networks.