John Augustine

A 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.

We 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.

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.

This 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.

We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [15], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by some problem specific input, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds.We propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.

A 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.

We study graph realization problems from a distributed perspective. The problem is naturally applicable to the distributed construction of overlay networks that must satisfy certain degree or connectivity properties, and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node v is associated with a degree d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node v is d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes.Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge.The main realization algorithms we present are the following. (1) A O(□ m,Δ) time algorithm for implicit realization of a degree sequence. Here, Δ = maxv d(v) is the maximum degree and m = (1/2) v d(v) is the number of edges in the final realization. (2) A O (Δ) time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in O (Δ) additional rounds. (3) A O (Δ) time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved O (1) algorithm for implicit realization when all nodes know each other's IDs. These algorithms are 2-approximations w.r.t. the number of edges. Our algorithms are complemented by lower bounds showing tightness up to log n factors. Additionally, we provide algorithms for realizing trees and an O (1) round algorithm for approximate degree sequence realization.

This paper revisits the widely researched gathering problem for two robots without any agreement on the coordinate system in a scenario which allows randomization in the asynchronous scheduling model. The scheduler is considered to be the adversary which determines the activation schedule of the robots. The adversary comes in three flavors, namely, adaptive offline, adaptive online, and oblivious, based on the knowledge of the outcome of random bits. The robots follow wait-look-compute-move cycle. In this paper, we classify the problems based on the capability of the adversary to control the parameters such as wait time, computation delay and the speed of robots and check the feasibility of gathering in terms of adversarial knowledge and capabilities. First, we show the impossibility of gathering under an adaptive offline adversary with non-negative wait time and non-negative computation delay. Gradually relaxing the adversarial capabilities, we present impossibility of gathering for finite random choices and improbability for infinite random choices for an adaptive online adversary. Under an oblivious adversary, we establish the possibility of gathering with zero computation delay. We improve the runtime of the algorithm by restricting the oblivious adversary to choose wait time and computation delay such that the sum of wait time and computation delay is more than a positive constant. Finally, we also extend our algorithm for multiple robots with merging.

We 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.

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.