In this paper, we consider the distributed mean estimation problem where the server has access to some side information, e.g., its local computed mean estimation or the received information sent by the distributed clients at the previous iterations.
We propose a practical and efficient estimator based on an r-bit Wynzer-Ziv estimator proposed by Mayekar et al., which requires no probabilistic assumption on the data. Unlike Mayekars work which only utilizes side information at the server, our scheme jointly exploits the correlation between clients data and server s side information, and also between data of different clients. We derive an upper bound of the estimation error of the proposed estimator. Based on this upper bound, we provide two algorithms on how to choose input parameters for the estimator. Finally, parameter regions in which our estimator is better than the previous one are characterized.
We consider a MapReduce-type task running in a distributed computing model which consists of ${K}$ edge computing nodes distributed across the edge of the network and a Master node that assists the edge nodes to compute output functions. The Master n
ode and the edge nodes, both equipped with some storage memories and computing capabilities, are connected through a multicast network. We define the communication time spent during the transmission for the sequential implementation (all nodes send symbols sequentially) and parallel implementation (the Master node can send symbols during the edge nodes transmission), respectively. We propose a mixed coded distributed computing scheme that divides the system into two subsystems where the coded distributed computing (CDC) strategy proposed by Songze Li emph{et al.} is applied into the first subsystem and a novel master-aided CDC strategy is applied into the second subsystem. We prove that this scheme is optimal, i.e., achieves the minimum communication time for both the sequential and parallel implementation, and establish an {emph{optimal}} information-theoretic tradeoff between the overall communication time, computation load, and the Master nodes storage capacity. It demonstrates that incorporating a Master node with storage and computing capabilities can further reduce the communication time. For the sequential implementation, we deduce the approximately optimal file allocation between the two subsystems, which shows that the Master node should map as many files as possible in order to achieve smaller communication time. For the parallel implementation, if the Master nodes storage and computing capabilities are sufficiently large (not necessary to store and map all files), then the proposed scheme requires at most 1/2 of the minimum communication time of system without the help of the Master node.
This paper focuses on $ K $-receiver discrete-time memoryless broadcast channels (DM-BCs) with private messages, where the transmitter wishes to convey $K$ private messages to $K$ receivers respectively. A general inner bound on the capacity region i
s proposed based on an exhaustive message splitting and a $K$-level modified Martons coding. The key idea is to split every message into $ sum_{j=1}^K {Kchoose j} $ submessages each corresponding to a set of users who are assigned to recover them, and then send these submessages through codewords that are jointly typical with each other. To guarantee the joint typicality among all transmitted codewords, a sufficient condition on the subcodebooks sizes is derived through a newly establishing hierarchical covering lemma, which extends the 2-level multivariate covering lemma to the $K$-level case including $(2^{K}-1)$ random variables with more intricate dependence. As the number of auxiliary random variables and rate constraints both increase linearly with $(2^{K}-1)$, the standard Fourier-Motzkin elimination procedure becomes infeasible when $K$ is large. To tackle this problem, we obtain the final form of achievable rate region with a special observation of disjoint unions of sets that constitute the power set of $ {1,dots,K}$. The proposed achievable rate region allows arbitrary input probability mass functions (pmfs) and improves over all previously known ones for $ K$-receiver ($Kgeq 3$) BCs whose input pmfs should satisfy certain Markov chain(s).
In this paper, we investigate the transmission delay of cache-aided broadcast networks with user cooperation. Novel coded caching schemes are proposed for both centralized and decentralized caching settings, by efficiently exploiting time and cache r
esources and creating parallel data delivery at the server and users. We derive a lower bound on the transmission delay and show that the proposed centralized coded caching scheme is emph{order-optimal} in the sense that it achieves a constant multiplicative gap within the lower bound. Our decentralized coded caching scheme is also order-optimal when each users cache size is larger than the threshold $N(1-sqrt[{K-1}]{ {1}/{(K+1)}})$ (approaching 0 as $Kto infty$), where $K$ is the total number of users and $N$ is the size of file library. Moreover, for both the centralized and decentralized caching settings, our schemes obtain an additional emph{cooperation gain} offered by user cooperation and an additional emph{parallel gain} offered by the parallel transmission among the server and users. It is shown that in order to reduce the transmission delay, the number of users parallelly sending signals should be appropriately chosen according to users cache size, and alway letting more users parallelly send information could cause high transmission delay.
In this paper, we consider a cache-aided relay network, where a single server consisting of a library of N files connects with K1 relays through a shared noiseless link, and each relay connects with K2 users through a shared noiseless link. Each rela
y and user are equipped with a cache memory of M1 and M2 files, respectively. We propose a centralized and a decentralized coded caching scheme that exploit the spared transmission time resource by allowing concurrent transmission between the two layers. It is shown that both caching schemes are approximately optimal, and greatly reduce the transmission delay compared to the previously known caching schemes. Surprisingly, we show that when the relays caching size is equal to a threshold that is strictly smaller than N (e.g. M1=0.382N under the decentralized setup and (K1-1)N/K1 under the centralized setup, when K1=2), our schemes achieve the same delay as if each relay had access to the full library. To our best knowledge, this is the first result showing that even the caching size is strictly smaller than the librarys size, increasing the caching size is wasteful in reducing the transmission latency.
The relay broadcast channel (RBC) is considered, in which a transmitter communicates with two receivers with the assistance of a relay. Based on different degradation orders among the relay and the receivers outputs, three types of physically degrade
d RBCs (PDRBCs) are introduced. Inner bounds and outer bounds are derived on the capacity region of the presented three types. The bounds are tight for two types of PDRBCs: 1) one receivers output is a degraded form of the other receivers output, and the relays output is a degraded form of the weaker receivers output; 2) one receivers output is a degraded form of the relays output, and the other receivers output is a degraded form of the relays output. For the Gaussian PDRBC, the bounds match, i.e., establish its capacity region.
Achievable rate regions for cooperative relay broadcast channels with rate-limited feedback are proposed. Specifically, we consider two-receiver memoryless broadcast channels where each receiver sends feedback signals to the transmitter through a noi
seless and rate-limited feedback link, and meanwhile, acts as relay to transmit cooperative information to the other receiver. Its shown that the proposed rate regions improve on the known regions that consider either relaying cooperation or feedback communication, but not both.
