The Experts below are selected from a list of 3860694 Experts worldwide ranked by ideXlab platform

Nitin H Vaidya - One of the best experts on this subject based on the ideXlab platform.

  • exact byzantine consensus on undirected graphs under local broadcast model
    Principles of Distributed Computing, 2019
    Co-Authors: Muhammad Samir Khan, Syed Shalan Naqvi, Nitin H Vaidya
    Abstract:

    This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical Point-to-Point Communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical Point-to-Point Communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the Point-to-Point Communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least ⌋ 3 fƒ / 2 ⌊ + 1 and minimum node degree at least 2 ƒ. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the Point-to-Point Communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the Point-to-Point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.

  • exact byzantine consensus on undirected graphs under local broadcast model
    arXiv: Distributed Parallel and Cluster Computing, 2019
    Co-Authors: Muhammad Samir Khan, Syed Shalan Naqvi, Nitin H Vaidya
    Abstract:

    This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical Point-to-Point Communication model, it is well-known [7] that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among $n$ nodes in the presence of up to $f$ Byzantine faulty nodes: $n \ge 3f+1$ and vertex connectivity at least $2f+1$. In the classical Point-to-Point Communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the Point-to-Point Communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least $\lfloor 3f/2 \rfloor + 1$ and minimum node degree at least $2f$. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes $n$, as compared to the Point-to-Point Communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the Point-to-Point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.

  • multiparty equality function computation in networks with point to point links
    International Conference on Structural Information and Communication Complexity, 2011
    Co-Authors: Guanfeng Liang, Nitin H Vaidya
    Abstract:

    In this paper, we study the problem of computing the multiparty equality (MEQ) function: n ≥ 2 nodes, each of which is given an input value from {1,...,K}, determine if their inputs are all identical, under the Point-to-Point Communication model. The MEQ function equals to 1 if and only if all n inputs are identical, and 0 otherwise. The Communication complexity of the MEQ problem is defined as the minimum number of bits communicated in the worst case. It is easy to show that (n-1) log2 K bits is an upper bound, by constructing a simple algorithm with that cost. In this paper, we demonstrate that Communication cost strictly lower than this upper bound can be achieved. We show this by constructing a static protocol that solves the MEQ problem for n = 3, K = 6, of which the Communication cost is strictly lower than the above upper bound (2 log2 6 bits). This result is then generalized for large values of n and K.

  • multiparty equality function computation in networks with point to point links
    arXiv: Information Theory, 2010
    Co-Authors: Guanfeng Liang, Nitin H Vaidya
    Abstract:

    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 "number on the forehand" 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.

Jehoshua Bruck - One of the best experts on this subject based on the ideXlab platform.

  • efficient algorithms for all to all Communications in multiport message passing systems
    IEEE Transactions on Parallel and Distributed Systems, 1997
    Co-Authors: Jehoshua Bruck, Shlomo Kipnis, Eli Upfal, Derrick Weathersby
    Abstract:

    We present efficient algorithms for two all-to-all Communication operations in message-passing systems: index (or all-to-all personalized Communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any Point-to-Point Communication is independent of the sender-receiver pair. We also assume that each processor has k/spl ges/1 ports, through which it can send and receive k messages in every Communication round. The complexity measures we use are independent of the particular system topology and are based on the Communication start-up time, and on the Communication bandwidth.

  • efficient message passing interface mpi for parallel computing on clusters of workstations
    Journal of Parallel and Distributed Computing, 1997
    Co-Authors: Jehoshua Bruck, Danny Dolev, Marcelcătălin Rosu, Ray Strong
    Abstract:

    Parallel computing on clusters of workstations and personal computers has very high potential, since it leverages existing hardware and software. Parallel programming environments offer the user a convenient way to express parallel computation and Communication. In fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial standard for writing “portable” message-passing parallel programs. The Communication part of MPI consists of the usual Point-to-Point Communication as well as collective Communication. However, existing implementations of programming environments for clusters are built on top of a Point-to-Point Communication layer (send and receive) over local area networks (LANs) and, as a result, suffer from poor performance in the collective Communication part. In this paper, we present an efficient design and implementation of the collective Communication part in MPI that is optimized for clusters of workstations. Our system consists of two main components: the MPI-CCL layer that includes the collective Communication functionality of MPI and a User-Level Reliable Transport Protocol (URTP) that interfaces with the LAN Data-Link Layer and leverages the fact that the LAN is a broadcast medium. Our system is integrated with the operating system via an efficient kernel extension mechanism that we developed. The kernel extension significantly improves the performance of our implementation as it can handle part of the Communication overhead without involving user space. We have implemented our system on a collection of IBM RS/6000 workstations connected via a 10-Mbit Ethernet LAN. Our performance measurements are taken from typical scientific programs that run in a parallel mode by means of the MPI. The hypothesis behind our design is that the system's performance will be bounded by interactions between the kernel and user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our results indicate that the performance of our MPI Broadcast (on top of Ethernet) is about twice as fast as a recently published software implementation of broadcast on top of ATM.

  • efficient message passing interface mpi for parallel computing on clusters of workstations
    ACM Symposium on Parallel Algorithms and Architectures, 1995
    Co-Authors: Jehoshua Bruck, Danny Dolev, Marcelcătălin Rosu, Ray Strong
    Abstract:

    Parallel computing on clusters of workstations and personal computers has very high potential, since it leverages existing hardware and software. Parallel programming environments offer the user a convenient way to express parallel computation and Communication. In fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial standard for writing "portable" message-passing parallel programs. The Communication part of MPI consists of the usual Point-to-Point Communication as well as collective Communication. However, existing implementations of programming environments for clusters are built on top of a Point-to-Point Communication layer (send and receive) over local area networks (LANs) and, as a result, suffer from poor performance in the collective Communication part. In this paper, we present an efficient design and implementation of the collective Communication part in MPI that is optimized for clusters of workstations. Our system consists of two main components: the MPI-CCL layer that includes the collective Communication functionality of MPI and a User-level Reliable Transport Protocol (URTP) that interfaces with the LAN Data-link layer and leverages the fact that the LAN is a broadcast medium. Our system is integrated with the operating system via an efficient kernel extension mechanism that we developed. The kernel extension significantly improves the performance of our implementation as it can handle part of the Communication overhead without involving user space. We have implemented our system on a collection of IBM RS/6000 workstations con- nected via a lOMbit Ethernet LAN. Our performance measurements are taken from typical scientific programs that run in a parallel mode by means of the MPI. The hypothesis behind our design is that system's performance will be bounded by interactions between the kernel and user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our results indicate that the performance of our MPI Broadcast (on top of Ethernet) is about twice as fast as a recently published software implementation of broadcast on top of ATM.

Ray Strong - One of the best experts on this subject based on the ideXlab platform.

  • efficient message passing interface mpi for parallel computing on clusters of workstations
    Journal of Parallel and Distributed Computing, 1997
    Co-Authors: Jehoshua Bruck, Danny Dolev, Marcelcătălin Rosu, Ray Strong
    Abstract:

    Parallel computing on clusters of workstations and personal computers has very high potential, since it leverages existing hardware and software. Parallel programming environments offer the user a convenient way to express parallel computation and Communication. In fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial standard for writing “portable” message-passing parallel programs. The Communication part of MPI consists of the usual Point-to-Point Communication as well as collective Communication. However, existing implementations of programming environments for clusters are built on top of a Point-to-Point Communication layer (send and receive) over local area networks (LANs) and, as a result, suffer from poor performance in the collective Communication part. In this paper, we present an efficient design and implementation of the collective Communication part in MPI that is optimized for clusters of workstations. Our system consists of two main components: the MPI-CCL layer that includes the collective Communication functionality of MPI and a User-Level Reliable Transport Protocol (URTP) that interfaces with the LAN Data-Link Layer and leverages the fact that the LAN is a broadcast medium. Our system is integrated with the operating system via an efficient kernel extension mechanism that we developed. The kernel extension significantly improves the performance of our implementation as it can handle part of the Communication overhead without involving user space. We have implemented our system on a collection of IBM RS/6000 workstations connected via a 10-Mbit Ethernet LAN. Our performance measurements are taken from typical scientific programs that run in a parallel mode by means of the MPI. The hypothesis behind our design is that the system's performance will be bounded by interactions between the kernel and user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our results indicate that the performance of our MPI Broadcast (on top of Ethernet) is about twice as fast as a recently published software implementation of broadcast on top of ATM.

  • efficient message passing interface mpi for parallel computing on clusters of workstations
    ACM Symposium on Parallel Algorithms and Architectures, 1995
    Co-Authors: Jehoshua Bruck, Danny Dolev, Marcelcătălin Rosu, Ray Strong
    Abstract:

    Parallel computing on clusters of workstations and personal computers has very high potential, since it leverages existing hardware and software. Parallel programming environments offer the user a convenient way to express parallel computation and Communication. In fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial standard for writing "portable" message-passing parallel programs. The Communication part of MPI consists of the usual Point-to-Point Communication as well as collective Communication. However, existing implementations of programming environments for clusters are built on top of a Point-to-Point Communication layer (send and receive) over local area networks (LANs) and, as a result, suffer from poor performance in the collective Communication part. In this paper, we present an efficient design and implementation of the collective Communication part in MPI that is optimized for clusters of workstations. Our system consists of two main components: the MPI-CCL layer that includes the collective Communication functionality of MPI and a User-level Reliable Transport Protocol (URTP) that interfaces with the LAN Data-link layer and leverages the fact that the LAN is a broadcast medium. Our system is integrated with the operating system via an efficient kernel extension mechanism that we developed. The kernel extension significantly improves the performance of our implementation as it can handle part of the Communication overhead without involving user space. We have implemented our system on a collection of IBM RS/6000 workstations con- nected via a lOMbit Ethernet LAN. Our performance measurements are taken from typical scientific programs that run in a parallel mode by means of the MPI. The hypothesis behind our design is that system's performance will be bounded by interactions between the kernel and user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our results indicate that the performance of our MPI Broadcast (on top of Ethernet) is about twice as fast as a recently published software implementation of broadcast on top of ATM.

Aris L. Moustakas - One of the best experts on this subject based on the ideXlab platform.

  • optimizing multiple input single output miso Communication systems with general gaussian channels nontrivial covariance and nonzero mean
    IEEE Transactions on Information Theory, 2003
    Co-Authors: Aris L. Moustakas, Steven H. Simon
    Abstract:

    We consider a narrow-band Point-to-Point Communication system with many (input) transmitters and a single (output) receiver (i.e., a multiple-input single output (MISO) system). We assume the receiver has perfect knowledge of the channel but the transmitter only knows the channel distribution. We focus on two canonical classes of Gaussian channel models: (a) the channel has zero mean with a fixed covariance matrix and (b) the channel has nonzero mean with covariance matrix proportional to the identity. In both cases, we are able to derive simple analytic expressions for the ergodic average and the cumulative distribution function (c.d.f.) of the mutual information for arbitrary input (transmission) signal covariance. With minimal numerical effort, we then determine the ergodic and outage capacities and the corresponding capacity-achieving input signal covariances. Interestingly, we find that the optimal signal covariances for the ergodic and outage cases have very different behavior. In particular, under certain conditions, the outage capacity optimal covariance is a discontinuous function of the parameters describing the channel (such as strength of the correlations or the nonzero mean of the channel).

  • Optimizing MIMO antenna systems with channel covariance feedback
    IEEE Journal on Selected Areas in Communications, 2003
    Co-Authors: Steven H. Simon, Aris L. Moustakas
    Abstract:

    We consider a narrowband Point-to-Point Communication system with nT transmitters and nR receivers. We assume the receiver has perfect knowledge of the channel, while the transmitter has no channel knowledge. We consider the case where the receiving antenna array has uncorrelated elements, while the elements of the transmitting array are arbitrarily correlated. Focusing on the case where nT=2, we derive simple analytic expressions for the ergodic average and the cumulative distribution function of the mutual information for arbitrary input (transmission) signal covariance. We then determine the ergodic and outage capacities and the associated optimal input signal covariances. We thus show how a transmitter with covariance knowledge should correlate its transmissions to maximize throughput. These results allow us to derive an exact condition (both necessary and sufficient) that determines when beamforming is optimal for systems with arbitrary number of transmitters and receivers.

Xiaodong Wang - One of the best experts on this subject based on the ideXlab platform.

  • on the capacity of energy harvesting Communication link
    IEEE Journal on Selected Areas in Communications, 2015
    Co-Authors: Mehdi Ashraphijuo, Vaneet Aggarwal, Xiaodong Wang
    Abstract:

    We consider an energy harvesting Point-to-Point Communication system where the transmitter is powered by an energy arrival process and is equipped with a battery of finite capacity $B_{\max}$ , which could be used for saving energy for future use. We assume a discrete i.i.d. energy arrival process where at each time step, energy of amount $A_i$ is harvested with probability $p_i$ $\forall i \in \{1, 2, \ldots, K\}$ independent of the other time steps. We provide upper and lower bounds on the capacity of this channel. These bounds are shown to be within a constant gap for $K\le 3$ for all parameters, and for $K > 3$ when the battery capacity $B_{\max}$ is small or large enough, where this constant does not depend on any energy or battery parameters.