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

Nitin H. Vaidya

Nitin H. Vaidya appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster Computingmath.OCMachine LearningSystems and ControlCryptography and SecurityData Structures and Algorithmseess.SYMultiagent SystemsSocial and Information Networks

Catalog footprint

What is connected

19works
9topics
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

19 published item(s)

preprint2021arXiv

Byzantine Fault-Tolerance in Peer-to-Peer Distributed Gradient-Descent

We consider the problem of Byzantine fault-tolerance in the peer-to-peer (P2P) distributed gradient-descent method -- a prominent algorithm for distributed optimization in a P2P system. In this problem, the system comprises of multiple agents, and each agent has a local cost function. In the fault-free case, when all the agents are honest, the P2P distributed gradient-descent method allows all the agents to reach a consensus on a solution that minimizes their aggregate cost. However, we consider a scenario where a certain number of agents may be Byzantine faulty. Such faulty agents may not follow an algorithm correctly, and may share arbitrary incorrect information to prevent other non-faulty agents from solving the optimization problem. In the presence of Byzantine faulty agents, a more reasonable goal is to allow all the non-faulty agents to reach a consensus on a solution that minimizes the aggregate cost of all the non-faulty agents. We refer to this fault-tolerance goal as $f$-resilience where $f$ is the maximum number of Byzantine faulty agents in a system of $n$ agents, with $f < n$. Most prior work on fault-tolerance in P2P distributed optimization only consider approximate fault-tolerance wherein, unlike $f$-resilience, all the non-faulty agents' compute a minimum point of a non-uniformly weighted aggregate of their cost functions. We propose a fault-tolerance mechanism that confers provable $f$-resilience to the P2P distributed gradient-descent method, provided the non-faulty agents satisfy the necessary condition of $2f$-redundancy, defined later in the paper. Moreover, compared to prior work, our algorithm is applicable to a larger class of high-dimensional convex distributed optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Private and Finite-Time Algorithm for Solving a Distributed System of Linear Equations

This paper studies a system of linear equations, denoted as $Ax = b$, which is horizontally partitioned (rows in $A$ and $b$) and stored over a network of $m$ devices connected in a fixed directed graph. We design a fast distributed algorithm for solving such a partitioned system of linear equations, that additionally, protects the privacy of local data against an honest-but-curious adversary that corrupts at most $τ$ nodes in the network. First, we present TITAN, privaTe fInite Time Average coNsensus algorithm, for solving a general average consensus problem over directed graphs, while protecting statistical privacy of private local data against an honest-but-curious adversary. Second, we propose a distributed linear system solver that involves each agent/devices computing an update based on local private data, followed by private aggregation using TITAN. Finally, we show convergence of our solver to the least squares solution in finite rounds along with statistical privacy of local linear equations against an honest-but-curious adversary provided the graph has weak vertex-connectivity of at least $τ+1$. We perform numerical experiments to validate our claims and compare our solution to the state-of-the-art methods by comparing computation, communication and memory costs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asynchronous Byzantine Approximate Consensus in Directed Networks

In this work, we study the approximate consensus problem in asynchronous message-passing networks where some nodes may become Byzantine faulty. We answer an open problem raised by Tseng and Vaidya, 2012, proposing the first algorithm of optimal resilience for directed networks. Interestingly, our results show that the tight condition on the underlying communication networks for asynchronous Byzantine approximate consensus coincides with the tight condition for synchronous Byzantine exact consensus. Our results can be viewed as a non-trivial generalization of the algorithm by Abraham et al., 2004, which applies to the special case of complete networks. The tight condition and techniques identified in the paper shed light on the fundamental properties for solving approximate consensus in asynchronous directed networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Preserving Statistical Privacy in Distributed Optimization

We present a distributed optimization protocol that preserves statistical privacy of agents' local cost functions against a passive adversary that corrupts some agents in the network. The protocol is a composition of a distributed ``{\em zero-sum}" obfuscation protocol that obfuscates the agents' local cost functions, and a standard non-private distributed optimization method. We show that our protocol protects the statistical privacy of the agents' local cost functions against a passive adversary that corrupts up to $t$ arbitrary agents as long as the communication network has $(t+1)$-vertex connectivity. The ``{\em zero-sum}" obfuscation protocol preserves the sum of the agents' local cost functions and therefore ensures accuracy of the computed solution.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Resilience in Collaborative Optimization: Redundant and Independent Cost Functions

This report considers the problem of Byzantine fault-tolerance in multi-agent collaborative optimization. In this problem, each agent has a local cost function. The goal of a collaborative optimization algorithm is to compute a minimum of the aggregate of the agents' cost functions. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may send arbitrary or incorrect information regarding their local cost functions. A reasonable goal in presence of such faulty agents is to minimize the aggregate cost of the non-faulty agents. In this report, we show that this goal can be achieved if and only if the cost functions of the non-faulty agents have a minimal redundancy property. We present different algorithms that achieve such tolerance against faulty agents, and demonstrate a trade-off between the complexity of an algorithm and the properties of the agents' cost functions. Further, we also consider the case when the cost functions are independent or do not satisfy the minimal redundancy property. In that case, we quantify the tolerance against faulty agents by introducing a metric called weak resilience. We present an algorithm that attains weak resilience when the faulty agents are in the minority and the cost functions are non-negative.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Defending Non-Bayesian Learning against Adversarial Attacks

This paper addresses the problem of non-Bayesian learning over multi-agent networks, where agents repeatedly collect partially informative observations about an unknown state of the world, and try to collaboratively learn the true state. We focus on the impact of the adversarial agents on the performance of consensus-based non-Bayesian learning, where non-faulty agents combine local learning updates with consensus primitives. In particular, we consider the scenario where an unknown subset of agents suffer Byzantine faults -- agents suffering Byzantine faults behave arbitrarily. Two different learning rules are proposed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Optimization for Client-Server Architecture with Negative Gradient Weights

Availability of both massive datasets and computing resources have made machine learning and predictive analytics extremely pervasive. In this work we present a synchronous algorithm and architecture for distributed optimization motivated by privacy requirements posed by applications in machine learning. We present an algorithm for the recently proposed multi-parameter-server architecture. We consider a group of parameter servers that learn a model based on randomized gradients received from clients. Clients are computational entities with private datasets (inducing a private objective function), that evaluate and upload randomized gradients to the parameter servers. The parameter servers perform model updates based on received gradients and share the model parameters with other servers. We prove that the proposed algorithm can optimize the overall objective function for a very general architecture involving $C$ clients connected to $S$ parameter servers in an arbitrary time varying topology and the parameter servers forming a connected network.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Optimization of Convex Sum of Non-Convex Functions

We present a distributed solution to optimizing a convex function composed of several non-convex functions. Each non-convex function is privately stored with an agent while the agents communicate with neighbors to form a network. We show that coupled consensus and projected gradient descent algorithm proposed in [1] can optimize convex sum of non-convex functions under an additional assumption on gradient Lipschitzness. We further discuss the applications of this analysis in improving privacy in distributed optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient Timestamps for Capturing Causality

Consider an asynchronous system consisting of processes that communicate via message-passing. The processes communicate over a potentially {\em incomplete} communication network consisting of reliable bidirectional communication channels. Thus, not every pair of processes is necessarily able to communicate with each other directly. % For instance, when the communication network is a {\em star} graph, there is a {\em central} process % that can communicate with all the remaining processes (which are called {\em radial} processes), % but the radial processes cannot communicate with each other directly. The goal of the algorithms discussed in this paper is to assign timestamps to the events at all the processes such that (a) distinct events are assigned distinct timestamps, and (b) the happened-before relationship between the events can be inferred from the timestamps. We consider three types of algorithms for assigning timestamps to events: (i) Online algorithms that must (greedily) assign a timestamp to each event when the event occurs. (ii) Offline algorithms that assign timestamps to event after a finite execution is complete. (iii) Inline algorithms that assign a timestamp to each event when it occurs, but may modify some elements of a timestamp again at a later time. For specific classes of graphs, particularly {\em star} graphs and graphs with connectivity $\geq 1$, the paper presents bounds on the length of vector timestamps assigned by an {\em online} algorithm. The paper then presents an {\em inline} algorithm, which typically assigns substantially smaller timestamps than the optimal-length {\em online} vector timestamps. In particular, the inline algorithm assigns timestamp in the form of a tuple containing $2c+2$ integer elements, where $c$ is the size of the vertex cover for the underlying communication graph.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Private Learning on Networks

Continual data collection and widespread deployment of machine learning algorithms, particularly the distributed variants, have raised new privacy challenges. In a distributed machine learning scenario, the dataset is stored among several machines and they solve a distributed optimization problem to collectively learn the underlying model. We present a secure multi-party computation inspired privacy preserving distributed algorithm for optimizing a convex function consisting of several possibly non-convex functions. Each individual objective function is privately stored with an agent while the agents communicate model parameters with neighbor machines connected in a network. We show that our algorithm can correctly optimize the overall objective function and learn the underlying model accurately. We further prove that under a vertex connectivity condition on the topology, our algorithm preserves privacy of individual objective functions. We establish limits on the what a coalition of adversaries can learn by observing the messages and states shared over a network.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Relaxed Byzantine Vector Consensus

Exact Byzantine consensus problem requires that non-faulty processes reach agreement on a decision (or output) that is in the convex hull of the inputs at the non-faulty processes. It is well-known that exact consensus is impossible in an asynchronous system in presence of faults, and in a synchronous system, n>=3f+1 is tight on the number of processes to achieve exact Byzantine consensus with scalar inputs, in presence of up to f Byzantine faulty processes. Recent work has shown that when the inputs are d-dimensional vectors of reals, n>=max(3f+1,(d+1)f+1) is tight to achieve exact Byzantine consensus in synchronous systems, and n>= (d+2)f+1 for approximate Byzantine consensus in asynchronous systems. Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we consider two relaxed versions of Byzantine vector consensus: k-Relaxed Byzantine vector consensus and (delta,p)-Relaxed Byzantine vector consensus. In k-relaxed consensus, the validity condition requires that the output must be in the convex hull of projection of the inputs onto any subset of k-dimensions of the vectors. For (delta,p)-consensus the validity condition requires that the output must be within distance delta of the convex hull of the inputs of the non-faulty processes, where L_p norm is used as the distance metric. For (delta,p)-consensus, we consider two versions: in one version, delta is a constant, and in the second version, delta is a function of the inputs themselves. We show that for k-relaxed consensus and (delta,p)-consensus with constant delta>=0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when delta depends on the inputs, we show that the bound on n is smaller when d>=3.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Timestamps for Partial Replication

Maintaining causal consistency in distributed shared memory systems using vector timestamps has received a lot of attention from both theoretical and practical prospective. However, most of the previous literature focuses on full replication where each data is stored in all replicas, which may not be scalable due to the increasing amount of data. In this report, we investigate how to achieve causal consistency in partial replicated systems, where each replica may store different set of data. We propose an algorithm that tracks causal dependencies via vector timestamp in client-server model for partial replication. The cost of our algorithm in terms of timestamps size varies as a function of the manner in which the replicas share data, and the set of replicas accessed by each client. We also establish a connection between our algorithm with the previous work on full replication.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Application-Aware Consistency: An Application to Social Network

This work weakens well-known consistency models using graphs that capture applications' characteristics. The weakened models not only respect application semantic, but also yield a performance benefit. We introduce a notion of dependency graphs, which specify relations between events that are important with respect to application semantic, and then weaken traditional consistency models (e.g., causal consistency) using these graphs. Particularly, we consider two types of graphs: intra-process and inter-process dependency graphs, where intra-process dependency graphs specify how events in a single process are related, and inter-process dependency graphs specify how events across multiple processes are related. Then, based on these two types of graphs, we define new consistency model, namely {\em application-aware} consistency. We also discuss why such application-aware consistency can be useful in social network applications. This is a work in progress, and we present early ideas regarding application-aware consistency here.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks

We study the problem of constrained distributed optimization in multi-agent networks when some of the computing agents may be faulty. In this problem, the system goal is to have all the non-faulty agents collectively minimize a global objective given by weighted average of local cost functions, each of which is initially known to a non-faulty agent only. In particular, we are interested in the scenario when the computing agents are connected by an arbitrary directed communication network, some of the agents may suffer from crash faults or Byzantine faults, and the estimate of each agent is restricted to lie in a common constraint set. This problem finds its applications in social computing and distributed large-scale machine learning. The fault-tolerant multi-agent optimization problem was first formulated by Su and Vaidya, and is solved when the local functions are defined over the whole real line, and the networks are fully-connected. In this report, we consider arbitrary directed communication networks and focus on the scenario where, local estimates at the non-faulty agents are constrained, and only local communication and minimal memory carried across iterations are allowed. In particular, we generalize our previous results on fully-connected networks and unconstrained optimization to arbitrary directed networks and constrained optimization. As a byproduct, we provide a matrix representation for iterative approximate crash consensus. The matrix representation allows us to characterize the convergence rate for crash iterative consensus.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Byzantine Vector Consensus in Complete Graphs

Consider a network of n processes each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out). The problem of Byzantine vector consensus (BVC) requires agreement on a d-dimensional vector that is in the convex hull of the d-dimensional input vectors at the non-faulty processes. We obtain the following results for Byzantine vector consensus in complete graphs while tolerating up to f Byzantine failures: * We prove that in a synchronous system, n >= max(3f+1, (d+1)f+1) is necessary and sufficient for achieving Byzantine vector consensus. * In an asynchronous system, it is known that exact consensus is impossible in presence of faulty processes. For an asynchronous system, we prove that n >= (d+2)f+1 is necessary and sufficient to achieve approximate Byzantine vector consensus. Our sufficiency proofs are constructive. We show sufficiency by providing explicit algorithms that solve exact BVC in synchronous systems, and approximate BVC in asynchronous systems. We also obtain tight bounds on the number of processes for achieving BVC using algorithms that are restricted to a simpler communication pattern.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Iterative Byzantine Vector Consensus in Incomplete Graphs

This work addresses Byzantine vector consensus (BVC), wherein the input at each process is a d-dimensional vector of reals, and each process is expected to decide on a decision vector that is in the convex hull of the input vectors at the fault-free processes [3, 8]. The input vector at each process may also be viewed as a point in the d-dimensional Euclidean space R^d, where d > 0 is a finite integer. Recent work [3, 8] has addressed Byzantine vector consensus in systems that can be modeled by a complete graph. This paper considers Byzantine vector consensus in incomplete graphs. In particular, we address a particular class of iterative algorithms in incomplete graphs, and prove a necessary condition, and a sufficient condition, for the graphs to be able to solve the vector consensus problem iteratively. We present an iterative Byzantine vector consensus algorithm, and prove it correct under the sufficient condition. The necessary condition presented in this paper for vector consensus does not match with the sufficient condition for d > 1; thus, a weaker condition may potentially suffice for Byzantine vector consensus.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links - Part I: Statistical Moments Analysis Approach

This two-part paper discusses robustification methodologies for linear-iterative distributed algorithms for consensus and coordination problems in multicomponent systems, in which unreliable communication links may drop packets. We consider a setup where communication links between components can be asymmetric (i.e., component j might be able to send information to component i, but not necessarily vice-versa), so that the information exchange between components in the system is in general described by a directed graph that is assumed to be strongly connected. In the absence of communication link failures, each component i maintains two auxiliary variables and updates each of their values to be a linear combination of their corresponding previous values and the corresponding previous values of neighboring components (i.e., components that send information to node i). By appropriately initializing these two (decoupled) iterations, the system components can asymptotically calculate variables of interest in a distributed fashion; in particular, the average of the initial conditions can be calculated as a function that involves the ratio of these two auxiliary variables. The focus of this paper to robustify this double-iteration algorithm against communication link failures. We achieve this by modifying the double-iteration algorithm (by introducing some additional auxiliary variables) and prove that the modified double-iteration converges almost surely to average consensus. In the first part of the paper, we study the first and second moments of the two iterations, and use them to establish convergence, and illustrate the performance of the algorithm with several numerical examples. In the second part, in order to establish the convergence of the algorithm, we use coefficients of ergodicity commonly used in analyzing inhomogeneous Markov chains.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links - Part II: Coefficients of Ergodicity Analysis Approach

In this two-part paper, we consider multicomponent systems in which each component can iteratively exchange information with other components in its neighborhood in order to compute, in a distributed fashion, the average of the components' initial values or some other quantity of interest (i.e., some function of these initial values). In particular, we study an iterative algorithm for computing the average of the initial values of the nodes. In this algorithm, each component maintains two sets of variables that are updated via two identical linear iterations. The average of the initial values of the nodes can be asymptotically computed by each node as the ratio of two of the variables it maintains. In the first part of this paper, we show how the update rules for the two sets of variables can be enhanced so that the algorithm becomes tolerant to communication links that may drop packets, independently among them and independently between different transmission times. In this second part, by rewriting the collective dynamics of both iterations, we show that the resulting system is mathematically equivalent to a finite inhomogenous Markov chain whose transition matrix takes one of finitely many values at each step. Then, by using e a coefficients of ergodicity approach, a method commonly used for convergence analysis of Markov chains, we prove convergence of the robustified consensus scheme. The analysis suggests that similar convergence should hold under more general conditions as well.

0 citations0 reviewsNo code linkedOpen access