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
22 results
Now showing 1 - 10 of 22
- PublicationLocalized geometric query problems(01-04-2013)
; ;Das, Sandip ;Maheshwari, Anil ;Nandy, Sabhas C. ;Roy, SasankaSarvattomananda, SwamiA new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects P in the plane, so that for any arbitrary query point q, the largest circle that contains q but does not contain any member of P, can be reported efficiently. The geometric sets that we consider are point sets and boundaries of simple polygons. © 2012 Elsevier B.V. - PublicationLeader Election in Sparse Dynamic Networks with Churn(01-11-2016)
; ;Kulkarni, TejasSivasubramaniam, SumathiWe investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighborhood and, thus, hindering, their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability to establish a leader that can maintain good communication with the rest of the nodes. Because the dynamics could change eventually, it is also essential to reelect a new leader whenever the current leader either has left the network or is not well-connected with rest of the nodes. In such reelections, care must be taken to avoid premature and spurious leader election resulting in more than one leader being present in the network at the same time. We assume a broadcast-based communication model in which each node can send up to O(log3n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader’s ability to communicate is unhealthy, a new leader is reelected in a further O(log2n) rounds. Our running times hold with high probability provided a sufficiently large fraction of the nodes remain stable during the reelection process. Furthermore, we are guaranteed with high probability that there is at most one leader at any time. - PublicationOpportunities for energy efficient computing: A study of inexact general purpose processors for high-performance and big-data applications(22-04-2015)
;Duben, Peter ;Parishkrati, ;Yenugula, Sreelatha; ;Palem, K. ;Schlachter, Jeremy ;Enz, ChristianPalmer, T. N.In this paper, we demonstrate that disproportionate gains are possible through a simple devise for injecting inexactness or approximation into the hardware architecture of a computing system with a general purpose template including a complete memory hierarchy. The focus of the study is on energy savings possible through this approach in the context of large and challenging applications. We choose two such from different ends of the computing spectrum - the IGCM model for weather and climate modeling which embodies significant features of a high-performance computing workload, and the ubiquitous PageRank algorithm used in Internet search. In both cases, we are able to show in the affirmative that an inexact system outperforms its exact counterpart in terms of its efficiency quantified through the relative metric of operations per virtual Joule (OPVJ) - a relative metric that is not tied to particular hardware technology. As one example, the IGCM application can be used to achieve savings through inexactness of (almost) a factor of 3 in energy without compromising the quality of the forecast, quantified through the forecast error metric, in a noticeable manner. As another example finding, we show that in the case of PageRank, an inexact system is able to outperform its exact counterpart by close to a factor of 1.5 using the OPVJ metric. - PublicationMinimax regret 1-sink location problem in dynamic path networks(11-07-2015)
;Higashikawa, Yuya; ;Cheng, Siu Wing ;Golin, Mordecai J. ;Katoh, Naoki ;Ni, Guanqun ;Su, BingXu, YinfengThis paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O(nlog n) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network. - PublicationSpartan: A framework for sparse robust addressable networks(03-08-2018)
; Sivasubramaniam, SumathiA Peer-To-Peer (P2P) network is a dynamic collection of nodes that connect with each other via virtual overlay links built upon an underlying network (usually, the Internet). Typical P2P networks are highly dynamic and can experience very heavy churn, i.e., a large number of nodes join/leave the network every time step. We present an overlay framework called Sparse Robust Addressable Network (Spartan) that can tolerate heavy adversarial churn. We show that Spartan can be built efficiently in a fully distributed manner within O(log n) rounds. Furthermore, the Spartan overlay structure can be maintained, again, in a fully distributed manner despite adversarially controlled churn (i.e., nodes joining and leaving) and significant variation in the number of nodes. When the number of nodes in the network lies in [n, fn] for any fixed f > 1 the adversary can remove up to ?n nodes and add up to ? n nodes (for some small but fixed ? > 0) within any period of P rounds for some P ? O(log log n). Moreover, the adversary can add or remove nodes from the network at will and without any forewarning. Despite such uncertainty in the network, Spartan maintains ?(n/log n) committees that are stable and addressable collections of ?(log n) nodes each. Any node that enters the network will be able to gain membership in one of these committees within O(1) rounds. The committees are also capable of performing sustained computation and passing messages between each other. Thus, any protocol designed for static networks can be simulated on Spartan with minimal overhead. This makes Spartan an ideal platform for developing applications. All our results hold with high probability. - PublicationTowards robust and efficient computation in dynamic Peer-to-Peer networks(01-01-2012)
; ;Pandurangan, Gopal ;Robinson, PeterUpfal, EliMotivated 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. - PublicationStorage and search in dynamic peer-to-peer networks(01-01-2013)
; ;Molla, Anisur Rahaman ;Morsy, Ehab ;Pandurangan, Gopal ;Robinson, PeterUpfal, EliWe 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. - PublicationLeader Election in Sparse Dynamic Networks with Churn(17-07-2015)
; ;Kulkarni, TejasSivasubramaniam, SumathiWe investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighbourhood and thus hinder their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability and well-connectedness to establish a leader that can maintain good communication with rest of the nodes. Since the dynamics could change eventually, it is also essential to re-elect a new leader whenever the current leader has either left the network or is not well-connected with rest of the nodes. In such re-elections, care must be taken to avoid premature and spurious leader election resulting in more than one leader present in the network at the same time. We assume a broadcast based communication model in which each node can send up to O(log3 n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader's ability to communicate is unhealthy, a new leader is re-elected in a further O(log2 n) rounds. Our running times hold with high probability, and, furthermore, we are guaranteed with high probability that there is at most one leader at any time. - 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. - PublicationSublinear message bounds for randomized agreement(23-07-2018)
; ;Molla, Anisur RahamanPandurangan, GopalThis 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.
- «
- 1 (current)
- 2
- 3
- »