The multiaccess coded caching (MACC) system, as formulated by Hachem {\it et al.}, consists of a central server with a library of $N$ files, connected to $K$ cache-less users via an error-free shared link, and $K$ cache nodes, each equipped with cache memory of size $M$ files. Each user can access $L$ neighboring cache nodes under a cyclic wrap-around topology. Most existing studies operate under the strong assumption that users can retrieve content from their connected cache nodes at no communication cost. In practice, each user retrieves content from its $L$ different connected cache nodes at varying costs. Additionally, the server also incurs certain costs to transmit the content to the users. In this paper, we focus on a cost-aware MACC system and aim to minimize the total system cost, which includes cache-access costs and broadcast costs. Firstly, we propose a novel coded caching framework based on superposition coding, where the MACC schemes of Cheng \textit{et al.} are layered. Then, a cost-aware optimization problem is derived that optimizes cache placement and minimizes system cost. By identifying a sparsity property of the optimal solution, we propose a structure-aware algorithm with reduced complexity. Simulation results demonstrate that our proposed scheme consistently outperforms the scheme of Cheng {\it et al.} in scenarios with heterogeneous retrieval costs.

This paper considers a new secure gradient coding problem with uncoded groupwise keys, formalized as a (K, N, N_r, M, S) secure gradient coding model, where a user aims to compute the sum of the gradients from K datasets with the assistance of N distributed servers. We consider arbitrary heterogeneous data assignment, where each dataset is assigned to at least M servers. The user should recover the sum of gradients from the transmissions of any N_r servers. The security constraint guarantees that even if the user receives the transmitted messages from all servers, it cannot obtain any other information about the datasets except the sum of gradients. Compared to existing secure gradient coding works, we introduce a practical constraint on secret keys, namely uncoded groupwise keys, where the keys are mutually independent and each key is shared by precisely S servers. An achievable secure gradient coding scheme with uncoded groupwise keys is proposed, which is then proven to be optimal if S > M and to be order optimal within a factor of 2 otherwise.

This paper studies the master-worker distributed linearly separable computation problem, where the considered computation task, referred to as linearly separable function, is a generic linear map. This model includes cooperative distributed gradient coding, real-time rendering, linear transforms, etc. as special cases. The computation task on K datasets can be expressed as Kclinear combinations of K messages, where each message is the output of an individual function on one dataset. In this distributed computing model, the K datasets are assigned to N workers for computation. Due to the possible presence of stragglers, it is required that the master can obtain the desired computation task from the answers of any Nrout of N workers. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of codewords that should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. A common way to assign the datasets to the workers is “cyclic assignment”. This has been considered in several theoretical works, as well as gradient coding, etc. Motivated by its theoretical and practical relevance, in this paper we focus on the cyclic assignment and solve the problem by determining the optimal computation/communication cost tradeoff when N = K and order optimal within a factor of 2 otherwise. In particular, this paper proposes a new computing scheme with the cyclic assignment based on the concept of interference alignment, by treating each message which cannot be computed by a worker as an interference from this worker. The decodability of our scheme is proved for the cases Kc[K/N (Nr− m + 1) : K] and N = Nrwith m+u−1 dividing N (where u = [ KcN K ]), and is further numerically verified for N ≤ 60. Beyond the appealing order-optimality result, we also show that the proposed scheme achieves significant gains over the current state of the art in practice. Experimental results over Tencent Cloud show the reduction of whole distributed computing process time of our scheme is up to 72.8% compared to the benchmark scheme which treats the computation on Kclinear combinations as Kcindividual computations.

Gradient coding enables a user node to efficiently aggregate gradients computed by server nodes from local datasets, achieving low communication costs while ensuring resilience against straggling servers. This paper considers the secure gradient coding problem, where a user aims to compute the sum of the gradients from K datasets with the assistance of$N$distributed servers. The user is required to recover the sum of gradients from the transmissions of any$\mathrm{N}_{\mathrm{r}}$servers, with each dataset assigned to$N-N_{r}+m$servers. The security constraint guarantees that even if the user receives transmissions from all servers, no additional information about the datasets can be obtained beyond the sum of gradients. It has been shown in the literature that the security constraint does not increase the optimal communication cost of the gradient coding problem, provided that enough source keys are shared among the servers. However, the minimum required source key size to ensure security while achieving the optimal communication cost has been studied only for the case$m=1$. In this paper, we focus on the more general case$m \geq 1$and aim to characterize the minimum required source key size for this purpose. A new information-theoretic converse bound on the source key size and a novel achievable scheme with smartly designed assignments are proposed. Our proposed scheme outperforms the optimal scheme based on the widely used cyclic data assignment and coincides with the converse bound under specific system parameters.

Elasticity plays an important role in modern cloud computing systems. Elastic computing allows virtual machines (i.e., computing nodes) to be preempted when high-priority jobs arise, and also allows new virtual machines to participate in the computation. This paper consider the elastic computing with heterogeneous speeds under uncoded storage. In 2018, Yang et al. introduced Coded Storage Elastic Computing (CSEC) to address the elasticity using coding technology, with lower storage and computation load requirements. However, CSEC is limited to certain types of computations (e.g., linear) due to the coded data storage based on linear coding. Then Centralized Uncoded Storage Elastic Computing (CUSEC) with heterogeneous computation speeds was proposed, which directly copies parts of data into the virtual machines. In all existing works in elastic computing, the storage assignment is centralized, meaning that the number and identity of all virtual machines possible used in the whole computation process are known during the storage assignment. In this paper, we consider Decentralized Uncoded Storage Elastic Computing (DUSEC) with heterogeneous computation speeds, where any available virtual machine can join the computation which is not predicted and thus coordination among different virtual machines' storage assignments is not allowed. Under a decentralized storage assignment originally proposed in coded caching by Maddah-Ali and Niesen, we propose a computing scheme with closed-form optimal computation time. We also run experiments over MNIST dataset with Softmax regression model through the Tencent cloud platform, and the experiment results demonstrate that the proposed DUSEC system approaches the state-of-art best storage assignment in the CUSEC system in computation time.

Distributed Linearly Separable Computation problem under the cyclic assignment is studied in this paper. It is a problem widely existing in cooperated distributed gradient coding, real-time rendering, linear transformers, etc. In a distributed computing system, a master asks N distributed workers to compute a linearly separable function from K datasets. The task function can be expressed as Kclinear combinations of K messages, where each message is the output of one individual function of one dataset. Straggler effect is also considered, such that from the answers of each Nrworker, the master should recover the task. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of (coded) messages which should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. Various distributed computing scheme were proposed in the literature with a well-known cyclic data assignment, but the (order) optimality of this problem remains open, even under the cyclic assignment. This paper proposes a new computing scheme with the cyclic assignment based on interference alignment, which is near optimal under the cyclic assignment.