This work considers the multi-access caching system proposed by Hachem et al., where each user has access to L neighboring caches in a cyclic wrap-around fashion. We first propose a placement ...strategy called the consecutive cyclic placement, which achieves the maximal local caching gain. Then under the consecutive cyclic placement, we derive an upper bound on the coded caching gain of any PDA, thus obtaining a lower bound on the rate of PDA-based coded caching schemes. Finally, we construct a class of PDAs under the consecutive cyclic placement, leading to a multi-access coded caching scheme with linear subpacketization, which achieves the derived lower bound on the rate for some parameters; while for other parameters, the achieved coded caching gain is only 1 less than the derived upper bound on the coded caching gain. Analytical and numerical comparisons of the proposed scheme with existing schemes are provided to validate the performance.
Coded caching technique is an efficient approach to reduce the transmission load in networks. In this paper, we consider a new widespread caching system called ( K 1 , K 2 , U,r,M,N ) two-dimensional ...(2D) caching-aided ultra-dense networks (UDNs) with a server containing N files, K 1 K 2 cache nodes arranged neatly on a grid with K 1 rows and K 2 columns, and U cache-less users randomly distributed around cache nodes. Each cache node can cache at most M ≤ N files and has a certain service region by Euclidean distance. The server connects to users through the error-free shared link and the users in the service region of a cache node can freely retrieve all cached contents of this cache node. We aim to design a coded caching scheme for 2D caching-aided UDN system to reduce the transmission load in the worst case while meeting all possible users' demands. First, we divide all possible users into four classes according to their geographical locations. Then our first order optimal scheme is proposed based on the Maddah-Ali and Niesen scheme. Furthermore, by compressing the transmitted signals of our first scheme based on Maximum Distance Separable (MDS) code, we obtain an improved order optimal scheme with a smaller transmission load.
Coded caching is an effective technique to decongest the amount of traffic in the backhaul link. In such a scheme, each file hosted in the server is divided into a number of packets to pursue a low ...broadcasting rate based on the designed placements at each user's cache. However, the implementation complexity of this scheme increases with the number of packets. It is important to design a scheme with a small subpacketization level and a relatively low transmission rate. Recently, placement delivery array (PDA) was proposed to address the subpacketization bottleneck of coded caching. This paper investigates the design of PDA from a new perspective, i.e., the injective arc coloring of regular digraphs. It is shown that the injective arc coloring of a regular digraph can yield a PDA with the same number of rows and columns. Based on this, a new class of regular digraphs are defined and the upper bounds on the injective chromatic index of such digraphs are derived. Consequently, four new coded caching schemes with a linear subpacketization level and a relatively small transmission rate are proposed, one of which generalizes the existing scheme for the scenario with a more flexible number of users.
Coded caching is an emerging technique to reduce the data transmission load during the peak-traffic times. In such a scheme, each file in the data center or library is divided into a number of ...packets to pursue a low broadcasting rate based on the designed placements at each user's cache. However, the implementation complexity of this scheme increases with the number of packets. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. Recently, a combinatorial structure called placement delivery array (PDA) was proposed as an effective tool to design coded caching schemes with a relatively low subpacketization level. This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs), which generalizes the existing construction but with a more flexible memory size. Based on the proposed PDA construction, an effective transform is further proposed to enable a coded caching scheme to achieve a smaller subpacketization level. Moreover, two new coded caching schemes with the coded placement are derived. It is shown that the proposed schemes can yield a lower subpacketization level or transmission rate over the benchmark schemes.
Ji et al. (IEEE Transactions on Information Theory, 62(2): 849-869, 2016) first studied coded caching in device-to-device (D2D) networks, and proposed a D2D coded caching scheme, which is referred to ...as the JCM scheme. In practice, we prefer to design a scheme with its two important targets, i.e., the rate (the maximal total amount of transmission) and packet number <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula>, as small as possible. In this paper, we first propose a simple array called D2D placement delivery array (DPDA) to characterize the placement phase and the delivery phase in D2D networks. Consequently, some D2D coded caching schemes can be realized by an appropriate DPDA. Second, a lower bound on the rate of a DPDA is derived. And, we show that the JCM scheme achieves our lower bound. However, it is well known that its packet number <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula> increases exponentially with the number of users <inline-formula> <tex-math notation="LaTeX">{K} </tex-math></inline-formula>. So, we propose two classes of new schemes by constructing DPDAs. One reduces the packet number exponentially with K compared with the JCM scheme while keeping the rate near to our lower bound. The other further reduces <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula> to increasing sub-exponentially with <inline-formula> <tex-math notation="LaTeX">{K} </tex-math></inline-formula>.
In an <inline-formula> <tex-math notation="LaTeX">(H,r) </tex-math></inline-formula> combination network, a single content library is serving for <inline-formula> <tex-math ...notation="LaTeX">{\binom{H}{ r}} </tex-math></inline-formula> users through <inline-formula> <tex-math notation="LaTeX">H </tex-math></inline-formula> relays, where each user has local cache memories and simultaneously accesses a subset of <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> relays on orthogonal non-interfering and error-free channels. The combinatorial placement delivery array (CPDA in short) can be used to realize a coded caching scheme for combination networks. In this paper, a new algorithm used to realize a scheme for combination networks based on a CPDA is proposed. Based on the fixed CPDA, the scheme realized by our algorithm has smaller subpacketization. Then we focus on directly constructing CPDAs for any positive integers <inline-formula> <tex-math notation="LaTeX">H </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">r< H </tex-math></inline-formula> and obtain two new classes of CPDAs. Compared with the previously known CPDAs, the schemes realized by our CPDAs have significant advantages on the subpacketization levels with some costing of transmission rates.
Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a connection between locally repairable codes with multiple disjoint repair ...sets and packings is derived under the condition that each repair set contains exactly one check symbol. Particularly, conditions under which an optimal locally repairable code corresponds to a packing are also characterized. As an application of this connection, some optimal locally repairable codes can be obtained by packings. Specifically, two constructions of locally repairable codes are proposed which not only generalize some known explicit constructions but also give optimal locally repairable codes with flexible new parameters.
Distributed multi-task learning (MTL) is a learning paradigm where distributed users simultaneously learn multiple tasks by leveraging the correlations among tasks. However, distributed MTL suffers ...from a more severe communication bottleneck than single-task learning as more than one models need to be transmitted in the communication phase. To address this issue, we investigate the hierarchical MTL system where distributed users wish to jointly learn different learning models orchestrated by a central server with the help of multiple relays. We propose a coded distributed computing scheme for hierarchical MTL systems that jointly exploits the network topology and relays' computing capability to create coded multicast opportunities to improve communication efficiency. We theoretically prove that the proposed scheme can significantly reduce the communication loads both in the uplink and downlink transmissions between relays and the server. To further illustrate the optimality of the proposed scheme, we derive information-theoretic lower bounds on the minimum uplink and downlink communication loads and prove that the gaps between achievable upper bounds and lower bounds are within the minimum number of connected users among all relays. In particular, when the network topology can be delicately designed, the proposed scheme can achieve the information-theoretic optimal communication loads. Experiments on real-world datasets show that our proposed scheme can greatly reduce the overall training time compared to the conventional hierarchical MTL scheme.
We consider the cache-aided multiple-input single-output (MISO) broadcast channel, which consists of a server with <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> antennas ...and <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> single-antenna users, where the server contains <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> files of equal length and each user is equipped with a local cache of size <inline-formula> <tex-math notation="LaTeX">M </tex-math></inline-formula> files. Each user requests an arbitrary file from library. The objective is to design a coded caching scheme based on uncoded placement and one-shot linear delivery, to achieve the maximum sum Degree-of-Freedom (sum-DoF) with low subpacketization. It was shown in the literature that under the constraint of uncoded placement and one-shot linear delivery, the maximum sum-DoF is <inline-formula> <tex-math notation="LaTeX">\min \left\{{L+\frac {KM}{N},K}\right\} </tex-math></inline-formula>. However, previously proposed schemes for this setting incurred either an exponential subpacketization order in <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, or required specific conditions in the system parameters <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">M </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula>. In this paper, we propose a new combinatorial structure called multiple-antenna placement delivery array (MAPDA). Based on MAPDA and Latin square, the first proposed scheme achieves the maximum sum-DoF <inline-formula> <tex-math notation="LaTeX">\min \left\{{L+\frac {KM}{N},K}\right\} </tex-math></inline-formula> with the subpacketization of <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> when <inline-formula> <tex-math notation="LaTeX">\frac {KM}{N}+L=K </tex-math></inline-formula>. Subsequently, for the general case we propose a transformation approach to construct an MAPDA from any <inline-formula> <tex-math notation="LaTeX">g </tex-math></inline-formula>-regular PDA (a class of placement delivery arrays for the shared link caching problem where each integer in the array occurs <inline-formula> <tex-math notation="LaTeX">g </tex-math></inline-formula> times). When <inline-formula> <tex-math notation="LaTeX">g </tex-math></inline-formula>-regular PDA corresponds to the Maddah-Ali and Niesen scheme, the resulting MAPDA yields the maximum sum-DoF <inline-formula> <tex-math notation="LaTeX">\min \left\{{L+\frac {KM}{N},K}\right\} </tex-math></inline-formula> with reduced subpacketization compared to the existing schemes. The general scheme can be extended to the multiple independent single-antenna transmitters (servers) corresponding to the cache-aided interference channel proposed by Naderializadeh et al. and the scenario of transmitters equipped with multiple antennas.
PDF
