Title: Constructions of Codes with the Locality Property
We say that a code has the locality property if a part of the message can be decoded using a small number of code's coordinates. Locality has recently been the focus of many studies in coding theory and computer science. In this talk we present algebraic constructions of codes for a particular case of the locality problem motivated by applications in distributed storage. We begin with describing a family of Reed-Solomon-like codes with locality that have the highest possible distance among the codes of the same cardinality. The idea of this construction extends to codes on algebraic curves which give rise to a rich class of codes with locality. We also discuss bounds on codes, some other recent results in this area, and mention several open problems.
The talk is based on joint works with I.Tamo, S. Vladuts, and A. Frolov.
Title: The Impact of Network Coding on Mathematics - Notes from COST Action IC1104
Network communications theory is important not only for its numerous applications but also for its impact on various topics in mathematics. Network coding has progressed using ideas from algebra and discrete mathematics with the reciprocal effect of stimulating research in graph theory, finite geometry, lattices, rank-metric codes, subspace codes, q-analogues of designs, linearized polynomials, finite fields and semifields. We will discuss some of these influences, in particular those emerging from random network coding for error correction and the index coding problem.
Title: An Information-theoretic Perspective of Consistent Distributed Storage
In applications of distributed storage systems to cloud based key-value stores, an important requirement is the following property known, in computer science literature, as consistency: when the data is being constantly updated, a client that reads from the system should obtain the latest version of the data. In this talk, we present a network information theoretic formulation to analyze the storage cost of systems where consistency is important. Through an analysis of the formulation, we quantify the price of ensuring consistency over the presented storage models.
Title: Impact of Network Coding on Combinatorial Optimization
I will describe my personal perspective on the influence of network coding on combinatorial optimization. The plan is to discuss two topics. The first topic is on flow-cut gap results, new problems, and related structural results that were inspired by efforts to understand the gap between network coding and routing. The second topic is on faster algebraic algorithms for computing connectivity in graphs that are inspired by linear network coding in the multicast setting. (Based on work/papers by several authors.)
Title: Coding with Constraints: Different Flavors
Coding with constraints requires that each coded symbol is a function of a certain subset of data symbols. In this talk, I will discuss a couple of coding problems where different flavors of coding with constraints are observed. In particular, I will focus on a recently studied problem of jointly designing different local maximum distance separable (MDS) codes that share some subsets of data symbols so that the global minimum distance is maximized.
Title: Duality in Simple Multiple Access Networks
In a simple multiple access network the goal is to transmit reliably from multiple sources to a single destination via a single layer of intermediate nodes. We describe the dual version where information is broadcasted securely in the reverse direction over the same network, from the single destination to the multiple sources, and we show that the two scenarios have the same capacity regions.
Title: Index Coding Algorithms for Constructing Network Codes
I will talk about the equivalence between index coding and network coding and our ongoing efforts in using this equivalence to develop a software library for constructing linear network codes.
Title: Network Coding Beyond Network Coding
Network coding results are useful both for their direct application and for their implications about problems outside the network coding domain. This talk focuses on the latter, touching on equivalences, coding bounds, and hybrid network coding / non-network coding networks.
Title: Network (Coding) Security: Known knowns, Unknown knowns, and Unknowns
Known knowns: As a quick survey, the first chunk of this talk will remind the audience of "classical" results in network error-correction, starting with the elegant works of Cai-Yeung, Koetter-Kschischang-Silva, and others. Unknown knowns: I'll then segue to a smattering of recent results from my groups that aren't perhaps known as well as they could be, either because they've only recently been published, or because they aren't published yet. Examples include (i) the effect of limited adversarial knowledge on network error-correction capacity, (ii) arbitrarily varying networks, and (iii) network error-correction over constant-sized alphabets. Unknowns: Finally, I'll mention questions about network security that I personally find interesting, and don't know the answers to, such as network list-decoding, network tomography, network deniability, and network anonymity.
Title: Analyzing Large Communication Networks
The emergence of the Internet and mobile wireless networks gives rise to large networks involving millions of users and thousands of relay nodes. In such large networks, it is crucial to answer fundamental questions such as the structure of the capacity-achieving codes, or the loss incurred from sub-optimal low-complexity codes. On the other hand, the set of multi-user networks for which the answers to these questions are known is very limited. In this talk, I will discuss some approaches for bridging the gap between analyzable networks and real communication networks. These methods enable us to answer some fundamental questions related to the structure of capacity-achieving codes for general noisy wired networks, such as the Internet. I will then explain a new hierarchical network simplification method, which is based on iterative topological operations. For a given network, this new approach enables us to find simpler networks of smaller sizes whose capacity regions provide upper or lower bounds on the capacity of the original network. (This is based on joint work with Michelle Effros and Tracey Ho.)
Title: Delay-Constrained Unicast: Improved Upper Bounds
We consider the singleunicast communication problem in a network with a delay constraint. For this setting, it had recently been shown that network coding offers an advantage over routing. We show that the existing upper bound in the literature on the capacity offered by network coding can be a factor of \Theta(D) larger than the true capacity where D is the delay bound. In this work, we tighten this gap significantly to 8 log(D + 1) by proving a new upper bound. The key insight is a connection to a new traffic model that we call trianglecast for which we obtain a logarithmic flowcut gap by suitably adapting the techniques from the literature on combinatorial optimization.
Based on joint work with Chandra Chekuri, Sreeram Kannan, Pramod Viswanath.
Title: On the Relation Between Edge Removal and Strong Converses
In multiterminal network communication, the edge removal problem seeks to quantify the reduction of achievable network rates if a single edge is removed from the network. The general problem is open but various special cases have been addressed, as for example for single and multisource network coding and the connection of edge removal to epsilon versus zero-error coding. In this talk, we aim to relate edge removal to another class of network properties, namely the existence of strong converses. We define several classes of strong converses and edge removal properties and highlight connections between these two instances. We show that edge removal is implied by the existence of a specific class of strong converses, but the opposite direction holds true, if at all, only for deterministic networks. The result highlights the power of reductive studies, connecting the existence of strong converses to other properties implied by edge removal and vice versa.
Title: Network Equivalence in the Presence of Active Adversaries
We consider a multisource noisy network in the presence of an active (Byzantine) adversary that can transmit arbitrary signals from an unknown location. Finding the capacity region of such a network is highly challenging for several reasons: messages originate from several nodes (i.e. not a single multicast), the random channel noise, the unknown adversary location, and the unknown adversary transmission. We aim to use the network equivalence framework to reduce this problem to one without noise or the adversary; i.e. a multisource network coding problem. The adversary is characterized using a joint model with a compound-channel-type state (fixed across the coding block) modeling the adversary's position, and an arbitrarily-varying-channel-type state (changing across the code block) modeling the adversary's transmission. We present several results in networks composed of independent point-to-point channels. We find that when the network is fully connected, in that any node can send a message at some positive capacity to every other node, the problem simplifies and equivalence results usually exist.
Title: Capacity Bounds for Diamond Networks
A class of diamond networks is studied where the broadcast component is modeled by two independent bit pipes. New bounds on the capacity are derived, and the bounds are evaluated for Gaussian and binary adder multiple access channels (MACs). For Gaussian MACs, the bounds strengthen the Kang- Liu bounds and establish capacity for interesting ranges of bit-pipe capacities. For binary adder MACs, the capacity is established for all ranges of bit-pipe capacities.
Title: Coded MapReduce
MapReduce is a commonly used framework for executing data-intensive tasks on distributed server clusters. We present ''Coded MapReduce", a new framework that enables and exploits a particular form of coding to significantly reduce the inter-server communication load of MapReduce. In particular, Coded MapReduce exploits the repetitive mapping of data blocks at different servers to create coded multicasting opportunities in the shuffling phase, cutting down the total communication load by a multiplicative factor that grows linearly with the number of servers in the cluster. We will further discuss the tradeoff between the ''computation load'' and the ''communication load" in distributed computing. (This is a joint work with Sonze Li and Salman Avestimehr from USC.)
Title: Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems
Erasure codes are increasingly being studied in the context of implementing consistent shared storage objects in large scale asynchronous distributed storage systems. We adopt atomic consistency, which gives the users of the data service the impression that the various concurrent read and write operations happen sequentially in time. Usage of erasure codes in asynchronous, decentralized storage systems is more challenging when compared to their usage in settings which assume centralized controllers, and often results in additional communication or storage costs for a given level of fault tolerance. Even then, erasure codes offer significant gains over the traditional replication-based strategies that are commonly used in asynchronous decentralized systems. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic shared storage objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. (Based on joint work with Erez Kantor, Kishori Konwar, Nancy Lynch, Muriel Medard and Alexander Shvartsman.)
Title: Improved Lower bounds for Coded Caching
Content delivery networks often employ caching to reduce transmission rates from the central server to the end users. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server are considered. Prior results in this area demonstrate that (a) carefully designing placement of content in the caches and (b) designing appropriate coded delivery signals allow for a system where the delivery rates can be significantly smaller than conventional schemes. In this work, we derive tighter lower bounds on coded caching rates than were known previously. We show that this problem can equivalently be posed as one of optimally labeling the leaves of a directed tree. Analyzing the properties of this combinatorial problem allows us to arrive at the improved lower bound. In particular, we demonstrate a multiplicative gap of at most four between the achievable rate and our lower bound. (Joint work with Hooshang Ghasemi.)
Title: Scheduling and Transmission Aspects in Distributed Storage and Their Connections with Index Coding
Index coding is often studied with the assumption that a single source has all the messages requested by receivers. This is referred to as centralized index coding. In contrast, this talk focuses on distributed index coding and addresses the following question: How does the availability of messages at distributed sources (storage nodes) affect the solutions and achievable rates of index coding? An extension to the work of Arbabjolfaei et al. in ISIT 2013 is presented when distributed sources communicate via a deterministic multiple access channel (MAC) to simultaneous receivers. A numbers of examples are discussed that show the effect of message distribution and redundancy across the network on achievable rates of index coding and motivate future research on designing practical network storage codes that offer high index coding rates.
Title: Something Ancient and Something Recent
I will first talk about how the idea of network coding came about at the very beginning. I will then FF 20 years to talk about our latest effort on developing a network coding technology for transmission in networks with packet loss: BATS code. BATS code consists of an outer code and an inner code. The outer code is a matrix generalization of a fountain code. It works with the inner code which comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capabilities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. It has been verified theoretically for certain special cases and demonstrated numerically for general cases that BATS codes can achieve rates very close to optimality.