Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For real-time applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also quality of service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and code rate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate

We consider the setting of a Master server, M, who possesses confidential data and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who volunteered to help with this task. However, the data must be kept private in an information theoretic sense. Some of the workers may be stragglers, e.g., slow or busy. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms. We propose a solution based on new codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. We find upper and lower bounds on the Master’s mean waiting time. We derive the distribution of the Master’s waiting time, and its mean, for systems with up to two stragglers. We show that Staircase codes always outperform existing solutions based on classical secret sharing codes. We validate our results with extensive implementation on Amazon EC2.

We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. We focus on linear computations as an essential operation in many iterative algorithms. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. We propose to use instead new secure codes, called Staircase codes, introduced previously by two of the authors. We study the delay induced by Staircase codes which is always less than that of secret sharing. The reason is that secret sharing schemes need to wait for the responses of a fixed fraction of the workers, whereas Staircase codes offer more flexibility in this respect. For instance, for codes with rate R = 1/2 Staircase codes can lead to up to 40% reduction in delay compared to secret sharing.

A wireless communication system in which multiple users cooperate to transmit information to a common destination is considered. The traffic generated by the users is subject to a stringent quality of service requirement, which is defined in terms of the asymptotic decay-rate of buffer occupancy. The performance of this communication system is analyzed, and the corresponding achievable rate-region for the two-user scenario is identified. A simple user-cooperation scheme that improves performance is proposed. This cooperative scheme is shown to significantly enlarge the achievable rate-region of the service constrained communication system, provided that the quality of the wireless link between cooperating users is better than the individual connections from the users to the intended destination. Numerical results further indicate that the gains of cooperative strategies can be substantial. This suggests that cooperation allows for a fair distribution of the wireless resources among active users.

A transmitter observing a sequence of independent and identically distributed random variables seeks to keep a receiver updated about its latest observations. The receiver need not be apprised about each symbol seen by the transmitter, but needs to output a symbol at each time instant t. If at time t the receiver outputs the symbol seen by the transmitter at time U(t) ≤ t, the age of information at the receiver at time t is t-U(t). We study the design of lossless source codes that enable transmission with minimum average age at the receiver. We show that the asymptotic minimum average age can be attained up to a constant gap by the Shannon codes for a tilted version of the original pmf generating the symbols, which can be computed easily by solving an optimization problem. Furthermore, we exhibit an example with alphabet X where Shannon codes for the original pmf incur an asymptotic average age of a factor O(√log|x) more than that achieved by our codes. Underlying our prescription for optimal codes is a new variational formula for integer moments of random variables, which may be of independent interest. Also, we discuss possible extensions of our formulation to randomized schemes and to the erasure channel, and include a treatment of the related problem of source coding for minimum average queuing delay.

As sensing, control, and actuation become further integrated into modern communication infrastructures, special consideration must be given to the type of traffic generated by associated devices. Real-time decision making relies on the availability of accurate data and, as such, delivering status updates in a timely fashion is of paramount importance. The topics of real-time status updates and low- delay communications have received much attention in recent years. Within this context, this article presents new results by looking at the interplay between average timeliness and design decisions made at the physical layer for unreliable communication channels. This study focuses on the natural tension between the protection afforded by additional redundancy and the decoding delay associated with longer codewords. The average timeliness is adopted as a performance criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. The problem formulation precludes the use of asymptotically long codewords typical of information theory. Yet, the presence of limited feedback does not seem to boost performance in the present context. Rather, having accurate channel estimates is key in minimizing average timeliness. Numerical examples are included in this article to further illustrate the applicability of the findings.