How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and computing, i.e., two are inversely proportional each other. More specifically, general framework, motivated commonly used structures like MapReduce, is considered, where overall decomposed into set of “Map” “Reduce” functions distributedly across multiple nodes. A coded scheme, named “coded...

We consider a scenario involving computations over massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. propose Lagrange Coded Computing (LCC), new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security Byzantine (or malicious) workers deliberately modify computation for their benefit; and (3) (information-theoretic) privacy amidst possible collusion workers. LCC,...

We propose a unified coding framework for distributed computing with straggling servers, by introducing tradeoff between "latency of computation" and "load communication" some linear computation tasks. show that the coded scheme [1]-[3] repeats intermediate computations to create multicasting opportunities reduce communication load, [4] generates redundant combat against servers can be viewed as special instances proposed framework, considering two extremes this tradeoff: minimizing either...

Redundancy is abundant in fog networks (i.e., many computing and storage points) grows linearly with network size. We demonstrate the transformational role of coding for leveraging such redundancy to substantially reduce bandwidth consumption latency computing. In particular, we discuss two recently proposed concepts, minimum codes codes, illustrate their impacts on also review a unified framework that includes above techniques as special cases, enables trade-off between computation...

We consider a wireless distributed computing system, in which multiple mobile users, connected wirelessly through an access point, collaborate to perform computation task. In particular, users communicate with each other via the point exchange their locally computed intermediate results, is known as data shuffling. propose scalable framework for this required communication bandwidth shuffling does not increase number of network. The key idea utilize particular repetitive pattern placing set...

MapReduce is a commonly used framework for executing data-intensive tasks on distributed server clusters. We present "Coded MapReduce", new that enables and exploits particular form of coding to significantly reduce the inter-server communication load MapReduce. In particular, Coded repetitive mapping data blocks at different servers create coded multicasting opportunities in shuffling phase, cutting down total by multiplicative factor grows linearly with number cluster. also analyze...

Modern learning algorithms use gradient descent updates to train inferential models that best explain data. Scaling these approaches massive data sizes requires proper distributed schemes where worker nodes compute partial gradients based on their and local sets, send the results a master node all computations are aggregated into full model is updated. However, major performance bottleneck arises some of may run slow. These a.k.a. stragglers can significantly slow down computation as slowest...

Today's blockchain designs suffer from a trilemma claiming that no system can simultaneously achieve decentralization, security, and performance scalability. For current systems, as more nodes join the network, efficiency of (computation, communication, storage) stays constant at best. A leading idea for enabling blockchains to scale is notion sharding: different subsets handle portions blockchain, thereby reducing load each individual node. However, existing sharding proposals scaling by...

We propose <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> , a novel secure aggregation protocol for federated learning systems, where central server aggregates local models of <inline-formula xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N \in \mathbb {N}$ </tex-math></inline-formula> distributed users, each size notation="LaTeX">$L trained on their data, in privacy-preserving manner. can...

We introduce a general distributed computing framework, motivated by commonly used structures like MapReduce, and formulate an information-theoretic tradeoff between computation communication in such framework. characterize the optimal to within constant factor, for all system parameters. In particular, we propose coded scheme, namely "Coded MapReduce" (CMR), which creates exploits coding opportunities data shuffling computing, reducing load factor that is linearly proportional load. then...

Secure model aggregation is a key component of federated learning (FL) that aims at protecting the privacy each user's individual while allowing for their global aggregation. It can be applied to any aggregation-based FL approach training or personalized model. Model needs also resilient against likely user dropouts in systems, making its design substantially more complex. State-of-the-art secure protocols rely on secret sharing random-seeds used mask generations users enable reconstruction...

To execute cloud computing tasks over a data center hosting hundreds of thousands server nodes, it is natural to distribute computations across the nodes take advantage parallel processing. However, as we allocate more resources and further computations, large amount intermediate must be moved between consecutive computation stages among causing communication load become bottleneck. In this paper, study optimal resource allocation in distributed computing, order minimize total execution time...

We consider the problem of training a least-squares regression model on large dataset using gradient descent. The computation is carried out distributed system consisting master node and multiple worker nodes. Such systems are significantly slowed down due to presence slow-running machines (stragglers) as well various communication bottlenecks. propose "polynomially coded regression" (PCR) that substantially reduces effect stragglers lessens burden in such systems. key idea PCR encode...

In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash data shuffling load of distributed computing via coding, and then discuss extension CDC techniques cope with two major challenges in general problems, namely straggling servers multistage computations. When faced a cluster, describe unified coding scheme that superimposes Maximum-Distance-Separable (MDS) on computation tasks, which allows flexible tradeoff between latency...

We propose SwiftAgg, a novel secure aggregation protocol for federated learning systems, where central server aggregates local models of N distributed users, each size L, trained on their data, in privacy-preserving manner. Compared with state-of-the-art protocols, SwiftAgg significantly reduces the communication overheads without any compromise security. Specifically, presence at most D dropout achieves load (T +1)L and per-user up to (T+D+1)L, worst-case information-theoretic security...

Threshold fully homomorphic encryption (ThFHE) enables multiple parties to compute functions over their sensitive data without leaking privacy. Most of existing ThFHE schemes are restricted full threshold and require the participation \textit{all} output computing results. Compared with these full-threshold schemes, arbitrary (ATh)-FHE robust non-participants can be a promising solution many real-world applications. However, AThFHE either inefficient applied large number $N$ size $K$, or...

Vision-Language Models (VLMs) have gained considerable prominence in recent years due to their remarkable capability effectively integrate and process both textual visual information. This integration has significantly enhanced performance across a diverse spectrum of applications, such as scene perception robotics. However, the deployment VLMs also given rise critical safety security concerns, necessitating extensive research assess potential vulnerabilities these VLM systems may harbor. In...