Options
John Augustine
Loading...
Preferred name
John Augustine
Official Name
John Augustine
Alternative Name
Augustine, John
Main Affiliation
Email
Scopus Author ID
Google Scholar ID
5 results
Now showing 1 - 5 of 5
- PublicationGuarding a polygon without losing touch(01-01-2020)
;Ashok, Barath; ;Mehekare, Aditya ;Ragupathi, Sridhar ;Ramachandran, SrikkanthSourav, SumanWe study the classical Art Gallery Problem first proposed by Klee in 1973 from a mobile multi-agents perspective. Specifically, we require an optimally small number of agents (also called guards) to navigate and position themselves in the interior of an unknown simple polygon with n vertices such that the collective view of all the agents covers the polygon. We consider the visibly connected setting wherein agents must remain connected through line of sight links – a requirement particularly relevant to multi-agent systems. We first provide a centralized algorithm for the visibly connected setting that runs in time O(n), which is of course optimal. We then provide algorithms for two different distributed settings. In the first setting, agents can only perceive relative proximity (i.e., can tell which of a pair of objects is closer) whereas they can perceive exact distances in the second setting. Our distributed algorithms work despite agents having no prior knowledge of the polygon. Furthermore, we provide lower bounds to show that our distributed algorithms are near optimal. Our visibly connected guarding ensures that (i) the guards form a connected network and (ii) the polygon is fully guarded. Consequently, this guarding provides the distributed infrastructure to execute any geometric algorithm for this polygon. - PublicationInformation spreading in dynamic networks under oblivious adversaries(01-01-2016)
; ;Avin, Chen ;Liaee, Mehraneh ;Pandurangan, GopalRajaraman, RajmohanWe 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. - PublicationPlateau: A Secure and Scalable Overlay Network for Large Distributed Trust Applications(01-01-2022)
; ;Bhat, Wahid GulzarNair, SandipWe propose a novel two-tiered overlay network design called plateau. It has two levels: a small upper-level that regulates entry of new nodes into the network, and a lower-level comprising all nodes. The lower level is a well-connected expander that is ideal for building peer-to-peer distributed trust applications. It is designed to be secure despite the presence of adversarial Byzantine nodes and resilient to large amounts of churn. The good nodes only need to communicate with their neighbors in the network, thus making plateau fully distributed. Membership in the network must be earned through proof-of-work that is verified by the upper-level nodes. Plateau is robust despite heavy churn controlled by an adversary, i.e., up to C= poly (n) number of nodes can join and leave the network per round without disrupting the network structure; n is the total number of good nodes in the network. As long as the compute power controlled by the Byzantine adversary is bounded, the number of Byzantine nodes in the network is kept in check and, more importantly, they will not be able to disrupt the structure or functioning of the overlay network. Additionally, we show that all resources needed to operate this network is bounded polylogarithmically with respect to n. - PublicationFast Byzantine leader election in dynamic networks(01-01-2015)
; ;Pandurangan, GopalRobinson, PeterWe study the fundamental Byzantine leader election problem in dynamic networks where the 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). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an O(log3 n) round algorithm that achieves Byzantine leader election under the presence of up to O(n1/2-ε) Byzantine nodes (for a small constant ε > 0) and a churn of up to O(√n/ polylog(n)) nodes per round (where n is the stable network size). The algorithm elects a leader with probability at least 1 - n-Ω(1) and guarantees that it is an honest node with probability at least 1-n-Ω(1); assuming the algorithm succeeds, the leader’s identity will be known to a 1-o(1) fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in n) time and requires nodes to send and receive messages of only polylogarithmic size per round. To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way. We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest. - PublicationAwake Complexity of Distributed Minimum Spanning Tree(2024-01-01)
; ;Moses, William K.Pandurangan, GopalThe awake complexity of a distributed algorithm measures the number of rounds in which a node is awake. When a node is not awake, it is sleeping and does not do any computation or communication and spends very little resources. Reducing the awake complexity of a distributed algorithm can be relevant in resource-constrained networks such as sensor networks, where saving energy of nodes is crucial. Awake complexity of many fundamental problems such as maximal independent set, maximal matching, coloring, and spanning trees have been studied recently. In this work, we study the awake complexity of the fundamental distributed minimum spanning tree (MST) problem and present the following results. Lower Bounds.We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms.To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) factor) on the product of round complexity and awake complexity for any distributed algorithm (even randomized) that outputs an MST. Our lower bound is shown for graphs having diameter ranging from Ω~(n) to Ω~(n).Awake-Optimal Algorithms.We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). We note that by our trade-off lower bound, in general (in terms of n), this is the best round complexity (up to logarithmic factors) for an awake-optimal algorithm.We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n).Trade-Off Algorithms. To complement our trade-off lower bound, we present a parameterized family of distributed algorithms that gives an essentially optimal trade-off (up to polylogn factors) between the awake complexity and the round complexity. Specifically we show a family of distributed algorithms that find an MST of the given graph with high probability in O~(D+2k+n/2k) round complexity and O~(n/2k) awake complexity, where D is the network diameter and integer k is an input parameter to the algorithm. When k∈[max{⌈0.5logn⌉,⌈logD⌉},⌈logn⌉], we can obtain useful trade-offs. Lower Bounds.We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms.To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) factor) on the product of round complexity and awake complexity for any distributed algorithm (even randomized) that outputs an MST. Our lower bound is shown for graphs having diameter ranging from Ω~(n) to Ω~(n). We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms. To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) factor) on the product of round complexity and awake complexity for any distributed algorithm (even randomized) that outputs an MST. Our lower bound is shown for graphs having diameter ranging from Ω~(n) to Ω~(n). Awake-Optimal Algorithms.We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). We note that by our trade-off lower bound, in general (in terms of n), this is the best round complexity (up to logarithmic factors) for an awake-optimal algorithm.We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n). We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). We note that by our trade-off lower bound, in general (in terms of n), this is the best round complexity (up to logarithmic factors) for an awake-optimal algorithm. We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n). Trade-Off Algorithms. To complement our trade-off lower bound, we present a parameterized family of distributed algorithms that gives an essentially optimal trade-off (up to polylogn factors) between the awake complexity and the round complexity. Specifically we show a family of distributed algorithms that find an MST of the given graph with high probability in O~(D+2k+n/2k) round complexity and O~(n/2k) awake complexity, where D is the network diameter and integer k is an input parameter to the algorithm. When k∈[max{⌈0.5logn⌉,⌈logD⌉},⌈logn⌉], we can obtain useful trade-offs. Our work is a step towards understanding resource-efficient distributed algorithms for fundamental global problems such as MST. It shows that MST can be computed with any node being awake (and hence spending resources) for only O(logn) rounds which is significantly better than the fundamental lower bound of Ω~(Diameter(G)+n) rounds for MST in the traditional CONGEST model, where nodes can be active for at least so many rounds.