We study the problem of differentially private (DP) secure multiplication in distributed computing systems, focusing on regimes where perfect privacy and perfect accuracy cannot be simultaneously achieved. Specifically, N nodes collaboratively compute the product of M private inputs while guaranteeing epsilon-DP against any collusion of up to T nodes. Prior work has characterized the fundamental privacy-accuracy trade-off for the multiplication of two multiplicands. In this paper, we extend these results to the more general setting of computing the product of an arbitrary number M of multiplicands. We propose a secure multiplication framework based on carefully designed encoding polynomials combined with layered noise injection. The proposed construction generalizes existing schemes and enables the systematic cancellation of lower-order noise terms, leading to improved estimation accuracy. We explore two regimes: (M-1)T+1 <= N <= MT and N = T+1. For (M-1)T+1 <= N <= MT, we characterize the optimal privacy--accuracy trade-off. When N = T+1, we derive nontrivial achievability and converse bounds that are asymptotically tight in the high-privacy regime.

We consider the problem of finding latency optimal storage codes in a geographically distributed storage network of$n$nodes and$k \leq n$files, where inter-node communication involves certain round-trip times. The optimality is with respect to two metrics: the worst-case latency among files at each node, and the system-average latency across files and nodes. Storage can be uncoded where raw message files are stored on the nodes or coded where linear combinations of files are placed on some of the nodes. In our previous work, it was shown that a latency optimal uncoded scheme exists if and only if a certain extended graph associated with the storage network is$k$-colorable. In this paper, we explore the networks where this condition fails and thus require coded storage schemes for latency optimality. We first construct a family of worst-case latency optimal codes called MDS-chromatic codes that are built upon the vertex coloring of extended graph. Further, we derive necessary and sufficient conditions for binary-chromatic codes to exist, along with explicit construction of the codes. In specific networks that have unit-link ($k-1$) -nearest neighbor graph, we show that there exists a MDSchromatic code that is also system-average latency optimal.

We consider a private distributed multiplication problem involving$N$computation nodes and$T$colluding nodes. Shamir's secret sharing algorithm provides perfect informationtheoretic privacy, while requiring an honest majority, i.e.,$\mathrm{N} \geq 2 \mathrm{T}+1$. Recent work has investigated approximate computation and characterized privacy-accuracy trade-offs for the honest minority setting ($N \leq 2 \mathrm{T}$) for real-valued data, quantifying privacy leakage via the differential privacy (DP) framework and accuracy via the mean squared error. However, it does not incorporate the error correction capabilities of Shamir's secret-sharing algorithm. This paper develops a new polynomialbased coding scheme for secure multiplication with an honest minority, and characterizes its achievable privacy-utility tradeoff, showing that the tradeoff can approach the converse bound as closely as desired. Unlike previous schemes, the proposed scheme inherits the capability of the Reed-Solomon (RS) code to tolerate erasures and adversaries. We utilize a modified Berlekamp-Welch algorithm over the real number field to detect adversarial nodes.

In differentially private distributed mean estimation (DP-DME), a central server computes the mean of vectors distributed across$n$users while preserving differential privacy (DP). DP-DME has been studied under various DP models, with distributed DP with secure aggregation and local DP (LDP) being the main models that do not rely on a trusted third party. Distributed DP-based schemes leverage correlated noise among users to achieve higher accuracy than LDP-based schemes, where users operate independently. However, the accuracy of distributed DP comes at the cost of higher communication overhead for generating correlated noise and complex multiround protocols to handle dropouts. In this work, we analyze the communication-accuracy trade-off in distributed DP-DME under arbitrary communication constraints, and propose a method to generate correlated noise strategically within these constraints to enable single-round dropout handling. Our results show that the communication costs of existing distributed DP-DME approaches can be substantially reduced with minimal impact on accuracy.

We consider the problem of data storage in a geographically distributed (or geo-distributed) network of servers (or nodes) where inter-node communication incurs certain round-trip delays. Every node serves a set of users who can request any file in the network. If the requested file is not available at the node, it communicates with other nodes to obtain the file, thus causing the user to experience latency in obtaining the file. The files can be placed uncoded, where each node stores exact copies of the files, or in coded fashion, where certain linear combination of files are placed at each node. We aim to obtain an optimal file placement on the nodes with respect to minimizing the worst-case latency at each node, as well as the system-average latency. The prior literature considered the case of equiprobable file demands at the nodes. In this paper, we investigate the generic case of non-uniform file-demand probabilities at each node. The scheme presented here is optimal within the family of uncoded schemes. It is obtained first by modeling the worst-case latency constraint as a vertex coloring problem, and then converting the system-average latency optimization to a problem of balanced-assignment.

Coding theory revolves around the incorporation of redundancy into transmitted symbols, computation tasks, and stored data to guard against adversarial manipulation. However, error correction in coding theory is contingent upon a strict trust assumption. In the context of computation and storage, it is required that honest nodes outnumber adversarial ones by a certain margin. However, in several emerging real-world cases, particularly, in decentralized blockchain-oriented applications, such assumptions are often unrealistic. Consequently, despite the important role of coding in addressing significant challenges within decentralized systems, its applications become constrained. Still, in decentralized platforms, a distinctive characteristic emerges, offering new avenues for secure coding beyond the constraints of conventional methods. In these scenarios, the adversary benefits when the legitimate decoder recovers the data, and preferably with a high estimation error. This incentive motivates them to act rationally, trying to maximize their gains. In this paper, we propose a game theoretic formulation for coding, called the game of coding, that captures this unique dynamic where each of the adversaries and the data collector (decoder) have respective utility functions to optimize. The utility functions reflect the fact that both the data collector and the adversary are interested in increasing the chance of data being recoverable by the data collector. Moreover, the utility functions express the interest of the data collector to estimate the input with lower estimation error, but the opposite interest of the adversary. As a first, still highly non-trivial step, we characterize the equilibrium of the game for the repetition code with a repetition factor of 2 for a wide class of utility functions with minimal assumptions.

We consider the problem of geographically distributed data storage in a network of servers (or nodes) where the nodes are connected to each other via communication links having certain round-trip times (RTTs). Each node serves a specific set of clients, where a client can request for any of the files available in the distributed system. The parent node provides the requested file if available locally; else it contacts other nodes that have the data needed to retrieve the requested file. This inter-node communication incurs a delay resulting in a certain latency in servicing the data request. The worst-case latency incurred at a servicing node and the system average latency are important performance metrics of a storage system, which depend not only on inter-node RTTs, but also on how the data is stored across the nodes. Data files could be placed in the nodes as they are, i.e., in uncoded fashion, or can be coded and placed. This paper provides the necessary and sufficient conditions for the existence of uncoded storage schemes that are optimal in terms of both per-node worst-case latency and system average latency. In addition, the paper provides efficient binary storage codes for a specific case where optimal uncoded schemes do not exist.

Coding theory revolves around the incorporation of redundancy into transmitted symbols, computation tasks, and stored data to guard against adversarial manipulation. However, error correction in coding theory is contingent upon a strict trust assumption. In the context of computation and storage, it is required that honest nodes outnumber adversarial ones by a certain margin. However, in several emerging real-world cases, particularly, in decentralized blockchain-oriented applications, such assumptions are often unrealistic. Consequently, despite the important role of coding in addressing significant challenges within decentralized systems, its applications become constrained. Still, in decentralized platforms, a distinctive characteristic emerges, offering new avenues for secure coding beyond the constraints of conventional methods. In these scenarios, the adversary benefits when the legitimate decoder recovers the data, and preferably with a high estimation error. This incentive motivates them to act rationally, trying to maximize their gains. In this paper, we propose a game theoretic formulation for coding, called the game of coding, that captures this unique dynamic where each of the adversary and the data collector (decoder) have a utility function to optimize. The utility functions reflect the fact that both the data collector and the adversary are interested in increasing the chance of data being recoverable by the data collector. Moreover, the utility functions express the interest of the data collector to estimate the input with lower estimation error, but the opposite interest of the adversary. As a first, still highly non-trivial step, we characterize the equilibrium of the game for the repetition code with a repetition factor of 2, for a wide class of utility functions with minimal assumptions.

We consider the problem of private distributed multiparty computation. It is well-established that coding strategies can enable perfect information-theoretic privacy in distributed computation (e.g., the BGW protocol). However, perfect privacy comes at a high computational overhead cost, requiring 2t + 1 compute nodes to ensure privacy against any t colluding nodes. By allowing for approximate computation and operations over the real numbers, we demonstrate that noise can be added to data shared with computing nodes in order to ensure differential privacy instead of perfect privacy. Specifically, the signal-to-noise ratio of the data received by colluding nodes can be mapped to differential privacy guarantees. We precisely characterize the trade-off between differential privacy and accuracy in this setting, and prove that a degree of differential privacy against t colluding nodes can always be ensured whenever there are more than t+1 computing node—a reduction of t nodes compared to perfect privacy. A particularly novel technical aspect is an achievable scheme that carefully encodes the data and noise at different magnitude levels. This coding scheme ensures that the adversary’s input appears to be layers of noise, whereas the legitimate decoder is able to uncover the desired computation by "peeling" off the noise layers.

Current causally consistent data storage algorithms use partial or full replication to ensure data access to clients over a distributed setting. We develop, for the first time, an erasure coding based algorithm called CausalEC that ensures causal consistency for a collection of read-write objects stored in a distributed set of nodes over an asynchronous message passing system. CausalEC can use an arbitrary linear erasure code for data storage, and ensures liveness, fault-tolerance and storage properties prescribed by the erasure code. Unlike previous consistent erasure coding based algorithms, CausalEC is compatible with cross-object erasure coding, where nodes encode values across multiple objects. Every write operation in CausalEC is "local", that is, a server performs only local actions before returning to a client that issued a write operation. A read operation to an object can be returned by a server on contacting a small subset of other servers so long as the underlying erasure code allows for the object to be decoded from that subset.

The classic BGW algorithm of Ben Or, Goldwasser and Wigderson for secure multiparty computing demonstrates that secure distributed matrix multiplication over finite fields is possible over 2t+1 computation nodes, while keeping the input matrices private from every t colluding computation nodes. In this paper, we develop and study a novel coding formulation to explore the trade-offs between computation accuracy and privacy in secure multiparty computing for real-valued data, even with fewer than 2t+1 nodes, through a differential privacy perspective. For the case of t = 1, we develop achievable schemes and converse arguments that bound ϵ — the differential privacy parameter that measures the privacy loss — for a given accuracy level. Our achievable coding schemes are specializations of Shamir secret sharing applied to real-valued data, coupled with appropriate choice of evaluation points. We develop converse arguments that apply for general additive noise based schemes.

We design and implement LEGOStore, an erasure coding (EC) based linearizable data store over geo-distributed public cloud data centers (DCs). For such a data store, the confluence of the following factors opens up opportunities for EC to be latency-competitive with replication: (a) the necessity of communicating with remote DCs to tolerate entire DC failures and implement linearizability; and (b) the emergence of DCs near most large population centers. LEGOStore employs an optimization framework that, for a given object, carefully chooses among replication and EC, as well as among various DC placements to minimize overall costs. To handle workload dynamism, LEGOStore employs a novel agile reconfiguration protocol. Our evaluation using a LEGOStore prototype spanning 9 Google Cloud Platform DCs demonstrates the efficacy of our ideas. We observe cost savings ranging from moderate (5-20%) to significant (60%) over baselines representing the state of the art while meeting tail latency SLOs. Our reconfiguration protocol is able to transition key placements in 3 to 4 inter-DC RTTs (< 1s in our experiments), allowing for agile adaptation to dynamic conditions.

Emulating a shared atomic , read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [ 11 ]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fixed set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code -based atomic algorithm, called Ares , which allows the set of hosts to be modified in the course of an execution. Ares is composed of three main components: (i) a reconfiguration protocol , (ii) a read/write protocol , and (iii) a set of data access primitives (DAPs) . The design of Ares is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the Ares algorithm.

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of$P$computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with ∊ relative error from any$m$of the$P$nodes for any ∊ >0. We obtain this result through a careful specialization of MatDot codes-a class of matrix multiplication code previously developed in the context of exact recovery (∊ = 0). Since previous results showed that the MatDot code is tight for a class of linear coding schemes for exact recovery, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. Moreover, we develop an optimization framework based on alternating minimization that enables the discovery of new codes for approximate matrix multiplication.

In this work, we propose an erasure coding-based protocol that implements a key-value store with atomicity and near-optimal storage cost. Our protocol supports concurrent read and write operations while tolerating asynchronous communication and crash failures of any client and some fraction of servers. One novel feature is a tunable knob between the number of supported concurrent operations, availability, and storage cost. We implement our protocol into Cassandra, namely Cassan-drEAS (Cassandra + Erasure-coding Atomic Storage). Extensive evaluation using YCSB on Google Cloud Platform shows that CassandrEAS incurs moderate penalty on latency and throughput, yet saves significant amount of storage space.

Computing systems are evolving rapidly. At the device level, emerging devices are beginning to compete with traditional CMOS systems. At the architecture level, novel architectures are successfully avoiding the communication bottleneck that is a central feature, and a central limitation, of the von Neumann architecture. Furthermore, such systems are increasingly plagued by unreliability. This unreliability arises at device or gate-level in emerging devices, and can percolate up to processor or system-level if left unchecked. The goal of this article is to survey recent advances in reliable computing using unreliable elements, with an eye on nonsilicon and non-von Neumann architectures. We first observe that instead of aiming for generic computing problems, the community could use “dwarfs of modern computing,” first noted in the high-performance computing (HPC) community, as a starting point. These computing problems are the basic building blocks of almost all scientific computing, machine learning, and data analytics today. Next, we survey the state of the art in “coded computing,” which is an emerging area that advances on classical algorithm-based fault-tolerance (ABFT) and brings a fundamental information-theoretic perspective. By weaving error-correcting codes into a computing algorithm, coded computing provides dramatic improvements on solutions, as well as obtains novel fundamental limits, for problems that have been open for more than 30 years. We introduce existing and novel coded computing techniques in the context of “coded dwarfs,” where a specific dwarf's computation is made resilient by applying coding. We discuss how, for the same redundancy, “coded dwarfs” are significantly more resilient compared to classical techniques such as replication. Furthermore, by examining a widely popular computation task-training large neural networks-we demonstrate how coded dwarfs can be applied to address this fundamentally nonlinear problem. Finally, we discuss practical challenges and future directions in implementing coded computing techniques on emerging and existing nonsilicon and/or non-von Neumann architectures.

The multi-version coding problem is a recently formulated information-theoretic framework to study the storage cost of consistent key-value data stores. Previous work on multi-version coding considered a completely decentralized asynchronous system where the nodes (servers) are not aware of which updates (versions) of the data are received by the other nodes. In this paper, we relax this assumption and study a system where a node acquires side information of the versions propagated to some other nodes based on the network topology. Specifically, we study a storage system with n nodes over a graph that stores ν totally ordered versions of an object (message). Each node receives a subset of these ν versions. A node is aware of which versions that were received by its neighbors in the network graph. Our code constructions show that the side information can result in a better storage cost as compared with the case where the nodes do not exchange side information for some regimes at the expense of the additional latency and the negligible communication overhead of exchanging the side information. Through an information-theoretic converse, we identify surprising scenarios where exchanging tremendous amount of side information does not reduce the storage cost. Finally, we present a case study over Amazon web services (AWS) that demonstrates the potential storage cost reductions of our code constructions.

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent “Polynomial code” constructions in recovery threshold, i.e., the required number of successful workers. When a fixed 1/m fraction of each matrix can be stored at each worker node, Polynomial codes require m2 successful workers, while our MatDot codes only require 2m - 1 successful workers. However, MatDot codes have higher computation cost per worker and higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Furthermore, we propose “PolyDot” coding that interpolates between Polynomial codes and MatDot codes to trade off computation/communication costs and recovery thresholds. Finally, we demonstrate a novel coding technique for multiplying n matrices (n ≥ 3) using ideas from MatDot and PolyDot codes.

Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms to train large neural networks. In recent years, there has been a great deal of research to alleviate communication cost by compressing the gradient vector or using local updates and periodic model averaging. In this paper, we advocate the use of redundancy towards communication-efficient distributed stochastic algorithms for non-convex optimization. In particular, we, both theoretically and practically, show that by properly infusing redundancy to the training data with model averaging, it is possible to significantly reduce the number of communication rounds. To be more precise, we show that redundancy reduces residual error in local averaging, thereby reaching the same level of accuracy with fewer rounds of communication as compared with previous algorithms. Empirical studies on CIFAR10, CIFAR100 and ImageNet datasets in a distributed environment complement our theoretical results; they show that our algorithms have additional beneficial aspects including tolerance to failures, as well as greater gradient diversity.

We study the numerical stability of polynomial based encoding methods, which has emerged to be a powerful class of techniques for providing straggler and fault tolerance in the area of coded computing. Our contributions are as follows: 1)We construct new codes for matrix multiplication that achieve the same fault/straggler tolerance as the previously constructed MatDot Codes and Polynomial Codes.2)We show that the condition number of every m ×m sub-matrix of an m ×n, n ≥ m Chebyshev-Vandermonde matrix, evaluated on the n-point Chebyshev grid, grows as O(n2(n-m)) for n > m.3)By specializing our orthogonal polynomial based constructions to Chebyshev polynomials, and using our condition number bound for Chebyshev-Vandermonde matrices, we construct new numerically stable techniques for coded matrix multiplication. We empirically demonstrate that our constructions have significantly lower numerical errors compared to previous approaches which involve inversion of Vandermonde matrices. We generalize our constructions to explore the trade-off between computation/communication and fault-tolerance.4)We propose a numerically stable specialization of Lagrange coded computing. Our approach involves the choice of evaluation points and a suitable decoding procedure. Our approach is demonstrated empirically to have lower numerical errors as compared to standard methods.

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. In this paper, we strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Kojasiewicz condition, $O((pT)^{1/3})$ rounds of communication suffice to achieve a linear speed up, that is, an error of $O(1/pT)$, where $T$ is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPUs cluster.

Motivated by applications of distributed storage systems to key-value stores, the multi-version coding problem has been formulated to efficiently store frequently updated data in asynchronous decentralized storage systems. Inspired by consistency requirements in distributed systems, the main goal in the multi-version coding problem is to ensure that the latest possible version of the data is decodable even if the data updates have not reached all the servers in the system. In this paper, we study the storage cost of ensuring consistency for the case where the data versions are correlated, in contrast to previous work where the data versions were treated as being independent. We provide multi-version code constructions that show that the storage cost can be significantly smaller than the previous constructions depending on the degree of correlation, despite the asynchrony and the decentralized nature. Our achievability results are based on Reed-Solomon codes and random binning. Through an information-theoretic converse, we show that our multi-version codes are asymptotically nearly optimal, within a factor of 2, in certain interesting regimes.

We consider the problem of computing a matrix-vector product Ax using a set of P parallel or distributed processing nodes prone to “straggling,” i.e., unpredictable delays. Every processing node can access only a fraction (s/N) of the N-length vector x, and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call “Short-Dot”-that introduces redundant, shorter dot products such that only a subset of the nodes' outputs are sufficient to compute Ax. To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix A, but the length of the dot products computed at each processing node is still N. The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of x to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of x to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.

In applications of storage systems to modern key-value stores, the stored data is highly dynamic due to frequent updates from the system write clients. The multi-version coding problem has been formulated to study the cost of storing dynamic data in asynchronous distributed storage systems. In this problem, previous work considered a completely decentralized system where a server is not aware of which versions of the data are received by the other servers. In this paper, we relax this assumption and study a system where a server may acquire side information of the versions propagated to some other servers. In particular, we study a storage system with n servers that store v totally ordered independent versions of a message. Each server receives a subset of theseνversions that defines the state of that server. Assuming that the servers are distributed in a ring, a server is aware of which versions have been received by itsh-hop neighbors. If the server is aware of the states of (n- 2) other servers, we show that this side information can result in a better storage cost as compared with the case where there is no side information. Through an information-theoretic converse, we identify scenarios where, even if the server is aware of the states of (n-3) /2 other servers, the side information may not help in improving the worst-case storage cost beyond the case where servers have no side information.

Recent work has developed coding theoretic approaches to add redundancy to distributed matrix-vector multiplications with the goal of speeding up the computation by mitigating the straggler effect in distributed computing. In this paper, we consider the case where the matrix comes from a small (e.g., binary) alphabet, where a variant of a popular method called the “Four-Russians method” is known to have significantly lower computational complexity as compared with the usual matrix-vector multiplication algorithm. We develop novel code constructions that are applicable to binary matrix-vector multiplication via a variant of the Four-Russians method called the Mailman algorithm. Specifically, in our constructions, the encoded matrices have a low alphabet that ensures lower computational complexity, as well as good straggler tolerance. We also present a trade-off between the communication and computation cost of distributed coded matrix-vector multiplication for general, possibly non-binary, matrices.

In applications of distributed storage systems to distributed computing and implementation of key-value stores, the following property, usually referred to as consistency in distributed computing, is an important requirement: as the data stored changes, the latest version of the data must be accessible to a client that connects to the storage system. Motivated by technological trends where key-value stores are increasingly implemented in high-speed memory, an information theoretic formulation called multi-version coding is introduced in this paper in order to understand and minimize the memory overhead of consistent distributed storage. Multi-version coding is characterized by ν totally ordered versions of a message and a storage system with n servers. At each server, values corresponding to an arbitrary subset of the ν versions are received and encoded. For any subset of c servers in the storage system, the value corresponding to the latest common version or a later version, as per the total ordering, among the c servers is required to be decodable. An achievable multi-version code construction via linear coding and a converse result that shows that the construction is asymptotically tight when ν|(c - 1) are provided. An implication of the converse is that there is an inevitable price, in terms of storage cost, to ensure consistency in distributed storage systems.

We consider the problem of computing the convolution of two long vectors using parallel processors in the presence of “stragglers”. Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides improved resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target “deadline” time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e., the behavior of the “tail”. Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems.

We consider a two-unicast-Z network over a directed acyclic graph of unit capacitated edges; the two-unicast-Z network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-Z networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and nonlinear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous result of Wang et. al. regarding feasibility of rate (1,1) in the network.

The problem of one-way file synchronization, henceforth called “file updates”, is studied in this paper. Specifically, a client edits a file, where the edits are modeled by insertions and deletions (InDels). An old copy of the file is stored remotely at a data-centre, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the data-centre to update its old copy to the newly edited file. Two models for the source files and edit patterns are studied: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime, in which the number of insertions and deletions is a small (but constant) fraction of the length of the original file. For both models, information-theoretic lower bounds on the best possible compression rates that enable file updates are derived (up to first order terms). Conversely, a simple compression algorithm using dynamic programming (DP) and entropy coding (EC), henceforth called DP-EC algorithm, achieves rates that are within constant additive gap (which diminishes as the alphabet size increases) to information-theoretic lower bounds for both models. For the RPES-LtRRID model, a dynamic-programming-run-length-compression (DP-RLC) algorithm is proposed, which achieves a compression rate matching the information-theoretic lower bound up to first order terms. Therefore, when the insertion and deletion probabilities are small (such that first order terms dominate), the achievable rate by DP-RLC is nearly optimal for the RPES-LtRRID model.

Motivated by applications of distributed storage systems to key-value stores, recently, the multi-version coding problem was proposed to store data that is frequently being updated in a distributed storage system. In particular, in multi-version coding, it is desired to store the data consistently, that is, even if all servers do not receive the data updates simultaneously, the decoder can recover the latest possible version of the data. In this paper, we consider the case where there are correlations among various versions of the data. By respectively leveraging update-efficient codes and Slepian-Wolf, we provide two simple multi-version code constructions to show that the storage cost of multi-version codes can be significantly smaller than previous constructions depending on the degree of correlation between the versions. Moreover, we show that our Slepian-Wolf based construction is essentially optimal in a certain correlation regime.

Faced with saturation of Moore's law and increasing size and dimension of data, system designers have increasingly resorted to parallel and distributed computing to reduce computation time of machine-learning algorithms. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to complete their processing. To combat the effect of stragglers, recent literature proposes introducing redundancy in computations across processors, e.g., using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique - that we call "Short-Dot" - to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed more efficiently at individual processors. Further, only a subset of these short dot products are required at the fusion node to finish the computation successfully. We demonstrate through probabilistic analysis as well as experiments on computing clusters that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors required to finish), for any such strategy and compare it to that achieved by our strategy.

The focus of this paper is to understand storage costs of emulating an atomic shared memory over an asynchronous, distributed message passing system. Previous literature has developed several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this paper, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory emulation algorithms. Our storage cost lower bounds are universally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data.

The compute-and-forward framework permits each receiver in a Gaussian network to directly decode a linear combination of the transmitted messages. The resulting linear combinations can then be employed as an end-to-end communication strategy for relaying, interference alignment, and other applications. Recent efforts have demonstrated the advantages of employing unequal powers at the transmitters and decoding more than one linear combination at each receiver. However, neither of these techniques fit naturally within the original formulation of compute-and-forward. This paper proposes an expanded compute-and-forward framework that incorporates both of these possibilities and permits an intuitive interpretation in terms of signal levels. Within this framework, recent achievability and optimality results are unified and generalized.

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast-$Z$ network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs.

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.

We investigate an information theoretic problem motivated by storing multiple versions of a data object in distributed storage systems. Specifically, in a storage system with n server nodes, where there are ν independent message versions, each server receives message values corresponding to some arbitrary subset of the versions. The versions are assumed to be totally ordered. Each server is unaware of the set of versions at the other servers, and aims to encode the values corresponding to the versions it has. We investigate codes where, from any set of c nodes (c < n), the value corresponding to the highest common version, as per the version ordering, available at this set of c nodes is decodable. We aim to design codes that minimize the storage cost. We present two main results in this paper. First, we show that the storage cost is lower bounded by 1− (1− 1 c ) , measured in terms of the bits of the values. Second, for the cases of ν = 2 and ν = 3, we provide new code constructions that respectively achieve storage costs of 2c−1 c and 3c−2 c , measured in terms of the bits of the values. Our code constructions are simple in that we do not code across versions. We argue that when the number of versions ν is much larger than c, then replication is close to optimal.

We derive a new linear network coding algorithm for two-unicast-Z networks over directed acyclic graphs, that is, for two-unicast networks where one destination has apriori information of the interfering source message. Our algorithm discovers linear network codes for two-unicast-Z networks by combining ideas of random linear network coding and interference neutralization. We show that our algorithm outputs an optimal network code for networks where there is only one edge emanating from each of the two sources. The complexity of our algorithm is polynomial in the number of edges of the graph.

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer 'd' and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than d, the CASGC algorithm with parameter d satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate 1/(L + 1) per message when each destination desires at least L messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding.

We study the three-user interference channel where each transmitter has local feedback of the signal from its targeted receiver. We show that in the important case where the channel coefficients are static, exact alignment can be achieved over two time slots using linear schemes. This is in contrast with the interference channel where no feedback is utilized, where it seems that either an infinite number of channel extensions or infinite precision is required for exact alignment. We also demonstrate, via simulations, that our scheme outperforms time-sharing even at finite SNR.

In this paper, we propose a novel framework, integer-forcing interference alignment, that can simultaneously exploit both signal-space and signal-scale alignment. We consider receivers that can decode integer-linear combinations of desired and interfering streams and then solve for their desired symbols. This is possible by using appropriate lattice codes at the transmitters and can be applied to the class of wireless communication systems that use linear beamforming. At the core of our architecture lies the compute-and-forward framework, which we extend here to encompass asymmetric power allocations. We evaluate the performance of our scheme in the context of the three-user interference channel through simulation results.

We study two-unicast-Z networks1- two-source two-destination (two-unicast) wireline networks over directed acyclic graphs, where one of the two destinations (say the second destination) is apriori aware of the interfering (first) source's message. For certain classes of two-unicast-Z networks, we show that the rate-tuple (N, 1) is achievable as long as the individual source-destination cuts for the two source-destination pairs are respectively at least as large as N and 1, and the generalized network sharing cut - a bound previously defined by Kamath et. al. - is at least as large as N +1. We show this through a novel achievable scheme which is based on random linear coding at all the edges in the network, except at the GNS-cut set edges, where the linear coding co-efficients are chosen in a structured manner to cancel interference at the receiver first destination.

The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set ofdsurvivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e.,k≤d≤n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set ofr≤n-kfailed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.

The index coding problem is a multiple unicast wireline communication network where the network is represented by a directed graph having exactly one link with finite capacity (also known as the bottleneck link). There are K independent sources which share the ingress of this bottleneck link. Correspondingly there are K destinations which are on the receiving end of the bottleneck link, with each destination intending to decode the message of one (unique) corresponding source. Each destination can have apriori side-information of a (different) subset of the original source messages. In this paper, we study the capacity of such a network from the perspective of interference alignment, and derive information theoretically optimal schemes for a class of networks. In our first main result, we identify the set of graphs where each user can achieve half rate in the index coding problem. In a second result, we derive the capacity for a class of symmetric index coding networks.

We explore the capacity and generalized degrees of freedom (GDOF) of the two-user Gaussian X channel, i.e., a generalization of the two-user interference channel where there is an independent message from each transmitter to each receiver. There are three main results in this paper. First, we characterize the sum capacity of the deterministic X channel under a symmetric setting. Second, we characterize the GDOF of the Gaussian X channel under a similar symmetric model. Third. we extend the sum capacity characterization previously obtained for the Gaussian interference channel in the noisy interference regime to the Gaussian X channel. Specifically, we show that the Gaussian X channel has the same sum capacity as the underlying Gaussian interference channel in this regime.

We consider exact repair of failed nodes in maximum distance separable (MDS) code based distributed storage systems. It is well known that an (n, k) MDS code can tolerate failure (erasure) of up to n - k storage disks, when the code is used to store k information elements over n distributed storage disks. The focus of this paper is optimal recovery, in terms of repair bandwidth - the amount of data to be downloaded to repair a failed node - for a single failed node. When a single node fails, it has been previously shown by Dimakis et. al. that the amount of repair bandwidth is at least equation units, when each storage disk stores ℒ units of data. The achievability of this lower bound of equation units, for arbitrary values of (n, k); has been shown previously using asymptotic code constructions based on asymptotic interference alignment. However, the existence of finite codes satisfying this lower bound has been shown only for specific regimes of (n, k) and their existence for arbitrary values of (n, k) remained open. In this paper, we provide the first known construction of a finite code for arbitrary (n, k), which can repair a single failed systematic node by downloading exactly equation units of data. The code that we construct is based on permutation matrices and hence termed the Permutation Code.

Recent results establish the optimality of interference alignment to approach the Shannon capacity of interference networks at high SNR. However, the extent to which interference can be aligned over a finite number of signalling dimensions remains unknown. Another important concern for interference alignment schemes is the requirement of global channel knowledge. In this work, we provide examples of iterative algorithms that utilize the reciprocity of wireless networks to achieve interference alignment with only local channel knowledge at each node. These algorithms also provide numerical insights into the feasibility of interference alignment that are not yet available in theory.

It is known that the capacity of parallel (e.g., multi-carrier) Gaussian point-to-point, multiple access and broadcast channels (without common messages) can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. Recent results have shown that parallel interference channels are not separable, i.e., joint coding is needed to achieve capacity in general. This work studies the separability, from a sum-capacity perspective, of single hop Gaussian interference networks with independent messages and arbitrary number of transmitters and receivers. The main result is that the only network that is always (for all values of channel coefficients) separable from a sum-capacity perspective is the MAC-Z-BC network, i.e., a network where a MAC component and a BC component are linked by a Z component. The sum capacity of this network is explicitly characterized.

It has been conjectured by Hø-Madsen and Nosratinia that complex Gaussian interference channels with constant channel coefficients have only one degree-of-freedom regardless of the number of users. While several examples are known of constant channels that achieve more than 1 degree-of-freedom, these special cases only span a subset of measure zero. In other words, for almost all channel coefficient values, it is not known if more than 1 degree-of-freedom is achievable. In this paper, we settle the Høst-Madsen-Nosratinia conjecture in the negative. We show that at least 1.2 degrees-of-freedom are achievable for all values of complex channel coefficients except for a subset of measure zero. For the class of linear beamforming and interference alignment schemes considered in this paper, it is also shown that 1.2 is the maximum number of degrees-of-freedom achievable on the complex Gaussian 3 user interference channel with constant channel coefficients, for almost all values of channel coefficients. To establish the achievability of 1.2 degrees-of-freedom we use the novel idea of asymmetric complex signaling - i.e., the inputs are chosen to be complex but not circularly symmetric. It is shown that unlike Gaussian point-to-point, multiple-access and broadcast channels where circularly symmetric complex Gaussian inputs are optimal, for interference channels optimal inputs are in general asymmetric. With asymmetric complex signaling, we also show that the 2 user complex Gaussian X channel with constant channel coefficients achieves the outer bound of 4/3 degrees-of-freedom, i.e., the assumption of time-variations/frequency-selectivity used in prior work to establish the same result, is not needed.

We characterize the capacity region of a class of the deterministic Z channels. We show that, interestingly, Han-Kobayashi type rate-splitting is not required in the optimal achievable scheme for the class of channels considered.

We study the sum capacity of the X channel generalization of the symmetric 2-user interference channel. In this X channel, there are 4 independent messages, one from each transmitter to each receiver. We characterize the sum capacity of a deterministic version of this channel, and obtain the generalized degrees of freedom characterization for the Gaussian version. The regime where the X channel outperforms the underlying interference channel is explicitly identified, and an interesting interference alignment scheme based on a cyclic decomposition of the signal space is shown to be optimal in this regime.

We find the degrees of freedom of a network with S source nodes,Rrelay nodes, and D destination nodes, with random time-varying/frequency-selective channel coefficients and global channel knowledge at all nodes. We allow full-duplex operation at all nodes, as well as causal noise-free feedback of all received signals to all source and relay nodes. An outer bound to the capacity region of this network is obtained. Combining the outer bound with previous interference alignment based achievability results, we conclude that the techniques of relays, feedback, full-duplex operation and noisy cooperation do not increase the degrees of freedom of interference andXnetworks. As a second contribution, we show that for a network withKfull-duplex nodes andK(K-1) independent messages with one message from every node to each of the otherK-1 nodes, the total degrees of freedom are bounded above and below by[(K(K-1))/( (2K-2))] and[(K(K-1))/( (2K-3))], respectively.

We explore the degrees of freedom of M times N user wireless X networks, i.e., networks of M transmitters and N receivers where every transmitter has an independent message for every receiver. We derive a general outer bound on the degrees of freedom region of these networks. When all nodes have a single antenna and all channel coefficients vary in time or frequency, we show that thetotalnumber of degrees of freedom of theXnetwork is equal to [(MN)/(M+N-1)] per orthogonal time and frequency dimension. Achievability is proved by constructing interference alignment schemes for X networks that can come arbitrarily close to the outer bound on degrees of freedom. For the case where either M=2 or N=2 we find that the degrees of freedom characterization also provides a capacity approximation that is accurate to within O(1) . For these cases the degrees of freedom outer bound is exactly achievable.

It is known that the capacity of parallel (multicarrier) Gaussian point-to-point, multiple access and broadcast channels can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. In this paper we show that such a separation does not apply to parallel Gaussian interference channels in general. A counterexample is provided in the form of a 3 user interference channel where separate encoding can only achieve a sum capacity of 2 log(1+3 SNR) while the actual capacity, achieved only by joint encoding across carriers, is 3 log(1+2 SNR). As a byproduct of our analysis, we propose a class of multiple-access-outer bounds on the capacity of the 3 user interference channel.

An interference alignment example is constructed for the deterministic channel model of theK-user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected GaussianK-user interference network with single antenna nodes, real, nonzero and constant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the two-userXchannel as well.

It is known that the capacity of parallel (multi-carrier) Gaussian point-to-point, multiple access and broadcast channels can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. In this paper we show that such a separation does not apply to parallel Gaussian interference channels in general. A counter-example is provided in the form of a 3 user interference channel where separate encoding can only achieve a sum capacity of log(SNR) +o(log(SNR)) per carrier while the actual capacity, achieved only by joint-encoding across carriers, is 3/2(log(SNR))+o(log(SNR)) per carrier. As a byproduct of our analysis, we propose a class of multiple-access-outerbounds on the capacity of the 3 user interference channel.

Recent results establish the optimality of interference alignment to approach the Shannon capacity of interference networks at high SNR. However, the extent to which interference can be aligned over a finite number of signalling dimensions remains unknown. Another important concern for interference alignment schemes is the requirement of global channel knowledge. In this work we provide examples of iterative algorithms that utilize the reciprocity of wireless networks to achieve interference alignment with only local channel knowledge at each node. These algorithms also provide numerical insights into the feasibility of interference alignment that are not yet available in theory.

We show that the sum capacity of the K user frequency selective (or time-varying) interference channel is C(SNR) = (K/2) log(SNR) +o(log(SNR)) meaning that the channel has a total of K/2 degrees of freedom per orthogonal time and frequency dimension. Linear schemes of interference alignment and zero forcing suffice to achieve all the degrees of freedom and multi-user detection is not required.

We study stability regions of multi-rate Gaussian multiple access (MAC) and broadcast (BC) networks with centralized scheduling algorithms. Techniques are presented to characterize stability regions of BC and MAC networks with peak power constraints and average power constraints. The duality property that relates the MAC and BC information theoretic capacity regions is found to extend to their stability regions as well, in the average power constraint case.

We consider a fully connected network with S full duplex source nodes, D full duplex destination nodes and R relay nodes, perfect feedback to source and relay nodes, and noisy cooperation between all source, relay and destination nodes. We show that this network has SD/S+D-1 degrees of freedom if the channel gains are time-varying/frequency selective. The implication of the result is that, the techniques mentioned in the title (i.e relays etc.) can affect the capacity of a network only up to a o(log(SNR)) term and therefore cannot improve the degrees of freedom of a network. Certain communication scenarios excluded by our system model where these techniques improve the degrees of freedom are also identified. Bounds on the degrees of freedom of a fully connected K node network emerge as a by-product of our study.

We study the degrees of freedom characterization of wireless X networks, i.e. networks of M distributed single antenna transmitters and N distributed single antenna receivers where every transmitter has an independent message to every receiver. We provide an outerbound on the capacity region of X networks within o(log(SNR)). If the channel co-efficients are time-varying/frequency selective, we show that the total number of degrees of freedom is equal to MN/M+N-1 using a coding scheme based on the idea of interference alignment.

An interference alignment example is constructed for the deterministic channel model of the K user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected Gaussian K user interference network with single antenna nodes, real, non-zero and contant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the 2 user X channel as well.

For the fully connected K user wireless interference channel where the channel coefficients are time-varying and are drawn from a continuous distribution, the sum capacity is characterized as C(SNR)=K/2log(SNR)+o(log(SNR)) . Thus, the K user time-varying interference channel almost surely has K/2 degrees of freedom. Achievability is based on the idea of interference alignment. Examples are also provided of fully connected K user interference channels with constant (not time-varying) coefficients where the capacity is exactly achieved by interference alignment at all SNR values.