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

Nitin Vaidya

Nitin Vaidya contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingCryptography and SecurityInformation Theorymath.ITNetworking and Internet Architecture

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
19works
0followers
5topics
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

19 published item(s)

preprint2022arXiv

Impact of the Consistency Model on Checkpointing of Distributed Shared Memory

In this report, we consider the impact of the consistency model on checkpointing and rollback algorithms for distributed shared memory. In particular, we consider specific implementations of four consistency models for distributed shared memory, namely, linearizability, sequential consistency, causal consistency and eventual consistency, and develop checkpointing and rollback algorithms that can be integrated into the implementations of the consistency models. Our results empirically demonstrate that the mechanisms used to implement stronger consistency models lead to simpler or more efficient checkpointing algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Differentially Private Distributed Optimization

In distributed optimization and iterative consensus literature, a standard problem is for $N$ agents to minimize a function $f$ over a subset of Euclidean space, where the cost function is expressed as a sum $\sum f_i$. In this paper, we study the private distributed optimization (PDOP) problem with the additional requirement that the cost function of the individual agents should remain differentially private. The adversary attempts to infer information about the private cost functions from the messages that the agents exchange. Achieving differential privacy requires that any change of an individual's cost function only results in unsubstantial changes in the statistics of the messages. We propose a class of iterative algorithms for solving PDOP, which achieves differential privacy and convergence to the optimal value. Our analysis reveals the dependence of the achieved accuracy and the privacy levels on the the parameters of the algorithm. We observe that to achieve $ε$-differential privacy the accuracy of the algorithm has the order of $O(\frac{1}{ε^2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exact Byzantine Consensus in Directed Graphs

Consider a synchronous point-to-point network of n nodes connected by directed links, wherein each node has a binary input. This paper proves a tight necessary and sufficient condition on the underlying communication topology for achieving Byzantine consensus among these nodes in the presence of up to f Byzantine faults. We derive a necessary condition, and then we provide a constructive proof of sufficiency by presenting a Byzantine consensus algorithm for directed graphs that satisfy the necessary condition. Prior work has developed analogous necessary and sufficient conditions for undirected graphs. It is known that, for undirected graphs, the following two conditions are together necessary and sufficient [8, 2, 6]: (i) n ? 3f + 1, and (ii) network connectivity greater than 2f. However, these conditions are not adequate to completely characterize Byzantine consensus in directed graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimal CSMA-based Wireless Communication with Worst-case Delay and Non-uniform Sizes

Carrier Sense Multiple Access (CSMA) protocols have been shown to reach the full capacity region for data communication in wireless networks, with polynomial complexity. However, current literature achieves the throughput optimality with an exponential delay scaling with the network size, even in a simplified scenario for transmission jobs with uniform sizes. Although CSMA protocols with order-optimal average delay have been proposed for specific topologies, no existing work can provide worst-case delay guarantee for each job in general network settings, not to mention the case when the jobs have non-uniform lengths while the throughput optimality is still targeted. In this paper, we tackle on this issue by proposing a two-timescale CSMA-based data communication protocol with dynamic decisions on rate control, link scheduling, job transmission and dropping in polynomial complexity. Through rigorous analysis, we demonstrate that the proposed protocol can achieve a throughput utility arbitrarily close to its offline optima for jobs with non-uniform sizes and worst-case delay guarantees, with a tradeoff of longer maximum allowable delay.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Broadcast Using Certified Propagation Algorithm in Presence of Byzantine Faults

We explore the correctness of the Certified Propagation Algorithm (CPA) [6, 1, 8, 5] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA. To the best of our knowledge, this work is the first to solve the open problem in [8]. We also present some simple extensions of this result

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Byzantine Convex Consensus: An Optimal Algorithm

Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [9, 13]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [9, 13] require the fault-free nodes to decide on a point in the d-dimensional space. In our recent work [arXiv:/1307.1051], we proposed a generalization of the consensus problem, namely Byzantine convex consensus (BCC), which allows the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerance that also agrees on a convex polytope that is as large as possible under adversarial conditions. Our prior work [arXiv:/1307.1051] does not guarantee the optimality of the output polytope.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Byzantine Convex Consensus: Preliminary Version

Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [3, 7]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [8, 12]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [8, 12] require the fault-free nodes to decide on a point in the d-dimensional space. In this paper, we generalize the problem to allow the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We name this problem as Byzantine convex consensus (BCC), and present an asynchronous approximate BCC algorithm with optimal fault tolerance. Ideally, the goal here is to agree on a convex polytope that is as large as possible. While we do not claim that our algorithm satisfies this goal, we show a bound on the output convex polytope chosen by our algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding

The goal of Byzantine Broadcast (BB) is to allow a set of fault-free nodes to agree on information that a source node wants to broadcast to them, in the presence of Byzantine faulty nodes. We consider design of efficient algorithms for BB in {\em synchronous} point-to-point networks, where the rate of transmission over each communication link is limited by its &#34;link capacity&#34;. The throughput of a particular BB algorithm is defined as the average number of bits that can be reliably broadcast to all fault-free nodes per unit time using the algorithm without violating the link capacity constraints. The {\em capacity} of BB in a given network is then defined as the supremum of all achievable BB throughputs in the given network, over all possible BB algorithms. We develop NAB -- a Network-Aware Byzantine broadcast algorithm -- for arbitrary point-to-point networks consisting of $n$ nodes, wherein the number of faulty nodes is at most $f$, $f<n/3$, and the network connectivity is at least $2f+1$. We also prove an upper bound on the capacity of Byzantine broadcast, and conclude that NAB can achieve throughput at least 1/3 of the capacity. When the network satisfies an additional condition, NAB can achieve throughput at least 1/2 of the capacity. To the best of our knowledge, NAB is the first algorithm that can achieve a constant fraction of capacity of Byzantine Broadcast (BB) in arbitrary point-to-point networks.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs - Part II: Synchronous and Asynchronous Systems

This report contains two related sets of results with different assumptions on synchrony. The first part is about iterative algorithms in synchronous systems. Following our previous work on synchronous iterative approximate Byzantine consensus (IABC) algorithms, we provide a more intuitive tight necessary and sufficient condition for the existence of such algorithms in synchronous networks1. We believe this condition and the previous results also hold in partially asynchronous algorithmic model. In the second part of the report, we explore the problem in asynchronous networks. While the traditional Byzantine consensus is not solvable in asynchronous systems, approximate Byzantine consensus can be solved using iterative algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Iterative Approximate Byzantine Consensus under a Generalized Fault Model

In this work, we consider a generalized fault model that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. This fault model is general in the sense that fault models studied in prior related work, such as f -total and f -local models, are special cases of the generalized fault model. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms in arbitrary directed networks. We prove a necessary and sufficient condition for the existence of IABC algorithms. The use of the generalized fault model helps to gain a better understanding of IABC algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Token-DCF: An Opportunistic MAC protocol for Wireless Networks

IEEE 802.11 DCF is the MAC protocol currently used in wireless LANs. 802.11 DCF is inefficient due to two types of overhead; channel idle time and collision time. This paper presents the design and performance evaluation of an efficient MAC protocol for wireless networks, called Token-DCF. Token-DCF decreases both idle time and collision time. In Token-DCF, each station keeps track of neighboring links&#39; queue length by overhearing of transmitted packets on the wireless medium. The result is then used to assign privileges to the network stations. A privileged station does not follow the backoff mechanism and transmits immediately after the channel is sensed idle. Our simulation results show that Token-DCF can significantly improve channel utilization, system throughput and channel access delay over 802.11 DCF.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links

We consider the problem of maximizing the throughput of Byzantine consensus, when communication links have finite capacity. Byzantine consensus is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of consensus, and identify upper bound of achievable consensus throughput. We propose an algorithm that achieves consensus capacity in complete four-node networks with at most 1 failure with arbitrary distribution of link capacities.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Error-Free Multi-Valued Consensus with Byzantine Failures

In this paper, we present an efficient deterministic algorithm for consensus in presence of Byzantine failures. Our algorithm achieves consensus on an $L$-bit value with communication complexity $O(nL + n^4 L^{0.5} + n^6)$ bits, in a network consisting of $n$ processors with up to $t$ Byzantine failures, such that $t<n/3$. For large enough $L$, communication complexity of the proposed algorithm approaches $O(nL)$ bits. In other words, for large $L$, the communication complexity is linear in the number of processors in the network. This is an improvement over the work of Fitzi and Hirt (from PODC 2006), who proposed a probabilistically correct multi-valued Byzantine consensus algorithm with a similar complexity for large $L$. In contrast to the algorithm by Fitzi and Hirt, our algorithm is guaranteed to be always error-free. Our algorithm require no cryptographic technique, such as authentication, nor any secret sharing mechanism. To the best of our knowledge, we are the first to show that, for large $L$, error-free multi-valued Byzantine consensus on an $L$-bit value is achievable with $O(nL)$ bits of communication.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

New Efficient Error-Free Multi-Valued Consensus with Byzantine Failures

In this report, we investigate the multi-valued Byzantine consensus problem. We introduce two algorithms: the first one achieves traditional validity requirement for consensus, and the second one achieves a stronger &#34;q-validity&#34; requirement. Both algorithms are more efficient than the ones introduces in our recent PODC 2011 paper titled &#34;Error-Free Multi-Valued Consensus with Byzantine Failures&#34;.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Complexity of Multi-Value Byzantine Agreement

In this paper, we consider the problem of maximizing the throughput of Byzantine agreement, given that the sum capacity of all links in between nodes in the system is finite. We have proposed a highly efficient Byzantine agreement algorithm on values of length l>1 bits. This algorithm uses error detecting network codes to ensure that fault-free nodes will never disagree, and routing scheme that is adaptive to the result of error detection. Our algorithm has a bit complexity of n(n-1)l/(n-t), which leads to a linear cost (O(n)) per bit agreed upon, and overcomes the quadratic lower bound (Omega(n^2)) in the literature. Such linear per bit complexity has only been achieved in the literature by allowing a positive probability of error. Our algorithm achieves the linear per bit complexity while guaranteeing agreement is achieved correctly even in the worst case. We also conjecture that our algorithm can be used to achieve agreement throughput arbitrarily close to the agreement capacity of a network, when the sum capacity is given.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic Consensus Algorithm with Linear Per-Bit Complexity

In this report, building on the deterministic multi-valued one-to-many Byzantine agreement (broadcast) algorithm in our recent technical report [2], we introduce a deterministic multi-valued all-to-all Byzantine agreement algorithm (consensus), with linear complexity per bit agreed upon. The discussion in this note is not self-contained, and relies heavily on the material in [2] - please refer to [2] for the necessary background.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Multiparty Equality Function Computation in Networks with Point-to-Point Links

In this report, we study the multiparty communication complexity problem of the multiparty equality function (MEQ): EQ(x_1,...,x_n) = 1 if x_1=...=x_n, and 0 otherwise. The input vector (x_1,...,x_n) is distributed among n>=2 nodes, with x_i known to node i, where x_i is chosen from the set {1,...,M}, for some integer M>0. Instead of the &#34;number on the forehand&#34; model, we consider a point-to-point communication model (similar to the message passing model), which we believe is more realistic in networking settings. We assume a synchronous fully connected network of n nodes, the node IDs (identifiers) are common knowledge. We assume that all point-to-point communication channels/links are private such that when a node transmits, only the designated recipient can receive the message. The identity of the sender is known to the recipient. We demonstrate that traditional techniques generalized from two-party communication complexity problem are not sufficient to obtain tight bounds under the point-to-point communication model. We then introduce techniques which significantly reduce the space of protocols to study. These techniques are used to study some instances of the MEQ problem.

0 citations0 reviewsNo code linkedOpen access