Microservices are widely shared in production user-facing applications. These shared microservices have various resource usage patterns when queries from different call graphs of different services access them. However, existing microservice management works fail to efficiently scale resources for them, mainly due to the lack of fine-grained scheduling of diverse queries. We therefore propose Delphinus , a runtime system that efficiently manages resources for shared microservices while ensuring the Quality-of-Service (QoS). Delphinus comprises a group-oriented query scheduler and a borrowing-based load adapter . The query scheduler identifies diverse queries, groups the containers of shared microservices, and schedules the queries into separate groups. The load adapter efficiently scales resources for shared microservices, and fully utilizes the idle containers among groups when the loads of diverse queries change. Results show that Delphinus reduces CPU and memory usage by 40.1% and 36.4% for shared microservices, respectively, compared to state-of-the-art works.

Gradecast is a variant of the Byzantine broadcast problem introduced by Feldman and Micali in 1988. In Gradecast, n processors would like to agree on a value sent from a leader, as well as a grade in {0, 1, 2}, such that the following three requirements are satisfied: 1) Every non-faulty processor outputs the leader’s initial value and grade 2 if the leader is non-faulty; 2) For any two non-faulty processors, if their decided grades are greater than zero, then they output the same value; and 3) For any two non-faulty processors, the difference of their decided grades is less than 2. In this work, we present a new Gradecast protocol with a total communication complexity of O(nℓ + n2log n) bits, given t < n/3, where ℓ is the message size and t is the maximum number of faulty processors tolerated in n consensus processors. The proposed protocol is an error-free and deterministic Gradecast protocol that does not rely on the authentication techniques such as signatures and secret sharing. The proposed protocol is also information-theoretic secure, i.e., it satisfies the above three requirements even if the computation power of the adversary is unbounded.

We consider a distributed computing framework where the distributed nodes have different communication capabilities, motivated by the heterogeneous networks in data centers and mobile edge computing systems. Following the structure of MapReduce, this framework consists of Map computation phase, Shuffle phase, and Reduce computation phase. The Shuffle phase allows distributed nodes to exchange intermediate values, in the presence of heterogeneous communication bottlenecks for different nodes (heterogeneous communication load constraints). For this setting, we characterize the minimum total computation load and the minimum worst-case computation load in some cases, under the heterogeneous communication load constraints. While the total computation load depends on the sum of the computation loads of all the nodes, the worst-case computation load depends on the computation load of a node with the heaviest job. We show an interesting insight that, for some cases, there is a tradeoff between the minimum total computation load and the minimum worst-case computation load, in the sense that both cannot be achieved at the same time. The achievability schemes are proposed with careful design on the file assignment and the data shuffling. Beyond the cut-set bound, a novel converse is proposed using the proof by contradiction. For the general case, we identify two extreme regimes in which both the scheme with coding and the scheme without coding are optimal, respectively.

In this work, we focus on the problem of byzantine agreement (BA), in which$n$distributed processors seek to reach an agreement on an$\ell$-bit value, but up to$t$processors might be corrupted by a Byzantine adversary and act as dishonest nodes. In particular, we consider the communication-efficient BA in an asynchronous setting, where the network communication might have arbitrarily time delay. The primary challenge of designing the BA protocol in this setting is that we need to handle both the message delay from honest nodes and the Byzantine behavior from dishonest nodes simultaneously. In this work we propose a new signature-free asynchronous byzantine agreement (ABA) protocol, which achieves the optimal communication complexity of$O(n\ell)$when$\ell\geq t\log t$, given$n\geq 5t+1$. A protocol is said to be signature-free if the protocol design does not depend on the cryptographic machinery such as hashing and signature. To the best of our knowledge, this is the first signature-free ABA protocol that achieves the optimal communication complexity of$O(n\ell)$when$\ell$is almost linearly scaled with$t$.

Byzantine agreement (BA) is a distributed consensus problem where n processors want to reach agreement on an 𝓁-bit message or value, but up to t of the processors are dishonest or faulty. The challenge of this BA problem lies in achieving agreement despite the presence of dishonest processors who may arbitrarily deviate from the designed protocol. In this work by using coding theory, together with graph theory and linear algebra, we design a coded BA protocol (termed as COOL) that achieves consensus on an 𝓁-bit message with optimal resilience, asymptotically optimal round complexity, and asymptotically optimal communication complexity when 𝓁 ≥ t log t, simultaneously. The proposed COOL is a deterministic BA protocol that is guaranteed to be correct in all executions (error free) and does not rely on cryptographic technique such as signatures, hashing, authentication and secret sharing (signature free). It is secure against computationally unbounded adversary who takes full control over the dishonest processors (information-theoretic secure). The main idea of the proposed COOL is to use a carefully-crafted error correction code that provides an efficient way of exchanging "compressed" information among distributed nodes, while keeping the ability of detecting errors, masking errors, and making a consistent and validated agreement at honest distributed nodes. We show that our results can also be extended to the setting of Byzantine broadcast, aka Byzantine generals problem, where the honest processors want to agree on the message sent by a leader who is potentially dishonest. The results reveal that coding is an effective approach for achieving the fundamental limits of Byzantine agreement and its variants. Our protocol analysis borrows tools from coding theory, graph theory and linear algebra.

In wireless networks, link strengths are often affected by some topological factors such as propagation path loss, shadowing and inter-cell interference. Thus, different users in the network might experience different link strengths. In this work we consider a K-user asymmetric interference channel, where the channel gains of the links connected to Receiver k are scaled with √{Pαk}, k=1,2, ..., K, for 01≤ α2≤ ...≤ αK. For this setting, we show that the optimal sum generalized degrees-of-freedom (GDoF) is characterized as dsum= Σk=1Kαk+ αK-αK-1/2 which matches the existing result dsum= K/2 when α1= α2= ... = αK= 1. The achievability is based on multi-layer interference alignment, where different interference alignment sub-schemes are designed in different layers associated with specific power levels, and successive decoding is applied at the receivers. While the converse for the symmetric case only requires bounding the sum degrees-of-freedom (DoF) for selected two users, the converse for this asymmetric case involves bounding the weighted sum GDoF for selected J+2 users, with corresponding weights (2J, 2J-1, ..., 22, 21), a geometric sequence with common ratio 2, for the first J users and with corresponding weights (1, 1) for the last two users, for J ∈ {1,2, ..., [log K/2]}.

We study a symmetric Gaussian wiretap channel with a helper, where a confidential message is sent from a transmitter to a legitimate receiver, in the presence of a helper and an eavesdropper, under a weak notion of secrecy constraint. For this setting, we characterize the optimal secure generalized degrees-of-freedom (GDoF). The result reveals that, adding a helper can significantly increase the secure GDoF of the wiretap channel. The result is supported by a new converse and a new scheme. In the proposed scheme, the helper sends a cooperative jamming signal at a specific power level and direction. In this way, it minimizes the penalty in GDoF incurred by the secrecy constraint. In the secure rate analysis, the techniques of noise removal and signal separation are used.

In communication networks secrecy constraints usually incur an extra limit in capacity or generalized degrees-of-freedom (GDoF), in the sense that a penalty in capacity or GDoF is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to remove the secrecy penalty in communication networks, i.e., how to remove the GDoF penalty due to secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to remove the secrecy penalty in communication networks in terms of GDoF performance. Common randomness can be generated offline before the real-time message communication. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we need to minimize the amount of common randomness used for removing the secrecy penalty in terms of GDoF performance. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to remove secrecy penalty, based on our derived converses and achievability.

In this work we consider common randomness-aided secure communications, where a limited common randomness is available at the transmitters. Specifically, we focus on a two-user interference channel with secrecy constraints and a wiretap channel with a helper, in the presence of a limited common randomness shared between the transmitters. For both settings, we characterize the optimal secure sum degrees-of-freedom (DoF) or secure DoF as a function of the DoF of common randomness. The results reveal that the secure sum DoF or secure DoF increases as the DoF of common randomness increases, bridging the gap between the extreme DoF point without common randomness and the other extreme DoF point with unlimited common randomness. The proposed scheme is a two-layer coding scheme, in which two sub-schemes are designed in two layers respectively, i.e., at two different power levels, utilizing common randomness in the first layer only. The role of common randomness is to jam partial information signal at the eavesdroppers, without causing interference at the legitimate receivers. To prove the optimality of the proposed scheme, a new converse is also derived in this work.

In wireless networks, link strengths are often affected by some topological factors such as propagation path loss, shadowing and inter-cell interference. Thus, different users in the network might experience different link strengths. In this work we consider a K-user asymmetric interference channel, where the channel gains of the links connected to Receiver k are scaled with √(Pαk), k = 1,2,⋯K, for 01≤ α2≤⋯αK. For this setting, we show that the optimal sum generalized degrees-of-freedom (GDoF) is characterized as dsum= Σk=1KαK+ αK- αK-1/2 which matches the existing result dsum= K/2 when α1= α2= ⋯ = αK= 1. The achievability is based on multi-layer interference alignment, where different interference alignment sub-schemes are designed in different layers associated with specific power levels, and successive decoding is applied at the receivers. While the converse for the symmetric case only requires bounding the sum degrees-of-freedom (DoF) for selected two users, the converse for this asymmetric case involves bounding the weighted sum GDoF for selected J + 2 users, with corresponding weights (2J, 2J-1, ⋯ , 22, 21), a geometric sequence with common ratio 2, for the first J users and with corresponding weights (1, 1) for the last two users, for J ∈ {1,2,⋯, [log {K}{2}]}.

We consider a secure communication over a two-user Gaussian interference channel, where each transmitter sends a confidential message to its legitimate receiver. For this setting, we identify a regime where the simple scheme of using Gaussian wiretap codebook at each transmitter (without cooperative jamming) and treating interference as noise at each intended receiver (in short, GWC-TIN scheme) achieves the optimal secure sum capacity to within a constant gap. For the symmetric case, this simple scheme is optimal when the interference-to-signal ratio (all link strengths in decibel scale) is no more than 2/3. However, when the ratio is more than 2/3, we show that this simple scheme is not optimal anymore and a scheme with cooperative jamming is proposed to achieve the optimal secure sum generalized degrees-of-freedom (GDoF). Specifically, for the symmetric case, we complete the optimal secure sum GDoF characterization for all the interference regimes, for almost all channel gains (except for a set of channel gains of measure zero).

In many communication networks, secrecy constraints usually incur an extra limit in capacity (or generalized degrees-of-freedom, GDoF), in the sense that a penalty in capacity (or GDoF) is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to break the limits of secrecy constraints in communication networks, i.e., how to remove the penalty in GDoF due to the secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in sum GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to break the limits of secrecy constraints in communication networks. Common randomness can be generated offline. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we hope to use less common randomness to break the limits of secrecy constraints. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to break the limits of secrecy constraints, based on our derived converses.

We study a symmetric Gaussian wiretap channel with a helper, where a confidential message is sent from a transmitter to a legitimate receiver, in the presence of a helper and an eavesdropper. For this setting, we characterize the optimal secure generalized degrees-of-freedom (GDoF). The result reveals that, adding a helper can significantly increase the secure GDoF of the wiretap channel. The result is supported by a new converse and a new scheme. In the proposed scheme, the helper sends a cooperative jamming signal at a specific power level and direction. In this way, it minimizes the penalty in GDoF incurred by the secrecy constraint. In the secure rate analysis, the techniques of noise removal and signal separation are used.

In many communication channels, secrecy constraintsusuallyincur a penalty in capacity, as well as generalized degrees-of-freedom (GDoF). In this paper, we show an interesting observation that adding a helper cantotallyremove the penalty in sum GDoF for a two-user symmetric Gaussian interference channel. For the interference channel where each transmitter sends a message to an intended receiver without secrecy constraints, the sum GDoF is a well-known “W” curve, characterized by Etkin–Tse–Wang in 2008. If the secrecy constraints are imposed on this interference channel, where the message of each transmitter must be secure from the unintended receiver (eavesdropper), then a GDoF penalty is incurred and the secure sum GDoF is reduced to a modified “W” curve, derived by Chen recently. In this paper, we show that, by adding a helper into this interference channel with secrecy constraints, thesecuresum GDoF turns out to be a “W” curve, which is the same as the sum GDoF of the setting without secrecy constraints. The proposed scheme is based on the cooperative jamming and a careful signal design such that the jamming signal of the helper is aligned at a specific direction and power level with the information signals of the transmitters, which allows us to totally remove the penalty in GDoF due to the secrecy constraints. Furthermore, the estimation approaches of noise removal and signal separation due to the rational independence are used in the secure rate analysis.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.

We consider communication over a multiple-input single-output block fading channel in the presence of an independent noiseless feedback link. We assume that the transmitter and receiver have no prior knowledge of the channel state realizations, but the transmitter and receiver can acquire the channel state information (CSIT/CSIR) via downlink training and feedback. For this channel, we show that increasing the number of transmit antennas to infinity will not achieve an infinite capacity, for a finite channel coherence length and a finite input constraint on the second or fourth moment. This insight follows from our new capacity bounds that hold for any linear and nonlinear coding strategies, and any channel training schemes. In addition to the channel capacity bounds, we also provide a characterization on the beamforming gain that is also known as array gain or power gain, at the regime with a large number of antennas.

We consider communication over a multiple-input single-output (MISO) block fading channel in the presence of an independent noiseless feedback link. We assume that the transmitter and receiver have no prior knowledge of the channel state realizations, but the transmitter and receiver can acquire the channel state information (CSIT/CSIR) via downlink training and feedback. For this channel, we show that increasing the number of transmit antennas to infinity will not achieve an infinite capacity, for a finite channel coherence and a finite input constraint on the second or fourth moment. This insight follows from our new capacity bounds that hold for any linear and nonlinear coding strategies, and any channel training schemes. In addition to the channel capacity bounds, we also provide a characterization on the beamforming gain that is also known as array gain or power gain, at the regime with large number of antennas.

We consider communication over heterogeneous parallel channels, where a transmitter is connected to two users via two parallel channels: a multiple-input multiple-output (MIMO) broadcast channel (BC) and a noiseless rate-limited multicast channel. We characterize the optimal degrees of freedom (DoF) region of this setting when the transmitter has delayed channel state information (CSIT) regarding the MIMO BC. Our results show that jointly coding over the two channels strictly outperforms simple channel aggregation and can even achieve the instantaneous CSIT performance with completely outdated CSIT on the MIMO BC in the sum DoF sense; this happens when the multicast rate of the second channel is larger than a certain threshold. The main idea is to send information over the MIMO BC at a rate above its capacity and then use the second channel to send additional side information to allow for reliable decoding at both receivers. We call this scheme a two-phase overload-multicast strategy. We show that such a strategy is also sum DoF optimal for the K-user MIMO BC with a parallel multicast channel when the rate of the multicast channel is high enough and can again achieve the instantaneous CSIT performance (optimal sum DoF) with completely outdated CSIT. For the regime where the capacity of the multicast channel is small, we propose another joint coding strategy, which is sum DoF optimal.

We investigate the degrees of freedom (DoF) for the two-user multiple-input multiple-output interference channel (MIMO IC) with parallel multicasting channels. Specifically, in addition to the MIMO IC, each transmitter is also connected to both receivers via an out-of-band multicast channel. Our main contribution lies in the characterization of the optimal sum DoF when the channel state information (CSI) on the MIMO IC is available to the transmitters with some delay (delayed CSIT). We show that jointly coding over the parallel multicast channels can achieve higher DoF than channel aggregation does. Furthermore, as long as the rate of the multicast channels is above a certain threshold, delayed CSIT is enough to achieve the same DoF performance as with instantaneous CSIT.

In this paper, we investigate the capacity of a known interference channel, where a transmitter sends information to a receiver in the presence of a block-fading interference link, and the receiver knows the interference data but not the channel gain of the interference link. An upper bound and a lower bound for the capacity of this known interference channel are derived. Specifically, the capacity lower bound is achieved by a blind known interference cancellation (BKIC) scheme, which can remove the interference without the knowledge of the interference channel gain. We further show that the achievable lower bound of BKIC can approach the upper bound in high SNR regime. Our results show that the lack of the knowledge of the channel gain of the interfering link causes only a small fractional loss of degrees of freedom (capacity prelog).

In many wireless networks, link strengths are affected by many topological factors, such as different distances, shadowing, and intercell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects is still a novel approach, that has been recently fueled by strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. This paper here takes a step in exploring this interplay between topology, feedback, and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong versus weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter [alternating channel state information at the transmitter (CSIT)] where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort-of channel learning and feeding back CSIT-for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users.

In many wireless networks, link strengths are affected by many topological factors such as different distances, shadowing and inter-cell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects has remained largely unexplored, despite strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. The work here takes a step in exploring this interplay between topology, feedback and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong vs. weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter (alternating CSIT) where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management (TSM) schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort - of channel learning and feeding back CSIT - for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users.

We consider communication over heterogeneous parallel channels, where a transmitter is connected to two users via two parallel channels: (1) a MISO broadcast channel (BC), and (2) a noiseless rate-limited multicast channel. We characterize the optimal degrees of freedom (DoF) region of this setting when the transmitter has delayed channel state information (CSIT) regarding the MISO BC. Our results show that jointly coding over the two channels can strictly outperform simple channel aggregation (or channel separation) and can even achieve the same performance as with instantaneous CSIT when the CSIT on the MISO BC is completely stale; this occurs when the multicast rate of the second channel is larger than a certain threshold, in the DoF sense. The main idea to achieve full DoF with completely stale CSIT is to send information over the MISO BC at a rate above its capacity and use the second channel to send additional side information to allow for reliable decoding at both receivers.

The work considers the two-user MISO broadcast channel with a gradual and delayed accumulation of channel state information at the transmitter (CSIT), and addresses the question of how much feedback is necessary, and when, in order to achieve a certain degrees-of-freedom (DoF) performance. Motivated by limited-capacity feedback links with delays, that may not immediately convey perfect CSIT, and focusing on the block fading scenario, we consider a gradual accumulation of feedback bits that results in a progressively increasing CSIT quality as time progresses across the coherence period (T channel uses - current CSIT), or at any time after (delayed CSIT). Specifically, for any set {αt}Tt=1of feedback quality exponents describing the high-SNR rates-of-decay of the mean square error of the current CSIT estimates at time t ≤ T (01≤ · · · ≤ (αT≤ 1), given an average α = ΣTt=1αt/T, and given perfect delayed CSIT (received at any time t > T), the work here derives the optimal DoF region to be the polygon with corner points {(0,0),(0,1),(α,1),(2+α/3, 2+α/3),(1,α),(1,0)}. Aiming to now reduce the overall number of feedback bits, we also prove that the above optimal region holds even with imperfect delayed CSIT for any (delayed-CSIT) quality exponent β ≥ 1+2α/3. The results are supported by novel multi-phase precoding schemes that utilize gradually improving CSIT. The approach here incorporates different settings such as the delayed CSIT setting of Maddah-Ali and Tse (β = 1, αt= 0, ∀t ≤ T), the imperfect current CSIT setting of Yang et al. and of Gou and Jafar (β = 1, α1= · · · = αT> 0), and the not-so-delayed CSIT setting of Lee and Heath (β = 1, α1= · · · = αT= 0 for some τ<;T).

This work considers the multiuser multiple-input single-output (MISO) broadcast channel (BC), where a transmitter with M antennas transmits information to K single-antenna users, and where - as expected - the quality and timeliness of channel state information at the transmitter (CSIT) is imperfect. Motivated by the fundamental question of how much feedback is necessary to achieve a certain performance, this work seeks to establish bounds on the tradeoff between degrees-of-freedom (DoF) performance and CSIT feedback quality. Specifically, this work provides a novel DoF region outer bound for the general K-user M ×1 MISO BC with partial current CSIT, which naturally bridges the gap between the case of having no current CSIT (only delayed CSIT, or no CSIT) and the case with full CSIT. The work then characterizes the minimum CSIT feedback that is necessary for any point of the sum DoF, which is optimal for the case with M ≥ K, and the case with M = 2, K = 3.

For the two-user MISO broadcast channel with imperfect and delayed channel state information at the transmitter (CSIT), the work explores the tradeoff between performance on the one hand, and CSIT timeliness and accuracy on the other hand. This paper considers a broad setting where communication takes place in the presence of a random fading process, and in the presence of a feedback process that, at any point in time, may provide CSIT estimates-of some arbitrary accuracy - for any past, current or future channel realization. This feedback quality may fluctuate in time across all ranges of CSIT accuracy and timeliness, ranging from perfectly accurate and instantaneously available estimates, to delayed estimates of minimal accuracy. Under standard assumptions, the work derives the degrees-of-freedom (DoF) region, which is tight for a large range of CSIT quality. This derived DoF region concisely captures the effect of channel correlations, the accuracy of predicted, current, and delayed-CSIT, and generally captures the effect of the quality of CSIT offered at any time, about any channel. This paper also introduces novel schemes which-in the context of imperfect and delayed CSIT-employ encoding and decoding with a phase-Markov structure. The results hold for a large class of block and nonblock fading channel models, and they unify and extend many prior attempts to capture the effect of imperfect and delayed feedback. This generality also allows for consideration of novel pertinent settings, such as the new periodically evolving feedback setting, where a gradual accumulation of feedback bits progressively improves CSIT as time progresses across a finite coherence period.

Maddah-Ali and Tse have recently shown that delayed transmitter channel state information (CSIT) can still be useful in increasing the degrees-of-freedom (DoF) over the MIMO broadcast channel. This was achieved by constructing a scheme that, in the presence of two transmit antennas, of two single-antenna receivers, and of CSIT that is delayed by one coherence time, manages to provide each user with 2/3 DoF, improving upon the 1/2 DoF corresponding to no CSIT. This same scheme though, as well as all subsequent schemes pertinent schemes, achieve DoF gains by suppressing the inherent diversity of the broadcast parallel channel. The current work proposes a novel broadcast scheme which, over the above described setting of the delayed CSIT broadcast channel, employs a form of interference alignment to achieve both full DoF as well as full diversity.

In the context of multiuser relay-aided multi-way communications, we identify and meet the optimal degrees of freedom (DOF) for different multiuser uplink-downlink settings of practical importance. Under the imposed constraint of using simple linear techniques, the proposed solutions draw from interference-neutralization (IN) methods which linearly manipulate signals in time and space, and manage to reduce the effect of multiuser interference and of the half-duplex constraint. Focus is placed on asymmetric settings where the connectivity, size and rate of the uplink and downlink groups may vary.