We consider a time-slotted job-assignment system with a central server, N users and a machine which changes its state according to a Markov chain (hence called a Markov machine). The users submit their jobs to the central server according to a stochastic job arrival process. For each user, the server has a dedicated job queue. Upon receiving a job from a user, the server stores that job in the corresponding queue. When the machine is not working on a job assigned by the server, the machine can be either in internally busy or in free state, and the dynamics of these states follow a binary symmetric Markov chain. Upon sampling the state information of the machine, if the server identifies that the machine is in the free state, it schedules a user and submits a job to the machine from the job queue of the scheduled user. To maximize the number of jobs completed per unit time, we introduce a new metric, referred to as the age of job completion. To minimize the age of job completion and the sampling cost, we propose two policies and numerically evaluate their performance. For both of these policies, we find sufficient conditions under which the job queues will remain stable.

Beamforming has significance for enhancing spectral efficiency and mitigating interference in multi-antenna wireless systems, facilitating spatial multiplexing and diversity in dense and high mobility scenarios. Traditional beamforming techniques such as zero-forcing beamforming (ZFBF) and minimum mean square error (MMSE) beamforming experience performance deterioration under adverse channel conditions. Deep learning-based beamforming offers an alternative with nonlinear mappings from channel state information (CSI) to beamforming weights by improving robustness against dynamic channel environments. Transformer-based models are particularly effective due to their ability to model long-range dependencies across time and frequency. However, their quadratic attention complexity limits scalability in large OFDM grids. Recent studies address this issue through sparse attention mechanisms that reduce complexity while maintaining expressiveness, yet often employ patterns that disregard channel dynamics, as they are not specifically designed for wireless communication scenarios. In this work, we propose a Doppler-aware Sparse Neural Network Beamforming (Doppler-aware Sparse NNBF) model that incorporates a channel-adaptive sparse attention mechanism in a multi-user single-input multiple-output (MU-SIMO) setting. The proposed sparsity structure is configurable along 2D time-frequency axes based on channel dynamics and is theoretically proven to ensure full connectivity within p hops, where p is the number of attention heads. Simulation results under urban macro (UMa) channel conditions show that Doppler-aware Sparse NNBF significantly outperforms both a fixed-pattern baseline, referred to as Standard Sparse NNBF, and conventional beamforming techniques ZFBF and MMSE beamforming in high mobility scenarios, while maintaining structured sparsity with a controlled number of attended keys per query.

An important part of the information theory folklore had been about the output statistics of codes that achieve the capacity and how the empirical distributions compare to the output distributions induced by the optimal input in the channel capacity problem. Results for a variety of such empirical output distributions of good codes have been known in the literature, such as the comparison of the output distribution of the code to the optimal output distribution in vanishing and non-vanishing error probability cases. Motivated by these, we aim to achieve similar results for the quantum codes that are used for classical communication, that is the setting in which the classical messages are communicated through quantum codewords that pass through a noisy quantum channel. We first show the uniqueness of the optimal output distribution, to be able to talk more concretely about the optimal output distribution. Then, we extend the vanishing error probability results to the quantum case, by using techniques that are close in spirit to the classical case. We also extend non-vanishing error probability results to the quantum case on block codes, by using the second-order converses for such codes based on hypercontractivity results for the quantum generalized depolarizing semi-groups.

This work investigates the use of quantum resources in distributed storage systems. Consider an $(n,k,d)$ distributed storage system in which a file is stored across $n$ nodes such that any $k$ nodes suffice to reconstruct the file. When a node fails, any $d$ helper nodes transmit information to a newcomer to rebuild the system. In contrast to the classical repair, where helper nodes transmit classical bits, we allow them to send classical information over quantum channels to the newcomer. The newcomer then generates its storage by performing appropriate measurements on the received quantum states. In this setting, we fully characterize the fundamental tradeoff between storage and repair bandwidth (total communication cost). Compared to classical systems, the optimal storage--bandwidth tradeoff can be significantly improved with the enhancement of quantum entanglement shared only among the surviving nodes, particularly at the minimum-storage regenerating point. Remarkably, we show that when $d \geq 2k-2$, there exists an operating point at which \textit{both storage and repair bandwidth are simultaneously minimized}. This phenomenon breaks the tradeoff in the classical setting and reveals a fundamentally new regime enabled by quantum communication.

We provide new insights into an open problem recently posed by Yuan-Sun [ISIT 2025], concerning the minimum individual key rate required in the vector linear secure aggregation problem. Consider a distributed system with $K$ users, where each user $k\in [K]$ holds a data stream $W_k$ and an individual key $Z_k$. A server aims to compute a linear function $\mathbf{F}[W_1;\ldots;W_K]$ without learning any information about another linear function $\mathbf{G}[W_1;\ldots;W_K]$, where $[W_1;\ldots;W_K]$ denotes the row stack of $W_1,\ldots,W_K$. The open problem is to determine the minimum required length of $Z_k$, denoted as $R_k$, $k\in [K]$. In this paper, we characterize a new achievable region for the rate tuple $(R_1,\ldots,R_K)$. The region is polyhedral, with vertices characterized by a binary rate assignment $(R_1,\ldots,R_K) = (\mathbf{1}(1 \in \mathcal{I}),\ldots,\mathbf{1}(K\in \mathcal{I}))$, where $\mathcal{I}\subseteq [K]$ satisfies the \textit{rank-increment condition}: $\mathrm{rank}\left(\bigl[\mathbf{F}_{\mathcal{I}};\mathbf{G}_{\mathcal{I}}\bigr]\right) =\mathrm{rank}\bigl(\mathbf{F}_{\mathcal{I}}\bigr)+N$. Here, $\mathbf{F}_\mathcal{I}$ and $\mathbf{G}_\mathcal{I}$ are the submatrices formed by the columns indexed by $\mathcal{I}$. Our results uncover the novel fact that it is not necessary for every user to hold a key, thereby strictly enlarging the best-known achievable region in the literature. Furthermore, we provide a converse analysis to demonstrate its optimality when minimizing the number of users that hold keys.

Query-based sampling has become an increasingly popular technique for monitoring Markov sources in pull-based update systems. However, most of the contemporary literature on this assumes an exponential distribution for query delay and often relies on the assumption that the feedback or replies to the queries are instantaneous. In this work, we relax both of these assumptions and find optimal sampling policies for monitoring continuous-time Markov chains (CTMC) under generic delay distributions. In particular, we show that one can obtain significant gains in terms of mean binary freshness (MBF) by employing a waiting based strategy for query-based sampling.

We consider the storage problem in an asymmetric $X$-secure private information retrieval (A-XPIR) setting. The A-XPIR setting considers the $X$-secure PIR problem (XPIR) when a given arbitrary set of servers is communicating. We focus on the trade-off region between the average storage at the servers and the average download cost. In the case of $N=4$ servers and two non-overlapping sets of communicating servers with $K=2$ messages, we characterize the achievable region and show that the three main inequalities compared to the no-security case collapse to two inequalities in the asymmetric security case. In the general case, we derive bounds that need to be satisfied for the general achievable region for an arbitrary number of servers and messages. In addition, we provide the storage and retrieval scheme for the case of $N=4$ servers with $K=2$ messages and two non-overlapping sets of communicating servers, such that the messages are not replicated (in the sense of a coded version of each symbol) and at the same time achieve the optimal achievable rate for the case of replication. Finally, we derive the exact capacity for the case of asymmetric security and asymmetric collusion for $N=4$ servers, with the communication links $\{1,2\}$ and $\{3,4\}$, which splits the servers into two groups, i.e., $g=2$, and with the collusion links $\{1,3\}$, $\{2,4\}$, as $C=\frac{1}{3}$. More generally, we derive a capacity result for a certain family of asymmetric collusion and asymmetric security cases.

Immersive telepresence has the potential to transform real-time communication through highly interactive and engaging experiences. Despite recent advances in reducing communication and computation costs, existing systems largely overlook packet loss, which can severely degrade the quality of experience (QoE). Recovering lost immersive content is considerably more challenging than in 2D video due to the complexity of dense 3D representations. Recovery must be both accurate and timely while minimizing the communication and computation overhead it incurs. To address these challenges, we present LITE, the first loss-resilient immersive telepresence system. LITE incorporates three key design principles: (1) leveraging semantic communication to transmit compact motion and audio semantics, which can be reconstructed into the remote user's immersive representation and voice, enabling fast semantic-level recovery and remaining robust to congestion-control-induced rate reductions under loss; (2) fusing audio and motion semantics via a lightweight multimodal model to achieve accurate, real-time recovery of motion semantics; and (3) encoding audio semantics from multiple past frames into succinct neural redundancy to enable robust recovery. We prototype LITE using a well-known parametric facial motion representation and extensively evaluate its performance across diverse networks. Our results demonstrate that LITE improves QoE by up to 109% compared with existing schemes, while sustaining real-time streaming at 30 frames per second and preserving high visual fidelity (structural similarity index measure above 0.9, where 1 indicates perfect similarity).

Conventional double-spending attack models ignore the revenue losses stemming from the orphan blocks. On the other hand, selfish mining literature usually ignores the chance of the attacker to double-spend at no-cost in each attack cycle. In this paper, we give a rigorous stochastic analysis of an attack where the goal of the adversary is to double-spend while mining selfishly. To do so, we first combine stubborn and selfish mining attacks,i.e., construct a strategy where the attacker acts stubborn until its private branch reaches a certain length and then switches to act selfish. We provide the optimal stubbornness for each parameter regime. Next, we provide the maximum stubbornness that is still more profitable than honest mining and argue a connection between the level of stubbornness and thek-confirmation rule. We show that, at each attack cycle, if the level of stubbornness is higher thank, the adversary gets a free shot at double-spending. At each cycle, for a given stubbornness level, we rigorously formulate how great the probability of double-spending is. We further modify the attack in the stubborn regime in order to conceal the attack and increase the double-spending probability.

We consider a system model with two sources, a reliable source and an unreliable source, who are responsible for disseminating updates regarding a process to an age-based gossip network ofnnodes. Nodes wish to have fresh information, however, they have preference for packets that originate at the reliable source and are willing to sacrifice their version age of information by up toGversions to switch from an unreliable packet to a reliable packet. We study how this protocol impacts the prevalence of unreliable packets at nodes in the network and their version age. Using a stochastic hybrid system (SHS) framework, we formulate analytical equations to characterize two quantities: expected fraction of nodes with unreliable packets and expected version age of information at network nodes. We show that asGincreases, fewer nodes have unreliable packets, however, their version age increases as well, thereby inducing a freshness-reliability trade-off in the network. We further investigate the dependence of network reliability and freshness on various network parameters, such as, inter-node update rates and the network size. We support our analytical findings by extensive numerical and simulation results.

In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at mostrfiles. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.

We consider the quantumsymmetricprivate information retrieval (QSPIR) problem in a system withNdatabases andKmessages, withUunresponsive servers,T-colluding servers, andX-security parameter, under several fundamental threat models. In the first model, there areE1eavesdropped links in the uplink direction (the direction from the user to theNservers),E2eavesdropped links in the downlink direction (the direction from the servers to the user), where |E1|, |E2| ≤E; we coin this eavesdropper setting asdynamiceavesdroppers. We show that super-dense coding gain can be achieved for some regimes. In the second model, we consider the case with Byzantine servers, i.e., servers that can coordinate to devise a plan to harm the privacy and security of the system together with static eavesdroppers, by listening to the same links in both uplink and downlink directions. It is important to note the considerable difference between the two threat models, since the eavesdroppers can take huge advantage of the presence of the Byzantine servers. Unlike the previous works in SPIR with Byzantine servers, that assume that the Byzantine servers can send only random symbols independent of the stored messages, we follow the definition of Byzantine servers in [1], where the Byzantine servers can send symbols that can be functions of the storage, queries, as well as the random symbols in a way that can produce worse harm to the system. In the third and the most novel threat model, we consider the presence of Byzantine servers and dynamic eavesdroppers together. We show that having dynamic eavesdroppers along with Byzantine servers in the same system model creates more threats to the system than having static eavesdroppers with Byzantine servers. This is the first work that considers the quantum version of unresponsive and eavesdropped threat model. In addition, this is the first work, classical or quantum, that considers the presence of Byzantine servers together with eavesdroppers in the same system model (static or dynamic eavesdroppers). Another layer of difficulty that we handle in this work stems from the symmetric privacy requirement in the presence of Byzantine servers, which by itself has never been studied before in classical or quantum variations; here the Byzantine servers may attempt to leak information about undesired messages to the user, which is not allowed in SPIR.

We consider a gossip network consisting of a source generating updates andnnodes connected according to a given graph structure. The source keeps updates of a process, that might be generated or observed, and shares them with the gossiping network. The nodes in the network communicate with their neighbors and disseminate these version updates using a push-style gossip strategy. We use the version age metric to quantify the timeliness of information at the nodes. We first find an upper bound for the average version age for a set of nodes in a general network. Using this, we find the average version age scaling of a node in several network graph structures, such as two-dimensional grids, generalized rings and hyper-cubes. Prior to our work, it was known that whennnodes are connected on a ring the version age scales asO(n1/2), and when they are connected on a fully-connected graph the version age scales asO(logn). Ours is the first work to show an age scaling result for a connectivity structure other than the ring and the fully-connected network, which constitute the two extremes of network connectivity. Our work helps fill the gap between these two extremes by analyzing a large variety of graphs with intermediate connectivity, thus providing insight into the relationship between the connectivity structure of the network and the version age, and uncovering a network connectivity–information freshness tradeoff.

With the widespread adoption of internet-of-things (IoT) devices capable of supporting numerous intelligent applications, the demand for computational power has surged dramatically. Multi-access edge computing (MEC) technology is a promising solution to assist the often power-constrained IoT devices by providing additional computing resources for time-sensitive tasks. In this paper, we consider the problem of optimal task offloading in MEC systems with due consideration of the timeliness and scalability issues under two scenarios of equitable and priority access to the edge server (ES). In the first scenario, we consider a MEC system consisting of$N$devices assisted by one ES, where the devices can split task execution between a local processor and the ES, withequitable accessto the ES. In the second scenario, we consider a MEC system consisting of one primary user,$N$secondary users and one ES. The primary user haspriority accessto the ES while the secondary users haveequitable accessto the ES amongst themselves. In both scenarios, due to the power consumption associated with utilizing the local resource and task offloading, the devices must optimize their actions. Additionally, since the ES is a shared resource, other users' offloading activity serves to increase latency incurred by each user. We thus model both scenarios using alarge usernon-cooperative game framework. However, the presence of a large number of users makes it nearly impossible to compute the equilibrium offloading policies for each user, which would require a significant communication overhead to exchange information with each other. Thus, to alleviate such scalability issues, we invoke the paradigm of mean-field games (MFGs) to design completely distributed low complexity algorithms for the computation of approximate Nash equilibrium policies for each user based on only their local information. Further, by leveraging the novel age of information (AoI) metric, we study the trade-offs between increasing information freshness and reducing power consumption for each user. Using numerical evaluations, we show that our approach can recover the offloading trends displayed under centralized solutions, and provide additional insights into the results obtained.

We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs.

We consider a wireless network where a source generates packets and forwards them to a network containing n nodes. The nodes in the network use the asynchronous push, pull or push-pull gossip communication protocols to maintain the most recent updates from the source. We use the version age of information metric to quantify the freshness of information in the network. Prior to this work, only the push gossiping protocol has been studied for age of information analysis. In this paper, we use the stochastic hybrid systems (SHS) framework to obtain recursive equations for the expected version age of sets of nodes in the time limit. We then show that the pull and push-pull protocols can achieve constant version age, while it is already known that the push protocol can only achieve logarithmic version age. We then show that the push-pull protocol performs better than the push and the pull protocol. Finally, we carry out numerical simulations to evaluate these results.

We study a status update system with a source, a sampler, a transmitter, and a monitor. The source governs a stochastic process that the monitor wants to observe in a timely manner. To achieve this, the sampler samples fresh update packets which the transmitter transmits via an error prone communication channel to the monitor. The transmitter can transmit without any constraint, i.e., it can transmit whenever an update packet is available to the transmitter. However, the sampler is imposed with a sampling rate constraint. The goal of the sampler is to devise an optimal policy that satisfies the resource constraint while minimizing the age of the monitor. We formulate this problem as a constrained Markov decision process (CMDP). We find several structures of an optimal policy. We leverage the optimal structures to find a low complexity optimal policy in an explicit manner, without resorting to complex iterative schemes or techniques that require bounding the age.

Recent advancements in the reasoning capabilities of large language models (LLMs) show that employing group relative policy optimization (GRPO) algorithm for reinforcement learning (RL) training allows the models to use more thinking/reasoning tokens for generating better responses. However, LLMs can generate only a finite amount of tokens while maintaining attention to the previously generated tokens. This limit, also known as the context size of an LLM, is a bottleneck in LLM reasoning with arbitrarily large number of tokens. To think beyond the limit of context size, an LLM must employ a modular thinking strategy to reason over multiple rounds. In this work, we propose MOTIF: Modular Thinking via Reinforcement Fine-tuning – an RL training method for generating thinking tokens in multiple rounds, effectively allowing the model to think with additional context size. We trained the open-source model Qwen2.5-3B-Instruct on GSM8K dataset via parameter efficient fine-tuning and tested its accuracy on MATH500 and AIME2024 benchmarks. Our experiments show 3.8% and 3.3% improvements over vanilla GRPO based training in the respective benchmarks. Furthermore, this improvement was achieved with only 15% of samples, thus demonstrating sample efficiency of MOTIF. Our code and models are available at https://github.com/purbeshmitra/MOTIF and https://huggingface.co/purbeshmitra/MOTIF, respectively.

In this paper, we investigate the problem of remote estimation of a discrete-time joint Markov process using multiple sensors. Each sensor observes a different component of the joint Markov process, and in each time slot, the monitor obtains a partial state value by sending a pull request to one of the sensors. The monitor chooses the sequence of sensors to observe with the goal of minimizing the mean of age of incorrect information (MAoII) by using the partial state observations obtained, which have different freshness levels. For instance, a monitor may be interested in tracking the location of an object by obtaining observations from two sensors, which observe the$x$and$y$coordinates of the object separately, in different time slots. The monitor, then, needs to decide which coordinate to observe in the next time slot given the history. In addition to this partial observability of the state of Markov process, there is an erasure channel with a fixed one-slot delay between each sensor and the monitor. First, we obtain a sufficient statistic, namely the belief, representing the joint distribution of the age of incorrect information (AoII) and the current state of the observed process by using the history of all pull requests and observations. Then, we formulate the problem with a continuous state-space Markov decision problem (MDP), namely belief MDP. To solve the problem, we propose two model predictive control (MPC) methods, namely MPC without terminal costs (MPC-WTC) and reinforcement learning MPC (RL-MPC), that have different advantages in implementation.

We study networks of gossiping users where a source observing a process sends updates to an underlying graph. Nodes in the graph update their neighbors randomly and nodes always accept packets that have newer information, thus attempting to minimize their age of information (AoI). We show that while gossiping reduces AoI, information can rapidly degrade in such a network. We model degradation by arbitrary discrete-time Markov chains on$k$states. As a packet is transmitted through the network it modifies its state according to the Markov chain. In the last section, we specialize the Markov chain to represent misinformation spread, and show that the rate of misinformation spread is proportional to the age of information in both the fullyconnected graph and ring graph.

In a classification task, counterfactual explanations provide the minimum change needed for an input to be classified into a favorable class. We consider the problem of privately retrieving the exact closest counterfactual from a database of accepted samples while enforcing that certain features of the input sample cannot be changed, i.e., they are immutable. An applicant (user) whose feature vector is rejected by a machine learning model wants to retrieve the sample closest to them in the database without altering a private subset of their features, which constitutes the immutable set. While doing this, the user should keep their feature vector, immutable set and the resulting counterfactual index information-theoretically private from the institution. We refer to this as immutable private counterfactual retrieval (I-PCR) problem which generalizes PCR to a more practical setting. In this paper, we propose two I-PCR schemes by leveraging techniques from private information retrieval (PIR) and characterize their communication costs. Further, we quantify the information that the user learns about the database and compare it for the proposed schemes.

We consider the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) with$B$Byzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In [1], where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In [2], Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when symmetric privacy is required. To that end, we define Byzantine servers, inspired by [1], as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.

We consider a gossiping network, where a source node sends updates to a network of$n$gossiping nodes. Meanwhile, the connectivity topology of the gossiping network changes over time, among a finite number of connectivity “states,” such as the fully connected graph, the ring graph, the grid graph, etc. The transition of the connectivity graph among the possible options is governed by a finite state continuous time Markov chain (CTMC). When the CTMC is in a particular state, the associated graph topology of the gossiping network is in the way indicated by that state. We evaluate the impact of time-varying graph topologies on the freshness of information for nodes in the network. We use the version age of information metric to quantify the freshness of information at the nodes. Using a method similar to the first passage percolation method, we show that, if one of the states of the CTMC is the fully connected graph and the transition rates of the CTMC are constant, then the version age of a typical node in the network scales logarithmically with the number of nodes, as in the case if the network was always fully connected. That is, there is no loss in the age scaling, even if the network topology deviates from full connectivity, in this setting. We perform numerical simulations and analyze more generally how having different topologies and different CTMC rates (that might depend on the number of nodes) affect the average version age scaling of a node in the gossiping network.

We study a linear computation problem over a quantum multiple access channel (LC-QMAC), where S servers share an entangled state and separately store classical data streams W1,⋯,WSover a finite field ${\mathbb{F}_d}$. A user aims to compute K linear combinations of these data streams, represented as $Y = {{\mathbf{V}}_1}{W_1} + {{\mathbf{V}}_2}{W_2} + \cdot s + {{\mathbf{V}}_S}{W_S} \in \mathbb{F}_d^{K \times 1}$. To this end, each server encodes its classical information into its local quantum subsystem and transmits it to the user, who retrieves the desired computations via quantum measurements. In this work, we propose an achievable scheme for LC-QMAC based on the stabilizer formalism and the ideas from entanglement-assisted quantum error–correcting codes (EAQECC). Specifically, given any linear computation matrix, we construct a self-orthogonal matrix that can be implemented using the stabilizer formalism. Also, we apply precoding matrices to minimize the number of auxiliary qudits required. Our scheme achieves more computations per qudit, i.e., a higher computation rate, compared to the best-known methods in the literature, and attains the capacity in certain cases.

In recent literature, when modeling for information freshness in remote estimation settings, estimators have been mainly restricted to the class of martingale estimators, meaning the remote estimate at any time is equal to the most recently received update. This is mainly due to its simplicity and ease of analysis. However, these martingale estimators are far from optimal in some cases, especially in pull-based update systems. For such systems, maximum aposteriori probability (MAP) estimators are optimum, but can be challenging to analyze. Here, we introduce a new class of estimators, called structured estimators, which retain useful characteristics from a MAP estimate while still being analytically tractable. Our proposed estimators move seamlessly from a martingale estimator to a MAP estimator.

We consider a source that shares updates with a network of n gossiping nodes. The network’s topology switches between two arbitrary topologies, with switching governed by a two-state continuous time Markov chain (CTMC) process. Information freshness is well-understood for static networks. This work evaluates the impact of time-varying connections on information freshness. In order to quantify the freshness of information, we use the version age of information metric. If the two networks have static long-term average version ages of f1(n) and f2(n) with f1(n) ⪡ f2(n), then the version age of the varying-topologies network is related to f1(n), f2(n), and the transition rates in the CTMC. If the transition rates in the CTMC are faster than f1(n), the average version age of the varying-topologies network is f1(n). Further, we observe that the behavior of a vanishingly small fraction of nodes can severely impact the long-term average version age of a network in a negative way. This motivates the definition of a typical set of nodes in the network. We evaluate the impact of fast and slow CTMC transition rates on the typical set of nodes.

Mixture-of-Agents (MoA) has recently been proposed as a method to enhance performance of large language models (LLMs), enabling multiple individual LLMs to work together for collaborative inference. This collaborative approach results in improved responses to user prompts compared to relying on a single LLM. In this paper, we consider such an MoA architecture in a distributed setting, where LLMs operate on individual edge devices, each uniquely associated with a user and equipped with its own distributed computing power. These devices exchange information using decentralized gossip algorithms, allowing different device nodes to talk without the supervision of a centralized server. In the considered setup, different users have their own LLM models to address user prompts. Additionally, the devices gossip either their own user-specific prompts or augmented prompts to generate more refined answers to certain queries. User prompts are temporarily stored in the device queues when their corresponding LLMs are busy. Given the memory limitations of edge devices, it is crucial to ensure that the average queue sizes in the system remain bounded. In this paper, we address this by theoretically calculating the queuing stability conditions for the device queues under reasonable assumptions, which we validate experimentally as well. Further, we demonstrate through experiments, leveraging open-source LLMs for the implementation of distributed MoA, that certain MoA configurations produce higher-quality responses compared to others, as evaluated on AlpacaEval 2.0 benchmark. The implementation is available at: https://github.com/purbeshmitra/distributed_moa.

We consider the problem of assigning tasks efficiently to a set of workers that can exhaust themselves as a result of processing tasks. If a worker is exhausted, it will take a longer time to recover. To model efficiency of workers with exhaustion, we use a continuous-time Markov chain (CTMC). By taking samples from the internal states of the workers, the source assigns tasks to the workers when they are found to be in their efficient states. We consider two different settings where (i) the source can assign tasks to the workers only when they are in their most efficient state, and (ii) it can assign tasks to workers when they are also moderately efficient in spite of a potentially reduced success probability. In the former case, we find the optimal policy to be a threshold-based sampling policy where the thresholds depend on the workers’ recovery and exhaustion rates. In the latter case, we solve a non-convex sum-of-ratios problem using a branch-and-bound approach which performs well compared with the globally optimal solution.

The literature is abundant with methodologies focusing on using transformer architectures due to their prominence in wireless signal processing and their capability to capture long-range dependencies via attention mechanisms. In particular, separable convolutions enhance parameter efficiency for the process of high-dimensional data characteristics of MIMO systems. In this work, we introduce a novel unsupervised deep learning framework that integrates separable convolutions and transformers to generate beamforming weights under imperfect channel state information (CSI) for a multi-user single-input multiple-output (MU-SIMO) system in dense urban environments. The primary goal is to enhance throughput by maximizing sum-rate while ensuring reliable communication. Spectral efficiency and block error rate (BLER) are considered as performance metrics. Experiments are carried out under various conditions to compare the performance of the proposed NNBF framework against baseline methods zero-forcing beamforming (ZFBF) and minimum mean square error (MMSE) beamforming. Experimental results demonstrate the superiority of the proposed framework over the baseline techniques.

We consider the version age of information (AoI) in a network where a subset of nodes act as sensing nodes, sampling a source that in general can follow a continuous distribution. Any sample of the source constitutes a new version of the information and the version age of the information is defined with respect to the most recent version of the information available for the whole network. We derive a recursive expression for the average version AoI between different subsets of the nodes which can be used to evaluate the average version AoI for any subset of the nodes including any single node. We derive asymptotic behavior of the average AoI on any single node of the network for various topologies including line, ring, and fully connected networks. The prior art result on version age of a network by Yates [ISIT'21] can be interpreted as in our derivation as a network with a single view of the source, e.g., through a Poisson process with rate$\lambda_{00}$. Our result indicates that there is no loss in the average version AoI performance by replacing a single view of the source with distributed sensing across multiple nodes by splitting the same rate$\lambda_{00}$. Particularly, we show that asymptotically, the average AoI scales with$O(\log (n))$and$O(\sqrt{n})$for fully connected and ring networks, respectively. More interestingly, we show that for the ring network the same$O(\sqrt{n})$asymptotical performance on average AoI is still achieved with distributed sensing if the number of sensing nodes only scales with$O(\sqrt{n})$instead of prior known result which requires$O(n)$. Our results indicate that the sensing nodes can be arbitrarily chosen as long as the maximum number of consecutive non-sensing nodes also scales as$O(\sqrt{n})$.

We develop a novel source coding strategy for sampling and monitoring of a Wiener process. For the encoding process, we employ a four level “quantization” scheme, which employs monotone function thresholds as opposed to fixed constant thresholds. Leveraging the hitting times of the Wiener process with these thresholds, we devise a sampling and encoding strategy which does not incur any quantization errors. We give analytical expressions for the mean squared error (MSE) and find the optimal source code lengths to minimize the MSE under this monotone function threshold scheme, subject to a sampling rate constraint.

Use of multipath network topologies has become a prominent technique to assert timeliness in terms of Age of Information (AoI) and to improve resilience to link disruptions in communication systems. However, establishing multiple dedicated communication links among network nodes is a costly endeavor. Therefore, quite often, these secondary communication links are shared among multiple entities. Moreover, these multipath networks come with the added challenge of out-of-order transmissions. In this article, we study an amalgamation of the above two aspects, i.e., multipath transmissions and link sharing. In contrast to the existing literature where the main focus has been scheduling multiple sources on a single shared server, we delve into the realm where each source sharing the shared server is also supplemented with its dedicated server so as to improve its timeliness. In this multipath link sharing setting with generate-at-will transmissions, we first present the optimal probabilistic scheduler, and then propose several heuristic-based cyclic scheduling algorithms for the shared server, to minimize the weighted average AoI of the sources.

We study age of information (AoI) in a single-source dual-server continuous-time status update system for the generate-at-will (GAW) scenario, consisting of an information source, two heterogeneous servers, and a monitor (or destination). The technique of stochastic hybrid systems (SHS) has recently been used to obtain the average (or mean) AoI for a work-conserving (WC) zero wait (ZW) system imposed on the Non-parallel Transmission with Monitor Discarding (NT-MD) policy for which out-of-order packets are discarded upon reception by the monitor, for the case of exponentially distributed service times. In this paper, we exactly obtain the distributions (not only the means) of AoI and peak AoI (PAoI) processes for the NT-MD policy, in a more general setting with continuous phase-type distributed service times, by making use of the absorbing Markov chain (AMC) method, which was specifically developed for exact AoI modeling. Additionally, two Parallel Transmission (PT) policies resulting from either monitor discarding (PT-MD), or Source Preemption (PT-SP), are proposed and studied which allows us to comparatively evaluate these policies as a function of certain parameters of the service times. We also propose a non-work-conserving (NWC) NT policy with Freezing and source preemption, called NTF-SP, for which the transmission process is frozen for a certain amount of time upon each transmission, and we comparatively study NTF-SP against its NT-MD counterpart, for exponentially distributed, and also deterministic service times. Numerical results are presented for the validation of the proposed analytical models, and a comparative evaluation of the four transmission policies in terms of mean AoI.

We study the scheduling problem for a multi-source single-servergenerate-at-will(GAW) status update system with sources having heterogeneous service times and weights, for which the goal is to minimize the system age of information (AoI), or system peak AoI (PAoI), by employing scheduling algorithms with low runtime complexity. Here, system AoI/PAoI refers to weighted sum of the average AoI/PAoI values of information sources. In particular, we focus on open-loopcyclic schedulerswithO(1) runtime complexity, where status updates are scheduled according to a fixed finite transmission pattern whose construction is the main scope of this paper. We first develop an analytical method to obtain the exact average AoI/PAoI of the sources when a transmission pattern is given. Subsequently, we derive the optimum transmission pattern for system AoI in closed form, for the specific case of two sources. For general number of sources, a novel method is proposed based on adeletion search(DS) based algorithm which constructs a pattern whose system PAoI can be brought arbitrarily close to the minimum system PAoI that is attainable using open-loop scheduling. Using another outcome of the same DS-based algorithm, a heuristic scheduler is proposed for system AoI minimization, which is shown to outperform various existing age-agnostic schedulers in the literature, including theinsertion search(IS) based algorithm, in the majority of the examples we studied.

Gossiping is a communication mechanism, used for fast information dissemination in a network, where each node of the network randomly shares its information with the neighboring nodes. To characterize the notion of fastness in the context of gossip networks, age of information (AoI) is used as a timeliness metric. In this article, we summarize the recent works related to timely gossiping in a network. We start with the introduction of randomized gossip algorithms as an epidemic algorithm for database maintenance, and how the gossiping literature was later developed in the context of rumor spreading, message passing and distributed mean estimation. Then, we motivate the need for timely gossiping in applications such as source tracking and decentralized learning. We evaluate timeliness scaling of gossiping in various network topologies, such as, fully connected, ring, grid, generalized ring, hierarchical, and sparse asymmetric networks. We discuss age-aware gossiping and the higher order moments of the age process. We also consider different variations of gossiping in networks, such as, file slicing and network coding, reliable and unreliable sources, information mutation, different adversarial actions in gossiping, and energy harvesting sensors. Finally, we conclude this article with a few open problems and future directions in timely gossiping.

We study timeliness in cache-aided networks where the inter-update times on the links are not necessarily exponentially distributed. We focus on the set of non-arithmetic distributions for inter-update times, which includes continuous probability distributions as a subset. We first characterize instantaneous age of information at each node for arbitrary networks. We then explicate the recursive equations for instantaneous age of information in multi-hop networks and use them to derive closed form expressions for expected age of information at an end-user in tree networks. We show that expected age in multi-hop networks exhibits an additive structure. Further, we show that the expected age at each user is directly proportional to the variance of the inter-update times at all links between a user and the source. We next prove analogous results for the version age of information in multi-hop networks where updates at the source are marked with incrementing version numbers. We show that expected version age at end-users is inversely proportional to the mean update interval at the source, and exhibits an additive structure. Finally, we study expected age of information in networks with the property that the update processes on the links become sparse for large network sizes, and remark that expected age scales as$O(\log {n})$in symmetric fully connected networks. We expect the analysis in this work to help alleviate the over-dependence on exponential inter-update time (i.e., Poisson) updates for future work in age of information.

The rapid dissemination of real-time updates in interconnected networks often encounters the challenge of misinformation spreading alongside accurate information. This paper examines the interplay between timeliness and accuracy of updates in fully-connected gossip networks, where probabilistic mutations during transmission can convert truth into misinformation. We consider a network ofnuser nodes that receives updates from a source and employs an age-based gossip protocol for faster dissemination of version updates to all nodes. When a node forwards its packet to another node, the packet information gets mutated with probabilitypduring transmission, creating misinformation. The receiver node does not know whether an incoming packet contains correct information or misinformation. The receiver runs a gossip protocol that looks only at the version age of the incoming packet and accepts it if it is fresher than the packet in its possession. For the case when the incoming packet has the same version age as the receiver’s own packet, we consider two system models: In the first model, we assume that truth prevails over misinformation, and therefore, when a receiver encounters both accurate information and misinformation corresponding to the same version, the accurate information gets chosen for storage at the node. In the second model, we assume the opposite scenario, where misinformation prevails over truth. For both models, we study the expected fraction of nodes with correct information in the network and the version age at the nodes using the stochastic hybrid systems (SHS) method. We observe that when truth prevails over misinformation, very high or very low gossiping rates help curb misinformation, and misinformation spread is higher with moderate gossiping rates. However, when misinformation prevails, misinformation rises with increased inter-node gossiping. We support our theoretical findings with simulation results which shed further light on the behavior of the above studied quantities.

We consider both classical and quantum variations ofX-secure,E-eavesdropped andT-colluding symmetric private information retrieval (SPIR). This is the first work to study SPIR withX-security in classical or quantum variations. We first develop a scheme for classicalX-secure,E-eavesdropped andT-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate of$R= 1 - \frac {X+\max (T,E)}{N}$. The modified scheme achieves the same rate as the scheme used forX-secure PIR with the extra benefit of symmetric privacy, i.e., user-privacy as well as database-privacy. Next, we extend this scheme to its quantum counterpart based on theN-sum box abstraction. This is the first work to consider the presence of eavesdroppers in quantum private information retrieval (QPIR). In the quantum variation, the eavesdroppers have better access to information over the quantum channel compared to the classical channel due to the over-the-air decodability. To that end, we develop two different schemes for quantumX-secure,E-eavesdropped andT-colluding SPIR (QXSETSPIR) with secure over-the-air decoding. The first scheme achieves the highest possible super-dense coding gain, i.e.,$R_{Q} = \min \left \{{{ 1, 2\left ({{1-\frac {X+\max (T,E)}{N}}}\right)}}\right \}$, which requires additional uploads from the user. The second scheme on the other hand requires no extra uploads. However, it does not achieve the super-dense coding gain in some cases based on the relation between the number of eavesdropped links and the number of interference terms. The second scheme is based on the idea that there exist some special entanglement states that can be used to hide the contents of the user-required messages from the eavesdroppers using the interference symbols.

We study push-based sampling and transmission policies for a status update system consisting of a general finite-state continuous-time Markov chain (CTMC) information source with known dynamics, with the goal of minimizing the average age of incorrect information (AoII) defined via a linear time penalty function. The problem setting we investigate involves an exponentially distributed delay channel for transmissions and a constraint on the average sampling rate. We first show that the optimum sampling and transmission policy is amulti-thresholdpolicy, where the thresholds depend on both the estimation value and the state of the original process, and sampling and transmission need to be initiated when the instantaneous AoII exceeds the corresponding threshold, called the estimation-and state-aware transmission (ESAT) policy. Subsequently, we formulate the problem of finding the thresholds as a constrained semi-Markov decision process (CSMDP) and the Lagrangian approach. Additionally, we propose two lower complexity sub-optimum policies, namely the estimation-aware transmission (EAT) policy, and the single-threshold (ST) policy, for which it is possible to obtain these thresholds for CTMCs with relatively larger number of states. The underlying CSMDP formulation relies on themulti-regime phase-type(MR-PH) distribution which is a generalization of the well-known phase-type distribution, which allows us to obtain the first two moments of time until absorption in a CTMC whose transition rates change with respect to time, in a piece-wise manner. The effectiveness of the proposed ESAT, EAT, and ST sampling and transmission policies are shown through numerical examples, along with comparisons with a baseline scheme that transmits packets according to a Poisson process in out-of-sync periods.

We study security-latency bounds for Nakamoto consensus, i.e., how secure a block is after it becomes k-deep in the chain. We improve the state-of-the-art bounds by analyzing the race between adversarial and honest chains in three different phases. We find the probability distribution of the growth of the adversarial chains under models similar to those in Guo and Ren (2022) when a target block becomes k-deep in the chain. We analyze certain properties of this race to model each phase with random walks that provide tighter bounds than the existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small$\lambda \Delta $.

We consider the federated submodel learning (FSL) problem in a distributed storage system. In the FSL framework, the full learning model at the server side is divided into multiple submodels such that each selected client needs to download only the required submodel(s) and upload the corresponding update(s) in accordance with its local training data. The server comprises multiple independent databases and the full model is stored across these databases. A fundamental problem in FSL is to enable these multiple databases at the parameter server to collectively maintain a consistent view of the global parameters to facilitate parallel computing across distributed clients. In addition, a practically implementable FSL scheme should possess high throughput, efficient performance, fault tolerance, sufficient privacy, adequate security, certifiable stability, elastic scalability and easy usability features. To specifically resolve the fault tolerance and adequate security issues together, we propose a novel coding mechanism coined ramp secure regenerating coding (RSRC), which is a synthesis of ramp secret sharing and secure regenerating code. This coding technique matches FSL perfectly, as the system performance can be further improved when the full model is stored using RSRC in a distributed manner. By incorporating and extending available techniques cleverly, our new RSRC-based distributed FSL approach that is constructed on top of our earlier two-database FSL scheme which uses private set union (PSU), achieves all of the aforementioned important features. A complete one-round FSL process consists of: 1) an FSL-PSU phase where the union of the submodel indices to be updated by the selected clients in the current round is determined, 2) an FSL-write phase where the updated submodels are written back to the databases, and 3) additional auxiliary phases where sufficient amounts of necessary common randomness are generated at both server and client sides.

We consider a communication system consisting of a server that tracks and publishes updates about a time-varying data source or event, and a gossip network of users interested in closely tracking the event. The timeliness of the information is measured through the version age of information. The users wish to have their expected version ages remain below a threshold, and have the option to either rely on gossip from their neighbors or subscribe to the server directly to follow updates about the event if the former option does not meet the timeliness requirements. The server wishes to maximize its profit by increasing the number of subscribers and reducing costs associated with the frequent sampling of the event. We model the problem setup as a Stackelberg game between the server and the users, where the server commits to a frequency of sampling the event, and the users make decisions on whether to subscribe or not. As an initial work, we focus on directed networks with unidirectional flow of information and obtain the optimal equilibrium strategies for all the players. We provide simulation results to confirm the theoretical findings and provide additional insights.

We study a pull-based monitoring system in which a common remote monitor queries the states of a collection of heterogeneous finite-state irreducible continuous time Markov chain (CTMC) based information sources, according to a Poisson process with different per-source sampling rates, in order to maintain remote estimates of the states. Three information freshness models are considered to quantify the accuracy of the remote estimates: fresh when equal (FWE), fresh when sampled (FWS) and fresh when close (FWC). For each of these freshness models, closed-form expressions are derived for mean information freshness for each source, as a function of the sampling rate. Using these expressions, optimum sampling rates for all sources are obtained using water-filling based optimization for maximizing the weighted sum freshness of the monitoring system, under an overall sampling rate constraint. Numerical examples are presented to validate the effectiveness of the proposed method by comparing it to several baseline sampling policies.

We consider a system model with two sources, a reliable source and an unreliable source, who are responsible for disseminating updates regarding a process to an age-based gossip network of$n$nodes. Nodes wish to have fresh information, however, they have preference for packets that originated at the reliable source and are willing to sacrifice their version age of information by up to$G$versions to switch from an unreliable packet to a reliable packet. We study how this protocol impacts the prevalence of unreliable packets at nodes in the network and their version age. Using a stochastic hybrid system (SHS) framework, we formulate analytical equations to characterize two quantities: expected fraction of nodes with unreliable packets and expected version age of information at network nodes. We show that as$G$increases, fewer nodes have unreliable packet, however, their version age increases as well, thereby inducing a freshness-reliability trade-off in the network. We present numerical results to support our findings.

Ensuring high-quality video content for wireless users has become increasingly vital. Nevertheless, maintaining a consistent level of video quality faces challenges due to the fluctuating encoded bitrate, primarily caused by dynamic video content, especially in live streaming scenarios. Video compression is typically employed to eliminate unnecessary redundancies within and between video frames, thereby reducing the required bandwidth for video transmission. The encoded bitrate and the quality of the compressed video depend on encoder parameters, specifically, the quantization parameter (QP). Poor choices of en-coder parameters can result in reduced bandwidth efficiency and high likelihood of non-conformance. Non-conformance refers to the violation of the peak signal-to-noise ratio (PSNR) constraint for an encoded video segment. To address these issues, a real-time deep learning-based H.264 controller is proposed. This controller dynamically estimates the optimal encoder parameters based on the content of a video chunk with minimal delay. The objective is to maintain video quality in terms of PSNR above a specified threshold while minimizing the average bitrate of the compressed video. Experimental results, conducted on both QCIF dataset and a diverse range of random videos from public datasets, validate the effectiveness of this approach. Notably, it achieves improvements of up to 2.5 times in average bandwidth usage compared to the state-of-the-art adaptive bitrate video streaming, with a negligible non-conformance probability below 10−2.

We consider the problem of private set membership aggregation of$N$parties by using an entangled quantum state. In this setting, the$N$parties, which share an entangled state, aim to privately know the number of times each element (message) is repeated among the$N$parties, with respect to a universal set$\mathcal{K}$. This problem has applications in private comparison, ranking, voting, etc. We propose an encoding algorithm that maps the classical information into distinguishable quantum states, along with a decoding algorithm that exploits the distinguishability of the mapped states. The proposed scheme can also be used to calculate the$N$party private summation modulo$P$.

We consider a time-slotted status update system with an error-free preemptive queue. The goal of the sampler-scheduler pair is to minimize the age of information at the monitor by sampling and transmitting the freshly sampled update packets to the monitor. The sampler-scheduler pair also has a choice to preempt an old update packet from the server and transmit a new update packet to the server. We formulate this problem as a Markov decision process (MDP) and find the optimal sampling policy. We find a sufficient, and also separately a necessary, condition for the always preemption policy to be an optimal policy. We show that it is optimal for the sampler-scheduler pair to sample a new packet immediately upon the reception of an update packet at the monitor. We propose a double-threshold sampling policy which we show to be an optimal policy under some assumptions on the queue statistic.

We consider a sensor that samples an$N-\mathbf{state}$continuous-time Markov chain (CTMC)-based information source process, and transmits the observed state of the source, to a remote monitor tasked with timely tracking of the source process. The mismatch between the source and monitor processes is quantified by age of incorrect information (AoII), which penalizes the mismatch as it stays longer, and our objective is to minimize the average AoII under an average sampling rate constraint. We assume a perfect reverse channel and hence the sensor has information of the estimate while initiating a transmission or preempting an ongoing transmission. First, by modeling the problem as an average cost constrained semi-Markov decision process (CSMDP), we show that the structure of the problem gives rise to an optimum threshold policy for which the sensor initiates a transmission once the AoII exceeds a threshold depending on the instantaneous values of both the source and monitor processes. However, due to the high complexity of obtaining the optimum policy in this general setting, we consider a relaxed problem where the thresholds are allowed to be dependent only on the estimate. We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of$\mathcal{O}(N^{4})$, allowing one to obtain optimum policies for general CTMCs with over a hundred states.

We analyze how secure a block is after the block becomes$k-\mathbf{deep}$, i.e., security-latency, for Nakamoto consensus under an exponential network delay model. We give parameter regimes for which transactions are safe when sufficiently deep in the chain. Next, modeling the blockchain system as a batch service queue with exponential network delay, we connect the security-latency analysis to sustainable transaction rate of the queue system. We modify the selfish-mining attack to hamper the service process and consider its effect on the sustainable transaction rate of the queue.

Verifying user attributes to provide fine-grained access control to databases is fundamental to an attribute-based authentication system. In such systems, either a single (central) authority verifies all attributes, or multiple independent authorities verify individual attributes distributedly to allow a user to access records stored on the servers. While a central setup is more communication cost efficient, it causes privacy breach of all user attributes to a central authority. Recently, Jafarpisheh et al. studied an information theoretic formulation of the distributed multi-authority setup with$N$non-colluding authorities,$N$attributes and$K$possible values for each attribute, called an$(N, K)$distributed attribute-based private access control (DAPAC) system, where each server learns only one attribute value that it verifies, and remains oblivious to the remaining$N-1$attributes. We show that off-loading a subset of attributes to a central server for verification improves the achievable rate from$\frac{1}{2K}$in Jafarpisheh et al. to$\frac{1}{K+1}$in this paper, thus almost doubling the rate for relatively large$K$, while sacrificing the privacy of a few possibly non-sensitive attributes.

We consider a time slotted status update system with$(N+1)$sources,$N$users and one base station (BS). User$i$aims to receive fresh information from the stochastic processes at source$i$and source$(N+1)$. We measure the freshness of the system with the age of information metric. Thus, for user$i$, there are two notions of age of information, one corresponding to the age of source$i$, and another corresponding to the age of source$(N+1)$. The BS aims to employ an optimal scheduling policy to minimize the total average age of information. When the BS samples an update packet from the$i$th source,$1\leq i\leq N$, the BS transmits that sample only to the$i$th user. However, when the BS samples an update packet from the$(N+1)$th source, the BS transmits that sample to all the$N$users. Due to the energy constraint of the BS, we assume that when the BS transmits an update packet to a dedicated user, the probability of successful transmission is higher compared to the probability of successful transmission to the same user, when the BS transmits an update packet to all the$N$users. Due to this, there is a trade-off between the age of information and the probability of successful transmission. We find several structures for the optimal scheduling policy and exploit those properties to design a low-complexity relative value iteration-based scheduler. We propose a further lower complexity scheduling policy which is a mixture of the optimal scheduling policy and the max-weight policy.

Safety guarantees and security-latency problem of Nakamoto consensus have been extensively studied in the last decade with a bounded delay model. Recent studies have shown that PoW protocol is secure under random delay models as well. In this paper, we analyze the security-latency problem, i.e., how secure a block is, after it becomes k-deep in the blockchain, under general random delay distributions. We provide tight and explicit bounds which only require determining the distribution of the number of Poisson arrivals during the random delay. We further consider potential effects of recent Bitcoin halving on the security-latency problem by extending our results.

We consider the problems arising from the presence of Byzantine servers in a quantum private information retrieval (QPIR) setting. This is the first work to precisely define what the capabilities of Byzantine servers could be in a QPIR context. We show that quantum Byzantine servers have more capabilities than their classical counterparts due to the possibilities created by quantum encoding procedures. We focus on quantum Byzantine servers that can apply any reversible operation on their individual qudits. In this case, Byzantine servers can generate any error, i.e., this covers all possible single qudit operations that can be applied by Byzantine servers on their qudits. We design a scheme based on cross-subspace alignment (CSA) and we show that this scheme achieves superdense coding gain in some cases.

In this paper, we address task-oriented (or goal-oriented) communications where an encoder at the transmitter learns compressed latent representations of data, which are then transmitted over a wireless channel. At the receiver, a decoder performs a machine learning task, specifically for classifying the received signals. The deep neural networks corresponding to the encoder-decoder pair are jointly trained, taking both channel and data characteristics into account. Our objective is to achieve high accuracy in completing the underlying task while minimizing the number of channel uses determined by the encoder's output size. To this end, we propose a multi-round, multi-task learning (MRMTL) approach for the dynamic update of channel uses in multi-round transmissions. The transmitter incrementally sends an increasing number of encoded samples over the channel based on the feedback from the receiver, and the receiver utilizes the signals from a previous round to enhance the task performance, rather than only considering the latest transmission. This approach employs multi-task learning to jointly optimize accuracy across varying number of channel uses, treating each configuration as a distinct task. By evaluating the confidence of the receiver in task decisions, MRMTL decides on whether to allocate additional channel uses in multiple rounds. We characterize both the accuracy and the delay (total number of channel uses) of MRMTL, demonstrating that it achieves the accuracy close to that of conventional methods requiring large numbers of channel uses, but with reduced delay by incorporating signals from a prior round. We consider the CIFAR-10 dataset, convolutional neural network architectures, and AWGN and Rayleigh channel models for performance evaluation. Our results show that MRMTL significantly improves the efficiency of task-oriented communications, balancing accuracy and latency effectively.

Most existing stochastic models on age of information (AoI) focus on a single shared server serving status update packets from N > 1 sources where each packet update stream is Poisson, i.e., single-hop scenario. In the current work, we study a two-hop edge computing system for which status updates from the information sources are still Poisson but they are not immediately available at the shared edge server, but instead they need to first receive service from a transmission server dedicated to each source. For exponentially distributed and heterogeneous service times for both the dedicated servers and the edge server, and bufferless preemptive resource management, we develop an analytical model using absorbing Markov chains (AMC) for obtaining the distribution of AoI for any source in the system. Moreover, for a given tagged source, the traffic arriving at the shared server from the N - 1 un-tagged sources, namely the interference traffic, is not Poisson any more, but is instead a Markov modulated Poisson process (MMPP) whose state space grows exponentially with N. Therefore, we propose to employ a model reduction technique that approximates the behavior of the MMPP interference traffic with two states only, making it possible to approximately obtain the AoI statistics even for a very large number of sources. Numerical examples are presented to validate the proposed exact and approximate models.

In many federated learning (FL) models, a common strategy employed to ensure the progress in the training process, is to wait for at least M clients out of the total N clients to send back their local gradients based on a reporting deadline T, once the parameter server (PS) has broadcasted the global model. If enough clients do not report back within the deadline, the particular round is considered to be a failed round and the training round is restarted from scratch. If enough clients have responded back, the round is deemed successful and the local gradients of all the clients that responded back are used to update the global model. In either case, the clients that failed to report back an update within the deadline would have wasted their computational resources. Having a tighter deadline (small T) and waiting for a larger number of participating clients (large M) leads to a large number of failed rounds and therefore greater communication cost and computation resource wastage. However, having a larger T leads to longer round durations whereas smaller M may lead to noisy gradients. Therefore, there is a need to optimize the parameters M and T such that communication cost and the resource wastage is minimized while having an acceptable convergence rate. In this regard, we show that the average age of a client at the PS appears explicitly in the theoretical convergence bound, and therefore, can be used as a metric to quantify the convergence of the global model. We provide an analytical scheme to select the parameters M and T in this setting.

We study a remote monitoring system in which a mutually independent and heterogeneous collection of finite-state irreducible continuous time Markov chain (CTMC) based information sources is considered. In this system, a common remote monitor queries the instantaneous states of the individual CTMCs according to a Poisson process with possibly different intensities across the sources, in order to maintain accurate estimates of the original sources. Three information freshness models are considered to quantify the accuracy of the remote estimates: fresh when equal (FWE), fresh when sampled (FWS) and fresh when close (FWC). For each of these freshness models, closed-form expressions are derived for mean information freshness for a given source. Using these expressions, optimum sampling rates for all sources are obtained so as to maximize the weighted sum freshness of the monitoring system, subject to an overall sampling rate constraint. This optimization problem leads to a water-filling solution with quadratic worst case computational complexity in the number of information sources. Numerical examples are provided to validate the effectiveness of the optimum sampling policy in comparison to several baseline sampling policies.

We consider gossip networks consisting of a source that maintains the current version of a file, n nodes that use asynchronous gossip mechanisms to disseminate fresh information in the network, and an oblivious adversary who infects the packets at a target node through data timestamp manipulation, with the intent to replace circulation of fresh packets with outdated packets in the network. We demonstrate how network topology capacitates an adversary to influence age scaling in a network. We show that in a fully connected network, a single infected node increases the expected age from O(log n) to O(n). Further, we show that the optimal behavior for an adversary is to reset the timestamps of all outgoing packets to the current time and of all incoming packets to an outdated time for the infected node; thereby preventing any fresh information to go into the infected node, and facilitating acceptance of stale information out of the infected node into other network nodes. Additionally, if the adversary allows the infected node to accept a small fraction of incoming packets from the network, then a large network can manage to curb the spread of stale files coming from the infected node and pull the network age back to O(log n). Lastly for fully connected network, we show that if an infected node contacts only a single node instead of all nodes of the network, the system age can still be degraded to O(n). These show that fully connected nature of a network can be both a benefit and a detriment for information freshness; full connectivity, while enabling fast dissemination of information, also enables fast dissipation of adversarial inputs. We then analyze the unidirectional ring network, the other end of the network connectivity spectrum, where we show that the adversarial effect on age scaling of a node is limited by its distance from the adversary, and the age scaling for a large fraction of the network continues to be O(√n), unchanged from the case with no adversary. We finally support our findings with simulations.

We consider a fully-connected wireless gossip network which consists of a source andnreceiver nodes. The source updates itself with a Poisson process and also sends updates to the nodes as Poisson arrivals. Upon receiving the updates, the nodes update their knowledge about the source. The nodes gossip the data among themselves in the form of Poisson arrivals to disperse their knowledge about the source. The total gossiping rate is bounded by a constraint. The goal of the network is to be as timely as possible with the source. We propose a scheme which we coinage sense updating multiple access in networks (ASUMAN), which is a distributed opportunistic gossiping scheme, where after each time the source updates itself, each node waits for a time proportional to its current age and broadcasts a signal to the other nodes of the network. This allows the nodes in the network which have higher age to remain silent and only the low-age nodes to gossip, thus utilizing a significant portion of the constrained total gossip rate. We calculate the average age for a typical node in such a network with symmetric settings, and show that the theoretical upper bound on the age scales asO(1). ASUMAN, with an average age ofO(1), offers significant gains compared to a system where the nodes just gossip blindly with a fixed update rate, in which case the age scales asO(logn). Further, we show that thisO(1) age performance is sustained if a network has only a fraction of fully-connected edges. However, if the nodes have finiteO(1) connectivity, e.g., ring networks, two-dimensional grids, we show that ASUMAN scheme underperforms uniform gossiping, pointing to the need for connectivity with opportunistic gossiping. We improve this performance by introducing a hierarchical structure in the network, which recovers O(1) age scaling underO(√n) connected networks. Further, we show how the age of the nodes scale when the cluster heads are finitely connected among themselves, e.g.,O(c) age scaling for disconnected andO(√c) age scaling for ring-connected cluster heads, wherecis the number of clusters. Finally, we show that theO(1) age scaling can be extended to asymmetric settings as well. We give an example of power law arrivals, where nodes’ ages scale differently but follow theO(1) bound.

In many existing communication models, the channel state (i.e., busy or idle) is conveyed to the sampler via ACKs which are often assumed to be instantaneous. Previous literature shows that in this ideal feedback setting, an optimal sampling policy that minimizes the age of information (AoI), should not sample when the channel is busy, and therefore, must always wait for the ACK of the previous sample before taking the next sample. However, this may not be optimal when the feedback channel (backward channel) has a random delay. In this work, we study the structure of the optimal sampling policy to minimize the AoI when the channel state (forward channel state) is not immediately perceived by the sampler due to random delays in the feedback channel. In this setting, we show that it is not always optimal to wait for ACKs before sampling, and thus,early samplingwith the available channel state information may be better. We show that, under certain conditions on the distribution of the ACK delays, the (asymptotically) optimal sampling policy reduces to a mixture of two threshold policies.

We investigate the problem of private read-update-write (PRUW) in relation to private federated submodel learning (FSL), where a machine learning model is divided into multiple submodels based on the different types of data used to train the model. In PRUW, each user downloads the required submodel without revealing its index in the reading phase, and uploads the updates of the submodel without revealing the submodel index or the values of the updates in the writing phase. In this work, we first provide a basic communication efficient PRUW scheme, and study further means of reducing the communication cost via sparsification. Gradient sparsification is a widely used concept in learning applications, where only a selected set of parameters is downloaded and updated, which significantly reduces the communication cost. In this paper, we study how the concept of sparsification can be incorporated in private FSL with the goal of reducing the communication cost, while guaranteeing information-theoretic privacy of the updated submodel index as well as the values of the updates. To this end, we introduce two schemes: PRUW with top$r$sparsification and PRUW with random sparsification. The former communicates only the most significant parameters/updates among the servers and the users, while the latter communicates a randomly selected set of parameters/updates. The two proposed schemes introduce novel techniques such as parameter/update (noisy) permutations to handle the additional sources of information leakage in PRUW caused by sparsification. Both schemes result in significantly reduced communication costs compared to that of the basic (non-sparse) PRUW scheme.

In federated learning (FL), a machine learning (ML) model is collectively trained by a large number of users, using their private data in their local devices. With toprsparsification in FL, the users only upload the most significantrfraction of updates, and download only the most significantr’ fraction of parameters in order to reduce the communication cost. However, the values and the indices of the sparse updates and parameters leak information about the users’ private data. In this work, we consider an FL setting whereNnon-colluding databases store the model to be trained, from which the users download and update sparse parameters privately, without revealing the values of the updates/parameters or their indices to the databases. We propose four schemes with different properties that are based on cross subspace alignment (CSA) and permutation techniques, to perform this task while achieving the minimum communication costs within the scope of CSA, and show that the information theoretic privacy of both the values and the positions of the sparse updates/parameters can be guaranteed. This is achieved at a considerable storage cost, though. To alleviate this, we generalize the schemes in such a way that the storage cost is reduced at the expense of a certain amount of information leakage, using a model segmentation mechanism. In general, we provide the trade-off between the communication cost, storage cost and information leakage in private FL with toprsparsification.

In federated submodel learning (FSL), a machine learning model is divided into multiple submodels based on different types of data used for training. Each user involved in the training process only downloads and updates the submodel relevant to the user’s local data, which significantly reduces the communication cost compared to classical federated learning (FL). However, the index of the submodel updated by the user and the values of the updates reveal information about the user’s private data. In order to guarantee information-theoretic privacy in FSL, the model is stored at multiple non-colluding databases, and the user sends queries and updates to each database in such a way that no information is revealed on the updating submodel index or the values of the updates. In this work, we consider the practical scenario where the multiple non-colluding databases are allowed to have arbitrary storage constraints. The goal of this work is to develop read-write schemes and storage mechanisms for FSL that efficiently utilize the available storage in each database to store the submodel parameters in such a way that the total communication cost is minimized while guaranteeing information-theoretic privacy of the updating submodel index and the values of the updates. As the main result, we consider both heterogeneous and homogeneous storage constrained databases, and propose private read-write and storage schemes for the two cases.

We consider the federated submodel learning (FSL) problem and propose an approach where clients are able to update the central model information theoretically privately. Our approach is based on private set union (PSU), which is further based on multi-message symmetric private information retrieval (MM-SPIR). The server has two non-colluding databases which keep the model in a replicated manner. With our scheme, the server does not get to learn anything further than the subset of submodels updated by the clients: the server does not get to know which client updated which submodel(s), or anything about the local client data. In comparison to the state-of-the-art private FSL schemes of Jia-Jafar and Vithana-Ulukus, our scheme does not require noisy storage of the model at the databases; and in comparison to the secure aggregation scheme of Zhao-Sun, our scheme does not require pre-distribution of client-side common randomness, instead, our scheme creates the required client-side common randomness via random symmetric private information retrieval (RSPIR) and one-time pads. Our system is initialized with a replicated storage of submodels and a sufficient amount of common randomness at the two databases on the server-side. The protocol starts with a common randomness generation (CRG) phase where the two databases establish common randomness at the client-side using RSPIR and one-time pads (this phase is called FSL-CRG). Next, the clients utilize the established client-side common randomness to have the server determine privately the union of indices of submodels to be updated collectively by the clients (this phase is called FSL-PSU). Then, the two databases broadcast the current versions of the submodels in the set union to clients. The clients update the submodels based on their local training data. Finally, the clients use a variation of FSL-PSU to write the updates back to the databases privately (this phase is called FSL-write). As the databases at the server do not communicate, as a novel approach, we utilize carefully chosen alive clients to route the required information between the two databases. Our proposed private FSL scheme is robust against client drop-outs, client late-arrivals, and database drop-outs.

We consider a communication system where a base station (BS) transmits update packets to N users, one user at a time, over a wireless channel. We investigate the age of this status updating system with an adversary that jams the update packets in the downlink. We consider two system models: with diversity and without diversity. In the model without diversity, in each time slot, the BS schedules a user from N users according to a user scheduling algorithm. The constrained adversary blocks at most a given fraction,$\alpha $, of the time slots over a horizon of T slots, i.e., it can block at most$\alpha T$slots of its choosing out of the total T time slots. We show that if the BS schedules the users with a stationary randomized policy, then the optimal choice for the adversary is to block the user which has the lowest probability of getting scheduled by the BS, at the middle of the time horizon, consecutively for$\alpha T$time slots. The interesting consecutive property of the blocked time slots is due to the cumulative nature of the age metric. In the model with diversity, in each time slot, the BS schedules a user from N users and chooses a sub-carrier from$N_{sub}$sub-carriers to transmit update packets to the scheduled user according to a user scheduling algorithm and a sub-carrier choosing algorithm, respectively. The adversary blocks$\alpha T$time slots of its choosing out of T time slots at the sub-carriers of its choosing. We show that for large T, the uniform user scheduling algorithm together with the uniform sub-carrier choosing algorithm is$\frac {2 N_{sub}}{N_{sub}-1}$optimal. Next, we investigate the game theoretic equilibrium points of this status updating system. For the model without diversity, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the BS acts as the leader and the adversary acts as the follower. For the model with diversity, we show that a Nash equilibrium exists and identify the Nash equilibrium. Finally, we extend the model without diversity to the case where the BS can serve multiple users and the adversary can jam multiple users, at a time.

We consider a system consisting of a server, which receives updates for$N$files according to independent Poisson processes. The goal of the server is to deliver the latest version of the files to a user through a parallel network of$K$caches. We consider an update received by the user successful, if the user receives the same file version that is currently prevailing at the server. We derive an analytical expression for information freshness at the user. We observe that freshness for a file increases with increase in consolidation of rates across caches. To solve the multi-cache problem, we first solve the auxiliary problem of a single-cache system. We then rework this auxiliary solution to our parallel-cache network by consolidating rates to single routes as much as possible. This yields an approximate (sub-optimal) solution for the original problem. We provide an upper bound on the gap between the sub-optimal solution and the optimal solution. We present counterpart expressions and policies for version age of information by employing a stochastic hybrid system approach. Numerical results for both timeliness metrics show that the proposed sub-optimal policy closely follows the optimal policy.

We consider a network of$n$user nodes that receives updates from a source and employs an age-based gossip protocol for faster dissemination of version updates to all nodes. When a node forwards its packet to another node, the packet information gets mutated with probability$p$during transmission, creating misinformation. The receiver node does not know whether an incoming packet information is different from the packet information originally at the sender node. We assume that truth prevails over misinformation, and therefore, when a receiver encounters both accurate information and misinformation corresponding to the same version, the accurate information gets chosen for storage at the node. We study the expected fraction of nodes with correct information in the network and version age at the nodes in this setting using stochastic hybrid systems (SHS) modelling and study their properties. We observe that very high or very low gossiping rates help curb misinformation, and misinformation spread is higher with moderate gossiping rates. We support our theoretical findings with simulation results which shed further light on the behavior of above quantities.

We investigate the trade-off between rate, privacy and storage in federated learning (FL) with top$r$sparsification, where the users and the servers in the FL system only share the most significant$r$and$r^{\prime}$fractions, respectively, of updates and parameters in the FL process, to reduce the communication cost. We present schemes that guarantee information theoretic privacy of the values and indices of the sparse updates sent by the users at the expense of a larger storage cost. To this end, we generalize the scheme to reduce the storage cost by allowing a certain amount of information leakage. Thus, we provide the general trade-off between the communication cost, storage cost, and information leakage in private FL with top$r$sparsification, along the lines of two proposed schemes.

We improve security-latency bounds of Nakamoto consensus by analyzing the race between adversarial and honest chains in three different phases: pre-mining, confirmation and post-confirmation. We find the probability distribution of the length of the adversarial chain and the rigged adversarial chain under jumper models during the confirmation interval. We analyze certain properties of this race to model pre-mining and post-confirmation phases with random walks that provide tighter bounds than existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small λΔ.

We study age of information in multi-hop multi-cast cache-enabled networks where the inter-update times on the links are not necessarily exponentially distributed. We focus on the set of non-arithmetic distributions for inter-update times, which includes continuous probability distributions as a subset. We first characterize instantaneous age of information at each node for arbitrary networks. We then explicate the recursive equations for instantaneous age of information in multi-hop networks and derive closed form expressions for expected age of information at an end-user. We show that expected age in multi-hop networks exhibits an additive structure. Further, we show that the expected age at each user is directly proportional to the variance of inter-update times at all links between a user and the source. We expect the analysis in this work to help alleviate the over-dependence on Poisson processes for future work in age of information.

We consider a network consisting of n nodes that aim to track a continually updating process or event. To disseminate updates about the event to the network, two sources are available, such that information obtained from one source is considered more reliable than the other source. The nodes wish to have access to information about the event that is not only latest but also more reliable, and prefer a reliable packet over an unreliable packet even when the former is a bit outdated with respect to the latter. We study how such preference affects the fraction of users with reliable information in the network and their version age of information. We derive the analytical equations to characterize the two quantities, long-term expected fraction of nodes with reliable packets and their long-term expected version age using stochastic hybrid systems (SHS) modelling and study their properties. We also compare these results with the case where nodes give more preference to freshness of information than its reliability. Finally we show simulation results to verify the theoretical results and shed further light on behavior of above quantities with respect to dependent variables.

We investigate the problem of private read update write (PRUW) with heterogeneous storage constrained databases in federated submodel learning (FSL). In FSL a machine learning model is divided into multiple submodels based on different types of data used to train it. A given user downloads, updates and uploads the updates back to a single submodel of interest, based on the type of user’s local data. With PRUW, the process of reading (downloading) and writing (uploading) is carried out such that information-theoretic privacy of the updating submodel index and the values of updates is guaranteed. We consider the practical scenario where the submodels are stored in databases with arbitrary (heterogeneous) storage constraints, and provide a PRUW scheme with a storage mechanism that utilizes submodel partitioning and encoding to minimize the communication cost.

We consider the federated submodel learning (FSL) problem and propose an approach where clients are able to update the central model information theoretically privately. Our approach is based on private set union (PSU), which is further based on multi-message symmetric private information retrieval (MM-SPIR). With our scheme, the server does not learn anything further than the subset of submodels updated by the clients: the server does not know which client updated which submodel(s), or anything about the local client data. In comparison to the state-of-the-art private FSL schemes of Jia-Jafar and Vithana-Ulukus, our scheme does not require noisy storage of the model at the databases; and in comparison to the secure aggregation scheme of Zhao-Sun, our scheme incorporates the creation of the required client-side common randomness via random symmetric private information retrieval (RSPIR) and one-time pads. Our system is initialized with a replicated storage of submodels and a sufficient amount of common randomness in two databases at the server-side. The protocol starts with a common randomness generation (CRG) where the two databases establish common randomness at the client-side (FSL-CRG phase). Next, the clients utilize the established client-side common randomness to have the server determine privately the union of indices of submodels to be updated collectively by the clients (FSL-PSU phase). Then, the two databases broadcast the current versions of the submodels in the set union to clients. The clients update the submodels based on their local data. Finally, the clients use a variation of FSL-PSU to write the updates back to the databases privately (FSL-write phase). Our proposed private FSL scheme achieves low communication cost, and is also robust against client dropouts, client late-arrivals, and database drop-outs.

We consider a slotted communication system consisting of a source, a cache, a user and a timestomping adversary. The time horizon consists of total$T$time slots, such that the source transmits update packets to the user directly over$T_1$time slots and to the cache over$T_{2}$time slots. We consider$T_{1}\ll T_{2}, T_{1}+T_{2} < T$, such that the source transmits to the user once between two consecutive cache updates. Update packets are marked with timestamps corresponding to their generation times at the source. All nodes have a buffer size of one and store the packet with the latest timestamp to minimize their age of information. In this setting, we consider the presence of an oblivious adversary that fully controls the communication link between the cache and the user. The adversary manipulates the timestamps of outgoing packets from the cache to the user, with the goal of bringing staleness at the user node. At each time slot, the adversary can choose to either forward the cached packet to the user, after changing its timestamp to current time$t$, thereby rebranding an old packet as a fresh packet and misleading the user into accepting it, or stay idle. The user compares the timestamps of every received packet with the latest packet in its possession to keep the fresher one and discard the staler packet. If the user receives update packets from both cache and source in a time slot, then the packet from source prevails. The goal of the source is to design an algorithm to minimize the average age at the user, and the goal of the adversary is to increase the average age at the user. We formulate this problem in an online learning setting and provide a fundamental lower bound on the competitive ratio for this problem. We further propose a deterministic algorithm with a provable guarantee on its competitive ratio.

We consider a time slotted communication network with a base station (BS) and a user. At each time slot a fresh update packet arrives at the BS with probability$p > 0$. When the BS transmits an update packet for the first time, it goes through with a success probability of$q_1$. In all subsequent re-transmissions, the packet goes through with a success probability of$q_{2}$where$q_{2} > q_1$, due to the accumulation of observations at the receiver used to decode the packet. When the packet goes through the first time, the age of the user drops to 1, while when the packet goes through in subsequent transmissions, the age of the user drops to the age of the packet since its generation. Thus, when the BS is in the process of re-transmitting an old packet, if it receives a new packet, it has to decide whether to re-transmit the old packet with higher probability of successful transmission but resulting in higher age, or to transmit the new packet which will result in a lower age upon successful reception but this will happen with lower probability. In this paper, we provide an optimal algorithm to solve this problem.

We consider an asynchronous hierarchical federated learning (AHFL) setting with a client-edge-cloud framework. The clients exchange the trained parameters with their corresponding edge servers, which update the locally aggregated model. This model is then transmitted to all the clients in the local cluster. The edge servers communicate to the central cloud server for global model aggregation. The goal of each client is to converge to the global model, while maintaining timeliness of the clients, i.e., having optimum training iteration time. We investigate the convergence criteria for such a system with dense clusters. Our analysis shows that for a system of$n$clients with fixed average timeliness, the convergence in finite time is probabilistically guaranteed, if the nodes are divided into$O$(1) number of clusters, that is, if the system is built as a sparse set of edge servers with dense client bases each.

Distributed implementations are crucial in speeding up large scale machine learning applications. Distributed gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is straggling workers. Coded distributed computation techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. In this paper, we introduce a novel paradigm of dynamic coded computation, which assigns redundant data to workers to acquire the flexibility to dynamically choose from among a set of possible codes depending on the past straggling behavior. In particular, we propose gradient coding (GC) with dynamic clustering, called GC-DC, and regulate the number of stragglers in each cluster by dynamically forming the clusters at each iteration. With time-correlated straggling behavior, GC-DC adapts to the straggling behavior over time; in particular, at each iteration, GC-DC aims at distributing the stragglers across clusters as uniformly as possible based on the past straggler behavior. For both homogeneous and heterogeneous worker models, we numerically show that GC-DC provides significant improvements in the average per-iteration completion time without an increase in the communication load compared to the original GC scheme.

We investigate the problem of private federated submodel learning, where a machine learning model is divided into M submodels and stored in N databases, from which a given user privately reads, updates and writes back an arbitrary submodel. We consider information-theoretic privacy of the updated submodel index as well as the values of the updates. We provide an efficient private read update write (PRUW) scheme which achieves a lower total communication cost compared to the state-of-the-art. Our scheme significantly reduces the writing cost by combining all updates into a single bit in a way that it can be privately decomposed and placed at the relevant positions at the databases. This is achieved by over-designing the system with additional random noise terms in storage, which in turn provides additional security to the submodels. The scheme is designed for arbitrary privacy and security requirements.

We study a dynamic infection spread model, inspired by the discrete time SIR model, where infections are spread via non-isolated infected individuals. While infection keeps spreading over time, a limited capacity testing is performed at each time instance as well. In contrast to the classical, static, group testing problem, the objective in our setup is not to find the minimum number of required tests to identify the infection status of every individual in the population, but to control the infection spread by detecting and isolating the infections over time by using the given, limited number of tests. To analyze the performance of the proposed algorithms, we focus on the mean-sense analysis of the number of individuals that remain non-infected throughout the process of controlling the infection. We propose two dynamic algorithms that both use given limited number of tests to identify and isolate the infections over time, while the infection spreads. While the first algorithm is a dynamic randomized individual testing algorithm, in the second algorithm we employ the group testing approach similar to the original work of Dorfman. By considering weak versions of our algorithms, we obtain lower bounds for the performance of our algorithms. Finally, we implement our algorithms and run simulations to gather numerical results and compare our algorithms and theoretical approximation results under different sets of system parameters.

We investigate the game theoretic equilibrium points of a status updating system with an adversary that jams the updates in the downlink. We consider the system models with and without diversity. The adversary can jam up to α proportion of the entire communication window. In the model without diversity, in each time slot, the base station schedules a user from N users according to a stationary distribution. The adversary blocks (jams) αT time slots of its choosing out of the total T time slots. For this system, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the base station acts as the leader and the adversary acts as the follower. In the model with diversity, in each time slot, the base station schedules a user from N users and chooses a sub-carrier from Nsubsub-carriers to transmit update packets to the scheduled user according to a stationary distribution. The adversary blocks αT time slots of its choosing out of T time slots at the sub-carriers of its choosing. For this system, we show that a Nash equilibrium exists and identify the Nash equilibrium.

We consider a system consisting of a large network of n users and a library of files, wherein inter-user communication is established based upon gossip mechanisms. Each file is initially present at exactly one node, which is designated as the file source. The source gets updated with newer versions of the file according to an arbitrary distribution in real time, and the other users in the network wish to acquire the latest possible version of the file. We present a class of gossip protocols that achieve O(1) age at a typical node in a single-file system and O(n) age at a typical node for a given file in an n-file system. We show that file slicing and network coding based protocols fall under the presented class of protocols. Numerical evaluation results are presented to confirm the aforementioned bounds.

In status update systems, multiple features carried by the status updating process require pursuit of objectives beyond timeliness measured by the age of information of updates. We consider such a problem where the transmitter sends status update messages through a noiseless binary energy harvesting channel that is equivalent to a timing channel. The transmitter aims to amplify or mask the energy state information that is carried in the updating process. The receiver extracts encoded information, infers the energy state sequence while maintaining timeliness of status updates. Consequently, the timings of the updates must be designed to control the message rate, the energy state uncertainty, and the age of information. We investigate this three-way trade-off between the achievable rate, the reduction in energy arrival state uncertainty, and the age of information, for zero and infinite battery cases.

We investigate the problem of private read update write (PRUW) in relation to federated submodel learning (FSL) with storage constrained databases. In PRUW, a user privately reads a submodel from a system of N databases containing M submodels, updates it locally, and writes the update back to the databases without revealing the submodel index or the value of the update. The databases considered in this problem are only allowed to store a given amount of information specified by an arbitrary storage constraint. We provide a storage mechanism that determines the contents of each database prior to the application of the PRUW scheme, such that the total communication cost is minimized. We show that the proposed storage scheme achieves a lower total cost compared to what is achieved by using coded storage or divided storage to meet the given storage constraint.

We consider the total (upload plus download) communication cost of two-database symmetric private information retrieval (SPIR) through its relationship to conditional disclosure of secrets (CDS). In SPIR, a user wishes to retrieve a message out of K messages from N non-colluding and replicated databases without learning anything beyond the retrieved message, while no individual database learns the retrieved message index. In CDS, two parties each holding an individual input and sharing a common secret wish to disclose this secret to an external party in an efficient manner if and only if their inputs satisfy a public deterministic function. As a natural extension of CDS, we introduce conditional disclosure of multiple secrets (CDMS) where two parties share multiple i.i.d. common secrets rather than a single common secret as in CDS. We show that a special configuration of CDMS is equivalent to two-database SPIR. Inspired by this equivalence, we design download cost efficient SPIR schemes using bipartite graph representation of CDS and CDMS, and determine the exact minimum total communication cost of N = 2 database SPIR for K = 3 messages when the message length is 1.

We consider a fully connected network consisting of a source that maintains the current version of a file, n nodes that use asynchronous gossip mechanisms to disseminate fresh information in the network, and an adversary who infects the packets at a target node through data timestamp manipulation, with the intent to replace circulation of fresh packets with outdated packets in the network. We show that a single infected node increases the expected age of a fully connected network from O(log n) to O(n). Further, we show that the optimal behavior for an adversary is to reset the timestamps of all outgoing packets to the current time and of all incoming packets to an outdated time. Additionally, if the adversary allows the infected node to accept a small fraction of incoming packets from the network, then a large network can manage to curb the spread of stale files coming from the infected node and pull the network age back to O(log n). Lastly, we show that if an infected node contacts only a single node instead of all nodes of the network, the system age can still be degraded to O(n). These show that fully connected nature of a network can be both a benefit and a detriment for information freshness; full connectivity, while enabling fast dissemination of information, also enables fast dissipation of adversarial inputs.

We investigate the problem of private read update write (PRUW) in federated submodel learning (FSL) with sparsification. In FSL, a machine learning model is divided into multiple submodels, where each user updates only the submodel that is relevant to the user’s local data. PRUW is the process of privately performing FSL by reading from and writing to the required submodel without revealing the submodel index or the values of updates to the databases. Sparsification is a widely used concept in learning, where the users update only a small fraction of parameters to reduce the communication cost. Revealing the coordinates of these selected (sparse) updates leaks privacy of the user. We show how PRUW in FSL can be performed with sparsification. We propose a novel scheme which privately reads from and writes to arbitrary parameters of any given submodel, without revealing the submodel index, values of the updates, or the coordinates of the sparse updates, to databases. The proposed scheme achieves significantly lower reading and writing costs compared to what is achieved without sparsification.

We introduce the problem of random symmetric private information retrieval (RSPIR). In canonical PIR, a user downloads a message out of K messages from N non-colluding and replicated databases in such a way that no database can know which message the user has downloaded (user privacy). In SPIR, the privacy is symmetric, in that, not only that the databases cannot know which message the user has downloaded, the user itself cannot learn anything further than the particular message it has downloaded (database privacy). In RSPIR, different from SPIR, the user does not have an input to the databases, i.e., the user does not pick a specific message to download, instead is content with any one of the messages. In RSPIR, the databases need to send symbols to the user in such a way that the user is guaranteed to download a message correctly (random reliability), the databases do not know which message the user has received (user privacy), and the user does not learn anything further than the one message it has received (database privacy). This is the digital version of a blind box, also known as gachapon, which implements the above specified setting with physical objects for entertainment. This is also the blind version of 1-out-of-K oblivious transfer (OT), an important cryptographic primitive. We study the information-theoretic capacity of RSPIR for the case of N = 2 databases. We determine its exact capacity for the cases of K = 2,3,4 messages. While we provide a general achievable scheme that is applicable to any number of messages, the capacity for K ≥5 remains open.

By moving from massive antennas to antenna surfaces for software-defined wireless systems, the reconfigurable intelligent surfaces (RISs) rely on arrays of unit cells to control the scattering and reflection profiles of signals, mitigating the propagation loss and multipath attenuation, and thereby improving the coverage and spectral efficiency. In this paper, covert communication is considered in the presence of the RIS. While there is an ongoing transmission boosted by the RIS, both the intended receiver and an eavesdropper individually try to detect this transmission using their own deep neural network (DNN) classifiers. The RIS interaction vector is designed by balancing two (potentially conflicting) objectives of focusing the transmitted signal to the receiver and keeping the transmitted signal away from the eavesdropper. To boost covert communications, adversarial perturbations are added to signals at the transmitter to fool the eavesdropper’s classifier while keeping the effect on the receiver low. Results from different network topologies show that adversarial perturbation and RIS interaction vector can be jointly designed to effectively increase the signal detection accuracy at the receiver while reducing the detection accuracy at the eavesdropper to enable covert communications.

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

Coded computation techniques provide robustness againststragglingworkers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behavior and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, calledcoded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed scheme in terms of the trade-off between the computation accuracy and latency.

We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user retrieves a message out of$K$independent messages stored in$N$replicated and non-colluding databases without revealing the identity of the desired message to any individual database. The messages come withdifferent semantics, i.e., the messages are allowed to havenon-uniform a priori probabilitiesdenoted by$(p_{i}>0,\: i \in [K])$, which are a proxy for their respective popularity of retrieval, andarbitrary message sizes$(L_{i},\: i \in [K])$. This is a generalization of the classical private information retrieval (PIR) problem, where messages are assumed to have equal message sizes. We derive the semantic PIR capacity for general$K$,$N$. The results show that the semantic PIR capacity depends on the number of databases$N$, the number of messages$K$, the a priori probability distribution of messages$p_{i}$, and the message sizes$L_{i}$. We present two achievable semantic PIR schemes: The first one is a deterministic scheme which is based on message asymmetry. This scheme employs non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive necessary and sufficient conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate over the classical PIR capacity. We provide two extensions of the semantic PIR problem, namely, the semantic PIR from MDS-coded databases and the semantic PIR from colluding databases. For both extensions, we derive the exact PIR capacity in addition to providing a corresponding optimal scheme.

We study the problem of private set intersection (PSI). In this problem, there are two entities$E_{i}$, for$i=1, 2$, each storing a set$\mathcal {P}_{i}$, whose elements are picked from a finite set$\mathbb {S}_{K}$, on$N_{i}$replicated and non-colluding databases. It is required to determine the set intersection${\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}$without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR,$C_{MM-SPIR}$. We show that with$K$messages,$N$databases, and a given size of the desired message set$P$, the exact capacity of MM-SPIR is$C_{MM-SPIR} = 1 - \frac {1}{N}$when$P \leq K-1$, provided that the entropy of the common randomness$S$satisfies$H(S) \geq \frac {P}{N-1}$per desired symbol. When$P = K$, the MM-SPIR capacity is trivially 1 without the need for any common randomness$S$. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any$P$, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by$\min \left \{{\left \lceil{ \frac {P_{1} N_{2}}{N_{2}-1}}\right \rceil, \left \lceil{ \frac {P_{2} N_{1}}{N_{1}-1}}\right \rceil }\right \}$, where$P_{i}$is the cardinality of set${\mathcal {P}}_{i}$.

This paper presents channel-aware adversarial attacks against deep learning-based wireless signal classifiers. There is a transmitter that transmits signals with different modulation types. A deep neural network is used at each receiver to classify its over-the-air received signals to modulation types. In the meantime, an adversary transmits an adversarial perturbation (subject to a power budget) to fool receivers into making errors in classifying signals that are received as superpositions of transmitted signals and adversarial perturbations. First, these evasion attacks are shown to fail when channels are not considered in designing adversarial perturbations. Then, realistic attacks are presented by considering channel effects from the adversary to each receiver. After showing that a channel-aware attack is selective (i.e., it affects only the receiver whose channel is considered in the perturbation design), a broadcast adversarial attack is presented by crafting a common adversarial perturbation to simultaneously fool classifiers at different receivers. The major vulnerability of modulation classifiers to over-the-air adversarial attacks is shown by accounting for different levels of information available about the channel, the transmitter input, and the classifier model. Finally, a certified defense based on randomized smoothing that augments training data with noise is introduced to make the modulation classifier robust to adversarial perturbations.

In distributed synchronous gradient descent (GD) the main performance bottleneck for the per-iteration completion time is the slowest straggling workers. To speed up GD iterations in the presence of stragglers, coded distributed computation techniques are implemented by assigning redundant computations to workers. In this paper, we propose a novel gradient coding (GC) scheme that utilizes dynamic clustering, denoted by GC-DC, to speed up gradient calculations. Under time-correlated straggling behavior, GC-DC aims at regulating the number of straggling workers in each cluster based on the straggler behavior in the previous iteration. We numerically show that GC-DC provides significant improvements in the average completion time (of each iteration) with no increase in the communication load compared to the original GC scheme.

We consider a wireless communication system that consists of a background emitter, a transmitter, and an adversary. The transmitter is equipped with a deep neural network (DNN) classifier for detecting the ongoing transmissions from the background emitter and transmits a signal if the spectrum is idle. Concurrently, the adversary trains its own DNN classifier as the surrogate model by observing the spectrum to detect the ongoing transmissions of the background emitter and generate adversarial attacks to fool the transmitter into misclassifying the channel as idle. This surrogate model may differ from the transmitter’s classifier significantly because the adversary and the transmitter experience different channels from the background emitter and therefore their classifiers are trained with different distributions of inputs. This system model may represent a setting where the background emitter is a primary user, the transmitter is a secondary user, and the adversary is trying to fool the secondary user to transmit even though the channel is occupied by the primary user. We consider different topologies to investigate how different surrogate models that are trained by the adversary (depending on the differences in channel effects experienced by the adversary) affect the performance of the adversarial attack. The simulation results show that the surrogate models that are trained with different distributions of channel-induced inputs severely limit the attack performance and indicate that the transferability of adversarial attacks is neither readily available nor straightforward to achieve since surrogate models for wireless applications may significantly differ from the target model depending on channel effects.

We propose a novel infection spread model based on a random connection graph which represents connections between$n$individuals. Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. (correlated) infection status for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. We investigate the metrics associated with two-step sampled group testing algorithms. To demonstrate our results, for analytically tractable exponentially split cluster formation trees, we calculate the required number of tests and the expected number of false classifications in terms of the system parameters, and identify the trade-off between them. For such exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is$O(\log_{2}n)$. Thus, for such cluster formation trees, our algorithm outperforms any zero-error non-adaptive group test, binary splitting algorithm, and Hwang's generalized binary splitting algorithm. Our results imply that, by exploiting probabilistic information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high, contrasting the prevalent belief that group testing is useful only when infection rate is low.

We introduce the problem of timely private information retrieval (PIR) from$N$non-colluding and replicated servers. In this problem, a user desires to retrieve a message out of$M$messages from the servers, whose contents are continuously updating. The retrieval process should be executed in a timely manner such that no information is leaked about the identity of the message. To assess the timeliness, we use the age of information (AoI) metric. Interestingly, the timely PIR problem reduces to an AoI minimization subject to PIR constraints under asymmetric traffic. We explicitly characterize the optimal tradeoff between the PIR rate and the AoI metric (peak AoI or average AoI) for the case of$N=2,\ M=3$. Further, we provide some structural insights on the general problem with arbitrary$N,\ M$.

We consider a system consisting of a server, which receives updates for$N$files according to independent Poisson processes. The goal of the server is to deliver the latest version of the files to the user through a parallel network of$K$caches. We consider an update received by the user successful, if the user receives the same file version that is currently prevailing at the server. We derive an analytical expression for information freshness at the user. We observe that freshness for a file increases with increase in consolidation of rates across caches. To solve the multi-cache problem, we first solve the auxiliary problem of a single-cache system. We then rework this auxiliary solution to our parallel-cache network by consolidating rates to single routes as much as possible. This yields an approximate (sub-optimal) solution for the original problem. We provide an upper bound on the gap between the sub-optimal solution and the optimal solution. Numerical results show that the sub-optimal policy closely approximates the optimal policy.

We investigate the problem of semantic private information retrieval (PIR) from coded databases, where a user requires to download a message out of$M$independent messages, without revealing its identity to the databases. These messages are coded using an (N, K) MDS code and stored in$N$non-colluding databases. The$M$messages are allowed to have different semantics, e.g., different sizes and different probabilities of retrieval. We characterize the exact capacity of semantic PIR with coded databases, and provide an achievable scheme with non-uniform subpacketization. We show that the retrieval rate of semantic PIR with coded databases outperforms that of classical PIR with coded databases when the effects of zero padding shorter messages are taken into account.

We investigate the problem of multi-party private set intersection (MP-PSI). In MP-PSI, there are$M$parties, each storing a data set$\mathcal{P}_{i}$over$N_{i}$replicated and non-colluding databases, and we want to calculate the intersection of the data sets$\cap_{i=1}^{M}\mathcal{P}_{i}$without leaking any information beyond the set intersection to any of the parties. For a specific communication protocol, we propose an information-theoretic scheme for MP-PSI based on the connection between the PSI problem and the multi-message symmetric private information retrieval (MM-SPIR) problem. Our scheme is a non-trivial generalization of the 2-party PSI scheme as it needs an intricate design of the shared common randomness. Interestingly, our scheme does not incur any penalty due to the more stringent privacy constraints in the MP-PSI problem compared to the 2-party PSI problem.

We consider the problem of symmetric private information retrieval (SPIR) with user-side common randomness. In SPIR, a user retrieves a message out of$K$messages from$N$non-colluding and replicated databases in such a way that no single database knows the retrieved message index (user privacy), and the user gets to know nothing further than the retrieved message (database privacy). SPIR has a capacity smaller than the PIR capacity which requires only user privacy, is infeasible in the case of a single database, and requires shared common randomness among the databases. We introduce a new variant of SPIR where the user is provided with a random subset of the shared database common randomness, which is unknown to the databases. We determine the exact capacity region of the triple ($d, \rho S, \rho U$), where$d$is the download cost,$\rho S$is the amount of shared database (server) common randomness, and$\rho U$is the amount of available user-side common randomness. We show that with a suitable amount of$\rho U$, this new SPIR achieves the capacity of conventional PIR. As a corollary, single-database SPIR becomes feasible. Further, the presence of user-side$\rho U$reduces the amount of required server-side$\rho S$.

We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.

An information source generates independent and identically distributed status update messages from an observed random phenomenon which takes n distinct values based on a given probability mass function (PMF). These update packets are encoded at the transmitter node to be sent to a receiver node which wants to track the observed random variable with as little age as possible. The transmitter node implements a selective k encoding policy such that rather than encoding all possible n realizations, the transmitter node encodes the most probable k realizations. We consider three different policies regarding the remaining n-k less probable realizations: highest k selective encoding which disregards whenever a realization from the remaining n-k values occurs; randomized selective encoding which encodes and sends the remaining n-k realizations with a certain probability to further inform the receiver node at the expense of longer codewords for the selected k realizations; and highest k selective encoding with an empty symbol which sends a designated empty symbol when one of the remaining n-k realizations occurs. For all of these three encoding schemes, we find the average age and determine the age-optimal real codeword lengths, including the codeword length for the empty symbol in the case of the latter scheme, such that the average age at the receiver node is minimized. Through numerical evaluations for arbitrary PMFs, we show that these selective encoding policies result in a lower average age than encoding every realization, and find the corresponding age-optimal k values. Since we focus on real-valued codeword lengths in this paper, the resulting age value obtained in each case studied here serves as a lower bound to what can be attained by integer-valued codeword lengths in that case.

We consider the average age of information in G/G/1/1 systems under two service discipline models. In the first model, if a new update arrives when the service is busy, it is blocked; in the second model, a new update preempts the current update in service. For the blocking model, we first derive an exact age expression for G/G/1/1 systems. Then, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. We observe that deterministic interarrivals minimize the average age of G/M/1/1 systems for a given mean interarrival time. Next, for the preemption in service model, we first derive an exact average age expression for G/G/1/1 systems. Then, similar to blocking discipline, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. Average age for G/M/1/1 can be written as a summation of two terms, the first of which depends only on the first and second moments of interarrival times and the second of which depends only on the service rate. In other words, interarrival and service times are decoupled. We prove that deterministic interarrivals are optimum for G/M/1/1 systems for a given mean interarrival time. On the other hand, we observe for non-exponential service times that the optimal distribution of interarrival times depends on the relative values of the mean interarrival time and the mean service time. Finally, we propose a simple to calculate upper bound to the average age for the preemption in service discipline.

We consider an information update system where an information receiver requests updates from an information provider in order to minimize its age of information. The updates are generated at the information provider (transmitter) as a result of completing a set of tasks such as collecting data and performing computations on them. We refer to this as the update generation process. We model thequalityof an update as an increasing function of the processing time spent while generating the update at the transmitter. In particular, we usedistortionas a proxy forquality, and model distortion as a decreasing function of processing time. Processing longer at the transmitter results in a better quality (lower distortion) update, but it causes the update to age in the process. We determine the age-optimal policies for the update request times at the receiver and the update processing times at the transmitter subject to a minimum required quality (maximum allowed distortion) constraint on the updates. For the required quality constraint, we consider the cases of constant maximum allowed distortion constraints, as well as age-dependent maximum allowed distortion constraints.

We consider a cache updating system with a source, a cache and a user. There are n files. The source keeps the freshest version of the files which are updated with known rates λi. The cache downloads and keeps the freshest version of the files from the source with rates ci. The user gets updates from the cache with rates ui. When the user gets an update, it either gets a fresh update from the cache or the file at the cache becomes outdated by a file update at the source in which case the user gets an outdated update. We find an analytical expression for the average freshness of the files at the user. Next, we generalize our setting to the case where there are multiple caches in between the source and the user, and find the average freshness at the user. We provide an alternating maximization based method to find the update rates for the cache(s), ci, and for the user, ui, to maximize the freshness of the files at the user. We observe that for a given set of update rates for the user (resp. for the cache), the optimal rate allocation policy for the cache (resp. for the user) is a threshold policy, where the optimal update rates for rapidly changing files at the source may be equal to zero. Finally, we consider a system where multiple users are connected to a single cache and find update rates for the cache and the users to maximize the total freshness over all users.

We study age of information in a multiple source-multiple destination setting with a focus on its scaling in large wireless networks. There are n nodes uniformly and independently distributed on a fixed area that are randomly paired with each other to form n source-destination (S-D) pairs. Each source node wants to keep its destination node as up-to-date as possible. To accommodate successful communication between all n S-D pairs, we first propose a three-phase transmission scheme which utilizes local cooperation between the nodes along with what we call mega update packets to serve multiple S-D pairs at once. We show that under the proposed scheme average age of an S-D pair scales as O(n1/4logn) as the number of users, n, in the network grows. Next, we observe that communications that take place in Phases I and III of the proposed scheme are scaled-down versions of network-level communications. With this along with scale-invariance of the system, we introduce hierarchy to improve this scaling result and show that when hierarchical cooperation between users is utilized, an average age scaling of O(nα(h)logn) per-user is achievable, where h denotes the number of hierarchy levels and α(h) = 1/3·2h+1. We note that α(h) tends to 0 as h increases, and asymptotically, the average age scaling of the proposed hierarchical scheme is O(logn). To the best of our knowledge, this is the best average age scaling result in a status update system with multiple S-D pairs.

Coded computation can speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration; however, this can result in biased estimators, which may slow down convergence, or even cause divergence. Estimator bias is particularly prevalent when the straggling behavior is correlated over time, which results in the gradient estimators being dominated by a few fast servers. To mitigate biased estimators, we design a timely dynamic encoding framework for partial recovery that includes an ordering operator that changes the codewords and computation orders at workers over time. To regulate the recovery frequencies, we adopt an age metric in the design of the dynamic encoding scheme. The proposed age-based scheme prioritizes the recovery of computations with relatively large age. We show through numerical results that the proposed dynamic encoding strategy increases the timeliness of the recovered computations, which, as a result, reduces the bias in model updates, and accelerates the convergence compared to conventional static partial recovery schemes.

We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user privately retrieves a message out of K independent messages stored in N replicated and non-colluding databases. The messages come with different semantics, i.e., the messages are allowed to have non-uniform a priori probabilities denoted by (pi> 0, i ∈ [K]) and arbitrary message sizes (Li, i ∈ [K]). We derive the semantic PIR capacity for general K, N. We present two achievable semantic PIR schemes: The first one is a deterministic scheme with non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are of equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate.

We consider an information updating system where a source produces updates as requested by a transmitter. The transmitter further processes these updates in order to generate partial updates, which have smaller information compared to the original updates, to be sent to a receiver. We study the problem of generating partial updates, and finding their corresponding real-valued codeword lengths, in order to minimize the average age experienced by the receiver, while maintaining a desired level of mutual information between the original and partial updates. This problem is NP hard. We relax the problem and develop an alternating minimization based iterative algorithm that generates a pmf for the partial updates, and the corresponding age-optimal real-valued codeword length for each update. We observe that there is a tradeoff between the attained average age and the mutual information between the original and partial updates.

An information source generates independent and identically distributed status update messages from an observed random phenomenon which takes n distinct values based on a given pmf. These update packets are encoded at the transmitter to be sent to a receiver which wants to track the observed random variable with as little age as possible. The transmitter implements a selective k encoding policy such that rather than encoding all possible n realizations, the transmitter encodes the most probable k realizations and sends a designated empty symbol when one of the remaining n-k realizations occurs. We consider two scenarios: when the empty symbol does not reset the age and when the empty symbol resets the age. We find the time average age of information and the age-optimal real codeword lengths, including the codeword length for the empty symbol, for both of these scenarios. Through numerical evaluations for arbitrary pmfs, we show that this selective encoding policy yields a lower age at the receiver than encoding every realization and find the corresponding age-optimal k values.

We study the problem of private set intersection (PSI). In PSI, there are two entities, each storing a set Pi, whose elements are picked from a finite set SK, on Nireplicated and non-colluding databases. It is required to determine the set intersection P1∩P2without leaking any information about the remaining elements to the other entity. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem. Next, as a stand-alone result, we show that the exact capacity of MM-SPIR is CMM-SPIR= 1 - 1/N when P ≤ K - 1, if the common randomness S satisfies H(S) ≥ P/N-1 per desired symbol. This result implies that there is no gain for MM-SPIR over successive single-message SPIR. We present a novel capacity-achieving scheme which builds seamlessly over the multi-message PIR (MM-PIR) scheme. Based on this capacity result for the MM-SPIR problem, we show that the optimal download cost for the PSI problem is given by min{[P1N2/N2-1],[P2N1/N1-1]}, where P i is the cardinality of the set Pi.

We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and n worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it updated. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d. exponential transmission delays and i.i.d shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.

An energy-harvesting sensor node that is sending status updates to a destination is considered. The sensor is equipped with a battery of finite size to save its incoming energy, and consumes one unit of energy per status update transmission, which is delivered to the destination instantly over an error-free channel. The setting is online in which the harvested energy is revealed to the sensor causally over time after it arrives, and the goal is to design status update transmission times (policy) such that the long term average age of information (AoI) is minimized. The AoI is defined as the time elapsed since the latest update has reached at the destination. Two energy arrival models are considered: a random battery recharge (RBR) model, and an incremental battery recharge (IBR) model. In both models, energy arrives according to a Poisson process with unit rate, with values that completely fill up the battery in the RBR model, and with values that fill up the battery incrementally in a unit-by-unit fashion in the IBR model. The key approach to characterizing the optimal status update policy for both models is showing the optimality of renewal policies, in which the inter-update times follow a renewal process in a certain manner that depends on the energy arrival model and the battery size. It is then shown that the optimal renewal policy has an energy-dependent threshold structure, in which the sensor sends a status update only if the AoI grows above a certain threshold that depends on the energy available in its battery. For both the random and the incremental battery recharge models, the optimal energy-dependent thresholds are characterized explicitly, i.e., in closed-form, in terms of the optimal long term average AoI. It is also shown that the optimal thresholds are monotonically decreasing in the energy available in the battery, and that the smallest threshold, which comes in effect when the battery is full, is equal to the optimal long term average AoI.

We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints m = (m1, ⋯, mN). The aim of this work is to jointly design the content placement phase and the information retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint μ = 1/N Σn=1Nmn. N Thus, we show that there is no loss in the PIR capacity due to heterogeneity of storage spaces of the databases. We provide the optimum content placement explicitly for N = 3.

We consider the problem of private information retrieval through wiretap channel II (PIR-WTC-II). In PIR-WTC-II, a user wants to retrieve a single message (file) privately out of M messages, which are stored in N replicated and non-communicating databases. An external eavesdropper observes a fraction μn(of its choice) of the traffic exchanged between the nth database and the user. In addition to the privacy constraint, the databases should encode the returned answer strings such that the eavesdropper learns absolutely nothing about the contents of the databases. We aim at characterizing the capacity of the PIR-WTC-II under the combined privacy and security constraints. We obtain a general upper bound for the problem in the form of a max-min optimization problem, which extends the converse proof of the PIR problem under asymmetric traffic constraints. We propose an achievability scheme that satisfies the security constraint by encoding a secret key, which is generated securely at each database, into an artificial noise vector using an MDS code. The user and the databases operate at one of the corner points of the achievable scheme for the PIR under asymmetric traffic constraints such that the retrieval rate is maximized under the imposed security constraint. The upper bound and the lower bound match for the case of M = 2 and M = 3 messages, for any N, and any μ = (μ1, · · · , μN).

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size S possesses side information in the form of uncoded portions of the messages where the message identities are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint S as D* = 1+ 1/N + 1/N2+· · ·+ 1/NK-1-M+ 1-rM/NK-M+ 1-rM-1/NK-M+1+ · · · + 1-r1/NK-1, where M is the number of side information messages and ri is the portion of the ith side information message that is cached with Σi=1Mri= S. Based on this capacity result, we prove two facts: First, for a fixed memory size S and a fixed number of accessible messages M, uniform caching achieves the lowest normalized download cost, i.e., ri= S/M, for i = 1, . . . , M, is optimum. Second, for a fixed memory size S, among all possible K - ⌈S⌉ + 1 uniform caching schemes, the uniform caching scheme which caches M = K messages achieves the lowest normalized download cost.

Given n randomly located source-destination (S- D) pairs on a fixed area network that want to communicate with each other, we study the age of information with a particular focus on its scaling as the network size n grows. We propose a three- phase transmission scheme that utilizes hierarchical cooperation between users along with mega update packets and show that an average age scaling of O(nα(h)log n) per-user is achievable where h denotes the number of hierarchy levels and α(h) = 1 / (3.2h+1) which tends to 0 as h increases such that asymptotically average age scaling of the proposed scheme is O(log n). To the best of our knowledge, this is the best average age scaling result in a status update system with multiple S-D pairs.

Coded computation techniques provide robustness against straggling servers in distributed computing, with the following limitations: First, they increase decoding complexity. Second, they ignore computations carried out by straggling servers; and they are typically designed to recover the full gradient, and thus, cannot provide a balance between the accuracy of the gradient and per-iteration completion time. Here we introduce a hybrid approach, called coded partial gradient computation (CPGC), that benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and decoding complexity.

We study age of information in a multiple source-multiple destination setting with a focus on its scaling in large wireless networks. There are n nodes that are randomly paired with each other on a fixed area to form n source-destination (SD) pairs. We propose a three-phase transmission scheme which utilizes local cooperation between the nodes by forming what we call mega update packets to serve multiple S-D pairs at once. We show that under the proposed scheme average age of an S-D pair scales as O(n1/4log n) as the number of users, n, in the network grows. To the best of our knowledge, this is the best age scaling result for a multiple source-multiple destination setting.

A real-time status updating system is considered, in which an energy harvesting sensor is acquiring measurements regarding some physical phenomenon and sending them to a destination through an erasure channel. The setting is online, in which energy arrives in units according to a Poisson process with unit rate, with arrival times being revealed causally over time. Energy is saved in a unit-sized battery. The sensor is notified by the destination of whether updates were erased via feedback. Updates need to reach the destination successfully in a timely fashion, namely, such that the long term average age of information, defined as the time elapsed since the latest successful update has reached the destination, is minimized. First, it is shown that the optimal status update policy has a renewal structure: successful update times should constitute a renewal process. Then, threshold-greedy policies are investigated: a new update is transmitted, following a successful one, only if the age of information grows above a certain threshold; and if it is erased, then all subsequent update attempts are greedily scheduled whenever energy is available. The optimal threshold-greedy policy is then analytically derived.

We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints m = (m1, ⋯, mN). The aim of this work is to jointly design the content placement phase and the retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint μ = 1/N Σn = 1Nmn. We show the optimum content placement explicitly for N = 3.

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N non-colluding and non-replicated databases. Different from the majority of the existing literature, here, we consider the case of non-replicated databases under a special non-replication structure where each database stores M out of K messages and each message is stored across R different databases. This generates an R-regular graph structure for the storage system where the vertices of the graph are the messages and the edges are the databases. We derive a general upper bound for M = 2 that depends on the graph structure. We then specialize the problem to storage systems described by two special types of graph structures: cyclic graphs and fully-connected graphs. We prove that the PIR capacity for the case of cyclic graphs is 2/K+1, and the PIR capacity for the case of fully-connected graphs is min{2/K, 1/2}. In both cases, the results show severe degradation in PIR capacity due to non-replication.

When gradient descent (GD) is scaled to many parallel computing servers (workers) for large scale machine learning problems, its per-iteration computation time is limited by the straggling workers. Coded distributed GD (DGD) can tolerate straggling workers by assigning redundant computations to the workers, but in most existing schemes, each non-straggling worker transmits one message per iteration to the parameter server (master) after completing all its computations. We allow multiple computations to be conveyed from each worker per iteration in order to exploit computations executed also by the straggling worker. We show that the average completion time per iteration can be reduced significantly at a reasonable increase in the communication load. We also propose a general coded DGD technique which can trade-off the average computation time with the communication load.

We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint μKL bits exist in the system. Each database independently chooses μKL bits out of the total KL bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be D/L = Σn-1N+1(n-1N)μn-1(1 - μ)N+1-n(1 + 1/n + ⋯ + 1/nK-1). We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by MaddahAli and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly result in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar and Tandon for the centralized case.

We consider the problem of private information retrieval from N storage-constrained databases. In this problem, a user wishes to retrieve a single message out of M messages (of size L) without revealing any information about the identity of the message to individual databases. Each database stores μML symbols, i.e., a μ fraction of the entire library, where 1/N ≤ μ ≤ 1. Our goal is to characterize the optimal tradeoff 1 curve for the storage cost (captured by μ) and the normalized download cost (D/L). We show that the download cost can be reduced by employing a hybrid storage scheme that combines MDS coding ideas with uncoded partial replication ideas. When there is no coding, our scheme reduces to Attia-Kumar-Tandon storage scheme, which was initially introduced by Maddah-AliNiesen in the context of the caching problem, and when there is no uncoded partial replication, our scheme reduces to BanawanUlukus storage scheme; in general, our scheme outperforms both.

We consider an information update system where an information receiver requests updates from an information provider in order to minimize its age of information. The updates are generated at the transmitter as a result of completing a set of tasks such as collecting data and performing computations. We refer to this as the update generation process. We model the quality (i.e., distortion) of an update as an increasing (resp. decreasing) function of the processing time spent while generating the update at the transmitter. While processing longer at the transmitter results in a better quality (lower distortion) update, it causes the update to age. We determine the age-optimal policies for the update request times at the receiver and update processing times at the transmitter subject to a minimum required quality (maximum allowed distortion) constraint on the updates.

We consider the two-user multiple-input multipleoutput (MIMO) interference channel with confidential messages (ICCM). We determine the exact secure degrees of freedom (s.d.o.f.) region for the symmetric case of M antennas at both transmitters and N antennas at both receivers. We develop the converse by combining the broadcast channel with confidential messages (BCCM) cooperative upper bound, decodability upper bound for the interference channel with no secrecy constraints, and vector extensions of the secrecy penalty and role of a helper lemmas. For the achievability, we first show that the s.d.o.f. region is a four-vertex polytope. For the sum s.d.o.f. point, we propose a novel achievable scheme for the 2 × 2 ICCM, which combines asymptotic real interference alignment with spatial interference alignment. Using this scheme, we provide achievable schemes for any M and N by proper vector space operations. We achieve the other non-trivial extreme polytope points by employing one of the transmitters as a deaf helper for assisting the secure transmission of the other user. We present simplified achievable schemes for the special case of time-varying MIMO ICCM. The achievable schemes, in this case, make use of the time-varying nature of the channel to construct vector-space alignment counterpart of the real interference alignment used in the static channel case.

We consider the problem of single-round private information retrieval (PIR) from N replicated databases. We consider the case when B databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of M messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the T-privacy constraint in this paper, where any T databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately (under the T-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be C = (N -2B)/N·(1-T/(N-2B))/(1-(T/(N - 2B))M), if 2B + T <; N. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing 2B databases from the system, with a penalty factor of (N - 2B)/N, which signifies that even though the number of databases needed for PIR is effectively N - 2B, the user still needs to access the entire N databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are missynchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases as opposed to erasures in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.

We consider the classical setting of private information retrieval (PIR) of a single message (file) out of M messages from N distributed databases under the new constraint of asymmetric traffic from databases. In this problem, the ratios between the traffic from the databases are constrained, i.e., the ratio of the length of the answer string that the user (retriever) receives from the nth database to the total length of all answer strings from all databases is constrained to be τn. This may happen if the user's access to the databases is restricted due to database availability, channel quality to the databases, and other factors. For this problem, for fixed M, N, we develop a general upper bound C̅(τ), which generalizes the converse proof of Sun-Jafar, where database symmetry was inherently used. Our converse bound is a piece-wise affine function in the traffic ratio vector τ = (τ1, · · · ,τN). For the lower bound, we explicitly show the achievability of (M+N-1/M) corner points. For the remaining traffic ratio vectors, we perform time-sharing between these corner points. The recursive structure of our achievability scheme is captured via a system of difference equations. The upper and lower bounds exactly match for M = 2 and M = 3 for any N and any τ. The results show strict loss of PIR capacity due to the asymmetric traffic constraints compared with the symmetric case of Sun-Jafar which implicitly uses τn= N1for all n.

We consider the problem of noisy private information retrieval (NPIR) from$N$non-communicating databases, each storing the same set of$M$messages. In this model, the answer strings are not returned through noiseless bit pipes, but rather throughnoisymemoryless channels. We aim at characterizing the PIR capacity for this model as a function of the statistical information measures of the noisy channels such as entropy and mutual information. We derive a general upper bound for the retrieval rate in the form of a max-min optimization. We use the achievable schemes for the PIR problem under asymmetric traffic constraints and random coding arguments to derive a general lower bound for the retrieval rate. The upper and lower bounds match for$M=2$and$M=3$, for any$N$, and any noisy channel. The lower and upper bounds show a separation between channel coding and retrieval scheme except for adapting the traffic ratio from the databases. We refer to this asalmost separation. Next, we consider the private information retrieval problem from multiple access channels (MAC-PIR). In MAC-PIR, the database responses reach the user through a multiple access channel (MAC) that mixes the responses together in a stochastic way. We show that for the additive MAC and the conjunction/disjunction MAC, channel coding and retrieval scheme areinseparableunlike in NPIR. We show that the retrieval scheme depends on the properties of the MAC, in particular on the linearity aspect. For both cases, we provide schemes that achieve the full capacity without any loss due to the privacy constraint, which implies that the user can exploit the nature of the channel to improve privacy. Finally, we show that the full unconstrained capacity is not always attainable by determining the capacity of the selection channel.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D*(r) the optimal download cost normalized with the message size as a function of K, N, and r. For a fixed K and N, we develop an inner bound (converse bound) for the D*(r) curve. The inner bound is a piece-wise linear function in r that consists of K line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve K -1 non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in r that consists of K line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest gap between the achievability and the converse bounds is 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content.

We consider the problem of private information retrieval (PIR) of a single message out of$K$messages from$N$replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size$M$possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives$m_{n}$full messages from the$n$th database, under the cache memory size constraint$\sum _{n=1}^{N} m_{n} \leq M$. In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model aspartially known private side information. We characterize the capacity of the PIR with partially known private side information to be$C=\left ({1+\frac {1}{N}+\cdots +\frac {1}{N^{K-M-1}}}\right)^{-1}=\frac {1-\frac {1}{N}}{1-\left({\frac {1}{N}}\right)^{K-M}}$. Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases.

A two-hop energy harvesting communication network is considered, in which measurement updates are transmitted by a source to a destination through an intermediate relay. Updates are to be sent in a timely fashion that minimizes the age of information, defined as the time elapsed since the most recent update at the destination was generated at the source. The source and the relay communicate using energy harvested from nature, which is stored in infinite-sized batteries. Both nodes use fixed transmission rates, and hence updates incur fixed delays (service times). Two problems are formulated: an offline problem, in which the energy arrival information is known a priori, and an online problem, in which such information is revealed casually over time. In both problems, it is shown that it is optimal to transmit updates from the source just in time as the relay is ready to forward them to the destination, making the source and the relay act as one combined node. A recurring theme in the optimal policy is that updates should be as uniformly spread out over time as possible, subject to energy causality and service time constraints. This is perfectly achieved in the offline setting, and is achieved almost surely in the online setting by a best effort policy.

We consider an energy harvesting sensor that is sending measurement updates regarding some physical phenomenon to a destination. The sensor relies on energy harvested from nature to measure and send its updates, and is equipped with a battery of finite size to collect its harvested energy. The energy harvesting process is Poisson with unit rate, and arrives in amounts that fully recharge the battery. Our setting is online in the sense that the times of energy arrivals are revealed causally to the sensor after the energy is harvested; only the statistics of the arrival process is known a priori. Updates need to be sent in a timely manner to the destination, namely, such that the long term average age of information is minimized over the course of communication. The age of information is defined as the time elapsed since the freshest update has reached the destination. We first show that the optimal scheduling update policy is a renewal policy, and then show that it has a multi threshold structure: the sensor sends an update only if the age of information grows above a certain threshold that depends on the available energy.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receivesrN uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D*(r) as a function of K, N, r. For a fixed K, N, we develop an inner bound (converse) and an outer bound (achievability) for the D*(r) curve. The bounds match in general for the cases of very low caching ratio (r ≤ 1/NK-1) and very high caching ratio (r ≥ K-2/N2-3N+KN). As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest gap between the achievability and the converse bounds is 5/32.

We consider an energy harvesting transmitter sending status updates regarding a physical phenomenon it observes to a receiver. Different from the existing literature, we consider a scenario where the status updates carry information about an independent message. The transmitter encodes this message into the timings of the status updates. The receiver needs to extract this encoded information, as well as update the status of the observed phenomenon. The timings of the status updates, therefore, determine both the age of information (AoI) and the message rate (rate). We study the tradeoff between the achievable message rate and the achievable average AoI. We propose several achievable schemes and compare their rate-AoI performances.

We consider the problem of private information retrieval through a wiretap channel II (PIR-WTC-II). In PIR-WTC-II, a user wants to retrieve a message (or file) privately out of M messages, which are stored in N replicated and noncommunicating databases. An eavesdropper observes a fraction μnof the traffic exchanged between the nth database and the user. The databases should encode the returned answer strings such that the eavesdropper learns nothing about the contents of the databases. We aim at characterizing the capacity of the PIR-WTC-II under these joint privacy and security constraints. We obtain an upper bound in the form of a max-min optimization problem. We propose an achievability scheme that satisfies the security constraint by encoding a secret key into an artificial noise vector using an MDS code. The user and the databases operate at one of the corner points of the achievable scheme of the PIR under asymmetric traffic constraints such that the retrieval rate is maximized under the imposed security constraint. The upper bound and the lower bound match for the cases of M = 2 and M = 3 messages, for any number of databases N, and any μn.

We consider the problem of private information retrieval (PIR) of a single message (file) out of M messages from N distributed databases under asymmetric traffic from databases. In this problem, the ratios between the traffic from the databases are constrained, i.e., the ratio of the length of the answer string that the user receives from the nth database to the total length of all answer strings from all databases is constrained to be τn. For this problem, for fixed M, N, we develop a general upper bound C̅(τ). Our converse bound is a piece-wise affine function in the traffic ratio vector τ = (τ1, ⋯, τN). For the lower bound, we explicitly show the achievability of (MM+N-1) corner points. For the remaining traffic ratio vectors, we perform time-sharing between these corner points. The recursive structure of our achievability scheme is captured via a system of difference equations. The upper and lower bounds exactly match for M=2 and M=3 for any N and any τ.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D*(r) the optimal download cost normalized with the message size as a function of K, N, r. We develop inner and outer bounds for the optimal download cost. Both inner and outer bounds are piece-wise linear functions in r (for fixed N, K) that consist of K line segments. The inner and the outer bounds match in general for the cases of very low caching ratios and very high caching ratios. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest additive gap between the achievability and the converse bounds is [1/6].

We consider the private information retrieval problem from multiple access channels (MAC-PIR). In MAC-PIR, there areN databases, each storing the same set of M messages. The database responses reach the user through a multiple access channel (MAC) that may mix the responses together in a stochastic way. We show that for the additive MAC and the conjunction/disjunction MAC, channel coding and retrieval scheme are inseparable unlike the noisy private information retrieval problem (NPIR). We show that the retrieval scheme depends on the properties of the MAC, in particular on the linearity aspect. For both cases, we provide schemes that achieve the full capacity without any loss due to the privacy constraint, which implies that the user can exploit the nature of the channel in its favor. Finally, we show that the full capacity is not always attainable by determining the capacity of the selection channel.

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size S possesses side information in the form of uncoded portions of the messages that are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint S as D* =1+1/N+ 1/N2+ · · · + 1/NK-1-M+ 1 - rM/NK-M+ 1 - rM1/NK-M+1 + · · · + 1-r1/ NK-1, where riis the portion of the ith side information message that is cached with Σi=1Mri= S. Based on this capacity result, we prove two facts: First, for a fixed memory size S and a fixed number of accessible messages M, uniform caching achieves the lowest normalized download cost, i.e., ri= S/M, for i = 1,· · ·, M, is optimum. Second, for a fixed memory size S, among all possible K - 〈S〉 +1 uniform caching schemes, the uniform caching scheme which caches M = K messages achieves the lowest normalized download cost.

We consider a two-user energy harvesting multiple access channel where the temperatures of the nodes are affected by the electromagnetic waves caused by the data transmission. To protect the nodes from excess heat, power allocation policies should take into consideration the temperature of all the nodes. In this paper, we study the optimal power allocations when the temperatures of the nodes are subject to peak temperature constraints. We first study the general case where each node has a different peak temperature requirement and the nodes have different temperature parameters. For this case, we show that the capacity region of the single energy arrival case is a single pentagon. We also show that the optimal policy for the multiple energy arrivals can be obtained by using generalized water-filling. We then study the temperature limited case where the transmitters have abundant energy and the only binding constraints are the temperature constraints. We study the optimal power allocation in this case and we derive sufficient conditions under which the rate region collapses to a single pentagon.

We consider the problem of private information retrieval from N non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction r of the symbols from each of the K stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receives r/N uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D*(r) in the retrieval phase as a function of K, N, and r. We develop lower and upper bounds for the optimal download cost. The bounds match in general for the cases of very low caching ratio and very high caching ratio. We fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r values, we show that the largest additive gap between the achievability and the converse bounds is 5/32.

We characterize delay minimal power scheduling policies in energy harvesting communication systems. We consider a continuous-time system, where the delay experienced by each bit is given by the time spent by the bit in the queue waiting to be transmitted to its receiver. We first consider a single-user channel, where the transmitter has a finite-sized battery to save its harvested energy. Data arrives during the course of communication and are saved in a finite data buffer as well. We find the optimal power policy that minimizes the average delay experienced by the bits subject to energy and data causality constraints. We characterize the optimal solution in terms of Lagrange multipliers, and calculate their values in a recursive manner. We show that, different from the existing literature, the optimum transmission power is not constant between the energy and data arrival events; the transmission power starts high, decreases linearly, and potentially reaches zero between energy and data arrivals. Intuitively, untransmitted bits experience cumulative delay due to the bits to be transmitted ahead of them, and hence the reason for transmission power starting high and decreasing over time. Next, we study a multiuser version of this problem, namely, a two-user broadcast channel, and characterize the optimal transmission policies that minimize the sum delay. For this setting, we consider the case, where the transmitter has an infinite-sized battery, and that all data packets intended for the receivers are available at the beginning of the communication session. We characterize the optimal solution in terms of Lagrange multipliers, and present an iterative solution that calculates their values. Our results show that in the optimal policy, both users may not be served simultaneously all the time; there may be times, where only one of the two users is served alone. We also show that the optimal policy may have gaps in transmission in between energy arrivals, where none of the users is served, echoing the results of the single-user setting.

We consider online transmission policies for a two-user multiple access channel, where both users harvest energy from nature. The energy harvests are independent and identically distributed (i.i.d.) over time, but can be arbitrarily correlated between the two users. The transmitters are equipped with arbitrary but finite-sized batteries. We focus on the online case where the transmitters know the energy arrivals only causally as they happen. The users do not know the probability distribution of the energy arrivals; each user knows only its own average recharge rate. We consider the most general case of arbitrarily distributed energy arrivals with arbitrary correlation between the users. In order to study this general case, we first study a special case for the energy arrivals, namely, we first consider the special case of synchronized (i.e., fully-correlated) Bernoulli energy arrivals at the two users. Even though the energy arrivals are fully-correlated, average recharge rates at the users are different due to the different battery sizes. For this case, we determine the exactly optimal policies that achieve the boundary of the long-term average capacity region. We show that the optimal power allocation policy is decreasing within the renewal interval, and that the long-term average capacity region is a single pentagon. We then propose a distributed fractional power (DFP) policy, which users implement distributedly with no knowledge of the other user's energy arrival or battery state. We develop a lower bound on the performance of the DFP for synchronized Bernoulli energy arrivals. We then consider the case of two arbitrarily correlated asynchronous Bernoulli energy arrivals under the assumption of equal normalized average recharge rates. We show that extreme correlation between the energy sources hurts the achievable rate by showing that the throughput with asynchronous Bernoulli energy arrivals is larger than the throughput with the corresponding perfectly synchronized Bernoulli energy arrivals. We then show that under the DFP policy, the performance of Bernoulli energy arrivals forms a lower bound on the performance of any arbitrary energy arrivals. We also develop a universal upper bound on the performance of all online policies, and show that the proposed DFP is near-optimal in that it yields rates which are within a constant gap of the derived lower and upper bounds, and hence, of the optimal policy, for all system parameters.

We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K/N + K2/N2+ ⋯ + KM-1/NM-1)-1= (1 + Rc+ Rc2+ ⋯ + RcM-1)-1= (1 - Rc)/(1 - RcM), where Rcis the rate of the (N, K) MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases.

We consider the problem of multi-message private information retrieval (MPIR) from N non-communicating replicated databases. In MPIR, the user is interested in retrieving P messages out of M stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR CsP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol, where the symbols are defined over the same field. For the case P ≥ M/2, we determine the exact sum capacity of MPIR as CPs= 1/(1+(M - P)/(PN)). The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For P ≤ M/2, we develop lower and upper bounds for all M, P, N. These bounds match if the total number of messages M is an integer multiple of the number of desired messages P, i.e., M/P ∈ N. In this case, CsP= (1+1/N+⋯+1/NM/P-1)-1, i.e., CsP= (1 - 1/N)/(1 - 1/NM/P) for N>1, and CsP= P/M for N = 1. The achievable scheme in this case generalizes the singlemessage capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most 0.0082, which occurs for M = 5, P = 2, N = 2. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes even after considering the free savings that result from downloading undesired symbols in each single-message retrieval round.

We consider a two-user multiple-input multiple-output multiple access wiretap channel with N antennas at each transmitter, N antennas at the legitimate receiver, and K antennas at the eavesdropper. We determine the optimal sum secure degrees of freedom (s.d.o.f.) for this model for all values of N and K. We subdivide our problem into several regimes based on the values of N and K, and provide achievable schemes based on vector space alignment and real alignment techniques for fixed and fading channel gains. To prove the optimality of the achievable schemes, we provide matching converses for each regime. Our results show how the number of eavesdropper antennas affects the optimal sum s.d.o.f. of the multiple access wiretap channel.

We consider power scheduling policies for single-user energy harvesting communication systems, where the goal is to characterize online policies that maximize the long term average utility, for general concave and monotonically increasing utility functions. The transmitter relies on energy harvested from nature to send its messages to the receiver, and is equipped with a finite-sized battery to store its harvested energy. Energy packets are independent and identically distributed (i.i.d.) over time slots, and are revealed causally to the transmitter. We first characterize the optimal solution for the case of Bernoulli arrivals. Then, for general i.i.d. arrivals, we first show that fixed fraction policies, in which a fixed fraction of the battery state is consumed in each time slot, are within a constant multiplicative gap from the optimal solution for all energy arrivals and battery sizes. We then derive a set of sufficient conditions on the utility function to guarantee that fixed fraction policies are within a constant additive gap as well from the optimal solution. We then apply these results to a specific scenario where a sensor node collects samples from a Gaussian source and sends them to a destination node over a Gaussian channel, and the goal is to minimize the long term average distortion of the source samples received at the destination. We study two problem settings for this case: the first is when sampling is cost-free, and the second is when there is a sampling cost incurred whenever samples are collected. For the problem with sampling costs, the transmission policy can be bursty; the sensor may collect samples and transmit for only a portion of the time. Finally, we present an alternative analysis approach that is more tailored to these distortion problems to show that fixed fraction policies achieve an additive gap that is independent of the sampling cost.

With a motivation to understand the effects of temperature sensitivity on wireless data transmission performance, we consider an energy harvesting communication system, where the temperature dynamics are governed by the transmission power policy. Different from the previous work, we consider a discrete time system where transmission power is kept constant in each slot. We consider two models that capture different effects of temperature. In the first model, the temperature is constrained to be below a critical temperature at all time instants; we coin this the explicit temperature constrained model. We investigate throughput optimal power allocation for multiple energy arrivals under general, as well as temperature and energy limited regimes. We show that the optimal power allocation for the temperature limited case is monotone decreasing. In the second model, we consider the effect of the temperature on the channel quality via its influence on additive noise power; we coin this the implicit temperature constrained model. In this model, the change in the variance of the additive noise due to previous transmissions is non-negligible. In particular, transmitted signals contribute as interference for all subsequent slots and thus affect the signal to interference plus noise ratio (SINR). In this case, we investigate throughput optimal power allocation under general, as well as low and high SINR regimes. We show in the low SINR regime that the optimal allocation dictates the transmitter to save its harvested energy till the last slot. In the high SINR regime, we show that the optimal power sequence is monotone increasing. Finally, we consider the case in which implicit and explicit temperature constraints are simultaneously active and we show under certain conditions that the optimal power sequence is monotone decreasing.

We consider an energy harvesting two user cooperative Gaussian multiple access channel, where both of the users harvest energy from nature. The users cooperate at the physical layer (data cooperation) by establishing common messages through overheard signals and then cooperatively sending them. We study two scenarios within this model. In the first scenario, the data packets arrive intermittently over time. We find the optimal offline transmit power and rate allocation policy that maximize the departure region. We first show that there exists an optimal policy, in which the single user rate constraints in each time slot are tight, yielding a one-to-one relation between the powers and rates. Then, we formulate the departure region maximization problem as a weighted sum departure maximization in terms of rates only. Next, we propose a sequential convex approximation method to approximate the problem at each step and show that it converges to the optimal solution. We solve the approximate problems using an inner-outer decomposition method. In the second scenario, the data packets are available at the beginning of the transmission, but the users now have the ability to cooperate at the battery level (energy cooperation), in addition to data cooperation. The energy cooperation is facilitated by wireless energy transfer and is bidirectional. For this scenario, we find the jointly optimal offline transmit power and rate allocation policy together with the energy transfer policy that maximize the departure region. We provide necessary conditions for energy transfer and prove some properties of the optimal transmit policy, thereby shedding some light on the interplay between energy and data cooperation.

We consider an energy harvesting two-hop network where a source is communicating to a destination through a relay. During a given communication session time, the source collects measurement updates from a physical phenomenon and sends them to the relay, which then forwards them to the destination. The objective is to send these updates to the destination as timely as possible; namely, such that the total age of information is minimized by the end of the communication session, subject to energy causality constraints at the source and the relay, and data causality constraints at the relay. Both the source and the relay use fixed, yet possibly different, transmission rates. Hence, each update packet incurs fixed non-zero transmission delays. We first solve the single-hop version of this problem, and then show that the two-hop problem is solved by treating the source and relay nodes as one combined node, with some parameter transformations, and solving a single-hop problem between that combined node and the destination.

We consider an energy harvesting communication system where the temperature dynamics is governed by the transmission power policy. Different from the previous work, we consider a discrete time system where transmission power is kept constant in each slot. We consider two models that capture different effects of temperature. In the first model, the temperature is constrained to be below a critical temperature at all time instants; we coin this model as explicit temperature constraint model. We investigate throughput optimal power allocation for multiple energy arrivals under general, as well as temperature and energy limited regimes. In the second model, we consider the effect of the temperature on the channel quality; we coin this model as implicit temperature constraint model. As the dynamic range of the temperature changes significantly, the change in the thermal noise becomes non-negligible, affecting the signal to interference plus noise ratio (SINR). In effect, transmitted signals contribute as interference for all subsequent slots. In this case, we investigate throughput optimal power allocation under general, as well as low and high SINR regimes.

We consider a mobile energy harvesting transmitter where movement is motivated by finding better energy harvesting locations. Movement comes with an energy cost expenditure, and hence there exists a tradeoff between staying at the same location and moving to a new one. On one hand, the transmitter may opt not to move and use all its available energy for transmission; on the other hand, it can choose to move to a potentially better location, spending some of its available energy during the movement process, and yet harvest larger amounts of energy at the new location and achieve higher throughput. In this paper, we characterize this tradeoff by designing throughput-optimal power allocation policies subject to energy causality constraints and moving costs. In our setup, the transmitter moves along a straight line, where two energy sources are located at the opposite ends of the line. We first study the case of a single energy arrival at both sources, and then generalize it to the case of multiple energy arrivals.

We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K/N + K2/N2+ ··· + KM-1/NM-1)-1= (1 + Rc+ R2c+ ··· + RcM-1)-1= 1-Rc/RcM, where Rcis the rate of the (N, K) code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases.

We consider online scheduling policies for single-user energy harvesting communication systems, where the goal is to characterize online policies that maximize the long term average utility, for some general concave and monotonically increasing utility function. In our setting, the transmitter relies on energy harvested from nature to send its messages to the receiver, and is equipped with a finite-sized battery to store its energy. Energy packets are independent and identically distributed (i.i.d.) over time slots, and are revealed causally to the transmitter. Only the average arrival rate is known a priori. We first characterize the optimal solution for the case of Bernoulli arrivals. Then, for general i.i.d. arrivals, we first show that fixed fraction policies [1] are within a constant multiplicative gap from the optimal solution for all energy arrivals and battery sizes. We then derive a set of sufficient conditions on the utility function to guarantee that fixed fraction policies are within a constant additive gap as well from the optimal solution.

We consider online scheduling for an energy harvesting communication system where a sensor node collects samples from a Gaussian source and sends them to a destination node over a Gaussian channel. The sensor is equipped with a finite-sized battery that is recharged by an independent and identically distributed (i.i.d.) energy harvesting process over time. The goal is to minimize the long term average distortion of the source samples received at the destination. We study two problems: the first is when sampling is cost-free, and the second is when there is a sampling cost incurred whenever samples are collected. We show that fixed fraction policies [1], in which a fixed fraction of the battery state is consumed in each time slot, are near-optimal in the sense that they achieve a long term average distortion that lies within a constant additive gap from the optimal solution for all energy arrivals and battery sizes. For the problem with sampling costs, the transmission policy is bursty; the sensor can collect samples and transmit for only a portion of the time.

We consider a single-user channel in which the transmitter is equipped with finite-sized data and energy buffers. The transmitter receives energy and data packets randomly and intermittently over time and stores them in the finite-sized buffers. The arrival amounts are known only causally as they happen. We study the online power allocation problem, in which the transmitter relies only on the causal arrival (energy and data) information. We focus on the special case when the energy and data arrivals are fully-correlated. We first study the case when the arrivals are Bernoulli. For this case, we determine the optimal policy. Inspired by this policy and in order to study the case of general fully-correlated arrivals, we propose a structured policy and bound its performance by a multiplicative gap from the optimal. We then show that this policy is optimal when the energy arrivals dominate the data arrivals, and is within a constant additive gap from the optimal policy when the data arrivals dominate the energy arrivals.

We consider the problem of multi-message private information retrieval (MPIR) from N non-communicating replicated databases. In MPIR, the user is interested in retrieving P messages out of M stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR CP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case P ≥ M/2, we determine the exact sum capacity of MPIR as CPs=1/1+M-P/PN For P≤M/2, we develop lower and upper bounds for all M, P, N. These bounds match if the number of messages M is an integer multiple of the number of desired messages P, in which case, CPs= 1-1N/1-(1/N)M/P. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.

Temperature constraints arise naturally in communication scenarios where the act of data transmission causes heat dissipation. We address this problem in point to point communications over an additive white Gaussian noise channel in an information theoretic setting. In the specific scenario, transmitted code symbols cause heat dissipation as an input to a first order discrete time heat circuit and the output of this dynamical system, being the temperature, has to remain below a critical level Tc. Additionally, we allow the transmitter to use an energy harvesting device to power its transmission. We investigate channel capacity for various combinations of peak and average temperature, average power, and energy harvesting constraints on the transmitted code symbols.

We propose a new decentralized coded caching scheme for a two-phase caching network, where the data placed in user caches in the prefetching phase are random portions of a maximal distance separable (MDS) coded version of the original files. The proposed scheme achieves a better rate memory trade-off by utilizing the reconstruction property of MDS codes which reduces the number of transmissions that are useful only for a small subset of users in the delivery phase. Unlike the previously available coded prefetching schemes, the proposed scheme does not require to have more users than files. The proposed scheme can be viewed as a generalization of the original uncoded prefetching based decentralized coded caching scheme, and likewise, is applicable to various network topologies.

We consider two fundamental multi-user channel models: the multiple-input multiple-output (MIMO) wiretap channel with one helper (WTH) and the MIMO multiple access wiretap (MAC-WT) channel. In each case, the eavesdropper has K antennas while the remaining terminals have N antennas each. We consider a fast fading channel where the channel state information (CSI) of the legitimate receiver is available at the transmitters but no CSI at the transmitters (CSIT) is available for the eavesdropper's channel. We determine the optimal sum secure degrees of freedom (s.d.o.f.) for each channel model for the regime K ≤ N, and show that in this regime, the MAC-WT channel reduces to the WTH in the absence of eavesdropper CSIT. For the regime N ≤ K ≤ 2N, we obtain the optimal linear s.d.o.f., and show that the MAC-WT channel and the WTH have the same optimal s.d.o.f. when restricted to linear encoding strategies. In the absence of any such restrictions, we provide an upper bound for the sum s.d.o.f. of the MAC-WT channel in the regime N ≤ K ≤ 2N. Our results show that unlike in the single-input single-output case, there is loss of s.d.o.f. for even the WTH due to lack of eavesdropper CSIT when K ≥ N.

The two user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied, in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form Ii, i = 1, 2 where I1, I2∈ {P, D, N}, and the forms P, D, and N correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate between nine possible states corresponding to all possible values of I1I2, with each state occurring for λI1I2fraction of the total duration. We assume that perfect and instantaneous CSI is available at the all receivers. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption, where λI1I2= λI2I1. The main technical contributions include developing 1) novel achievable schemes for MISO BCCM with alternating CSIT with security constraints, which also highlight the synergistic benefits of inter-state coding for secrecy; 2) new converse proofs via local statistical equivalence and channel enhancement; and 3) showing the interplay between various aspects of channel knowledge and their impact on s.d.o.f.

We consider three channel models: the wiretap channel with M helpers, the K-user multiple access wiretap channel, and the K-user interference channel with an external eavesdropper, when no eavesdropper's channel state information (CSI) is available at the transmitters. In each case, we establish the optimal sum secure degrees of freedom (s.d.o.f.) by providing achievable schemes and matching converses. We show that the unavailability of the eavesdropper's channel state information at the transmitter (CSIT) does not reduce the s.d.o.f. of the wiretap channel with helpers. However, there is loss in s.d.o.f. for both the multiple access wiretap channel and the interference channel with an external eavesdropper. In particular, we show that in the absence of eavesdropper's CSIT, the K-user multiple access wiretap channel reduces to a wiretap channel with (K - 1) helpers from a sum s.d.o.f. perspective, and the optimal sum s.d.o.f. reduces from K(K-1) /K(K-1)+1 to K-1 K . For the interference channel with an external eavesdropper, the optimal sum s.d.o.f. decreases from K(K-1) /2K-1 to K-1/ 2 in the absence of the eavesdropper's CSIT. Our results show that the lack of eavesdropper's CSIT does not have a significant impact on the optimal s.d.o.f. for any of the three channel models, especially when the number of users is large. This implies that physical layer security can be made robust to the unavailability of eavesdropper CSIT at high signal-to-noise ratio regimes by the careful modification of the achievable schemes as demonstrated in this paper.

We consider a binary energy harvesting communication channel with a finite-sized battery at the transmitter. In this model, the channel input is constrained by the available energy at each channel use, which is driven by an external energy harvesting process, the size of the battery, and the previous channel inputs. We consider an abstraction where energy is harvested in binary units and stored in a battery with the capacity of a single unit, and the channel inputs are binary. Viewing the available energy in the battery as a state, this is a state-dependent channel with input-dependent states, memory in the states, and causal state information available at the transmitter only. We find an equivalent representation for this channel based on the timings of the symbols, and determine the capacity of the resulting equivalent timing channel via an auxiliary random variable. We present achievable rates based on certain selections of this auxiliary random variable, which resemble lattice coding for the timing channel. We develop upper bounds for the capacity by using a genie-aided method, and also by quantifying the leakage of the state information to the receiver. We show that the proposed achievable rates are asymptotically capacity achieving for small energy harvesting rates. We extend the results to the case of ternary channel inputs. We numerically observe that our achievable rates are notably close to the upper bounds, and outperform basic Shannon strategies that only consider instantaneous battery states, for all parameter values.

We consider scheduling for a single-user energy harvesting channel in which the transmitter incurs processing cost per unit time it is on. The presence of processing costs forces the transmitter to operate in a bursty mode. We consider online transmission scheduling where the transmitter knows the energy harvests only causally as they arrive, and needs to determine the optimum transmit power and the optimum burst duration on the fly. We first consider the case of independent and identically distributed (i.i.d.) Bernoulli energy arrivals, and then extend it to the case of general i.i.d. energy arrivals. We determine the exactly optimum online policy for Bernoulli arrivals and propose a nearly optimum online policy for general arrivals. The proposed policy is near-optimum in that it performs within a constant gap from the optimum policy for all energy arrivals and battery-sizes.

We consider an energy harvesting two-way channel with decoding costs. In this system, each node spends energy to transmit data to the other user, and also to decode data coming from the other user; that is, each user divides its harvested energy for transmission and reception. The power needed for decoding the incoming data is a function of the incoming data rate. We determine the optimal offline power scheduling policies for both users that maximize the sum throughput of the system by a given deadline. We first consider the case with a single energy arrival at each user. We show that the transmission is limited by the user with the smaller energy. In this case, the user with larger energy may not consume all of its energy. We next consider the case with multiple energy arrivals at both users. We show that the optimal power allocations are non-decreasing over time, and they increase synchronously at both users. We then develop an iterative algorithm based on two-slot updates to obtain the optimal power allocations for both users.

We consider a two-user energy harvesting broadcast channel, and characterize the delay minimal transmission policies that minimize the total delay experienced by the data packets in the system. We consider a continuous time system where the delay experienced by each bit is given by the time spent by the bit in the queue waiting to be transmitted to its receiver. We consider the case where all data packets are available at the transmitter at the beginning of the communication session. We characterize the optimal solution in terms of the Lagrange multipliers, and present an iterative algorithm that optimally calculates their values. Our results show that in the optimal policy, both users may not be served simultaneously all the time; there may be times where only the strong user or only the weak user is served alone. We also show that the optimal policy may have gaps in transmission where none of the users is served until the next energy arrival.

We consider an energy harvesting two user cooperative Gaussian multiple access channel (MAC), where both of the users harvest energy from nature. The data packets arrive intermittently over time. The users overhear each other's transmitted signals and can cooperate by forming common messages. We find the optimal offline transmit power and rate allocation policy that maximize the departure region. We first show that there exists an optimal policy, in which the single user rate constraints in each time slot are tight, yielding a one to one relation between the powers and rates. Then, we formulate the departure region maximization problem as a weighted sum rate maximization in terms of rates only. Next, we propose a sequential convex approximation method to approximate the problem at each step and show that it converges to the optimal solution. Finally, we solve the approximate problems using an inner outer decomposition method. Numerically, we observe that higher data rates can be supported with the same amount of energy.

We consider a two-user multiple-input multiple-output (MIMO) multiple access wiretap channel with N antennas at each transmitter, N antennas at the legitimate receiver, and K antennas at the eavesdropper. We determine the optimal sum secure degrees of freedom (s.d.o.f.) when the channel gains are fixed for the duration of the communication. We provide optimal achievable schemes based on a combination of Gaussian signaling and real interference alignment for all regimes of N and K.

We consider online transmission scheduling for an energy harvesting broadcast channel with a finite-sized battery. The energy harvests are independent and identically distributed (i.i.d.) in time, and the transmitter gets to know them only causally as they happen. We first consider the case of Bernoulli energy arrivals, and determine the optimum online strategy that allocates power over time and between users optimally. We then consider the case of general i.i.d. energy arrivals, and propose a sub-optimum strategy coined fractional power constant cut-off (FPCC) policy. We develop a lower bound for the performance of the proposed FPCC policy, and a universal upper bound for the capacity region of the energy harvesting broadcast channel. We show that the proposed FPCC policy is near-optimal in that it yields rates that are within a constant gap from the optimum online policy, for all system parameters.

We consider online transmission policies for the two-user multiple access channel, where both users harvest energy from a common source. The transmitters are equipped with arbitrary but finite-sized batteries. The energy harvests are independent and identically distributed (i.i.d.) over time, and synchronized at the two users due to their common source. The transmitters know the energy arrivals only causally. We first consider the special case of Bernoulli energy arrivals. For this case, we determine the optimal policies that achieve the boundary of the capacity region. We show that the optimal power allocation decreases in time, and that the capacity region is a pentagon. We then consider general i.i.d. energy arrivals, and propose a distributed fractional power (DFP) policy. We develop lower and upper bounds on the performance of the proposed DFP policy for general i.i.d. energy arrivals, and show that the proposed DFP is near-optimal in that it yields rates which are within a constant gap of the derived lower and upper bounds.

We investigate the secure degrees of freedom (s.d.o.f.) of two new channel models: broadcast channel with combating helpers and interference channel with selfish users. In the first model, over a classical broadcast channel with confidential messages (BCCM), there are two helpers, each associated with one of the receivers. In the second model, over a classical interference channel with confidential messages (ICCM), there is a helper and users are selfish. The goal of introducing these channel models is to investigate various malicious interactions that arise in networks, including active adversaries. By casting each problem as an extensive-form game and applying recursive real interference alignment, we show that, for the first model, the combating intentions of the helpers are neutralized and the full s.d.o.f. is retained; for the second model, selfishness precludes secure communication and no s.d.o.f. is achieved.

We consider the multiple access wiretap channel (MAC-WTC), where multiple legitimate users wish to have secure communication with a legitimate receiver in the presence of an eavesdropper. The exact secure degrees of freedom (s.d.o.f.) region of this channel is known. Achieving this region requires users to follow a certain protocol altruistically and transmit both message-carrying and cooperative jamming signals in an optimum manner. In this paper, we consider the case when a subset of users deviate from this optimum protocol. We consider two kinds of deviation: when some of the users stop transmitting cooperative jamming signals, and when a user starts sending intentional jamming signals. For the first scenario, we investigate possible responses of the remaining users to counteract such deviation. For the second scenario, we use an extensive-form game formulation for the interactions of the deviating and well-behaving users. We prove that a deviating user can drive the s.d.o.f. to zero; however, the remaining users can exploit its intentional jamming signals as cooperative jamming signals against the eavesdropper and achieve an optimum s.d.o.f.

We present a real interference alignment technique for multiple-input multiple-output (MIMO) networks. This technique is based on a theorem due to Dirichlet and Khintchine for simultaneous Diophantine approximation and uses the outputs of all the antennas at the receiver simultaneously for decoding, instead of using them in an antenna-by-antenna basis. This allows us to forgo asymptotic real interference alignment for several multi-user scenarios such as the two-user MIMO interference channel with confidential messages and the two-user MIMO multiple access wiretap channel.

We consider a channel with N parallel sub-bands. There is a single user that can access exactly k channels, while maintaining some minimum rate at each accessed channel. The transmission takes place in the presence of a jammer which can access at most m channels. We cast the problem as an extensive-form game and derive the optimal power allocation strategies for both the user and the jammer. We present extensive simulation results regarding convergence of rates, effect of changing the number of accessed bands for the user and the jammer, and the minimum rate constraint.

We consider the energy harvesting two user Gaussian multiple access channel (MAC), where both users harvest energy from nature. The users cooperate at the physical layer (data cooperation) by establishing common messages through overheard signals and then cooperatively sending them. In addition, the users cooperate at the battery level (energy cooperation) by wirelessly transferring energy to each other. We find the jointly optimal offline transmit power and rate allocation policy together with the energy transfer policy that maximizes the departure region. We provide necessary conditions for energy transfer, and prove some properties of the optimal transmit policy, thereby shedding some light on the interplay between energy and data cooperation.

We consider a two-way communication channel in which both users rely solely on energy harvested from nature. Each user incurs a processing cost per unit time as long as it communicates; that is, each user's energy consumption includes energy spent for transmission and energy spent for processing. We maximize the sum throughput by a given deadline subject to energy causality constraints. We first show that the optimal power policy is bursty; the two users communicate only during a portion of the time that is uniquely determined by their available energies and processing costs. We show that it is optimal for the two users to be fully synchronized; they turn on and exchange data during the same portion of time, and then turn off together. We first solve the single energy arrival case, and then extend it to solve the multiple energy arrival throughput maximization problem. We show that it is optimal for the users to communicate in a deferred fashion; users postpone their energy consumption to utilize later time slots first. We present an algorithm that gives the optimal deferred policy by iteratively applying a modified version of the single energy arrival result in a backward manner.

We consider an energy harvesting broadcast channel where a transmitter powered by energy harvested from the environment serves data to two receivers on the downlink. Energy harvests occur randomly over time as an independent and identically distributed (i.i.d.) random process; the battery at the transmitter in which the harvested energy is stored is of finite size. We focus on online transmission schemes where the transmitter knows the energy arrivals only causally as they happen. We first consider the case where the energy arrivals follow a Bernoulli distribution, where the incoming energy is either zero or it fills the battery completely. For this case, we determine the optimum online strategy that allocates power over time and between users optimally. We note that the optimum total transmit power is not equal to the optimum single-user transmit power as it depends on the receiver noise variance; this is unlike the offline problem, where the optimum total transmit power in the broadcast channel equals the optimum single-user transmit power. We then consider the case of general i.i.d. energy arrivals, and propose a sub-optimum strategy coined fractional power constant cut-off (FPCC) policy. We develop a lower bound for the performance of the proposed FPCC policy. In addition, we develop a universal upper bound for the broadcast channel capacity region that depends only on the average recharge rate. We show that the FPCC policy is near-optimal in that it yields rates that are within a constant gap from the developed upper bound, and therefore, from the actual capacity region, for all system parameters.

We consider the energy harvesting diamond channel, where the source and two relays harvest energy from nature and the physical layer is modeled as a concatenation of a broadcast and a multiple access channel. Since the broadcast channel is degraded, one of the relays has the message of the other relay and the multiple access channel can be modeled as a cooperative multiple access channel with common data. We find the optimal offline transmit power and rate allocations that maximize the end-to-end throughput. For the broadcast side, we show that there exists an optimal source power allocation, which is equal to the single-user optimal power allocation for the source energy arrivals. We then show that the fraction of the power spent on each broadcast link depends on the energy arrivals for the relays. For the multiple access side with no co-operation, with fixed source rates, we show that the problem can be cast as a multiple access channel with both data and energy arrivals and can be formulated in terms of data transmission rates only. We use a dual decomposition method to solve the overall problem efficiently. Finally, we focus on the diamond channel with co-operative multiple access capacity region and find the optimal rates and powers using a decomposition into inner and outer maximization problems.

Information-theoretic work for wiretap channels is mostly based on random coding schemes. Designing practical coding schemes to achieve information-theoretic secrecy is an important problem. By applying two recently developed techniques for polar codes, namely, universal polar coding and polar coding for asymmetric channels, we propose a polar coding scheme to achieve the secrecy capacity of the general wiretap channel. We then apply this coding scheme to achieve the best-known inner bounds for the multiple access wiretap channel (MAC-WTC), and the broadcast and interference channels with confidential messages (BC-CM and IC-CM).

We consider the multiple-input multiple-output (MIMO) wiretap channel under a minimum receiver-side power constraint in addition to the usual maximum transmitter-side power constraint. This problem is motivated by energy harvesting communications with wireless energy transfer, where an added goal is to deliver a minimum amount of energy to a receiver in addition to delivering secure data to another receiver. In this paper, we characterize the exact secrecy capacity of the MIMO wiretap channel under transmitter and receiver-side power constraints. We first show that solving this problem is equivalent to solving the secrecy capacity of the wiretap channel under a double-sided correlation matrix constraint on the channel input. We show the converse by extending the channel enhancement technique to our case. We present two achievable schemes that achieve the secrecy capacity: the first achievable scheme uses a Gaussian codebook with a fixed mean, and the second achievable scheme uses artificial noise (or cooperative jamming) together with a Gaussian codebook. The role of the mean or the artificial noise is to enable energy transfer without sacrificing from the secure rate. This is the first instance of a channel model where either the use of a mean signal or the use of channel prefixing via artificial noise is strictly necessary for the MIMO wiretap channel. We then extend our work to consider a maximum receiver-side power constraint instead of a minimum receiver-side power constraint. This problem is motivated by cognitive radio applications, where an added goal is to decrease the received signal energy (interference temperature) at a receiver. We further extend our results to: requiring receiver-side power constraints at both receivers; considering secrecy constraints at both receivers to study broadcast channels with confidential messages; and removing the secrecy constraints to study the classical broadcast channel.

In this paper, we determine the entire secure degrees of freedom (s.d.o.f.) regions of the K-user Gaussian multiple access (MAC) wiretap channel and the K-user interference channel (IC) with secrecy constraints. For the IC, we consider three secrecy constraints: K-user IC with an external eavesdropper (ICEE), K-user IC with confidential messages (IC-CM), and their combination Kuser IC with confidential messages and external eavesdropper (IC-CM-EE). The converse for the IC includes constraints both due to secrecy as well as due to interference. For the IC, although the portion of the region close to the optimum sum s.d.o.f. point is governed by the upper bounds due to secrecy constraints, the other portions of the region are governed by the upper bounds due to interference constraints. Different from the existing literature, in order to fully understand the characterization of the s.d.o.f. region of the IC, one has to study the four-user case, i.e., the twoor three-user cases do not illustrate the full generality of the problem. In order to prove the achievability, we use the polytope structure of the converse region. In both MAC and IC cases, we develop explicit schemes that achieve the extreme points of the polytope region given by the converse. In particular, the extreme points of the MAC region are achieved by an m-user MAC wiretap channel with K - m helpers, i.e., by setting K - m users' secure rates to zero and utilizing them as pure (structured) cooperative jammers. The extreme points of the IC region are achieved by a (K - m)-user IC with confidential messages, m helpers, and N external eavesdroppers, for m ≥ 1 and a finite N. A byproduct of our results in this paper is that the sum s.d.o.f. is achieved only at one extreme point of the s.d.o.f. region, which is the symmetric-rate extreme point, for both MAC and IC channel models.

We consider the delay minimization problem in an energy harvesting communication network with energy cooperation. In this network, nodes harvest energy from nature to sustain the power needed for data transmission, and may transfer a portion of their harvested energies to neighboring nodes through energy cooperation. For fixed data and energy routing topologies, we determine the optimum data rates, transmit powers, and energy transfers, subject to flow and energy conservation constraints, to minimize the network delay. We start with a simplified problem where data flows are fixed and optimize energy management at each node for the case of a single energy harvest per node. This is tantamount to distributing each node's available energy over its outgoing data links and energy transfers to neighboring nodes. For this case, with no energy cooperation, we show that each node should allocate more power to links with more noise and/or more data flow. In addition, when there is energy cooperation, our numerical results indicate that the energy is routed from nodes with lower data loads to nodes with higher data loads. We then extend this setting to the case of multiple energy harvests per node over time. In this case, we optimize each node's energy management over its outgoing data links and its energy transfers to neighboring nodes, over multiple time slots. For this case, with no energy cooperation, we show that, for any given node, the sum of powers on the outgoing links over time is equal to the single-link optimal power over time. Finally, we consider the problem of joint flow control and energy management for the entire network. We determine the necessary conditions for joint optimality of a power control, energy transfer, and routing policy. We provide an iterative algorithm that updates the data flows, energy flows, and power distribution over outgoing data links sequentially. We show that this algorithm converges to a Pareto-optimal operating point.

Motivated by the damage due to heating in sensor operation, we consider the throughput optimal offline data scheduling problem in an energy harvesting transmitter, such that the resulting temperature remains below a critical level. We model the temperature dynamics of the transmitter as a linear system and determine the optimal transmit power policy under such temperature constraints as well as energy harvesting constraints over an additive white Gaussian noise channel. We first derive the structural properties of the solution for the general case with multiple energy arrivals. We show that the optimal power policy is piecewise monotone decreasing with possible jumps at the energy harvesting instants. We derive analytical expressions for the optimal solution in the single energy arrival case. We show that, in the single energy arrival case, the optimal power is monotone decreasing, the resulting temperature is monotone increasing, and both remain constant after the temperature hits the critical level. We then generalize the solution for the multiple energy arrival case.

We consider the energy harvesting two user Gaussian multiple access channel (MAC), where both of the users harvest energy from nature and their data packets arrive intermittently over time. We find the optimal offline transmit power and rate allocations that maximize the sum rate. First, we show that the optimization problem can be formulated in terms of the data rates only, instead of both transmission powers and data rates. Next, we show that the optimal sum rates are non-decreasing in time, similar to the single-user optimal powers. Then, we use a dual decomposition method to solve this problem efficiently. Specifically, we show that this problem is equivalent to three subproblems where each subproblem is a throughput maximization problem with fading, data and energy arrival constraints. We decompose the problem into inner and outer optimization problems and solve the overall problem using the subgradient descent method. Finally, we consider a relaxed problem where the data and energy arrivals to both of the users are merged into single energy and data queues and show that the optimal sum rates of the original problem are majorized by the solution to this relaxed problem.

We consider a cooperative multiple access channel (MAC) with two energy harvesting transmitters. The transmitters perform delay constrained transmission, i.e., every information block is encoded, transmitted and decoded between two consecutive energy harvests. We aim to maximize the achievable departure region over a finite transmission duration. We formulate the departure region maximization as a convex optimization problem. We propose an iterative algorithm which uses a directional waterfilling strategy to calculate the optimal power components. The departure region obtained by cooperation is shown to be significantly larger than that of a MAC without cooperation under the same energy arrival patterns. As a special case, we also analyze an energy harvesting relay channel with full duplex cooperation.

The two-user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form Ii, i = 1, 2 where I1; I2∈ {P;D;N}, and the forms P, D and N correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate over time between 9 possible states corresponding to all possible values of I1I2, with each state occurring for λI1I2fraction of the total duration. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption λI1I2= λI2I1. The results highlight the synergistic benefits of coding across CSIT states for secrecy and the interplay between various aspects of channel knowledge and its impact on s.d.o.f.

We consider an energy harvesting communication system, where both energy and data packets arrive at the transmitter during the course of communication. We determine the optimum packet scheduling scheme that minimizes the average delay experienced by all packets. We show that, different from the existing literature, the optimum transmission power is not constant between the energy harvesting and data arrival events; the transmission power starts high, decreases linearly, and potentially reaches zero between energy harvests and data arrivals. Intuitively, untransmitted bits experience cumulative delay due to the bits to be transmitted ahead of them, and hence the reason for transmission power starting high and decreasing over time between energy harvests and data arrivals.

We consider the energy harvesting diamond channel, where the source and two relays harvest energy from nature. The physical layer is modeled as a concatenation of a broadcast and a multiple access channel. We find the optimal offline transmit power and rate allocations that maximize the end-to-end throughput. First, we show that there exists an optimal source power allocation which is equal to the single-user optimal power allocation for the source energy arrivals and does not depend on the relay energy arrivals. Second, we show that the fraction of the power spent on each broadcast link depends on the energy arrivals for the relays. Specifically, we show that the optimal source rate allocation can be found by solving an optimal broadcasting problem with slot-dependent user priorities and these priorities can change only at instants where one of the relay data buffers is empty. Finally, we decompose the problem into inner and outer optimization problems and solve the overall problem by iterating between the two.

We consider the two-user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM), in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form P, D and N, corresponding to perfect and instantaneous, completely delayed, and no CSIT, respectively. We focus on the cases with heterogeneous CSIT from the users, that is, the states PD, PN and DN. The main contribution of this paper is to establish the exact secure degrees of freedom (s.d.o.f.) regions of the MISO BCCM in all of these three heterogeneous states. The results highlight the impact of availability of CSIT on the s.d.o.f. region.

We consider the K-user Gaussian multiple access wiretap channel (MAC-WT), where no eavesdropper channel state information (CSI) is available at the transmitters. We show that the exact sum secure degrees of freedom (s.d.o.f.) of this channel model is K-1/K . This result shows that, under the condition of no eavesdropper CSI, the MAC-WT acts like a single-transmitter K - 1 helper wiretap channel. We further show that, when a subset of the transmitters have eavesdropper CSI, then higher sum s.d.o.f. can be achieved, and the system can be operated as a MAC-WT for the users with eavesdropper CSI, with the remaining users acting as helpers. In particular, if m of the K transmitters have eavesdropper CSI, we show that m(K-1)/m(K-1)+1 sum s.d.o.f. can be achieved, showing the benefits of having the eavesdropper CSI at the transmitters.

A noiseless binary energy harvesting channel with on-off fading is considered. When causal fading state information is available at the transmitter only, an equivalent timing channel with additive geometric noise and noise information known at the transmitter is obtained. In this channel, the transmitter's strategy is a stopping rule with respect to the channel fade levels given the message and the additive noise. Next, capacity when energy arrival information is available at the receiver and capacity when both energy arrival and fading information are available at the receiver are obtained. Additionally, several achievable schemes are proposed and evaluated.

Motivated by damage due to heating in sensor operation, we consider the throughput optimal offline data scheduling problem in an energy harvesting transmitter such that resulting temperature increase remains below a critical level. We model the temperature dynamics of the transmitter as a linear system and determine the optimal transmit power policy under such temperature constraints as well as energy harvesting constraints over an AWGN channel. We first derive the structural properties of the solution for the general case with multiple energy arrivals. We, then, obtain closed form solutions for the case of a single energy arrival. We observe that the optimal power policy is piecewise monotone decreasing with possible jumps at the energy harvesting instants, and remains constant after the temperature reaches the critical level.

Information-theoretic work for wiretap channels is mostly based on random coding schemes. Designing practical coding schemes to achieve information-theoretic security is an important problem. By applying two recently developed techniques for polar codes, namely, universal polar coding and polar coding for asymmetric channels, we propose a polar coding scheme to achieve the secrecy capacity of the general wiretap channel.

We consider the effects of decoding costs in energy-harvesting communication systems. In our setting, receivers, in addition to transmitters, rely solely on energy harvested from nature, and need to spend some energy in order to decode their intended packets. We model the decoding energy as an increasing convex function of the rate of the incoming data. In this setting, in addition to the traditional energy causality constraints at the transmitters, we have the decoding causality constraints at the receivers, where energy spent by the receiver for decoding cannot exceed its harvested energy. We first consider the point-to-point single-user problem where the goal is to maximize the total throughput by a given deadline subject to both energy and decoding causality constraints. We show that decoding costs at the receiver can be represented as generalized data arrivals at the transmitter, and thereby moving all system constraints to the transmitter side. Then, we consider several multiuser settings. We start with a two-hop network where the relay and the destination have decoding costs, and show that separable policies, where the transmitter's throughput is maximized irrespective of the relay's transmission energy profile, are optimal. Next, we consider the multiple access channel (MAC) and the broadcast channel (BC) where the transmitters and the receivers harvest energy from nature, and characterize the maximum departure region. In all multiuser settings considered, we decompose our problems into inner and outer problems. We solve the inner problems by exploiting the structure of the particular model, and solve the outer problems by water-filling algorithms.

We consider an energy harvesting network where the transmitter harvests energy from nature, and the harvested energy can be saved in an imperfect battery which suffers from charging/ discharging inefficiency. In particular, when E units of energy is to be stored in the battery, only ηE units is saved and (1 - η)E is lost due to charging/discharging inefficiency, where 0 ≤ η ≤ 1 represents the storing efficiency. We determine the optimum offline transmit power schedule for such a system for single-user and broadcast channel models, for static and fading channels, with and without a finite battery size. We show that the optimum policy is a double-threshold policy: specifically, we store energy in the battery only when the harvested energy is above an upper threshold, and retrieve energy from the battery only when the harvested energy is below a lower threshold; when the harvested energy is in between these two thresholds, we use it in its entirety in the current slot. We show that the two thresholds remain constant unless the battery is depleted or full. We provide an algorithm to determine the sequence of optimum thresholds. For the case with fading, we develop a directional water-filling algorithm which has a double-threshold structure. Finally, we formulate the online problem using dynamic programming, and numerically observe that the online policy exhibits a double-threshold structure as well.

The papers in this special issue presents cutting-edge research results in the emerging area of energy harvesting wireless communications and wireless energy transfer. This first issue starts with a review article coauthored by the guest editors that summarizes recent results in the broad area of energy harvesting communications, in particular, in information-theoretic, offline and online schedulingtheoretic, medium access, networking approaches to energy harvesting communications, as well as in energy cooperation and simultaneous wireless energy and information transfer.

This paper summarizes recent contributions in the broad area of energy harvesting wireless communications. In particular, we provide the current state of the art for wireless networks composed of energy harvesting nodes, starting from the information-theoretic performance limits to transmission scheduling policies and resource allocation, medium access, and networking issues. The emerging related area of energy transfer for self-sustaining energy harvesting wireless networks is considered in detail covering both energy cooperation aspects and simultaneous energy and information transfer. Various potential models with energy harvesting nodes at different network scales are reviewed, as well as models for energy consumption at the nodes.

We revisit the recent secure degrees of freedom (s.d.o.f.) results for one-hop multiuser wireless networks by considering three fundamental wireless network structures: Gaussian wiretap channel with helpers, Gaussian multiple access wiretap channel, and Gaussian interference channel with secrecy constraints. We present main enabling tools and resulting communication schemes in an expository manner, along with key insights and design principles emerging from them. The main achievable schemes are based on real interference alignment, channel prefixing via cooperative jamming, and structured signalling. Real interference alignment enables aligning the cooperative jamming signals together with the message carrying signals at the eavesdroppers to protect them akin to one-time-pad protecting messages in wired systems. Real interference alignment also enables decodability at the legitimate receivers by rendering message carrying and cooperative jamming signals separable, and simultaneously aligning the cooperative jamming signals in the smallest possible subspace. The main converse techniques are based on two key lemmas which quantify the secrecy penalty by showing that the net effect of an eavesdropper on the system is that it eliminates one of the independent channel inputs; and the role of a helper by developing a direct relationship between the cooperative jamming signal of a helper and the message rate. These two lemmas when applied according to the unique structure of individual networks provide tight converses. Finally, we present a blind cooperative jamming scheme for the helper network with no eavesdropper channel state information at the transmitters that achieves the same optimal s.d.o.f. as in the case of full eavesdropper channel state information.

Physical-layer security utilizes resources of the transmission medium to guarantee secure communication against an adversary with unlimited computational power. Rooted in information theory, physical-layer security advocates for a foundational approach by requiring security of communicated information as well as its reliability at the outset. The past decade has seen an unprecedented effort in physical-layer security research resulting in promising new design insights. The majority of these advances has been in wireless communications security, well-motivated by the fact that most data at large, including those of sensitive nature, flow over wireless links that are more vulnerable to security breaches, e.g., eavesdropping. At the same time, the open broadcast nature of wireless brings possibilities of cooperation by the network entities for improving security, e.g., resistance to eavesdropping. This article aims to provide an overview of research results in information-theoretic security with multiple wireless transmitters, and focuses on distilling insights for designing wireless systems with confidentiality guarantees.

We consider the Gaussian wiretap channel with amplitude and variance constraints on the channel input. We first show that the entire rate-equivocation region of the Gaussian wiretap channel with an amplitude constraint is obtained by discrete input distributions with finite support. We prove this result by considering the existing single-letter description of the rate-equivocation region, and showing that discrete distributions with finite support exhaust this region. Our result highlights an important difference between the peak power (amplitude) constrained and the average power (variance) constrained cases. Although, in the average power constrained case, both the secrecy capacity and the capacity can be achieved simultaneously, our results show that in the peak power constrained case, in general, there is a tradeoff between the secrecy capacity and the capacity, in the sense that, both may not be achieved simultaneously. We also show that under sufficiently small amplitude constraints the possible tradeoff between the secrecy capacity and the capacity does not exist and they are both achieved by the symmetric binary distribution. Finally, we prove the optimality of discrete input distributions in the presence of an additional variance constraint.

We determine the exact sum secure degrees of freedom (d.o.f.) of the K-user Gaussian interference channel. We consider three different secrecy constraints: 1) K-user interference channel with one external eavesdropper (IC-EE); 2) K-user interference channel with confidential messages (IC-CM); and 3) K-user interference channel with confidential messages and one external eavesdropper (IC-CM-EE). We show that for all of these three cases, the exact sum secure d.o.f. is K(K - 1)/(2K - 1). We show converses for IC-EE and IC-CM, which imply a converse for IC-CM-EE. We show achievability for IC-CM-EE, which implies achievability for IC-EE and IC-CM. Our converse is based on developing a direct relationship between the differential entropies of the channel inputs and the rates of the users, and quantifying the effect of eavesdropping on the rates in terms of the differential entropies of the eavesdroppers' observations. Our achievability is based on structured signaling, structured cooperative jamming, channel prefixing, and asymptotic real interference alignment. While the traditional interference alignment provides some amount of secrecy by mixing unintended signals in a smaller subspace at every receiver, in order to attain the optimum sum secure d.o.f., we incorporate structured cooperative jamming into the achievable scheme, and intricately design the structure of all of the transmitted signals jointly.

We consider the block Rayleigh fading multiple-input multiple-output (MIMO) wiretap channel with no prior channel state information (CSI) available at any of the terminals. The channel gains remain constant within a coherence interval of T symbols, and then change to another independent realization in the next coherence interval. The transmitter, the legitimate receiver, and the eavesdropper have nt, nr, and ne antennas, respectively. We determine the exact secure degrees of freedom (s.d.o.f.) of this system when T ≥ 2min(nt,nr). We show that, in this case, the s.d.o.f. is exactly equal to (min(nt,nr)-ne)+(T -min(nt,nr))/T. The first term in this expression can be interpreted as the eavesdropper with ne antennas taking away ne antennas from both the transmitter and the legitimate receiver. The second term can be interpreted as a fraction of the s.d.o.f. being lost due to the lack of CSI at the legitimate receiver. In particular, the fraction loss, min(nt,nr)/T, can be interpreted as the fraction of channel uses dedicated to training the legitimate receiver for it to learn its own CSI. We prove that this s.d.o.f. can be achieved by employing a constant norm channel input, which can be viewed as a generalization of discrete signalling to multiple dimensions.

We consider the block Rayleigh fading multiple-input multiple-output (MIMO) wiretap channel with no prior channel state information (CSI) available at any of the terminals. The channel gains remain constant in a coherence time of T symbols, and then change to another independent realization. The transmitter, the legitimate receiver and the eavesdropper have nt, nrand neantennas, respectively. We determine the exact secure degrees of freedom (s.d.o.f.) of this system when T ≥ 2 min(nt, nr). We show that, in this case, the s.d.o.f. is exactly (min(nt, nr) − ne)+(T − min(nt, nr))/T. The first term can be interpreted as the eavesdropper with neantennas taking away neantennas from both the transmitter and the legitimate receiver. The second term can be interpreted as a fraction of s.d.o.f. being lost due to the lack of CSI at the legitimate receiver. In particular, the fraction loss, min(nt, nr)/T, can be interpreted as the fraction of channel uses dedicated to training the legitimate receiver for it to learn its own CSI. We prove that this s.d.o.f. can be achieved by employing a constant norm channel input, which can be viewed as a generalization of discrete signalling to multiple dimensions.

We consider the energy harvesting diamond channel, where the source and two relays harvest energy from nature, the relays help deliver the source's messages via signal cooperation, and the source has the option of wirelessly transferring some of its energy to the relays via energy cooperation. We find the optimal offline transmit power allocations and energy transfer policies that maximize the end-to-end throughput. For the case of no energy cooperation, we decompose the problem into inner and outer maximization problems, and solve the overall problem iterating between the two. We show that the class of procrastinating policies, where energy is transferred only when it will be immediately used, is optimal. We then show that the problem with energy cooperation is equivalent to a problem without energy cooperation with suitably modified rate expressions. We show that, in this system, if the source sends more energy to a relay, then it sends less data, showing us how data and energy should flow together optimally in this network.

We study the two-user multiple-input single-output (MISO) broadcast channel with confidential messages under the assumption of alternating channel state information at the transmitter (CSIT). We consider two alternating states: PD and DP which occur for an equal fraction of time. In state PD, the CSIT of the channel to the first receiver is available perfectly without delay (P) while that of the second receiver is available with a delay of one channel use (D); in state DP, the roles of the receivers are reversed. We characterize the exact secure degrees of freedom (s.d.o.f.) region of this system, and show as a corollary that the sum s.d.o.f. is 3/2. We observe that this sum s.d.o.f. is the same as what can be achieved by the states PP and DD occurring for equal fraction of time. Though the s.d.o.f. of the system in the states PD and DP is not known individually, we are able to establish the s.d.o.f. region when the two states alternate and occur for an equal fraction of the time.

We determine the capacity of a discrete memoryless communication channel with an energy harvesting transmitter and its battery state information available at the transmitter and the receiver. This capacity is an upper bound for the problem where side information is available only at the transmitter. Since channel output feedback does not increase the capacity in this case, we equivalently study the resulting finite-state Markov channel with feedback. We express the capacity in terms of directed information. Additionally, we provide sufficient conditions under which the capacity expression is further simplified to include the stationary distribution of the battery state. We also obtain a single-letter expression for the capacity with battery state information at both sides and an infinite-sized battery. Lastly, we consider achievable schemes when side information is available only at the transmitter for the case of an arbitrary finite-sized battery. We numerically evaluate the capacity and achievable rates with and without receiver side information.

We consider a binary energy harvesting channel (BEHC) where the encoder has unit energy storage capacity. We first show that an encoding scheme based on block indexing is asymptotically optimal for small energy harvesting rates. We then present a novel upper bounding technique, which upper bounds the rate by lower-bounding the rate of information leakage to the receiver regarding the energy harvesting process. Finally, we propose a timing based hybrid encoding scheme that achieves rates within 0.03 bits/channel use of the upper bound; hence determining the capacity to within 0.03 bits/channel use.

We examine the separability of the parallel multiple access wiretap channel. Separability, when exists, is useful as it enables us to code separately over parallel channels, and still achieve the optimum overall performance. It is well-known that the parallel single-user channel, parallel multiple access channel (MAC) and parallel broadcast channel (BC) are all separable, however, the parallel interference channel (IC) is not separable in general. In this paper, we show that, while MAC is separable MAC wiretap channel is not separable in general. We prove this via a specific linear deterministic MAC wiretap channel. We then show that even the Gaussian MAC wiretap channel is inseparable in general. Finally, we show that, when the channel gains are drawn from continuous distributions, and when the secure degrees of freedom (s.d.o.f.) region is considered, then the Gaussian MAC wiretap channel is almost surely separable.

We determine the capacity of a discrete memoryless communication channel with an energy harvesting transmitter and the energy arrival information available at the receiver as well as the transmitter. We obtain an n-letter capacity expression and prove that the capacity is achieved by an encoding scheme that depends only on the current battery state. Moreover, the capacity is invariant to the non-causal knowledge of energy arrivals. Finally, we show that the capacity expression is equivalently the maximum directed mutual information and that the channel output feedback does not increase the capacity in this case. We obtain upper and lower bounds on the capacity and numerically evaluate them for comparison.

In this paper, we consider a binary energy harvesting transmitter that wishes to control the amount of side information the receiver can obtain about its energy harvests. Specifically, we study state amplification and state masking, which define the maximum and minimum amount of state information conveyed to the receiver for a given message rate, respectively. For an independent and identically distributed energy harvesting process, we first find the amplification and masking regions for a transmitter without a battery and a transmitter with an infinite battery. Next, we find inner bounds for these regions for a unit-sized battery at the transmitter using two different encoding schemes, using instantaneous Shannon strategies and using a scheme based on the equivalent timing channel introduced in our previous work. We observe that the former provides better state amplification, while the latter provides better state masking.

The sum secure degrees of freedom (s.d.o.f.) of the K-user interference channel (IC) with secrecy constraints has been determined recently as equation [1], [2]. In this paper, we determine the entire s.d.o.f. region of this channel model. The converse includes constraints both due to secrecy as well as due to interference. Although the portion of the region close to the optimum sum s.d.o.f. point is governed by the upper bounds due to secrecy constraints, the other portions of the region are governed by the upper bounds due to interference constraints. Different from the existing literature, in order to fully understand the characterization of the s.d.o.f. region of the IC, one has to study the 4-user case, i.e., the 2 or 3-user cases do not illustrate the generality of the problem. In order to prove the achievability, we use the polytope structure of the converse region. The extreme points of the converse region are achieved by a (K - m)-user IC with confidential messages, m helpers, and N external eavesdroppers, for m ≥ 1 and a finite N. A byproduct of our results in this paper is that the sum s.d.o.f. is achieved only at one extreme point of the s.d.o.f. region, which is the symmetric-rate extreme point.

We study the vector Gaussian CEO problem, where there are arbitrary number of agents, each having a noisy observation of a vector Gaussian source. The goal of the agents is to describe the source to a central unit, which wants to reconstruct the source within a given distortion. The rate-distortion region of the vector Gaussian CEO problem is unknown in general. Here, we provide an outer bound for the rate-distortion region of the vector Gaussian CEO problem. We obtain our outer bound by evaluating an outer bound for the multiterminal source coding problem by means of a technique relying on the de Bruijn identity and properties of the Fisher information. Next, we investigate the tightness of our outer bound. Although our outer bound is tight for certain cases, we show that our outer bound does not provide the exact rate-distortion region in general. To this end, we provide an example and show that the rate-distortion region is strictly contained in our outer bound for this example.

We study the secure degrees of freedom (d.o.f.) of one-hop wireless networks by considering four fundamental wireless network structures: 1) Gaussian wiretap channel; 2) Gaussian broadcast channel with confidential messages; 3) Gaussian interference channel with confidential messages; and 4) Gaussian multiple access wiretap channel. The secrecy capacity of the canonical Gaussian wiretap channel does not scale with the transmit power, and hence, the secure d.o.f. of the Gaussian wiretap channel with no helpers is zero. It has been known that a strictly positive secure d.o.f. can be obtained in the Gaussian wiretap channel by using a helper, which sends structured cooperative signals. We show that the exact secure d.o.f. of the Gaussian wiretap channel with a helper is 1/2. Our achievable scheme is based on real interference alignment and cooperative jamming, which renders the message signal and the cooperative jamming signal separable at the legitimate receiver, but aligns them perfectly at the eavesdropper preventing any reliable decoding of the message signal. Our converse is based on two key lemmas. The first lemma quantifies the secrecy penalty by showing that the net effect of an eavesdropper on the system is that it eliminates one of the independent channel inputs. The second lemma quantifies the role of a helper by developing a direct relationship between the cooperative jamming signal of a helper and the message rate. We extend this result to the case of M helpers, and show that the exact secure d.o.f. in this case is M/M+1.We then generalize this approach to more general network structures with multiple messages. We show that the sum secure d.o.f. of the Gaussian broadcast channel with confidential messages and M helpers is 1, the sum secure d.o.f. of the twouser interference channel with confidential messages is 2/3, the sum secure d.o.f. of the two-user interference channel with confidential messages and M helpers is 1, and the sum secure d.o.f. of the K-user multiple access wiretap channel is K(K-1)/K(K-1)+1.

This work focuses on the design and analysis of distributed stochastic precoding algorithms for multiple-input single-output (MISO) interference channels, where each transmitter is provided with mean information of its intended channel and that of interfering channels. Unlike in cases where exact channel gains are known as in most existing works, here generalrank precoding is required for optimality instead of the rank-one beamforming. An efficient algorithm for the distributed implementation of the Nash equilibrium precoding is first proposed. A sufficient condition for this algorithm to converge to the unique equilibrium is derived for the two-user case based on stochastic ordering, and is valid for a wide range of system parameters. To improve the sum-rate performance under medium to strong interference, a pricing-based algorithm is also provided and its convergence analyzed. The two algorithms are compared in terms of sum-rate and system overhead.

In this paper, we investigate a two-way communication channel where users can harvest energy from nature and energy can be transferred in one-way from one of the users to the other. Energy required for data transmission is randomly harvested by the users throughout the communication duration and users have unlimited batteries to store energy for future use. In addition, there is a separate wireless energy transfer unit that facilitates energy transfer only in one-way and with efficiency α. We study the energy cooperation made possible by wireless energy transfer in the two-way channel. Assuming that both users know the energy arrivals in advance, we find jointly optimal offline energy management policies that maximize the sum throughput of the users. We show that this problem is a convex optimization problem, and find the solution by a generalized two-dimensional directional water-filling algorithm which transfers energy from one user to another while maintaining that the energy is allocated in the time dimension optimally. Optimal solution equalizes the energy levels as much as possible both among users and among slots, permitted by causality constraints of the energy arrivals and one-way energy transfer.

We consider the fast Rayleigh fading wiretap channel, over which a legitimate transmitter wishes to have secure communication with a legitimate receiver in the presence of an eavesdropper. We consider an average power constraint on the input, and assume that no channel state information (CSI) is available to any user. We show that the input distribution that achieves the secrecy capacity for this wiretap channel is discrete with a finite number of mass points.

We consider data transmission with an energy harvesting transmitter which has a hybrid energy storage unit composed of a perfectly efficient super-capacitor (SC) and an inefficient battery. The SC has finite space for energy storage while the battery has unlimited space. The transmitter can choose to store the harvested energy in the SC or in the battery. The energy is drained from the SC and the battery simultaneously. In this setting, we consider the offline throughput maximization problem by a deadline over a point-to-point channel. In contrast to previous works, the hybrid energy storage model with finite and unlimited storage capacities imposes a generalized set of constraints on the transmission policy. As such, we show that the solution generalizes that for a single battery and is obtained by applying directional water-filling algorithm multiple times.

We consider the capacity of an energy harvesting communication channel with a finite-sized battery. As an abstraction of this problem, we consider a system where energy arrives at the encoder in multiples of a fixed quantity, and the physical layer is modeled accordingly as a finite discrete alphabet channel based on this fixed quantity. Further, for tractability, we consider the case of binary energy arrivals into a unit-capacity battery over a noiseless binary channel. Viewing the available energy as state, this is a state-dependent channel with causal state information available only at the transmitter. Further, the state is correlated over time and the channel inputs modify the future states. We show that this channel is equivalent to an additive geometric-noise timing channel with causal information of the noise available at the transmitter. We provide a single-letter capacity expression involving an auxiliary random variable, and evaluate this expression with certain auxiliary random variable selection, which resembles noise concentration and lattice-type coding in the timing channel. We evaluate the achievable rates by the proposed auxiliary selection and extend our results to noiseless ternary channels.

Abstract—We determine the exact sum secure degrees of freedom (d.o.f.) of the K-user Gaussian interference channel. We consider three different secrecy constraints: 1) K-user interference channel with one external eavesdropper (IC-EE), 2) K-user interference channel with confidential messages (IC-CM), and 3) K-user interference channel with confidential messages and one external eavesdropper (IC-CM-EE). We show that for all of these three cases, the exact sum secure d.o.f. is K(K−1)

We show that the sum secure degrees of freedom (d.o.f.) of the K-user Gaussian multiple access (MAC) wiretap channel is K(K-1)/K(K-1)+1. Our achievability is based on real interference alignment and structured cooperative jamming. Each user divides its message into K - 1 sub-messages, and sends a linear combination of signals carrying these sub-messages together with a structured cooperative jamming signal. All cooperative jamming signals are aligned in a single dimension at the legitimate receiver allowing for reliable decoding of the message carrying signals by the legitimate receiver. Each cooperative jamming signal is aligned with K-1 message signals at the eavesdropper limiting the information leakage rate to the eavesdropper. We provide a matching converse establishing the exact sum secure d.o.f. of the Gaussian MAC wiretap channel as K(K-1)/K(K-1)+1.

In this paper, we study the sum secure degrees of freedom (d.o.f.) of two-unicast layered wireless networks. Without any secrecy constraints, the sum d.o.f. of this class of networks was studied by and shown to take only one of three possible values: 1, 3/2 and 2, for all network configurations. We consider the setting where, in addition to being reliably transmitted, each message is required to be kept information-theoretically secure from the unintended receiver. We show that the sum secure d.o.f. can only take one of five possible values: 0, 2/3, 1, 3/2, 2, for all network configurations. To determine the sum secure d.o.f., we divide the class of two-unicast layered networks into several sub-classes, and propose an achievable scheme based on the specific structure of the networks in each sub-class. Our achievable schemes are based on real interference alignment, cooperative jamming, interference neutralization and cooperative jamming neutralization techniques.

In energy harvesting communications, users transmit messages using energy harvested from nature during the course of communication. With an optimum transmit policy, the performance of the system depends only on the energy arrival profiles. In this paper, we introduce the concept of energy cooperation, where a user wirelessly transmits a portion of its energy to another energy harvesting user. This enables shaping and optimization of the energy arrivals at the energy-receiving node, and improves the overall system performance, despite the loss incurred in energy transfer. We consider several basic multi-user network structures with energy harvesting and wireless energy transfer capabilities: relay channel, two-way channel and multiple access channel. We determine energy management policies that maximize the system throughput within a given duration using a Lagrangian formulation and the resulting KKT optimality conditions. We develop a two-dimensional directional water-filling algorithm which optimally controls the flow of harvested energy in two dimensions: in time (from past to future) and among users (from energy-transferring to energy-receiving) and show that a generalized version of this algorithm achieves the boundary of the capacity region of the two-way channel.

We study the multi-receiver wiretap channel (MR-WC) with public and confidential messages. In this channel, there is a transmitter that wishes to communicate with two legitimate users in the presence of an external eavesdropper. The transmitter sends a pair of public and confidential messages to each legitimate user. While there are no secrecy constraints on the public messages, confidential messages need to be transmitted in perfect secrecy. We study the discrete memoryless MR-WC as well as its Gaussian multi-input multi-output (MIMO) counterpart. First, we propose an inner bound for the general, not necessarily degraded, discrete memoryless MR-WC by using Marton's inner bound and rate splitting in conjunction with superposition coding and binning. Second, we specialize this inner bound for the degraded discrete memoryless case. This specialized form of the inner bound can be obtained by using superposition coding and binning only. Next, we obtain an outer bound for the capacity region of the degraded channel, which matches the inner bound for some special cases. Third, we consider the degraded Gaussian MIMO channel, and show that, to evaluate both the inner and outer bounds, considering only jointly Gaussian auxiliary random variables and channel input is sufficient. Similar to the discrete memoryless case, for the Gaussian MIMO case as well, these bounds match for some special cases.

We study the secure lossy transmission of a vector Gaussian source to a legitimate user in the presence of an eavesdropper, where both the legitimate user and the eavesdropper have vector Gaussian side information. The aim of the transmitter is to describe the source to the legitimate user in a way that the legitimate user can reconstruct the source within a certain distortion level while the eavesdropper is kept ignorant of the source as much as possible as measured by the equivocation. We obtain an outer bound for the rate, equivocation and distortion region of this secure lossy transmission problem. This outer bound is tight when the transmission rate constraint is removed. In other words, we obtain the maximum equivocation at the eavesdropper when the legitimate user needs to reconstruct the source within a fixed distortion level while there is no constraint on the transmission rate. This characterization of the maximum equivocation involves two auxiliary random variables. We show that a nontrivial selection for both random variables may be necessary in general. The necessity of two auxiliary random variables also implies that, in general, Wyner-Ziv coding is suboptimal in the presence of an eavesdropper. In addition, we show that, even when there is no rate constraint on the legitimate link, uncoded transmission (deterministic or stochastic) is suboptimal; the presence of an eavesdropper necessitates the use of a coded scheme to attain the maximum equivocation.

Characterization of the rate-equivocation region of a general wiretap channel involves two auxiliary random variables:U, for rate splitting andV, for channel prefixing. In this paper, we explore specific classes of wiretap channels for which the evaluation of the rate-equivocation region is simpler. We show that if the wiretap channel is more capable,V=Xis optimal and the boundary of the rate-equivocation region is achieved by varying rate splittingUalone. Conversely, we show under a mild condition that if the wiretap channel is not more capable, thenV=Xis strictly suboptimal. Next, we focus on the class of cyclic shift symmetric wiretap channels. We show that optimal rate splittingUthat achieves the boundary of the rate-equivocation region is uniform with cardinality |X| and the prefix channel between optimalUandVis expressed as cyclic shifts of the solution of an auxiliary optimization problem over a single variable. We provide a special class of cyclic shift symmetric wiretap channels for whichU=φ is optimal. We apply our results to the binary-input cyclic shift symmetric wiretap channels and thoroughly characterize the rate-equivocation regions of the BSC-BEC and BEC-BSC wiretap channels.

We consider a secure lossless source coding problem with a rate-limited helper. In particular, Alice observes an independent and identically distributed (i.i.d.) sourceXnand wishes to transmit this source losslessly to Bob over a rate-limited link of capacity not exceedingRx. A helper, say Helen, observes an i.i.d. correlated sourceYnand can transmit information to Bob over another link of capacity not exceedingRy. A passive eavesdropper (say Eve) can observe the coded output of Alice, i.e., the link from Alice to Bob is public. The uncertainty about the sourceXnat Eve (denoted by Δ) is measured by the conditional entropy [(H(Xn|Jx))/(n)] , whereJxis the coded output of Alice andnis the block length. We completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian-Wolf binning ofXnwith respect to the coded side information received at Bob is optimal. We next consider a modification of this model in which Alice also has access to the coded output of Helen. We call this model as the two-sided helper model. For the two-sided helper model, we characterize the rate-equivocation region. While the availability of side information at Alice does not reduce the rate of transmission from Alice, it significantly enhances the resulting equivocation at Eve. In particular, the resulting equivocation for the two-sided helper case is shown to be min(H(X),Ry), i.e., one bit from the two-sided helper provides one bit of uncertainty at Eve. From this result, we infer that Slepian-Wolf binning ofXis suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side information at Alice. We, finally, generalize both of these results to the case in which there is additional uncoded side informationWnavailable at Bob and characterize the rate-equivocation regions under the assumption thatYn→Xn→Wnforms a Markov chain.

We consider the two-user additive Gaussian multiple access channel (MAC) where the transmitters communicate by using energy harvested from nature. Energy arrivals of the users are i.i.d. in time, and for any given time, they are distributed according to a joint distribution. Energy arrivals cause time-variations for the amplitude constraints of the users. We first consider the static amplitude constrained Gaussian MAC and prove that the boundary of the capacity region is achieved by discrete input distributions of finite support. When both of the transmitters are equipped with no battery, Shannon strategies applied by users provide an inner bound for the capacity region. We prove that the boundary of this inner bound is achieved by input distributions with support set of zero Lebesgue measure.

We study the vector Gaussian CEO problem, and provide an outer bound for its rate-distortion region. We obtain our outer bound by evaluating an outer bound for the multiterminal source coding problem by means of a technique relying on the de Bruijn identity and the properties of the Fisher information. Next, we address the tightness of our outer bound, and show that our outer bound does not provide the ratedistortion region in general. In particular, we provide a specific example where the rate-distortion region is strictly contained in our outer bound.

We consider a simple multi-hop communication scenario composed of a source node, a relay node and a destination node where the source and the relay can harvest energy from the nature. Energy required for communication arrives (is harvested) at the transmitter and an unlimited battery stores it before being consumed for transmission. In addition, the source can assist the relay by transferring a portion of its energy to the relay through a separate energy transfer unit. We address this energy cooperation between the source and the relay in a deterministic setting. Assuming that the source and the relay nodes are informed of the energy arrivals in advance, we find jointly optimal offline energy management policies for the source and the relay that maximize the end-to-end throughput. We show that this problem is a convex problem. In order to gain insight about the structure of the solution, we consider specific scenarios. In particular, we show that if the relay energy profile is higher at the beginning and lower at the end with only one intersection, then matching the power sequences of the source and the relay slot-by-slot is optimal. We also consider the case when the energy of the source is available at the beginning and show that transferring energy in the first slot is optimal.

In energy harvesting communication systems, the energy required for message transmission is maintained by an exogenous energy arrival process independent of the message. This links the problem of communication with an energy harvesting transmitter to the problem of communication over state-dependent channels. In particular, if the transmitter has no battery, the available energy can be viewed as a state and the resulting channel is a state-dependent channel with causal state information at the transmitter only. In general, information transmission blurs the state information that the receiver can get from the received signal. In this paper, we explore the trade-off between the information rate R and the entropy reduction of the energy arrival process Δ at the receiver side over an AWGN channel with an energy harvesting transmitter. If the transmitter has no battery, the trade-off points are achieved by Shannon strategies and we show that the optimal input distributions are discrete. Next, we consider the state amplification problem for an energy harvesting transmitter with an unlimited battery. We show that the optimal trade-off region in this extreme case is expressed explicitly in a simple form and its boundary is achieved by a combination of best-effort-transmit and random binning schemes with an i.i.d. Gaussian codebook of average power equal to the average recharge rate. Finally, we propose an uncoded state amplification scheme that splits the energy between message transmission and entropy reduction and study its performance in a numerical example.

In this paper, we study the sum secure degrees of freedom (d.o.f.) of two-unicast layered wireless networks. Without a secrecy constraint, the sum d.o.f. of this class of networks was studied by [1] and shown to take only one of three possible values: 1, 3/2 and 2, for all network configurations. We consider the setting where the message of each source-destination pair must be kept information-theoretically secure from the unintended receiver. We show that the sum secure d.o.f. can take 0, 1, 3/2, 2 and at most countably many other positive values, which we enumerate.

We study the Gaussian wiretap channel with an energy harvesting transmitter which does not have a battery to save energy. In the absence of a battery, the necessary transmission energy is maintained by an i.i.d. energy arrival process. We observe that this channel is an instance of the state-dependent wiretap channel with state available only to the transmitter causally, where the state is the available energy at the transmitter. We prove that the entire capacity-equivocation region can be obtained by single-letter Shannon strategies and its boundary is achieved by input distributions with support set of Lebesgue measure zero.

We consider the Gaussian wiretap channel with an amplitude constraint, i.e., a peak power constraint, on the channel input. We show that the entire rate-equivocation region of the Gaussian wiretap channel with an amplitude constraint is obtained by discrete input distributions with finite support. We prove this result by considering the existing single-letter description of the rate-equivocation region, and showing that discrete distributions with finite support exhaust this region. Our result highlights an important difference between the peak power constraint and the average power constraint cases: Although, in the average power constraint case, both the secrecy capacity and the capacity can be achieved simultaneously, our results show that in the peak power constraint case, in general, there is a tradeoff between the secrecy capacity and the capacity, in the sense that, both may not be achieved simultaneously.

In this paper, we first study the Decode-and-Forward strategy for secrecy in a single-relay network. We propose a suboptimal Decode-and-Forward with Zero Forcing (DF/ZF) strategy for which we obtain the optimal power control policy. Next, we consider the multiple relay problem. We propose three different strategies based on DF/ZF. The first strategy is a single-hop strategy in which all the relays decode the source message at the same time, then perform beamforming such that all the relays' signals are eliminated from the eavesdropper's observation (full zero-forcing). We give the achievable rate by this strategy and derive the optimal power control policy. We show that, in this strategy, the relays which are far from the source create a bottleneck and limit the achievable rate. The second strategy is a multiple hop strategy that overcomes the drawback of the first strategy, however, with the disadvantage of enabling partial zero-forcing only, assuming that all the relays are required to transmit fresh information in every transmission block. The third strategy is also a multiple hop strategy in which full zero-forcing is possible and the rate achieved does not suffer from the drawback of the first strategy.

We consider the optimal packet scheduling problem in a single-user energy harvesting wireless communication system. In this system, both the data packets and the harvested energy are modeled to arrive at the source node randomly. Our goal is to adaptively change the transmission rate according to the traffic load and available energy, such that the time by which all packets are delivered is minimized. Under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the data traffic arrivals, we consider two different scenarios. In the first scenario, we assume that all bits have arrived and are ready at the transmitter before the transmission starts. In the second scenario, we consider the case where packets arrive during the transmissions, with known arrival times and sizes. We develop optimal off-line scheduling policies which minimize the time by which all packets are delivered to the destination, under causality constraints on both data and energy arrivals.

In this paper, we investigate the roles of cooperative jamming (CJ) and noise forwarding (NF) in improving the achievable secrecy rates of a Gaussian wiretap channel (GWT) when the helper node is equipped with multiple antennas. We decompose the channel from the helper to the eavesdropper into two orthogonal components: one is aligned in the direction of the channel between the helper and the legitimate receiver (direct component) and the other is in the orthogonal direction to the channel between the helper and the legitimate receiver (orthogonal component). We then propose a strategy in which the helper uses the orthogonal component to transmit pure Gaussian noise as in the CJ strategy while he uses the direct component for either CJ or NF depending on the given channel conditions. We explicitly derive the optimal power control policy for this strategy and give the achievable secrecy rates when the direct component is used to perform CJ or NF. We hence derive the channel conditions where CJ is better than NF over the direct component and vice-versa. Finally, we consider the reversely degraded multiple antenna relay-eavesdropper channel. We show that a simple strategy in which the relay jams with full power along the orthogonal component and transmits nothing in the direct component achieves a secrecy rate that approaches the secrecy capacity of this channel as the relay's average power goes to infinity. Moreover, we show that this result holds almost surely even if the relay-eavesdropper's channel state information is unavailable.

In this paper, we introduce two new achievable schemes for the fading multiple access wiretap channel (MAC-WT).In the model that we consider, we assume that perfect knowledge of the state of all channels is available at all the nodes in a causal fashion.Our schemes use this knowledge together with the time-varying nature of the channel model to align the interference from different users at the eavesdropper perfectly in a one-dimensional space while creating a higher dimensionality space for the interfering signals at the legitimate receiver, hence allowing for better chance of recovery.While we achieve this alignment through signal scaling at the transmitters in our first scheme (scaling-based alignment), we let nature provide this alignment through the ergodicity of the channel coefficients in the second scheme [ergodic secret alignment (ESA)] [1], [2].For each scheme, we obtain the resulting achievable secrecy rate region.We show that the secrecy rates achieved by both schemes in the two-user fading MAC-WT scale with signal-to-noise ratio (SNR) as 1 2 log(SNR).Hence, we show the suboptimality of the independent identically distributed (i.i.d.) Gaussian signaling-based schemes with and without cooperative jamming by showing that the secrecy rates achieved using i.i.d.Gaussian signaling with cooperative jamming do not scale with SNR.In addition, we introduce an improved version of our ESA scheme where we incorporate cooperative jamming to achieve higher secrecy rates.Moreover, we derive the necessary optimality conditions for the power control policy that maximizes the secrecy sum rate achievable by our ESA scheme when used solely and with cooperative jamming.Finally, we discuss the extension of the proposed schemes to the case where there are more than two users and show that, for the -user fading MAC-WT, each of the two schemes achieves secrecy sum rate that scales with SNR as 1 log(SNR).

We provide an alternative proof for the capacity region of the degraded Gaussian multiple-input multiple-output (MIMO) broadcast channel. Our proof does not use the channel enhancement technique as opposed to the original proof of Weingertan and the alternative proof of Liu et al. Our proof starts with the single-letter description of the capacity region of the degraded broadcast channel, and by using it, obtains a tight (i.e., achievable) outer bound for the capacity region of the degraded Gaussian MIMO broadcast channel, by using two main technical tools. The first one is the generalized de Bruijn identity due to Palomar which provides a connection between the differential entropy and the Fisher information matrix. The second tool we use is an inequality due to Dembo which lower bounds the differential entropy in terms of the Fisher information matrix.

We study the two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and confidential messages. In this channel, the transmitter sends a common message to both users, and a confidential message to each user which needs to be kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between the capacity region we obtain for the Gaussian MIMO broadcast channel with common and confidential messages and the capacity region of its nonconfidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private messages, which is not known completely.

We study the degraded compound multi-receiver wiretap channel (DCMRWC). DCMRWC consists of two groups of users and a group of eavesdroppers, where, if we pick an arbitrary user from each group of users and an arbitrary eavesdropper, they satisfy a certain Markov chain. We study two different communication scenarios for this channel. In the first scenario, the transmitter wants to send a confidential message to users in the first (stronger) group and a different confidential message to users in the second (weaker) group, where both messages need to be kept confidential from the eavesdroppers. For this scenario, we assume that there is only one eavesdropper. We obtain the secrecy capacity region for the discrete memoryless channel model, the parallel channel model, and the Gaussian parallel channel model. For the Gaussian multiple-input multiple-output (MIMO) channel model, we obtain the secrecy capacity region when there is only one user in the second group. In the second scenario we study, the transmitter sends a confidential message to users in the first group which needs to be kept confidential from the second group of users and the eavesdroppers. Moreover, the transmitter sends a different confidential message to users in the second group which needs to be kept confidential only from the eavesdroppers. For this scenario, we do not put any restriction on the number of eavesdroppers. As in the first scenario, we obtain the secrecy capacity region for the discrete memoryless channel model, the parallel channel model, and the Gaussian parallel channel model. For the Gaussian MIMO channel model, we establish the secrecy capacity region when there is only one user in the second group.

We study the Gaussian multiple-input multiple-output (MIMO) wiretap channel, which consists of a transmitter, a legitimate user, and an eavesdropper. In this channel, the transmitter sends a common message to both the legitimate user and the eavesdropper. In addition to this common message, the legitimate user receives a private message, which is desired to be kept hidden as much as possible from the eavesdropper. We obtain the entire capacity-equivocation region of the Gaussian MIMO wiretap channel. This region contains all achievable common message, private message, and private message's equivocation (secrecy) rates. In particular, we show the sufficiency of jointly Gaussian auxiliary random variables and channel input to evaluate the existing single-letter description of the capacity-equivocation region due to Csiszar–Korner.

We consider the Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and private messages. We obtain an outer bound for the capacity region of this channel. To this end, we show that a parallel Gaussian broadcast channel can be constructed from any given Gaussian MIMO broadcast channel by using the generalized singular value decomposition and a relaxation on the power constraint for the channel input. Due to this relaxation of the power constraint, the capacity region of the constructed parallel channel, which is known, provides an outer bound for the capacity region of the original channel. We show that this outer bound is within a finite gap of the capacity region by comparing it with an achievable rate region that can be obtained either by using dirty-paper coding or by using a variation of the zero-forcing scheme.

In energy harvesting communication systems, an exogenous recharge process supplies energy necessary for data transmission and the arriving energy can be buffered in a battery before consumption. We determine the information-theoretic capacity of the classical additive white Gaussian noise (AWGN) channel with an energy harvesting transmitter with an unlimited sized battery. As the energy arrives randomly and can be saved in the battery, codewords must obey cumulative stochastic energy constraints. We show that the capacity of the AWGN channel with such stochastic channel input constraints is equal to the capacity with an average power constraint equal to the average recharge rate. We provide two capacity achieving schemes: save-and-transmit and best-effort-transmit. In the save-and-transmit scheme, the transmitter collects energy in a saving phase of proper duration that guarantees that there will be no energy shortages during the transmission of code symbols. In the best-effort-transmit scheme, the transmission starts right away without an initial saving period, and the transmitter sends a code symbol if there is sufficient energy in the battery, and a zero symbol otherwise. Finally, we consider a system in which the average recharge rate is time varying in a larger time scale and derive the optimal offline power policy that maximizes the average throughput, by using majorization theory.

We consider the minimization of the transmission completion time with a battery limited energy harvesting transmitter in an M-user AWGN broadcast channel where the transmitter is able to harvest energy from the nature, using a finite storage capacity rechargeable battery. The harvested energy is modeled to arrive (be harvested) at the transmitter during the course of transmissions at arbitrary time instants. The transmitter has fixed number of packets for each receiver. Due to the finite battery capacity, energy may overflow without being utilized for data transmission. We derive the optimal offline transmission policy that minimizes the time by which all of the data packets are delivered to their respective destinations. We analyze the structural properties of the optimal transmission policy using a dual problem. We find the optimal total transmit power sequence by a directional water-filling algorithm. We prove that there exist M-1 cut-off power levels such that user i is allocated the power between the i-1st and the ith cut-off power levels subject to the availability of the allocated total power level. Based on these properties, we propose an algorithm that gives the globally optimal offline policy. The proposed algorithm uses directional water-filling repetitively. Finally, we illustrate the optimal policy and compare its performance with several suboptimal policies under different settings.

In this paper, we investigate the transmission completion time minimization problem in an additive white Gaussian noise (AWGN) broadcast channel, where the transmitter is able to harvest energy from the nature, using a rechargeable battery. The harvested energy is modeled to arrive at the transmitter during the course of transmissions. The transmitter has a fixed number of packets to be delivered to each receiver. The objective is to minimize the time by which all of the packets are delivered to their respective destinations. To this end, we optimize the transmit powers and transmission rates in a deterministic setting. We first analyze the structural properties of the optimal transmission policy in a two-user broadcast channel via the dual problem of maximizing the departure region by a fixed time T. We prove that the optimal total transmit power sequence has the same structure as the optimal single-user transmit power sequence in . In addition, the total power is split optimally based on a cut-off power level; if the total transmit power is lower than this cut-off level, all transmit power is allocated to the stronger user; otherwise, all transmit power above this level is allocated to the weaker user. We then extend our analysis to an M-user broadcast channel. We show that the optimal total power sequence has the same structure as the two-user case and optimally splitting the total power among M users involves M-1 cut-off power levels. Using this structure, we propose an algorithm that finds the globally optimal policy. Our algorithm is based on reducing the broadcast channel problem to a single-user problem as much as possible. Finally, we illustrate the optimal policy and compare its performance with several suboptimal policies under different settings.

In this paper, we investigate the transmission completion time minimization problem in a two-user additive white Gaussian noise (AWGN) broadcast channel, where the transmitter is able to harvest energy from the nature. The harvested energy is modeled to arrive at the transmitters randomly. In this paper, under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. The transmitter has a fixed number of packets to be delivered to each receiver. Our goal is to minimize the time by which all of the packets for both users are delivered to their respective destinations. To this end, we optimize the transmit powers and transmission rates intended for both users. We first analyze the structural properties of the optimal transmission policy. We prove that the optimal total transmit power has the same structure as the optimal single-user transmit power. We also prove that there exists a cut-off power level for the stronger user. If the optimal total transmit power is lower than this level, all transmit power is allocated to the stronger user, and when the optimal total transmit power is larger than this level, all transmit power above this level is allocated to the weaker user. Based on these structural properties of the optimal policy, we propose an algorithm that yields the globally optimal off-line scheduling policy.

In this paper, we investigate the optimal packet scheduling problem in a two-user multiple access communication system, where the transmitters are able to harvest energy from the nature. Under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the packet arrivals, we assume that packets have already arrived and are ready to be transmitted at the transmitter before the transmission starts. Our goal is to minimize the time by which all packets from both users are delivered to the destination through controlling the transmission powers and transmission rates of both users. We first develop a generalized iterative backward waterfilling algorithm to characterize the maximum departure region of the transmitters for any given deadline $T$. Then, based on the departure region at energy arrival epochs, we decompose the transmission completion time minimization problem into a convex optimization problem and solve it efficiently.

Wireless systems comprised of rechargeable nodes have a significantly prolonged lifetime and are sustainable. A distinct characteristic of these systems is the fact that the nodes can harvest energy throughout the duration in which communication takes place. As such, transmission policies of the nodes need to adapt to these harvested energy arrivals. In this paper, we consider optimization of the transmission policy of an energy harvesting transmitter which has a limited battery capacity, communicating in a wireless fading channel. In particular, we identify the optimal offline transmission policies that maximize the number of bits delivered by a deadline, and minimize the transmission completion time of the communication session. We introduce a directional water-filling algorithm which provides a simple and concise interpretation of the necessary optimality conditions as well as energy storage capacity and causality. We solve the throughput maximization problem for the fading channel using the directional water-filling algorithm, which simultaneously adapts to the energy harvested as well as the channel variations in time. We then solve the transmission completion time minimization problem by utilizing its equivalence to its throughput maximization counterpart.

We study the secure lossy transmission of a Gaussian vector source to a legitimate user in the presence of an eaves-dropper, where both the legitimate user and the eavesdropper have Gaussian vector side information. The transmitter describes the source to the legitimate user in a way that the legitimate user can reconstruct the source within a certain distortion while the eavesdropper is kept ignorant of the source as much as possible. We obtain an outer bound for the rate, equivocation and distortion region of this secure lossy transmission problem. This outer bound is tight when the transmission rate constraint is removed. In other words, we obtain the maximum equivocation at the eavesdropper when the legitimate user needs to reconstruct the source within a fixed distortion level while there is no constraint on the transmission rate.

Csiszár and Körner's characterization of the rate-equivocation region of a general wiretap channel involves two auxiliary random variables: U, which represents rate splitting and V, which represents channel prefixing. For some channels, one or both of these auxiliary random variables are unnecessary, simplifying the expression and evaluation of the rate-equivocation region. In this paper, we provide new conditions under which channel prefixing or rate splitting does not improve the rate-equivocation region. In particular, we show that when the main channel is more capable than the eavesdropping channel, channel prefixing is unnecessary; the entire rate-equivocation region can be achieved by rate splitting alone. Conversely, we show under a mild assumption that if the main receiver is not more capable, then channel prefixing is strictly necessary. Moreover, we show that if the main channel is more capable but not less noisy, then rate splitting is strictly necessary. Next, we focus on the set of cyclic shift symmetric channels. We prove that for these channels, if in addition I(X; Y) - I(X;Z) is maximized at the uniform distribution, then rate splitting is unnecessary. Our results apply to BSC-BEC and BEC-BSC wiretap channels. We identify the conditions on the parameters of the BSC and BEC under which channel prefixing and/or rate splitting are unnecessary.

In this paper, we study the two-user one-sided interference channel with confidential messages. In this interference channel, in addition to the usual selfishness of the users, the relationship between the two pairs of users is further adversarial in the sense of both receivers' desires to eavesdrop on the communication of the other pair. We develop a game-theoretic model to study the information-theoretic secure communications in this setting. We first start with a game-theoretic model where each pair's payoff is their own secrecy rate. The analysis of the binary deterministic interference channel with this payoff function shows that self-jamming of a transmitter, which injures the eavesdropping ability of its own receiver, is not excluded by the Nash equilibria. We propose a refinement for the payoff function by explicitly accounting for the desire of the receiver to eavesdrop on the other party's communication. This payoff function captures the adversarial relationship between the two pairs of users better. We determine the Nash equilibria for the binary deterministic channel for both payoff functions.

We consider the minimization of the transmission completion time with a battery limited energy harvesting transmitter in a two-user AWGN broadcast channel. The transmitter has fixed number of packets for each receiver and energy is modeled to arrive (be harvested) at the transmitter at random instants. The battery at the transmitter has a finite storage capacity, hence energy may overflow without being utilized for data transmission. We derive the optimal offline transmission policy that minimizes the time by which all of the data packets are delivered to their respective destinations. We analyze the structural properties of the optimal transmission policy using a dual problem. We find the optimal total transmit power sequence by a directional water-filling algorithm. We prove that there exists a cut-off power level such that if the allocated power is lower than this level, then only the stronger user is served in that epoch; otherwise, the power above this level is allocated to the weaker user. Based on these properties, we propose an algorithm that gives the globally optimal offline policy. The proposed algorithm uses directional water-filling repetitively.

Wireless systems comprised of rechargeable nodes have a significantly prolonged lifetime and are sustainable. A distinct characteristic of these systems is the fact that the nodes can harvest energy throughout the duration in which communication takes place. As such, transmission policies of the nodes need to adapt to these harvested energy arrivals. In this paper, we consider optimization of point-to-point data transmission with an energy harvesting transmitter which has a limited battery capacity, communicating in a wireless fading channel. We consider two objectives: maximizing the throughput by a deadline, and minimizing the transmission completion time of the communication session. We optimize these objectives by controlling the time sequence of transmit powers subject to energy storage capacity and causality constraints. We, first, study optimal offline policies. We introduce a directional water-filling algorithm which provides a simple and concise interpretation of the necessary optimality conditions. We show the optimality of an adaptive directional water-filling algorithm for the throughput maximization problem. We solve the transmission completion time minimization problem by utilizing its equivalence to its throughput maximization counterpart. Next, we consider online policies. We use stochastic dynamic programming to solve for the optimal online policy that maximizes the average number of bits delivered by a deadline under stochastic fading and energy arrival processes with causal channel state feedback. We also propose near-optimal policies with reduced complexity, and numerically study their performances along with the performances of the offline and online optimal policies under various different configurations.

We consider a communication channel with two transmitters and one receiver, with an underlying rate region which is approximated as a general pentagon. Different from the Gaussian multiple access channel (MAC) capacity region, the sum-rate on the dominant face of this pentagon is not a constant. We allocate rates from this rate region to users according to their current queue lengths in order to minimize the average delay in the system. We formulate the problem as a Markov decision problem (MDP), and derive the structural properties of the corresponding discounted-cost MDP. We show that the delay-optimal policy has a switch curve structure. For the discounted-cost problem, we prove that the switch curve has a limit along one of the dimensions. The delay-optimal policy divides the entire queue state space into two via a switch curve. If the queue state is on one side of the switch curve, the system operates at one of the corner points of the rate pentagon which favors maximum sum-rate. When the queue state switches to the other side of the switch curve, the system operates at the other corner point of the rate pentagon which favors balancing the queue lengths. As a result, the system does not always operate at the sum-rate maximizing rate pair, but trades rate for balanced queue lengths for the goal of minimizing the overall delay. The existence of a limit in the switch curve along one of dimensions implies that, once the queue state is beyond the limit, the system always operates at one of the corner points, implying that the queues can be operated partially distributedly.

We investigate the effects of user cooperation on the secrecy of broadcast channels by considering a cooperative relay broadcast channel. We show that user cooperation can increase the achievable secrecy region. We propose an achievable scheme that combines Marton's coding scheme for broadcast channels and Cover and El Gamal's compress-and-forward scheme for relay channels. We derive outer bounds for the rate-equivocation region using auxiliary random variables for single-letterization. Finally, we consider a Gaussian channel and show that both users can have positive secrecy rates, which is not possible for scalar Gaussian broadcast channels without cooperation.

In this paper, we consider the Gaussian multiple-input multiple-output (MIMO) multi-receiver wiretap channel in which a transmitter wants to have confidential communication with an arbitrary number of users in the presence of an external eavesdropper. We derive the secrecy capacity region of this channel for the most general case. We first show that even for the single-input single-output (SISO) case, existing converse techniques for the Gaussian scalar broadcast channel cannot be extended to this secrecy context, to emphasize the need for a new proof technique. Our new proof technique makes use of the relationships between the minimum-mean-square-error and the mutual information, and equivalently, the relationships between the Fisher information and the differential entropy. Using the intuition gained from the converse proof of the SISO channel, we first prove the secrecy capacity region of the degraded MIMO channel, in which all receivers have the same number of antennas, and the noise covariance matrices can be arranged according to a positive semi-definite order. We then generalize this result to the aligned case, in which all receivers have the same number of antennas; however, there is no order among the noise covariance matrices. We accomplish this task by using the channel enhancement technique. Finally, we find the secrecy capacity region of the general MIMO channel by using some limiting arguments on the secrecy capacity region of the aligned MIMO channel. We show that the capacity achieving coding scheme is a variant of dirty-paper coding with Gaussian signals.

In the distributed coding of correlated sources, the problem of characterizing the joint probability distribution of a pair of random variables satisfying an n-letter Markov chain arises. The exact solution of this problem is intractable. In this paper, we seek a single-letter necessary condition for this n-letter Markov chain. To this end, we propose a new data processing inequality on a new measure of correlation through a spectral method. Based on this new data processing inequality, we provide a single-letter necessary condition for the required joint probability distribution. We apply our results to two specific examples involving the distributed coding of correlated sources: multiple-access channel with correlated sources and multiterminal rate-distortion region, and propose new necessary conditions for these two problems.

We study a special class of diamond channels which was introduced by Schein in 2001. In this special class, each diamond channel consists of a transmitter, a noisy relay, a noiseless relay and a receiver. We prove the capacity of this class of diamond channels by providing an achievability scheme and a converse. The capacity we show is strictly smaller than the cut-set bound. We note that there exists a duality between this diamond channel coding problem and the Kaspi-Berger source coding problem.

We obtain new outer bounds on the capacity regions of the two-user multiple access channel with generalized feedback (MAC-GF) and the two-user interference channel with generalized feedback (IC-GF). These outer bounds are based on the idea of dependence balance which was proposed by Hekstra and Willems. To illustrate the usefulness of our outer bounds, we investigate three different channel models.

We obtain the degrees of freedom region of the Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and private messages. We first show that a parallel Gaussian broadcast channel with unmatched sub-channels can be constructed from any given Gaussian MIMO broadcast channel by using the generalized singular value decomposition (GSVD) and a relaxation on the power constraint for the channel input, in a way that the capacity region of the constructed parallel channel provides an outer bound for the capacity region of the original channel. The capacity region of the parallel Gaussian broadcast channel with unmatched sub-channels is known, using which we obtain an explicit outer bound for the degrees of freedom region of the Gaussian MIMO broadcast channel. We finally show that this outer bound for the degrees of freedom region can be attained by the achievable scheme that uses a classical Gaussian coding for the common message and dirty-paper coding (DPC) for the private messages.

In this paper, we provide a new achievable ergodic secrecy rate region for the multiple access wiretap channel in fading. Our achievable scheme is based on repeating each symbol at two fading instances, as in the original ergodic interference alignment technique of Nazer et. al. We choose the channel states where the symbols are repeated in such a way that the received signals are aligned favorably at the legitimate receiver, while they are aligned unfavorably at the eavesdropper. We show that our new scheme outperforms plain Gaussian signaling and Gaussian signaling with Gaussian channel prefixing, i.e., cooperative jamming, in high signal-to-noise ratios (SNR). In particular, we show that, while Gaussian signaling with or without channel prefixing yields zero secure degrees of freedom, our new achievable scheme provides a total of 1/2 secure degrees of freedom in a two-user multiple access channel in fading.

We study the Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and private messages. We first obtain an outer bound for the capacity region of the two-user discrete memoryless broadcast channel with common and private messages. We next show that if jointly Gaussian random variables are sufficient to evaluate this outer bound for the Gaussian MIMO broadcast channel, the dirty-paper coding (DPC) region is the capacity region of the Gaussian MIMO broadcast channel with common and private messages. However, we can evaluate only a loosened version of this outer bound, which yields the result that extending the DPC region in the common message rate direction by a fixed amount is an outer bound for the capacity region of the Gaussian MIMO broadcast channel with common and private messages. However, this fixed amount, i.e., the gap, is not finite for all channels. We derive the necessary and sufficient conditions for this gap to be finite.

We study the two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and confidential messages. In this channel, the transmitter sends a common message to both users, and a confidential message to each user which is kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between the capacity region we obtained for the Gaussian MIMO broadcast channel with common and confidential messages and the capacity region of its non-confidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private messages, which is not known completely.

We consider diamond channels with a general broadcast channel p(y, z|x), with outputs Z and Y at relays 1 and 2, respectively, and where the relays 1 and 2 have noiseless links of capacities Rzand Ry, respectively, to the decoder. For the case when Y and Z are deterministic functions of X, we establish the capacity. We next give an upper bound for the capacity of the class of diamond channels with a physically degraded broadcast channel, i.e., when X → Y → Z forms a Markov chain. We show that this upper bound is tight, if in addition to X → Y → Z, the output of relay 2, i.e., Y, is a deterministic function of X. We finally consider the diamond channel with partially separated relays, i.e., when the output of relay 2 is available at relay 1. We establish the capacity for this model in two cases, a) when the broadcast channel is physically degraded, i.e., when X → Y → Z forms a Markov chain, and b) when the broadcast channel is semi-deterministic, i.e, when Y = f(X). For both of these cases, we show that the capacity is equal to the cut-set bound. This final result shows that even partial feedback from the decoder to relays strictly increases the capacity of the diamond channel.

We consider a communication channel with two transmitters and one receiver, with an underlying rate region which is approximated as a general pentagon. Different from the Gaussian multiple access channel (MAC) capacity region, the sum-rate on the dominant face of this pentagon is not a constant. We allocate rates from this rate region to users according to their current queue lengths in order to minimize the average delay in the system. We formulate the problem as a Markov decision problem (MDP), and derive the structural properties of the corresponding discounted-cost MDP. We show that the delay-optimal policy has a switch curve structure. For the discounted-cost problem, we prove that the switch curve has a limit along one of the dimensions.

We study the Gaussian multiple-input multiple-output (MIMO) wiretap channel, which consists of a transmitter, a legitimate user, and an eavesdropper. In this channel, the transmitter sends a common message to both the legitimate user and the eavesdropper. Moreover, the legitimate user receives a private message, which is desired to be kept hidden as much as possible from the eavesdropper. We obtain the entire capacity-equivocation region of the Gaussian MIMO wiretap channel. This region contains all achievable common message, private message, and private message's equivocation rates. This capacity-equivocation region is equal to the capacity region of a Gaussian MIMO broadcast channel where the transmitter sends a common message to both the legitimate user and the eavesdropper, a public message to the legitimate user on which there is no secrecy constraint, and a confidential message to the legitimate user which needs to kept perfectly secret from the eavesdropper.

Multiple antenna systems are known to provide very large data rates, when the perfect channel state information (CSI) is available at the receiver. However, this requires the receiver to perform a noise-free, multi-dimensional channel estimation, without using communication resources. In practice, any channel estimation is noisy and uses system resources. We shall examine the trade-off between improving channel estimation and increasing the achievable data rate. We consider transmit side correlated multi-input multi-output (MIMO) channels with block fading, where each block is divided into training and data transmission phases. The receiver has a noisy CSI that it obtains through a channel estimation process, while the transmitter has partial CSI in the form of covariance feedback. In Part I of this two-part paper, we consider the single-user case, and optimize the achievable rate jointly over parameters associated with the training phase and data transmission phase. In particular, we first choose the training signal to minimize the channel estimation error, and then, develop an iterative algorithm to solve for the optimum system resources such as time, power and spatial dimensions. Specifically, the algorithm finds the optimum training duration, the optimum allocation of power between training and data transmission phases, the optimum allocation of power over the antennas during the data transmission phase.

This is the second part of a two-part paper on the joint channel estimation and resource allocation problem in MIMO systems with noisy channel estimation at the receiver side and partial CSI, in the form of covariance feedback, available at the transmitter side.We consider transmit-side correlated MIMO channels with block fading, where each block is divided into training and data transmission phases. In this paper, we extend the single-user results of Part I to the multiple access channel. For the data transmission phase, we propose an iterative algorithm to solve for the optimum system resources such as time, power and spatial dimensions. This algorithm updates the parameters of the users in a round-robin fashion. In particular, the algorithm updates the training and data transmission parameters of a user, when those of the rest of the users are fixed, in a way to maximize the achievable sum-rate in a multiple access channel; and iterates over users in a round-robin fashion. Finally, we provide a detailed numerical analysis to support the analytical results of both parts of this two-part paper.

We investigate the problem of minimizing the overall transmission delay of packets in a multi-access wireless communication system, where the transmitters have average power constraints. We use a multi-dimensional Markov chain to model the medium access control layer behavior. The state of the Markov chain represents current queue lengths. Our goal is to minimize the average packet delay through controlling the probability of departure at each state, while satisfying the average power constraint for each queue. We consider a general asymmetric system, where the arrival rates to the queues, channel gains and average power constraints of the two users are arbitrary. We formulate the problem as a constrained optimization problem, and then transform it to a linear programming problem. We analyze the linear programming problem, and develop a procedure by which we determine the optimal solution analytically. We show that the optimal policy has a threshold structure: when the sum of the queue lengths is larger than a threshold, both users should transmit a packet during the current slot; when the sum of the queue lengths is smaller than a threshold, only one of the users, the one with the longer queue, should transmit a packet during the current slot. We provide numerical examples for both symmetric and asymmetric settings.

We consider the Gaussian multiple-input multiple-output (MIMO) multi-receiver wiretap channel, and derive the secrecy capacity region of this channel for the most general case. We first prove the secrecy capacity region of the degraded MIMO channel, in which all receivers have the same number of antennas, and the noise covariance matrices exhibit a positive semi-definite order. We then generalize this result to the aligned case, in which all receivers have the same number of antennas, however there is no order among the noise covariance matrices. We accomplish this task by using the channel enhancement technique. Finally, we find the secrecy capacity region of the general MIMO channel by using some limiting arguments on the secrecy capacity region of the aligned MIMO channel. We show that a variant of dirty-paper coding with Gaussian signals is optimal.

We consider the fading broadcast channel from a secrecy point of view. In this channel, each user views the other user as an eavesdropper, and wants to keep its information as secret from the other user as possible. First, we consider a more general channel model which consists of L independent sub-channels, where in each sub-channel, one of the users' channel is less noisy with respect to the other user. Since the user which has the less noisy observation can be different in each sub-channel, the overall channel is not less noisy for any one of the users. We establish the secrecy capacity region of this channel for the case where the transmitter sends a common message to both users and an individual confidential message to each user. This channel model encompasses the sub-class of channels, where in each sub-channel, one of the users' observation is degraded with respect to the other user. The parallel Gaussian broadcast channel belongs to this sub-class. In the Gaussian case, we identify the optimum input distribution, which is Gaussian, and the optimum power allocation corresponding to each point on the boundary of the secrecy capacity region. Finally, noting that the fading Gaussian broadcast channel is equivalent to a parallel Gaussian broadcast channel from an ergodic capacity perspective, we explicitly evaluate the ergodic secrecy capacity region of the fading broadcast channel.

We provide a new outer bound on the capacity region of the two-user Gaussian multiple access channel (MAC) with AWGN-corrupted feedback. Our outer bound is based on the idea of dependence balance due to Hekstra and Willems. Evaluating our outer bound is non-trivial as it involves taking a union over joint densities of three random variables, one of which is an auxiliary random variable. We resolve this difficulty by proving that it is sufficient to consider jointly Gaussian random variables when evaluating our outer bound. As the feedback noise variances become large, our outer bound collapses to the capacity region of the Gaussian MAC without feedback, thereby yielding the first non-trivial result for a Gaussian MAC with noisy feedback. Furthermore, as the feedback noise variances tend to zero, our outer bound collapses to the capacity region of the Gaussian MAC with noiseless feedback, which was established by Ozarow. For all non-zero, finite values of the feedback noise variances, our outer bound strictly improves upon the cutset outer bound.

We consider the Gaussian multi-receiver wiretap channel and evaluate its secrecy capacity region. This evaluation requires the identification of underlying auxiliary random variables. For this purpose, we first visit the converse proof of the scalar Gaussian broadcast channel, and show that this proof cannot be extended to this secrecy context. The failure of this extension comes from the insufficiency of the entropy-power inequality to resolve the ambiguity regarding the auxiliary random variables. Instead, we provide two converse proofs. The first one uses the alternative representation of the mutual information as an integration of the minimum-mean-square-error (MMSE) along with the properties of the MMSE. The second one uses the relationship between the differential entropy and the Fisher information via the de Bruin identity along with the properties of the Fisher information.

We obtain a dependence balance based outer bound on the capacity region of the two-user multiple access channel with generalized feedback (MAC-GF). We investigate a Gaussian MAC with user-cooperation (MAC-UC), where each transmitter receives an additive white Gaussian noise corrupted version of the channel input of the other transmitter. For all non-zero values of cooperation noise variances, our outer bound strictly improves upon the cut-set outer bound. Moreover, as the variances of the cooperation noises become large, our outer bound collapses to the capacity region of the Gaussian MAC without cooperation.

We study a rate-limited version of the well known problem of coding for channels with random parameters which was studied by Gelfand and Pinsker [1]. In particular, we consider a state-dependent channel when the transmitter is supplied with the state information at a rate Re. We obtain a new upper bound on the capacity, C(Re), for this channel. We explicitly evaluate this upper bound for the rate-limited dirty paper coding (DPC) problem and show that it strictly improves upon the DPC capacity for certain values of Re.

We investigate a delay minimization problem in a multiple access wireless communication system. We consider a discrete-time non-fading additive white Gaussian noise (AWGN) multiple access channel. In each slot, bits arrive at the transmitters randomly according to some distribution, which is i.i.d. from user to user and from slot to slot. Each transmitter has an average power constraint of P. Our goal is to allocate rates to users, from the multiple access capacity region, based on their current queue lengths, in order to minimize the average delay of the system. We formulate the problem as a Markov decision problem (MDP) with an average cost criterion. We first show that the value function is increasing, symmetric and convex in the queue length vector. Taking advantage of these properties, we show that the optimal rate allocation policy is one which tries to equalize the queue lengths as much as possible in each slot, while working on the dominant face of the capacity region.

We obtain a new outer bound on the capacity region of the two-user interference channel with generalized feedback (IC-GF). This outer bound is based on the idea of dependence balance which was proposed by Hekstra and Willems. We explicitly evaluate our outer bound for the Gaussian IC with user-cooperation (IC-UC), where each transmitter receives an additive white Gaussian noise corrupted version of the channel input of the other transmitter. We show that for all non-zero values of cooperation noise variances, our outer bound strictly improves upon the cut-set outer bound.

We consider the sum capacity of a multi-input multi-output (MIMO) multiple access channel (MAC) where the receiver has the perfect channel state information (CSI), while the transmitters have either no or partial CSI. When the transmitters have partial CSI, it is in the form of either the covariance matrix of the channel or the mean matrix of the channel. For the covariance feedback case, we mainly consider physical models that result in single-sided correlation structures. For the mean feedback case, we consider physical models that result in in-phase received signals. Under these assumptions, we analyze the MIMO-MAC from three different viewpoints. First, we consider a finite-sized system. We show that the optimum transmit directions of each user are the eigenvectors of its own channel covariance and mean feedback matrices, in the covariance and mean feedback models, respectively. Also, we find the conditions under which beamforming is optimal for all users. Second, in the covariance feedback case, we prove that the region where beamforming is optimal for all users gets larger with the addition of new users into the system. In the mean feedback case, we show through simulations that this is not necessarily true. Third, we consider the asymptotic case where the number of users is large. We show that in both no and partial CSI cases, beamforming is asymptotically optimal. In particular, in the case of no CSI, we show that a simple form of beamforming, which may be characterized as an arbitrary antenna selection scheme, achieves the sum capacity. In the case of partial CSI, we show that beamforming in the direction of the strongest eigenvector of the channel feedback matrix achieves the sum capacity. Finally, we generalize our covariance feedback results to double-sided correlation structures in the Appendix.

We find the secrecy capacity of the 2-2-1 Gaussian MIMO wiretap channel, which consists of a transmitter and a receiver with two antennas each, and an eavesdropper with a single antenna. We determine the secrecy capacity of this channel by proposing an achievable scheme and then developing a tight upper bound that meets the proposed achievable secrecy rate. We show that, for this channel, Gaussian signalling in the form of beam-forming is optimal, and no pre-processing of information is necessary.

We investigate the behavior of two users and one jammer in an additive white Gaussian noise (AWGN) channel with and without fading when they participate in a noncooperative zero-sum game, with the channel's input/output mutual information as the objective function. We assume that the jammer can eavesdrop on the channel and can use the information obtained to perform correlated jamming. We also differentiate between the availability of perfect and noisy information about the user signals at the jammer. Under various assumptions on the channel characteristics, and the extent of information available at the users and the jammer, we show the existence, or otherwise nonexistence of a simultaneously optimal set of strategies for the users and the jammer, and characterize those strategies whenever they exist.

We use the idea of dependence balance to obtain a new outer bound for the capacity region of the discrete memoryless multiple-access channel with noiseless feedback (MAC-FB). We consider a binary additive noisy MAC-FB whose feedback capacity is not known. The binary additive noisy MAC considered in this paper can be viewed as the discrete counterpart of the Gaussian MAC-FB. Ozarow established that the capacity region of the two-user Gaussian MAC-FB is given by the cut-set bound. Our result shows that for the discrete version of the channel considered by Ozarow, this is not the case. Direct evaluation of our outer bound is intractable due to an involved auxiliary random variable whose large cardinality prohibits an exhaustive search. We overcome this difficulty by using a composite function and its properties to explicitly evaluate our outer bound. Our outer bound is strictly less than the cut-set bound at all points on the capacity region where feedback increases capacity. In addition, we explicitly evaluate the Cover-Leung achievable rate region for the binary additive noisy MAC-FB in consideration. Furthermore, using the tools developed for the evaluation of our outer bound, we also explicitly characterize the boundary of the feedback capacity region of the binary erasure MAC, for which the Cover-Leung achievable rate region is known to be tight. This last result confirms that the feedback strategies developed by Kramer for the binary erasure MAC are capacity achieving.

We consider correlated MIMO multiple access channels with block fading, where each block is divided into training and data transmission phases. We find the channel estimation and data transmission parameters that jointly optimize the achievable data rate of the system. Our results for the training phase are particularly interesting, where we show that the optimum training signals of the users should be non-overlapping in time. For the data transmission phase, we propose an iterative algorithm that updates the parameters of the users in a round-robin fashion. In particular, the algorithm updates the training and data transmission parameters of a user, when those of the rest of the users are fixed, in a way to maximize the achievable sum-rate in a multiple access channel; and iterates over users in a round-robin fashion.

We use the idea of dependence balance to obtain the first improvement over the cut-set bound for the discrete memoryless multiple access channel with noiseless feedback (MAC-FB). More specifically, we consider a binary additive noisy MAC-FB whose capacity does not coincide with the Cover-Leung achievable rate region. Evaluating the dependence balance bound is difficult due to an involved auxiliary random variable. We overcome this difficulty by using functional analysis to explicitly evaluate our upper bound for the binary additive noisy MAC-FB and show that it is strictly less than the cut-set bound for the symmetric-rate point on the capacity region.

Cognitive radios have the ability to sense their RF environment and adapt their transmission parameters to perform optimally in any situation. Part of this involves selecting the best modulation type for a particular channel. In this paper we consider a variable-rate, variable-power, adaptive, m-ary quadrature amplitude modulation (M-QAM) scheme in a single-user communication scenario. The channel between the transmitter and receiver is assumed to be a Rayleigh block-fading channel. Each block is divided into training and data phases. During the training phase, the receiver estimates the channel and feeds the estimate back to the transmitter. During the data phase, the transmitter sends its message by adapting the size of the M- QAM constellation. We first find a closed-form expression that relates the bit error rate (BER) to the constellation size of the M-QAM, and therefore to the data rate of our system. Then, for a given target BER, we maximize the data rate over the training parameters, which are the training signal, the training duration, and the training power. When these optimum parameters are used in a MATLAB implementation, we find that the target BER is matched to within an order of magnitude, and the resulting data rate is close to the theoretical limit.

We investigate the problem of minimizing the overall transmission delay of data packets in a single-user wireless communication system, where the transmitter has a fixed amount of energy to transmit all of the data packets. We consider two different scenarios. In the first scenario, we assume that packets arrive randomly at the transmitter. We propose two different approaches to solve this problem. First, we develop an iterative algorithm that allocates the total energy of the transmitter to its individual packets, in a way to minimize the total delay. As a second approach, we develop a dynamic programming formulation for the problem. In the second scenario, we assume that all of the packets have already arrived before the transmission starts. In this situation, the cost function has a fixed form, and is convex and differentiable. In this scenario, the iterative algorithm we develop is guaranteed to converge to the unique global optimal solution.

We investigate the effects of user cooperation on the secrecy of broadcast channels by considering a cooperative relay broadcast channel. We show that user cooperation can increase the achievable secrecy region. We propose an achievable scheme that combines Martonpsilas coding scheme for broadcast channels and Cover and El Gamalpsilas compress-and-forward scheme for relay channels. We derive outer bounds for the rate-equivocation region using auxiliary random variables for single-letterization. Finally, we consider a Gaussian channel and show that both users can have positive secrecy rates, which is not possible for scalar Gaussian broadcast channels without cooperation.

The thirteen papers in this special issue focus on multiuser detection for advanced communication systems and networks. The papers can be divided into three thematic groups: Multiuser detection (MUD) in i) CDMA; ii) MIMO and Multicarrier CDMA/OFDM; and iii) Cooperative Communications.

We provide a single-letter characterization for the capacity region of a class of discrete degraded interference channels (DDICs). The class of DDICs considered includes the DADIC studied by Benzel in 1979. We show that for the class of DDICs studied, encoder cooperation does not enlarge the capacity region, and therefore, the capacity region of the class of DDICs is the same as the capacity region of the corresponding degraded broadcast channel.

A Gaussian MISO (multiple input single output) channel is considered where a transmitter is communicating to a receiver in the presence of an eavesdropper. The transmitter is equipped with multiple antennas, while the receiver and the eavesdropper each have a single antenna. The transmitter maximizes the communication rate, while concealing the message from the eavesdropper. The channel input is restricted to Gaussian signalling, with no preprocessing of information. For these channel inputs, and under different channel fading assumptions, optimal transmission strategies are found, in terms of the input covariance matrices. It is shown that, the optimal communication strategy in all cases, is beamforming.

We consider both the single-user and the multi-user power allocation problems in MIMO systems, where the receiver side has the perfect channel state information (CSI), and the transmitter side has partial CSI, which is in the form of covariance feedback. In a single-user MIMO system, we consider an iterative algorithm that solves for the eigenvalues of the optimum transmit covariance matrix that maximizes the rate. The algorithm is based on enforcing the Karush-Kuhn-Tucker (KKT) optimality conditions of the optimization problem at each iteration. We prove that this algorithm converges to the unique global optimum power allocation when initiated at an arbitrary point. We, then, consider the multi-user generalization of the problem, which is to find the eigenvalues of the optimum transmit covariance matrices of all users that maximize the sum rate of the MIMO multiple access channel (MIMO-MAC). For this problem, we propose an algorithm that finds the unique optimum power allocation policies of all users. At a given iteration, the multi-user algorithm updates the power allocation of one user, given the power allocations of the rest of the users, and iterates over all users in a round-robin fashion. Finally, we make several suggestions that significantly improve the convergence rate of the proposed algorithms.

We investigate the optimal performance of dense sensor networks by studying the joint source–channel coding problem. There are$N$uniformly spaced sensor nodes sampling noiselessly a one-dimensional spatial random process over an interval$[0,U_{0}]$. The overall goal of the sensor network is for the sensor nodes to code and transmit the measurement samples to a collector node over a cooperative multiple-access channel with noisy feedback, and for the collector node to reconstruct the entire random process with minimum expected distortion. We provide separation-based lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. When the Gaussian random process satisfies some general conditions, such as the eigenvalues of its Karhunen–Loeve expansion decrease roughly inverse polynomially in order$x$, i.e., the$k$th eigenvalue is roughly$k^{-x}$, we evaluate the lower and upper bounds explicitly, and show that they are of the same order for a wide range of power constraints. Thus, for these random processes, under these power constraints, we show that the minimum achievable expected distortion decreases as$\left (\log NP(N) \right )^{1-x}$, where$P(N)$is the sum power constraint on the sensor nodes. Further, we show that the achievability scheme that achieves the lower bound on the distortion is a separation-based scheme that is composed of multiterminal rate-distortion coding and amplify-

For a fading Gaussian multiple access channel with user cooperation, we obtain the power allocation policies that maximize the average rates achievable by block Markov superposition coding, subject to average power constraints. The optimal policies result in a coding scheme that is simpler than the one for a general multiple access channel with generalized feedback. This simpler coding scheme also leads to the possibility of formulating an otherwise non-concave optimization problem as a concave one. Using the perfect channel state information available at the transmitters to adapt the powers, we demonstrate gains over the achievable rates for existing cooperative systems.

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a co-operative multiple access channel with feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is stationary and Gaussian. In the case where the random process is also Markovian, we evaluate the lower and upper bounds explicitly and show that they are of the same order for a wide range of sum power constraints. Thus, for a Gauss-Markov random process, under these sum power constraints, we determine the achievability scheme that is order-optimal, and express the minimum achievable expected distortion as a function of the sum power constraint.

The multi-terminal rate-distortion problem has been studied extensively. Notably, among these, Tung and House-wright have provided the best known inner and outer bounds for the rate region under certain distortion constraints. In this paper, we first propose an outer bound for the rate region, and show that it is tighter than the outer bound of Tung and Housewright. Our outer bound involves some n-letter Markov chain constraints, which cause computational difficulties. We utilize a necessary condition for the Markov chain constraints to obtain another outer bound, which is represented in terms of some single-letter mutual information expressions evaluated over probability distributions that satisfy some single-letter conditions

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a cooperative multiple access channel with imperfect feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. In the case where the random process satisfies some general conditions, we evaluate the lower and upper bounds explicitly and show that they are of the same order for a wide range of sum power constraints. Thus, for these random processes, under these sum power constraints, we determine the achievability scheme that is order-optimal, and express the minimum achievable expected distortion as a function of the sum power constraint

A Gaussian multiple-access channel with common data is considered. Capacity region when there is no fading is known in an implicit form. We provide an explicitly characterization of the capacity region and provide a simpler encoding/decoding scheme than that previously mentioned in the literature. Next, we give a characterization of the ergodic capacity region when there is fading, and both the transmitters and the receiver know the channel perfectly. Then, we characterize the optimum power-allocation schemes that achieve arbitrary rate tuples on the boundary of the capacity region. Finally, we provide an iterative method for the numerical computation of the ergodic capacity region and the optimum power-control strategies.

A Gaussian multiple access channel (MAC) with common data is considered. Capacity region when there is no fading is known in an implicit form. We provide an explicit characterization of the capacity region and provide a simpler encoding/decoding scheme than that mentioned in work by Slepian and Wolf. Next, we give a characterization of the ergodic capacity region when there is fading, and both the transmitters and the receiver know the channel perfectly. Then, we characterize the optimum power allocation schemes that achieve arbitrary rate tuples on the boundary of the capacity region. Finally, we provide an iterative method for the numerical computation of the ergodic capacity region and the optimum power control strategies

We characterize the optimum power control policies that achieve arbitrary rate tuples on the boundary of the capacity region of a power controlled, code division multiple access (CDMA) system in a fading channel with perfect channel state information (CSI). We propose a "generalized" waterfilling approach, and provide an iterative algorithm that solves for the optimum power allocation policy, for a given arbitrary rate tuple on the boundary of the capacity region. We then investigate the effects of limited feedback on the capacity region, and demonstrate that a good power control policy may require only a very low rate feedback

We solve for the optimum signature sequence and power allocation policies that maximize the information-theoretic ergodic sum capacity of a code-division multiple-access (CDMA) system subject to fading. We show that at most N users may transmit at any given channel state, where N is the processing gain; and those users who are transmitting should be assigned orthogonal signature sequences. We also show that the power allocation policy that maximizes the capacity together with the choice of these signature sequences is single-user water-filling over sets of channel states that are favorable to each user. That is, the capacity maximizing signaling scheme is shown to dictate that the users allocate their powers and signature sequences in such a way that they always avoid interference from each other.

In an energy-efficient wireless communication system, transmit powers are minimized subject to predetermined signal-to-interference ratio (SIR) requirements. In this paper, a general framework for distributed stochastic power control (PC) algorithms is proposed, where the transmit powers are updated based on stochastic approximations. The proposed algorithms are distributed in the sense that no global information is needed in the power updates. Interference to each user is estimated locally via noisy observations. Two types of stochastic PC algorithms are studied: standard stochastic PC algorithms where the interference estimator is unbiased, and quasi-standard stochastic PC algorithms where the interference estimator is biased. The conditions under which the stochastic PC algorithms converge to the unique optimal solution are identified. Corresponding to two classes of iteration step-size sequences, two types of convergence, the probability one convergence and convergence in probability, are shown for both algorithms based on recent results in the stochastic approximation literature. Based on the theoretical results, some well-known stochastic PC algorithms, such as stochastic PC with matched filter receivers, and joint stochastic PC with blind minimum mean-squared error (MMSE) interference suppression, are revisited; several new stochastic PC algorithms, such as stochastic PC with minimum-power base-station assignment, and stochastic PC with limited diversity, are proposed. It is shown that these algorithms fall into either the standard or the quasi-standard stochastic PC framework. Simulation results are given to illustrate the performance of the proposed algorithms in practical systems.

The optimal signature sequences that maximize the sum capacity of a direct sequence code-division multiple-access (CDMA) system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

We investigate the capacity region of the Gaussian Z-channel with a small crossover link gain, i.e. /spl alpha//spl les/1. For the case of /spl alpha/<1, we provide an achievable region, and the converse for most of the achievable region. We also derive lower and upper bounds for the part of the region where the capacity boundary is unclear. For the case of /spl alpha/=1, we determine the capacity region exactly.

The optimal signature sequences that maximize the sum capacity of a direct sequence CDMA system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

In this paper a symbol synchronous CDMA system with processing gain where all the users transmit to a single receiver is considered. The receiver and the transmitter have perfect knowledge of the channel states. The set of long term achievable rates, i.e., the capacity region, for a power controlled scalar multiaccess channel is characterized for fading CDMA. The capacity region of a fading CDMA channel under additive white Gaussian noise, where users have perfect CSI and the powers are allocated as function of the CSI. The capacity region may contain a flat region but it is not strictly convex. The simultaneous transmission region with nonorthogonal signatures implies the sum-capacity, and therefore, a flat region on the capacity boundary exists

We specify the capacity region for a power-controlled, fading code-division multiple-access (CDMA) channel. We investigate the properties of the optimum power allocation policy that maximizes the information-theoretic ergodic sum capacity of a CDMA system where the users are assigned arbitrary signature sequences in a frequency flat-fading environment. We provide an iterative waterfilling algorithm to obtain the powers of all users at all channel fade levels, and prove its convergence. Under certain mild conditions on the signature sequences, the optimum power allocation dictates that more than one user transmit simultaneously in some nonzero probability region of the space of all channel states. We identify these conditions, and provide an upper bound on the maximum number of users that can transmit simultaneously at any given time. Using these properties of the sum capacity maximizing power control policy, we also show that the capacity region of the fading CDMA channel is not in general strictly convex.

For a symbol-asynchronous (but chip-synchronous) single-cell code-division multiple-access (CDMA) system, we define a system-wide quantity called the total squared asynchronous correlation (TSAC) which, for arbitrary signature sets, depends on the users' delay profile. We develop a lower bound for TSAC that is independent of the users' delays. We show that if the signature set achieves this TSAC lower bound, then the user capacity of the asynchronous CDMA system using matched filters becomes the same as that of a single-cell synchronous CDMA system; in this case, there is no loss in user capacity due to asynchronism. We present iterative signature adaptation algorithms, which, when executed sequentially by the users, appear to converge to these optimum signature sequences; however, the existence, for all user delay profiles, of signature sequences achieving this lower bound remains a significant open problem.

Optimization of the capacity of a single-cell code-division multiple-access (CDMA) system, both from the perspective of the maximum number of users that can be served at a required quality of service level and from the information theoretic perspective, has been recently shown to be achieved by the same joint transmit and receive strategies. We propose an alternating minimization based iterative algorithm that updates the transmitters and the corresponding receivers of the users. The algorithm is suitable for online implementation, and the objective function is suitable for extension to multicell networks, both of which are in contrast with the previously proposed algorithms. We show that the algorithm is provably convergent to the optimum signature sequences and the corresponding receivers.

We solve for the optimum signature sequence and power allocation policies that maximize the information theoretic ergodic sum capacity of a code division multiple access (CDMA) system subject to fading. We show that at most N users may transmit at any given channel state, where N is the processing gain, and that those users who are transmitting should be assigned orthogonal signature sequences. We also show that the power allocation policy that maximizes the capacity together with the choice of these signature sequences is single user waterfilling over sets of channel states that are favorable to each user. That is, the capacity maximizing signalling scheme is shown to dictate that the users allocate their powers and signature sequences in such a way that they always avoid interference from each other.

The optimum receiver to detect the bits of multiple code-division multiple access (CDMA) users has an exponential complexity in the number of active users in the system. Consequently, many suboptimum receivers have been developed to achieve good performance with less complexity. We take the approach of approximating the solution of the optimum multiuser detection problem (OMUD) using nonlinear programming relaxations. First, we observe that some popular suboptimum receivers indeed correspond to relaxations of the optimal detection problem. In particular, one proposed approximation method yields to iterative solutions which correspond to previously proposed heuristic nonlinear detectors. Using a nonlinear programming approach, we identify the convergence properties of these iterative detectors. Secondly, we propose a relaxation that yields a receiver which we call the generalized minimum mean squared error detector. We give a simple iterative implementation of the detector. Its performance is evaluated and comparisons to other suboptimum detection schemes are given.

Motivated by the emergence of programmable radios, we seek to understand a new class of communication system where pairs of transmitters and receivers can adapt their modulation/demodulation method in the presence of interference to achieve better performance. Using signal to interference ratio as a metric and a general signal space approach, we present a class of iterative distributed algorithms for synchronous systems which results in an ensemble of optimal waveforms for multiple users connected to a common receiver (or colocated independent receivers). That is, the waveform ensemble meets the Welch (1974) bound with equality and, therefore, achieves minimum average interference over the ensemble of signature waveforms. We derive fixed points for a number of scenarios, provide examples, look at ensemble stability under user addition and deletion as well as provide a simplistic comparison to synchronous code-division multiple-access. We close with suggestions for future work.

We characterize the user capacity, i.e., the maximum number of supportable users at a common SIR target level for a fixed processing gain, of a single-cell symbol asynchronous CDMA system. We show that the user capacity of an asynchronous system is the same as the user capacity of a synchronous system; that is there is no loss in user capacity due to asynchrony. Optimum signature sequences are those that minimize the total squared asynchronous correlation (TSAC) among the users, and depend on users' delay profile. Optimum received powers of the users are equal, and the optimum linear receiver filters in any observation window of size M/spl ges/1 symbols (i.e., M-shot MMSE filters) are one-shot matched filters. We present iterative and distributed signature adaptation algorithms where, at each iteration, only one user updates its signature sequence to decrease the TSAC of the set.

We study the problem of maximizing the total system throughput under a bit error rate constraint for all users in the uplink of a single-cell synchronous CDMA system. Users realize variable bit rates by using a combination of multicode transmission and adaptive QAM modulation. We assume random signature sequences for all users, and perform an asymptotic analysis. We parametrize each user's resource allocation scheme by two parameters, viz., the number of signatures the user transmits with and the number of signal points in the user's QAM constellation, and optimize the total throughput over this parameter space. We examine four different settings: single-user matched filter (SUMF) and minimum-mean-square error (MMSE) receiver at the base station, with and without maximum power constraints. For a single user system, we describe the jointly optimum number of multicodes and constellation sizes for these four different system models. When multiple users are present, we show that the total throughput is maximized when only one user transmits: with no maximum power constraints this user can be chosen arbitrarily, otherwise it should be the one with the largest SNR. This solution, although optimal in the sense of maximizing the total throughput, is unfair to all but one user: thus, we examine a scheduling mechanism that assigns equal time frames to all users, thus yielding maximum fairness, and discuss the resulting total throughput loss.

Among the ambitious challenges to be met by the third-generation systems is to provide high-capacity flexible services. Code-division multiple access (CDMA) emerges as a promising candidate to meet these challenges. It is well known that CDMA systems are interference-limited, and interference management is needed to maximally utilize the potential gains of this access scheme. Several methods of controlling and/or suppressing the interference through power control, multiuser detection (temporal filtering), and receiver beamforming (spatial filtering) have been proposed to increase the capacity of CDMA systems up to date. We investigate the capacity increase that is possible by combining power control with intelligent temporal and spatial receiver filter design. The signal-to-interference ratio maximizing joint temporal-spatial receiver filters in unconstrained and constrained filter spaces are derived. Two-step iterative power control algorithms that converge to the optimum powers and the joint temporal and spatial receiver filters in the corresponding filter domains are given. A power control algorithm with a less complex filter update procedure is also given. We observe that significant savings in total transmit power are possible if filtering in both domains is utilized compared with conventional power control and joint optimal power control and filtering in only one domain.

Optimum signature sequence sets that maximize the capacity of single-cell synchronous code division multiple access (CDMA) systems have been identified. Optimum signature sequences minimize the total squared correlation (TSC); they form a set of orthogonal sequences, if the number of users is less than or equal to the processing gain, and a set of Welch (1994) bound equality (WBE) sequences, otherwise. We present an algorithm where users update their transmitter signature sequences sequentially, in a distributed fashion, by using available receiver measurements. We show that each update decreases the TSC of the set, and produces better signature sequence sets progressively. We prove that the algorithm converges to a set of orthogonal signature sequences when the number of users is less than or equal to the processing gain. We observe and conjecture that the algorithm converges to a WBE set when the number of users is greater than the processing gain. At each step, the algorithm replaces one signature sequence from the set with the normalized minimum mean squared error (MMSE) receiver corresponding to that signature sequence. Since the MMSE filter can be obtained by a distributed algorithm for each user, the proposed algorithm is amenable to distributed implementation.

Handover is the process by which a mobile terminal maintains a communication session as it crosses through the coverage area of the grid of base stations providing service in a cellular wireless system. Because of imperfect channel measurements, it is difficult to determine the correct point for a handover. Acting too soon may force a handover back to the original base station; delaying too long may make it impossible for the mobile to meet its quality of service objectives. It is important to quantify the handover delay in terms of various system parameters in order to efficiently design cellular wireless communication systems. This paper presents an exact expression for handover delay as a function of the base station separation, the standard deviation of log-normal shadowing, and the averaging distance. It also presents a simple closed form approximation that includes the hysteresis margin. These are the first such expressions available within the literature. The approximation is validated via simulation and is shown to work well over the range of interest.

The decorrelating detector is known to eliminate multiaccess interference when the signature sequences of the users are linearly independent, at the cost of enhancing the Gaussian receiver noise. We present a blind adaptive decorrelating detector which is based on the observation of readily available statistics. The algorithm recursively updates the filter coefficients of a desired user by using the output of the current filter. Due to the randomness of the information bits transmitted and the ambient Gaussian channel noise, the filter coefficients evolve stochastically. We prove the convergence of the filter coefficients to a decorrelating detector in the mean squared error (MSE) sense. We develop lower and upper bounds on the MSE of the receiver filter from the convergence point and show that with a fixed step size sequence, the MSE can be made arbitrarily small by choosing a small enough step size. With a time-varying step size sequence, the MSE converges to zero implying an exact convergence. The proposed algorithm is distributed, in the sense that no information about the interfering users such as their signature sequences or power levels is needed. The algorithm requires the knowledge of only two parameters for the construction of the receiver filter of a desired user: the desired user's signature sequence and the variance of the additive white Gaussian (AWG) receiver noise. This detector, for an asynchronous code division multiple access (CDMA) channel, converges to the one-shot decorrelating detector.

For wireless communication systems, iterative power control algorithms have been proposed to minimize the transmitter power while maintaining reliable communication between mobiles and base stations. To derive deterministic convergence results, these algorithms require perfect measurements of one or more of the following parameters: (1) the mobile's signal-to-interference ratio (SIR) at the receiver; (2) the interference experienced by the mobile; and (3) the bit-error rate. However, these quantities are often difficult to measure and deterministic convergence results neglect the effect of stochastic measurements. We develop distributed iterative power control algorithms that use readily available measurements. Two classes of power control algorithms are proposed. Since the measurements are random, the proposed algorithms evolve stochastically and we define the convergence in terms of the mean-squared error (MSE) of the power vector from the optimal power vector that is the solution of a feasible deterministic power control problem. For the first class of power control algorithms using fixed step size sequences, we obtain finite lower and upper bounds for the MSE by appropriate selection of the step size. We also show that these bounds go to zero, implying convergence in the MSE sense, as the step size goes to zero. For the second class of power control algorithms, which are based on the stochastic approximations method and use time-varying step size sequences, we prove that the MSE goes to zero. Both classes of algorithms are distributed in the sense that each user needs only to know its own channel gain to its assigned base station and its own matched filter output at its assigned base station to update its power.

Power control algorithms assume that the receiver structure is fixed and iteratively update the transmit powers of the users to provide them with an acceptable quality of service while minimizing the total transmitter power. Multiuser detection on the other hand optimizes the receiver structure with the assumption that the users have fixed transmitter powers. In this study, we combine the two approaches for a CDMA cellular system and propose an iterative and distributed power control algorithm which iteratively updates the transmitter powers and receiver filter coefficients of the users. We show that the algorithm converges to a minimum power solution for the powers, and an MMSE multiuser detector for the filter coefficients.

A new class of block transforms is presented. These transforms are constructed from subband decomposition filter banks corresponding to regular wavelets. New transforms are compared to the discrete cosine transform (DCT). Image coding schemes that use the block wavelet transform (BWT) are developed. BWT's can be implemented by fast (O(N log N)) algorithms.>