BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Viveck R. Cadambe

Viveck R. Cadambe appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITDistributed, Parallel, and Cluster ComputingMachine Learningmath.CONetworking and Internet ArchitecturePerformance

Catalog footprint

What is connected

18works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2026arXiv

Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning

Coding theory plays a crucial role in enabling reliable communication, storage, and computation. Classical approaches assume a worst-case adversarial model and ensure error correction and data recovery only when the number of honest nodes exceeds the number of adversarial ones by some margin. However, in some emerging decentralized applications, particularly in decentralized machine learning (DeML), participating nodes are rewarded for accepted contributions. This incentive structure naturally gives rise to rational adversaries who act strategically rather than behaving in purely malicious ways. In this paper, we first motivate the need for coding in the presence of rational adversaries, particularly in the context of outsourced computation in decentralized systems. We contrast this need with existing approaches and highlight their limitations. We then introduce the game of coding, a novel game-theoretic framework that extends coding theory to trust-minimized settings where honest nodes are not in the majority. Focusing on repetition coding, we highlight two key features of this framework: (1) the ability to achieve a non-zero probability of data recovery even when adversarial nodes are in the majority, and (2) Sybil resistance, i.e., the equilibrium remains unchanged even as the number of adversarial nodes increases. Finally, we explore scenarios in which the adversary's strategy is unknown and outline several open problems for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption

Coding theory plays a crucial role in ensuring data integrity and reliability across various domains, from communication to computation and storage systems. However, its reliance on trust assumptions for data recovery, which requires the number of honest nodes to exceed adversarial nodes by a certain margin, poses significant challenges, particularly in emerging decentralized systems where trust is a scarce resource. To address this, the game of coding framework was introduced, offering insights into strategies for data recovery within incentive-oriented environments. In such environments, participant nodes are rewarded as long as the system remains functional (live). This incentivizes adversaries to maximize their rewards (utility) by ensuring that the decoder, as the data collector (DC), successfully recovers the data, preferably with a high estimation error. This rational behavior is leveraged in a game-theoretic framework, where the equilibrium leads to a robust and resilient system, referred to as the game of coding. The focus of the earliest version of the game of coding was limited to scenarios involving only two nodes. In this paper, we generalize the game of coding framework to scenarios with $N \ge 2$ nodes, exploring critical aspects of system behavior. Specifically, we (i) demonstrate that the adversary's utility at equilibrium is non-increasing with additional adversarial nodes, ensuring no gain for the adversary and no pain for the DC, thus establishing the game of coding framework's Sybil resistance; (ii) show that increasing the number of honest nodes does not always enhance the DC's utility, providing examples and proposing an algorithm to identify and mitigate this counterintuitive effect; and (iii) outline the optimal strategies for both the DC and the adversary, demonstrating that the system achieves enhanced liveness at equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

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. 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-Łojasiewicz 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 GPU cluster.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

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. In this paper, we present 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. We consider an arbitrary algorithm $A$ that implements an atomic multi-writer single-reader (MWSR) shared memory variable whose values come from a finite set $\mathcal{V}$ over a system of $N$ servers connected by point-to-point asynchronous links. We require that in every fair execution of algorithm $A$ where the number of server failures is smaller than a parameter $f$, every operation invoked at a non-failing client terminates. We define the storage cost of a server in algorithm $A$ as the logarithm (to base 2) of number of states it can take on; the total-storage cost of algorithm $A$ is the sum of the storage cost of all servers. Our results are as follows. (i) We show that if algorithm $A$ does not use server gossip, then the total storage cost is lower bounded by $2 \frac{N}{N-f+1}\log_2|\mathcal{V}|-o(\log_2|\mathcal{V}|)$. (ii) The total storage cost is at least $2 \frac{N}{N-f+2} \log_{2}|\mathcal{V}|-o(\log_{2}|\mathcal{V}|)$ even if the algorithm uses server gossip. (iii) We consider algorithms where the write protocol sends information about the value in at most one phase. We show that the total storage cost is at least $ν^* \frac{N}{N-f+ν^*-1} \log_2( |\mathcal{V}|)- o(\log_2(|\mathcal{V}|),$ where $ν^*$ is the minimum of $f+1$ and the number of active write operations of an execution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Alignment based Network Coding for Two-Unicast-Z Networks

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 apriori side information of the first message. We make three contributions in this paper: 1. We describe a new linear network coding algorithm for two-unicast-Z networks over directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and polynomial complexity in terms of the number of edges. 2. 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 directed acyclic graphs, to an earlier result of Wang et al. which studied necessary and sufficient conditions for feasibility of the rate pair (1, 1) in two-unicast networks. 3. We provide a new proof of the classical max-flow min-cut theorem for directed acyclic graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage

In applications of distributed storage systems to distributed computing and implementation of key- value stores, the following property, usually referred to as consistency in computer science and engineering, 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. An information theoretic formulation called multi-version coding is introduced in the paper, in order to study storage costs of consistent distributed storage systems. 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 approximately tight, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Coded Shared Atomic Memory Algorithm for Message Passing Architectures

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 three main contributions: (1) We present a 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 $\frac{N}{N-2f}$. The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer $δ$ 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 $δ$, the CASGC algorithm with parameter $δ$ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of $\frac{N}{N-f}$ measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Feedback Interference Alignment: Exact Alignment for Three Users in Two Time Slots

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 significantly outperforms time-sharing even at finite SNR.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Index Coding - An Interference Alignment Perspective

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 multiple unicast index coding where each message is desired by exactly one receiver, and multiple 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 multiple groupcast settings where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate $\frac{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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignment

It is well known that an (n,k) code can be used to store 'k' units of information in 'n' unit-capacity disks of a distributed data storage system. If the code used is maximum distance separable (MDS), then the system can tolerate any (n-k) disk failures, since the original information can be recovered from any k surviving disks. The focus of this paper is the design of a systematic MDS code with the additional property that a single disk failure can be repaired with minimum repair bandwidth, i.e., with the minimum possible amount of data to be downloaded for recovery of the failed disk. Previously, a lower bound of (n-1)/(n-k) units has been established by Dimakis et. al, on the repair bandwidth for a single disk failure in an (n,k) MDS code . Recently, the existence of asymptotic codes achieving this lower bound for arbitrary (n,k) has been established by drawing connections to interference alignment. While the existence of asymptotic constructions achieving this lower bound have been shown, finite code constructions achieving this lower bound existed in previous literature only for the special (high-redundancy) scenario where $k \leq \max(n/2,3)$. The question of existence of finite codes for arbitrary values of (n,k) achieving the lower bound on the repair bandwidth remained open. In this paper, by using permutation coding sub-matrices, we provide the first known finite MDS code which achieves the optimal repair bandwidth of (n-1)/(n-k) for arbitrary (n,k), for recovery of a failed systematic disk. We also generalize our permutation matrix based constructions by developing a novel framework for repair-bandwidth-optimal MDS codes based on the idea of subspace interference alignment - a concept previously introduced by Suh and Tse the context of wireless cellular networks.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Repair Optimal Erasure Codes through Hadamard Designs

In distributed storage systems that employ erasure coding, the issue of minimizing the total {\it communication} required to exactly rebuild a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Designing high-rate maximum-distance separable (MDS) codes that achieve the optimum repair communication has been a well-known open problem. In this work, we use Hadamard matrices to construct the first explicit 2-parity MDS storage code with optimal repair properties for all single node failures, including the parities. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite file size, or number of extensions. We generalize this construction to design $m$-parity MDS codes that achieve the optimum repair communication for single systematic node failures and show that there is an interesting connection between our $m$-parity codes and the systematic-repair optimal permutation-matrix based codes of Tamo {\it et al.} \cite{Tamo} and Cadambe {\it et al.} \cite{PermCodes_ISIT, PermCodes}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Data Storage with Minimum Storage Regenerating Codes - Exact and Functional Repair are Asymptotically Equally Efficient

We consider a set up where a file of size M is stored in n distributed storage nodes, using an (n,k) minimum storage regenerating (MSR) code, i.e., a maximum distance separable (MDS) code that also allows efficient exact-repair of any failed node. The problem of interest in this paper is to minimize the repair bandwidth B for exact regeneration of a single failed node, i.e., the minimum data to be downloaded by a new node to replace the failed node by its exact replica. Previous work has shown that a bandwidth of B=[M(n-1)]/[k(n-k)] is necessary and sufficient for functional (not exact) regeneration. It has also been shown that if k < = max(n/2, 3), then there is no extra cost of exact regeneration over functional regeneration. The practically relevant setting of low-redundancy, i.e., k/n>1/2 remains open for k>3 and it has been shown that there is an extra bandwidth cost for exact repair over functional repair in this case. In this work, we adopt into the distributed storage context an asymptotically optimal interference alignment scheme previously proposed by Cadambe and Jafar for large wireless interference networks. With this scheme we solve the problem of repair bandwidth minimization for (n,k) exact-MSR codes for all (n,k) values including the previously open case of k > \max(n/2,3). Our main result is that, for any (n,k), and sufficiently large file sizes, there is no extra cost of exact regeneration over functional regeneration in terms of the repair bandwidth per bit of regenerated data. More precisely, we show that in the limit as M approaches infinity, the ratio B/M = (n-1)/(k(n-k))$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sum-Capacity and the Unique Separability of the Parallel Gaussian MAC-Z-BC Network

It is known that the capacity of parallel (e.g., 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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Interference Alignment with Asymmetric Complex Signaling - Settling the Host-Madsen-Nosratinia Conjecture

It has been conjectured by Host-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 Host-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 introduce 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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Approaching the Capacity of Wireless Networks through Distributed Interference Alignment

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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Capacity of Wireless Networks within o(log(SNR)) - the Impact of Relays, Feedback, Cooperation and Full-Duplex Operation

Recent work has characterized the sum capacity of time-varying/frequency-selective wireless interference networks and $X$ networks within $o(\log({SNR}))$, i.e., with an accuracy approaching 100% at high SNR (signal to noise power ratio). In this paper, we seek similar capacity characterizations for wireless networks with relays, feedback, full duplex operation, and transmitter/receiver cooperation through noisy channels. First, we consider a network with $S$ source nodes, $R$ relay 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. The sum capacity of this network is characterized as $\frac{SD}{S+D-1}\log({SNR})+o(\log({SNR}))$. The implication of the result is that the capacity benefits of relays, causal feedback, transmitter/receiver cooperation through physical channels and full duplex operation become a negligible fraction of the network capacity at high SNR. Some exceptions to this result are also pointed out in the paper. Second, we consider a network with $K$ full duplex nodes with an independent message from every node to every other node in the network. We find that the sum capacity of this network is bounded below by $\frac{K(K-1)}{2K-2}+o(\log({SNR}))$ and bounded above by $\frac{K(K-1)}{2K-3}+o(\log({SNR}))$.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Multiple Access Outerbounds and the Inseparability of Parallel Interference Channels

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.

0 citations0 reviewsNo code linkedOpen access