BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Rawad Bitar

Rawad Bitar contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITDistributed, Parallel, and Cluster ComputingMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

12 published item(s)

preprint2024arXiv

Byzantine-Resilient Gradient Coding through Local Gradient Computations

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the responses from malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workers each partial gradient is computed by. In this work, we propose a way to reduce the replication to $s+1$ instead of $2s+1$ in the presence of $s$ malicious workers. Our method detects erroneous inputs from the malicious workers, transforming them into erasures. This comes at the expense of $s$ additional local computations at the main node and additional rounds of light communication between the main node and the workers. We define a general framework and give fundamental limits for fractional repetition data allocations. Our scheme is optimal in terms of replication and local computation and incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound. We furthermore show how additional redundancy can be exploited to reduce the number of local computations and communication cost, or, alternatively, tolerate straggling workers.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning

We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on $n$ workers, each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest $k<n$ workers before updating the model, where $k$ is a fixed parameter. The choice of the value of $k$ presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive~$k$, i.e., varying $k$ throughout the runtime of the algorithm. We first design an adaptive policy for varying $k$ that optimizes this trade-off based on an upper bound on the error as a function of the wall-clock time that we derive. Then, we propose and implement an algorithm for adaptive distributed SGD that is based on a statistical heuristic. Our results show that the adaptive version of distributed SGD can reach lower error values in less time compared to non-adaptive implementations. Moreover, the results also show that the adaptive version is communication-efficient, where the amount of communication required between the master and the workers is less than that of non-adaptive versions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits

We consider the distributed SGD problem, where a main node distributes gradient calculations among $n$ workers. By assigning tasks to all the workers and waiting only for the $k$ fastest ones, the main node can trade-off the algorithm&#39;s error with its runtime by gradually increasing $k$ as the algorithm evolves. However, this strategy, referred to as adaptive $k$-sync, neglects the cost of unused computations and of communicating models to workers that reveal a straggling behavior. We propose a cost-efficient scheme that assigns tasks only to $k$ workers, and gradually increases $k$. We introduce the use of a combinatorial multi-armed bandit model to learn which workers are the fastest while assigning gradient calculations. Assuming workers with exponentially distributed response times parameterized by different means, we give empirical and theoretical guarantees on the regret of our strategy, i.e., the extra time spent to learn the mean response times of the workers. Furthermore, we propose and analyze a strategy applicable to a large class of response time distributions. Compared to adaptive $k$-sync, our scheme achieves significantly lower errors with the same computational efforts and less downlink communication while being inferior in terms of speed.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Matrix-Vector Multiplication with Sparsity and Privacy Guarantees

We consider the problem of designing a coding scheme that allows both sparsity and privacy for distributed matrix-vector multiplication. Perfect information-theoretic privacy requires encoding the input sparse matrices into matrices distributed uniformly at random from the considered alphabet; thus destroying the sparsity. Computing matrix-vector multiplication for sparse matrices is known to be fast. Distributing the computation over the non-sparse encoded matrices maintains privacy, but introduces artificial computing delays. In this work, we relax the privacy constraint and show that a certain level of sparsity can be maintained in the encoded matrices. We consider the chief/worker setting while assuming the presence of two clusters of workers: one is completely untrusted in which all workers collude to eavesdrop on the input matrix and in which perfect privacy must be satisfied; in the partly trusted cluster, only up to $z$ workers may collude and to which revealing small amount of information about the input matrix is allowed. We design a scheme that trades sparsity for privacy while achieving the desired constraints. We use cyclic task assignments of the encoded matrices to tolerate partial and full stragglers.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Equivalence of Insertion/Deletion Correcting Codes for $d$-dimensional Arrays

We consider the problem of correcting insertion and deletion errors in the $d$-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is interesting to know whether the same properties of insertion/deletion correcting codes generalize to the $d$-dimensional space. In this work, we show that the equivalence between insertion and deletion correcting codes generalizes to the $d$-dimensional space. As a particular result, we show the following missing equivalence for arrays: a code that can correct $t_\mathrm{r}$ and $t_\mathrm{c}$ row/column deletions can correct any combination of $t_\mathrm{r}^{\mathrm{ins}}+t_\mathrm{r}^{\mathrm{del}}=t_\mathrm{r}$ and $t_\mathrm{c}^{\mathrm{ins}}+t_\mathrm{c}^{\mathrm{del}}=t_\mathrm{c}$ row/column insertions and deletions. The fundamental limit on the redundancy and a construction of insertion/deletion correcting codes in the $d$-dimensional space remain open for future work.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Secure Private and Adaptive Matrix Multiplication Beyond the Singleton Bound

We consider the problem of designing secure and private codes for distributed matrix-matrix multiplication. A master server owns two private matrices and hires worker nodes to help compute their product. The matrices should remain information-theoretically private from the workers. Some of the workers are malicious and return corrupted results to the master. We design a framework for security against malicious workers in private matrix-matrix multiplication. The main idea is a careful use of Freivalds&#39; algorithm to detect erroneous matrix multiplications. Our main goal is to apply this security framework to schemes with adaptive rates. Adaptive schemes divide the workers into clusters and thus provide flexibility in trading decoding complexity for efficiency. Our new scheme, SRPM3, provides a computationally efficient security check per cluster that detects the presence of one or more malicious workers with high probability. An additional per worker check is used to identify the malicious nodes. SRPM3 can tolerate the presence of an arbitrary number of malicious workers. We provide theoretical guarantees on the complexity of the security checks and simulation results on both, the missed detection rate as well as on the time needed for the integrity check.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Adaptive Private Distributed Matrix Multiplication

We consider the problem of designing codes with flexible rate (referred to as rateless codes), for private distributed matrix-matrix multiplication. A master server owns two private matrices $\mathbf{A}$ and $\mathbf{B}$ and hires worker nodes to help computing their multiplication. The matrices should remain information-theoretically private from the workers. Codes with fixed rate require the master to assign tasks to the workers and then wait for a predetermined number of workers to finish their assigned tasks. The size of the tasks, hence the rate of the scheme, depends on the number of workers that the master waits for. We design a rateless private matrix-matrix multiplication scheme, called RPM3. In contrast to fixed-rate schemes, our scheme fixes the size of the tasks and allows the master to send multiple tasks to the workers. The master keeps sending tasks and receiving results until it can decode the multiplication; rendering the scheme flexible and adaptive to heterogeneous environments. Despite resulting in a smaller rate than known straggler-tolerant schemes, RPM3 provides a smaller mean waiting time of the master by leveraging the heterogeneity of the workers. The waiting time is studied under two different models for the workers&#39; service time. We provide upper bounds for the mean waiting time under both models. In addition, we provide lower bounds on the mean waiting time under the worker-dependent fixed service time model.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Network Coding with Myopic Adversaries

We consider the problem of reliable communication over a network containing a hidden {\it myopic} adversary who can eavesdrop on some $z_{ro}$ links, jam some $z_{wo}$ links, and do both on some $z_{rw}$ links. We provide the first information-theoretically tight characterization of the optimal rate of communication possible under all possible settings of the tuple $(z_{ro},z_{wo},z_{rw})$ by providing a novel coding scheme/analysis for a subset of parameter regimes. In particular, our vanishing-error schemes bypass the Network Singleton Bound (which requires a zero-error recovery criteria) in a certain parameter regime where the capacity had been heretofore open. As a direct corollary we also obtain the capacity of the corresponding problem where information-theoretic secrecy against eavesdropping is required in addition to reliable communication.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Communication Efficient Secret Sharing in the Presence of Malicious Adversary

Consider the communication efficient secret sharing problem. A dealer wants to share a secret with $n$ parties such that any $k\leq n$ parties can reconstruct the secret and any $z<k$ parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any $d$, $k\leq d \leq n$, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e. maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from $d$ parties, $k\leq d \leq n$. Error-correcting codes do not achieve capacity in this setting. We construct codes that achieve capacity and achieve minimum read and communication costs for all possible values of $d$. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect errors inserted by a limited knowledge adversary.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rateless Codes for Private Distributed Matrix-Matrix Multiplication

We consider the problem of designing rateless coded private distributed matrix-matrix multiplication. A master server owns two private matrices $\mathbf{A}$ and $\mathbf{B}$ and wants to hire worker nodes to help compute the multiplication. The matrices should remain private from the workers, in an information-theoretic sense. This problem has been considered in the literature and codes with a predesigned threshold are constructed. More precisely, the master assigns tasks to the workers and waits for a predetermined number of workers to finish their assigned tasks. The size of the tasks assigned to the workers depends on the designed threshold. We are interested in settings where the size of the task must be small and independent of the designed threshold. We design a rateless private matrix-matrix multiplications scheme, called RPM3. Our scheme fixes the size of the tasks and allows the master to send multiple tasks to the workers. The master keeps receiving results until it can decode the multiplication. Two main applications require this property: i) leverage the possible heterogeneity in the system and assign more tasks to workers that are faster; and ii) assign tasks adaptively to account for a possibly time-varying system.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes

We consider the setting of a Master server, M, who possesses confidential data (e.g., personal, genomic or medical data) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private and not revealed to the individual workers. Some of the workers may be stragglers, e.g., slow or busy, and will take a random time to finish the task assigned to them. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms such as principal component analysis, support vector machines and other gradient-descent based algorithms. A classical solution is to use a linear secret sharing scheme, such as Shamir&#39;s scheme, to divide the data into secret shares on which the workers can perform linear computations. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We propose a solution based on new secure codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master&#39;s mean waiting time. We derive the distribution of the Master&#39;s waiting time, and its mean, for systems with up to two stragglers. For systems with any number of stragglers, we derive an expression that can give the exact distribution, and the mean, of the waiting time of the Master. We show that Staircase codes always outperform classical secret sharing codes.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Minimizing Latency for Secure Distributed Computing

We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy, or even unresponsive, and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. We focus on linear computations as an essential operation in many iterative algorithms. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. We propose to use instead new secure codes, called Staircase codes, introduced previously by two of the authors. We study the delay induced by Staircase codes which is always less than that of secret sharing. The reason is that secret sharing schemes need to wait for the responses of a fixed fraction of the workers, whereas Staircase codes offer more flexibility in this respect. For instance, for codes with rate $R=1/2$ Staircase codes can lead to up to $40\%$ reduction in delay compared to secret sharing.

0 citations0 reviewsNo code linkedOpen access