In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at mostrfiles. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.

We consider a wireless network where a source generates packets and forwards them to a network containing n nodes. The nodes in the network use the asynchronous push, pull or push-pull gossip communication protocols to maintain the most recent updates from the source. We use the version age of information metric to quantify the freshness of information in the network. Prior to this work, only the push gossiping protocol has been studied for age of information analysis. In this paper, we use the stochastic hybrid systems (SHS) framework to obtain recursive equations for the expected version age of sets of nodes in the time limit. We then show that the pull and push-pull protocols can achieve constant version age, while it is already known that the push protocol can only achieve logarithmic version age. We then show that the push-pull protocol performs better than the push and the pull protocol. Finally, we carry out numerical simulations to evaluate these results.

We study networks of gossiping users where a source observing a process sends updates to an underlying graph. Nodes in the graph update their neighbors randomly and nodes always accept packets that have newer information, thus attempting to minimize their age of information (AoI). We show that while gossiping reduces AoI, information can rapidly degrade in such a network. We model degradation by arbitrary discrete-time Markov chains on$k$states. As a packet is transmitted through the network it modifies its state according to the Markov chain. In the last section, we specialize the Markov chain to represent misinformation spread, and show that the rate of misinformation spread is proportional to the age of information in both the fullyconnected graph and ring graph.

We consider a gossiping network, where a source node sends updates to a network of$n$gossiping nodes. Meanwhile, the connectivity topology of the gossiping network changes over time, among a finite number of connectivity “states,” such as the fully connected graph, the ring graph, the grid graph, etc. The transition of the connectivity graph among the possible options is governed by a finite state continuous time Markov chain (CTMC). When the CTMC is in a particular state, the associated graph topology of the gossiping network is in the way indicated by that state. We evaluate the impact of time-varying graph topologies on the freshness of information for nodes in the network. We use the version age of information metric to quantify the freshness of information at the nodes. Using a method similar to the first passage percolation method, we show that, if one of the states of the CTMC is the fully connected graph and the transition rates of the CTMC are constant, then the version age of a typical node in the network scales logarithmically with the number of nodes, as in the case if the network was always fully connected. That is, there is no loss in the age scaling, even if the network topology deviates from full connectivity, in this setting. We perform numerical simulations and analyze more generally how having different topologies and different CTMC rates (that might depend on the number of nodes) affect the average version age scaling of a node in the gossiping network.

We consider a source that shares updates with a network of n gossiping nodes. The network’s topology switches between two arbitrary topologies, with switching governed by a two-state continuous time Markov chain (CTMC) process. Information freshness is well-understood for static networks. This work evaluates the impact of time-varying connections on information freshness. In order to quantify the freshness of information, we use the version age of information metric. If the two networks have static long-term average version ages of f1(n) and f2(n) with f1(n) ⪡ f2(n), then the version age of the varying-topologies network is related to f1(n), f2(n), and the transition rates in the CTMC. If the transition rates in the CTMC are faster than f1(n), the average version age of the varying-topologies network is f1(n). Further, we observe that the behavior of a vanishingly small fraction of nodes can severely impact the long-term average version age of a network in a negative way. This motivates the definition of a typical set of nodes in the network. We evaluate the impact of fast and slow CTMC transition rates on the typical set of nodes.

In gossip networks, a source node forwards time-stamped updates to a network of observers according to a Poisson process. The observers then update each other on this information according to Poisson processes as well. The Age of Information (AoI) of a given node is the difference between the current time and the most recent time-stamp of source information that the node has received. We provide a method for evaluating the AoI of a node in terms of first passage percolation. We then use this distributional identity to prove matching upper and lower bounds on the AoI in terms of connectivity properties of the underlying network. In particular, if one setsXvto be the AoI of nodevon a finite graphGwithnnodes, then we definem*= min{m:m· |Bm(v)| ≥n} whereBm(v) is the ball of radiusminG. In the case when the maximum degree ofGis bounded by Δ we prove EXv= ΘΔ(m*). As corollaries, we solve multiple open problems in the literature such as showing the age of information on a subset of Zdis Θ(n1/(d+1)). We also demonstrate examples of graphs with AoI scaling likenαfor each α ∈ (0, 1/2). These graphs are not vertex-transitive and in fact we show that if one considers the AoI on a graph coming from a vertex-transitive infinite graph then either EXv= Θ(n1/k) for some integerk≥ 2 or EXv=no(1).

In this paper we consider recovering combinatorial objects from many noisy observations. The first part of the paper concerns reconstructing trees from traces in the tree edit distance model. Previous work focused on reconstructing various classes of labelled trees, while our work gives reductions from the classic string reconstruction setting to unlabelled trees. In the second part of the paper we discuss combinatorial identities of the binary deletion channel on finite and infinite strings. We link probabilities of observing bits in a trace to derivatives of certain generating functions. We also give identities for the deletion channel, conditioned on traces having fixed length.

In this paper we study gossip networks where a source observing a process sends updates to an underlying graph. Nodes in the graph communicate to their neighbors by randomly sending updates. Our interest is studying the version age of information (vAoI) metric over various classes of networks. It is known that the version age of the complete graph is logarithmic, and the version age of the empty graph is linear. We study the question 'how does the vAoI evolve as we interpolate between these two extremes by studying Erdos-Reyni random graphs, random d-regular graphs, and bipartite networks. Our main results are proving the existence of a threshold in Erdos-Reyni graphs from rational to logarithmic average version age, and showing the random d-regular graph almost surely has logarithmic version age for constant$d$. We also characterize the version age of complete bipartite graphs KL,R, when we let$L$vary from to