Kenneth W. Shum

There are multiple performance metrics in the design of coding schemes for distributed storage systems. The first metric is called repair bandwidth, which measures the network resources required during the repair process. Another critical metric for repair efficiency is disk I/O cost, defined as the amount of data packets accessed at helper nodes to repair the failed node. In an encoding scheme with optimal I/O cost, the number of packets sent to the newcomer is exactly the same as the number of packets read from memory. This mode of repair is referred to as uncoded repair, as no coding operations are performed at the helper node. In addition to minimizing disk I/O cost, an uncoded repair mechanism has the advantage of incurring minimal computational overhead at the helper node. In this paper, we demonstrate that for single node failures, if all surviving nodes participate in the repair of the failed node, we can achieve all points on the fundamental tradeoff curve between storage and repair bandwidth. The design of the proposed encoding scheme is based on the theory of gammoids, a specialized class of graph-based matroids. We prove that this scheme can tolerate an unlimited number of node repair iterations over a field of fixed size.

In the deployment of distributed gradient descent algorithms in a network, the computational time and response time of a worker node are affected by various factors, such as processor speed, memory, network delay, and congestion. Straggler feedback delays can severely set back the effectiveness of distributed learning. To leverage the advantage of parallel processing in model training, gradient coding is designed to mitigate the effect of stragglers. This paper investigates gradient coding for heterogeneous workers with varying computational capabilities. We formulate the problem of approximating the gradient vector by minimizing the average error of the recovered gradient vector and propose a solution that leverages fractional repetition codes for data assignment to mitigate the impact of stragglers.

Around the year 2000, network coding introduced the concept that coding can replace the basic packet forwarding operation used in traditional network communication systems

This paper investigates the allocation of coded computing tasks in edge networks with uncertain conditions. Specifically, it focuses on scenarios where the computing speed-related parameters of edge devices are heterogeneous and unknown. The challenge lies in mitigating the impact of stragglers, which involves identifying fast workers and distributing a reasonable workload among them. In this paper, we put the fast worker identification into a multi-armed bandit (MAB) framework and propose a Thompson sampling (TS)-based approach to tackle it. Then, our approach leverages the heterogeneity of computing speeds by formulating the task allocation problem to minimize the expected computing delay. We derive a lower bound for the delay and prove that our proposed algorithm minimizes this bound. Importantly, the time complexity of our algorithm is independent of the number of tasks to be assigned, which is typically large in practical scenarios. When our scheme is applied to solve the linear regression problem, simulation results show that it reduces the computing delay of a state-of-the-art method by more than 15% in two different scenarios.

In this correspondence, a corrected version of the upper bound on the number of codewords for a multichannel CAC of weight three [1, Theorem 2] is presented.

Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we study the minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of the stored file. We derive a new upper bound on the minimum distance of FR codes, which is tighter than the Singleton bound and a Singleton-like bound that takes locality into account. Based on regular graphs and combinatorial designs, several families of FR codes with optimal minimum distance are obtained.

Conflict-avoiding codes (CACs) were introduced by Levenshtein as a single-channel transmission scheme for a multiple-access collision channel without feedback. When the number of simultaneously active source nodes is less than or equal to the weight of a CAC, it is able to provide a hard guarantee that each active source node transmits at least one packet successfully within a fixed time duration, no matter what the relative time offsets between the source nodes are. In this paper, we extend CACs to multichannel CACs for providing such a hard guarantee over multiple orthogonal channels. Upper bounds on the number of codewords for multichannel CACs of weights three and four are derived, and constructions that are optimal with respect to these bounds are presented.