Now showing 1 - 10 of 16
  • Placeholder Image
    Publication
    Byzantine Agreement and Leader Election: From Classical to the Modern
    (21-07-2021) ;
    Molla, Anisur Rahaman
    ;
    Pandurangan, Gopal
    We will present the fundamentals of Byzantine agreement and leader election problems from a modern perspective. Byzantine fault tolerant protocols are at the heart of secure and robust protocols that can tolerate the presence of malicious nodes in a distributed system, such as a Peer-to-Peer (P2P) network, which allows a large number of peers to enter the network with little or no admission control. Such malicious peers acting alone or in collaboration can cause disruption of service in P2P systems. Our tutorial is largely inspired by recent P2P applications like Blockchain and cryptocurrencies that espouse permissionless settings whereby peers can anonymously and dynamically join and leave the network at will. Our presentation will be in three parts. In the first part, we will present the historic foundations of Byzantine agreement and leader election and describe the fundamentals that underlie our modern understanding of these problems. Much of the classical results focus on complete networks where nodes have global knowledge. In the second part, motivated by real-world distributed networks such as P2P networks which are typically sparse and bounded degree with nodes having only local knowledge, we focus on Byzantine protocols for sparse networks. While the first two parts will focus on static settings, motivated by modern applications such as blockchains and cryptocurrencies which operate on dynamic P2P networks, the third part will delve into Byzantine procotols for dynamic networks where nodes continuously join and leave the system. The tutorial will cover various tools and techniques that are useful in designing Byzantine protocols in sparse and dynamic networks and will discuss key open problems in the area.
  • Placeholder Image
    Publication
    Towards robust and efficient computation in dynamic Peer-to-Peer networks
    (01-01-2012) ;
    Pandurangan, Gopal
    ;
    Robinson, Peter
    ;
    Upfal, Eli
    Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: 1. An O (log 2 n)-round (n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i.e., en, for some small constant ε > 0), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm). 2. An O(log m log3 n)-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks. Copyright © SIAM.
  • Placeholder Image
    Publication
    Storage and search in dynamic peer-to-peer networks
    (01-01-2013) ;
    Molla, Anisur Rahaman
    ;
    Morsy, Ehab
    ;
    Pandurangan, Gopal
    ;
    Robinson, Peter
    ;
    Upfal, Eli
    We study robust and efficient distributed algorithms for searching, storing, and maintaining data in dynamic Peer-to-Peer (P2P) networks. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to guarantee, despite high node churn rate, that a large number of nodes in the network can store, retrieve, and maintain a large number of data items. Our main contributions are fast randomized distributed algorithms that guarantee the above with high probability even under high adversarial churn. In particular, we present the following main results: 1. A randomized distributed search algorithm that with high probability guarantees that searches from as many as n - o(n) nodes (n is the stable network size) succeed in O(log n)-rounds despite 0(n/ log1+δ n) churn, for any small constant δ > 0, per round. We assume that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join © 2013 ACM.
  • Placeholder Image
    Publication
    Information spreading in dynamic networks under oblivious adversaries
    (01-01-2016) ;
    Avin, Chen
    ;
    Liaee, Mehraneh
    ;
    Pandurangan, Gopal
    ;
    Rajaraman, Rajmohan
    We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, there are n tokens arbitrarily distributed among the n network nodes, and the goal is to disseminate all the n tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. An important open question is whether gossip can be realized by a distributed protocol that can do significantly better than an easily achievable bound of O(n2) rounds. In this paper, we study oblivious adversaries, i.e., those that are oblivious to the random choices made by the protocol. We consider Rand-Diff, a natural distributed algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We present an Ω(n3/2) lower bound for Rand-Diff under an oblivious adversary. We also present an Ω (n4/3) lower bound under a stronger notion of oblivious adversary for a class of randomized distributed algorithms—symmetric knowledge-based algorithms— in which nodes make token transmission decisions based entirely on the sets of tokens they possess over time. On the positive side, we present a centralized algorithm that completes gossip in Õ(n3/2) rounds with high probability, under any oblivious adversary. We also show an Õ (n5/3) upper bound for Rand-Diff in a restricted class of oblivious adversaries, which we call paths-respecting, that may be of independent interest.
  • Placeholder Image
    Publication
    Sublinear message bounds for randomized agreement
    (23-07-2018) ;
    Molla, Anisur Rahaman
    ;
    Pandurangan, Gopal
    This paper focuses on understanding the message complexity of randomized agreement in synchronous distributed networks. We focus on the so-called implicit agreement problem where each node starts with an input value (0 or 1) and at the end one or more nodes should decide on a common input value which should be equal to some node's input value (there can be undecided nodes). Implicit agreement is a generalization of the fundamental agreement and leader election problems. We present sublinear (in n, where n is the number of nodes) algorithms and lower bounds on the message complexity of implicit agreement in fully-connected (i.e., complete) networks. Specifically our main results are: (1) We show that for any implicit agreement algorithm that succeeds with probability at least 1 −, for some suitably small constant > 0, needs at least Ω(n0.5) messages with constant probability. This bound holds regardless of the number of rounds used and applies to both LOCAL and CONGEST models. This lower bound is essentially tight for complete networks, as there exists a randomized agreement algorithm that uses only Õ (n0.5) messages1 with high probability2 and runs in O(1) rounds and succeeds with high probability. Both the upper and lower bounds assume that nodes have access to (only) private coins. (2) In contrast to the above bounds, if nodes have access to an unbiased global (shared) coin, we present a randomized algorithm which, with high probability, achieves implicit agreement, and uses Õ (n0.4) messages in expectation and runs in O(1) rounds (deterministically). This algorithm works in the CONGEST model as well. Our result shows the power of a global coin in significantly improving (by a polynomial factor) the message complexity of agreement. As another contrast, we show that the same benefit does not apply to leader election, i.e., even with access to a global coin, Ω(n0.5) messages (in expectation) are needed for any leader election algorithm that succeeds with probability at least 1 −, for a small constant > 0. (3) We extend our results to a natural generalization of agreement called as subset agreement where a given (non-empty) subset of nodes should agree on a common value. We show that subset agreement on a subset of size k nodes can be accomplished by a randomized algorithm that succeeds with high probability, and uses (in expecation) Õ(min{kn0.5,n}) (using only private coins) and Õ(min{kn0.4,n}) messages (using global coin) respectively. We view our results as a step towards understanding the complexity of randomized agreement in distributed networks, in particular, message complexity with or without shared randomness.
  • Placeholder Image
    Publication
    Scheduling mechanisms to control the spread of COVID-19
    (01-09-2022) ;
    Hourani, Khalid
    ;
    Molla, Anisur Rahaman
    ;
    Pandurangan, Gopal
    ;
    Pasic, Adi
    We study scheduling mechanisms that explore the trade-off between containing the spread of COVID-19 and performing in-person activity in organizations. Our mechanisms, referred to as group scheduling, are based on partitioning the population randomly into groups and scheduling each group on appropriate days with possible gaps (when no one is working and all are quarantined). Each group interacts with no other group and, importantly, any person who is symptomatic in a group is quarantined. We show that our mechanisms effectively trade-off in-person activity for more effective control of the COVID-19 virus spread. In particular, we show that a mechanism which partitions the population into two groups that alternatively work in-person for five days each, flatlines the number of COVID-19 cases quite effectively, while still maintaining in-person activity at 70% of pre-COVID-19 level. Other mechanisms that partitions into two groups with less continuous work days or more spacing or three groups achieve even more aggressive control of the virus at the cost of a somewhat lower in-person activity (about 50%). We demonstrate the efficacy of our mechanisms by theoretical analysis and extensive experimental simulations on various epidemiological models based on real-world data.
  • Placeholder Image
    Publication
    Fast byzantine agreement in dynamic networks
    (11-09-2013) ;
    Pandurangan, Gopal
    ;
    Robinson, Peter
    We study Byzantine agreement in dynamic networks where topology can change from round to round and nodes can also experience heavy churn (i.e., nodes can join and leave the network continuously over time). Our main contributions are randomized distributed algorithms that achieve almost-everywhere Byzantine agreement with high probability even under a large number of adaptively chosen Byzantine nodes and continuous adversarial churn in a number of rounds that is polylogarithmic in n (where n is the stable network size). We show that our algorithms are essentially optimal (up to polylogarithmic factors) with respect to the amount of Byzantine nodes and churn rate that they can tolerate by showing a lower bound. In particular, we present the following results: 1. An O(log3 n) round randomized algorithm to achieve almost-everywhere Byzantine agreement with high probability under a presence of up to O(√n/polylog(n)) Byzantine nodes and up to a churn of O(√n/ polylog(n)) nodes per round. We assume that the Byzantine nodes have knowledge about the entire state of network at every round (including random choices made by all the nodes) and can behave arbitrarily. We also assume that an adversary controls the churn - it has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power (but is oblivious to the topology changes from round to round). Our algorithm requires only polylogarithmic in n bits to be processed and sent (per round) by each node. 2. We also present an O(log3 n) round randomized algorithm that has same guarantees as the above algorithm, but works even when the connectivity of the network is controlled by an adaptive adversary (that can choose the topology based on the current states of the nodes). However, this algorithm requires up to polynomial in n bits to be processed and sent (per round) by each node. 3. We show that the above bounds are essentially the best possible, if one wants fast (i.e., polylogarithmic run time) algorithms, by showing that any (randomized) algorithm to achieve agreement in a dynamic network controlled by an adversary that can churn up to θ(√n log n) nodes per round should take at least a polynomial number of rounds. Our algorithms are the first-known, fully distributed, Byzantine agreement algorithms in highly dynamic networks. We view our results as a step towards understanding the possibilities and limitations of highly dynamic networks that are subject to malicious behavior by a large number of nodes.
  • Placeholder Image
    Publication
    Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
    (11-12-2015) ;
    Pandurangan, Gopal
    ;
    Robinson, Peter
    ;
    Roche, Scott
    ;
    Upfal, Eli
    Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.
  • Placeholder Image
    Publication
    Distributed agreement in dynamic peer-to-peer networks
    (01-11-2015) ;
    Pandurangan, Gopal
    ;
    Robinson, Peter
    ;
    Upfal, Eli
    Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we present first-known, fully-distributed algorithms for the fundamental distributed agreement problem in dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our algorithms guarantee stable almost-everywhere agreement with high probability even under high adversarial churn and run in time that is polylogarithmic in n (which is the stable network size). Our first algorithm can tolerate a churn of up to εn per time step, sends only polylogarithmic number of bits per node per time step, and works under an adversary that is oblivious to the algorithm's random choices. Our second algorithm, designed for the more challenging adaptive adversary, can tolerate a churn of up to εn. Being easy to implement, our algorithms could serve as building blocks for other non-trivial distributed computation in dynamic networks.
  • Placeholder Image
    Publication
    A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables
    (11-07-2022) ;
    Chatterjee, Soumyottam
    ;
    Pandurangan, Gopal
    Performing computation in the presence of faulty and malicious nodes is a central problem in distributed computing. Over 35 years ago, Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] studied the fundamental Byzantine agreement problem in sparse, bounded degree networks and presented the first protocol that achieved almost-everywhere agreement among good nodes. However, this protocol and several subsequent protocols including that of King, Saia, Sanwalani, and Vee [FOCS 2006] had the drawback that they were not fully-distributed - in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols not applicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and of their neighbors. In thiswork,we present the first scalable, fully-distributed Byzantine protocol for sparse, bounded degree, P2P networks that can tolerate a large number of Byzantine nodes. We assume that the Byzantine nodes can behave arbitrarily and maliciously, have unlimited computational power, and may collude among themselves. However, they are oblivious to (direct) communication between good nodes, i.e., we assume the existence of private channels, but make no cryptographic assumptions. In particular, Byzantine nodes do have knowledge of the messages sent by good nodes if those messages go through a Byzantine node. As is standard in P2P networks, we assume that nodes can communicate with each other if they know their identities. Our main contribution is a (randomized) fully-distributed protocol that guarantees with high probability the construction of an addressable P2P network that can be used to build a distributed hash table (DHT) that enables efficient, robust, and reliable storage and search of data even in the presence of up to n/polylog n number of Byzantine nodes (where n is the total number of nodes). Furthermore, our protocol is scalable, in the sense that it incurs only polylog n overhead - only polylog n bits need to be processed and sent by each node per round and any node's computation cost per round is also polylog n and the protocol takes polylog n rounds. To the best of our knowledge, this is the first-known, fullydistributed P2P protocol in sparse networks that guarantees construction of an efficiently addressable DHT that can operate under a large number of Byzantine nodes.