ﻻ يوجد ملخص باللغة العربية
We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffusion by {em flooding}, the process by which, once a node is informed, it broadcasts its information to all its neighbors. We study models in which the network is {em sparse}, meaning that it has $mathcal{O}(n)$ edges, where $n$ is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is born, it connects to $d=mathcal{O}(1)$ random other nodes. An edge remains alive as long as both its endpoints do. If no further edge creation takes place, we show that, although the network will have $Omega_d(n)$ isolated nodes, it is possible, with large constant probability, to inform a $1-exp(-Omega(d))$ fraction of nodes in $mathcal{O}(log n)$ time. Furthermore, the graph exhibits, at any given time, a large-set expansion property. We also consider models with {em edge regeneration}, in which if an edge $(v,w)$ chosen by $v$ at birth goes down because of the death of $w$, the edge is replaced by a fresh random edge $(v,z)$. In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes $mathcal{O}(log n)$ time. The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.
The broadcast operation in distributed systems is used to spread information located at some nodes to all other nodes. This operation is often realized by flooding, where the source nodes send a message containing the information to all neighbors. Ea
We present an algorithm for implementing a store-collect object in an asynchronous crash-prone message-passing dynamic system, where nodes continually enter and leave. The algorithm is very simple and efficient, requiring just one round trip for a st
We investigate a special case of hereditary property that we refer to as {em robustness}. A property is {em robust} in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contex
In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a giv
In this contribution we introduce local attachment as an universal network-joining protocol for peer-to-peer networks, social networks, or other kinds of networks. Based on this protocol nodes in a finite-size network dynamically create power-law con