Gossiping with Binary Freshness Metric

We consider the binary freshness metric for gossip networks that consist of a single source and $n$ end-nodes, where the end-nodes are allowed to share their stor

Age of Gossip in Networks with Community Structure

We consider a network consisting of a single source and $n$ receiver nodes that are grouped into $m$ equal size communities, i.e., clusters, where each cluster includes $k$ nodes and is served by a dedicated cluster head. The source node kee

Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning

Distributed implementations are crucial in speeding up large scale machine learning applications. Distributed gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is $straggling$ workers. Coded distributed computation techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. In this paper, we consider gradient coding (GC), and propose a novel dynamic GC scheme, which assigns redundant data to workers to acquire the flexibility to dynamically choose from among a set of possible codes depending on the past straggling behavior. In particular, we consider GC with clustering, and regulate the number of stragglers in each cluster by dynamically forming the clusters at each iteration; hence, the proposed scheme is called $GC$ $with$ $dynamic$ $clustering$ (GC-DC). Under a time-correlated straggling behavior, GC-DC gains from adapting to the straggling behavior over time such that, at each iteration, GC-DC aims at distributing the stragglers across clusters as uniformly as possible based on the past straggler behavior. For both homogeneous and heterogeneous worker models, we numerically show that GC-DC provides significant improvements in the average per-iteration completion time without an increase in the communication load compared to the original GC scheme.

Timely Communication in Federated Learning

We consider a federated learning framework in which a parameter server (PS) trains a global model by using $n$ clients without actually storing the client data centrally at a cloud server. Focusing on a setting where the client datasets are fast changing and highly temporal in nature, we investigate the timeliness of model updates and propose a novel timely communication scheme. Under the proposed scheme, at each iteration, the PS waits for $m$ available clients and sends them the current model. Then, the PS uses the local updates of the earliest $k$ out of $m$ clients to update the global model at each iteration. We find the average age of information experienced by each client and numerically characterize the age-optimal $m$ and $k$ values for a given $n$. Our results indicate that, in addition to ensuring timeliness, the proposed communication scheme results in significantly smaller average iteration times compared to random client selection without hurting the convergence of the global learning task.

Gradient Coding with Dynamic Clustering for Straggler Mitigation

In distributed synchronous gradient descent (GD) the main performance bottleneck for the per-iteration completion time is the slowest textit{straggling} workers. To speed up GD iterations in the presence of stragglers, coded distributed computation techniques are implemented by assigning redundant computations to workers. In this paper, we propose a novel gradient coding (GC) scheme that utilizes dynamic clustering, denoted by GC-DC, to speed up the gradient calculation. Under time-correlated straggling behavior, GC-DC aims at regulating the number of straggling workers in each cluster based on the straggler behavior in the previous iteration. We numerically show that GC-DC provides significant improvements in the average completion time (of each iteration) with no increase in the communication load compared to the original GC scheme.

Age-Based Coded Computation for Bias Reduction in Distributed Learning

Coded computation can be used to speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration; however, this can result in biased estimators, which may slow down convergence, or even cause divergence. Estimator bias will be particularly prevalent when the straggling behavior is correlated over time, which results in the gradient estimators being dominated by a few fast servers. To mitigate biased estimators, we design a $timely$ dynamic encoding framework for partial recovery that includes an ordering operator that changes the codewords and computation orders at workers over time. To regulate the recovery frequencies, we adopt an $age$ metric in the design of the dynamic encoding scheme. We show through numerical results that the proposed dynamic encoding strategy increases the timeliness of the recovered computations, which as a result, reduces the bias in model updates, and accelerates the convergence compared to the conventional static partial recovery schemes.

Selective Encoding Policies for Maximizing Information Freshness

An information source generates independent and identically distributed status update messages from an observed random phenomenon which takes $n$ distinct values based on a given pmf. These update packets are encoded at the transmitter node to be sent to a receiver node which wants to track the observed random variable with as little age as possible. The transmitter node implements a selective $k$ encoding policy such that rather than encoding all possible $n$ realizations, the transmitter node encodes the most probable $k$ realizations. We consider three different policies regarding the remaining $n-k$ less probable realizations: $highest$ $k$ $selective$ $encoding$ which disregards whenever a realization from the remaining $n-k$ values occurs; $randomized$ $selective$ $encoding$ which encodes and sends the remaining $n-k$ realizations with a certain probability to further inform the receiver node at the expense of longer codewords for the selected $k$ realizations; and $highest$ $k$ $selective$ $encoding$ $with$ $an$ $empty$ $symbol$ which sends a designated empty symbol when one of the remaining $n-k$ realizations occurs. For all of these three encoding schemes, we find the average age and determine the age-optimal real codeword lengths, including the codeword length for the empty symbol in the case of the latter scheme, such that the average age at the receiver node is minimized. Through numerical evaluations for arbitrary pmfs, we show that these selective encoding policies result in a lower average age than encoding every realization, and find the corresponding age-optimal $k$ values.

Age of Information with Gilbert-Elliot Servers and Samplers

We study age of information in a status updating system that consists of a single sampler, i.e., source node, that sends time-sensitive status updates to a single monitor node through a server node. We first consider a Gilbert-Elliot service profile at the server node. In this model, service times at the server node follow a finite state Markov chain with two states: ${bad}$ state $b$ and ${good}$ state $g$ where the server is faster in state $g$. We determine the time average age experienced by the monitor node and characterize the age-optimal state transition matrix $P$ with and without an average cost constraint on the service operation. Next, we consider a Gilbert-Elliot sampling profile at the source. In this model, the interarrival times follow a finite state Markov chain with two states: ${bad}$ state $b$ and ${good}$ state $g$ where samples are more frequent in state $g$. We find the time average age experienced by the monitor node and characterize the age-optimal state transition matrix $P$.

Optimal Selective Encoding for Timely Updates

We consider a system in which an information source generates independent and identically distributed status update packets from an observed phenomenon that takes $n$ possible values based on a given pmf. These update packets are encoded at the transmitter node to be sent to the receiver node. Instead of encoding all $n$ possible realizations, the transmitter node only encodes the most probable $k$ realizations and disregards whenever a realization from the remaining $n-k$ values occurs. We find the average age and determine the age-optimal real codeword lengths such that the average age at the receiver node is minimized. Through numerical evaluations for arbitrary pmfs, we show that this selective encoding policy results in a lower average age than encoding every realization and find the age-optimal $k$. We also analyze a randomized selective encoding policy in which the remaining $n-k$ realizations are encoded and sent with a certain probability to further inform the receiver at the expense of longer codewords for the selected $k$ realizations.

Timely Distributed Computation with Stragglers

We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and $n$ worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it emph{updated}. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d.~exponential transmission delays and i.i.d~shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.