BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

John Augustine

John Augustine contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingComputational GeometryData Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

Guarding Polygons with Holes

We study the Cooperative Guarding problem for polygons with holes in a mobile multi-agents setting. Given a set of agents, initially deployed at a point in a polygon with $n$ vertices and $h$ holes, we require the agents to collaboratively explore and position themselves in such a way that every point in the polygon is visible to at least one agent and that the set of agents are visibly connected. We study the problem under two models of computation, one in which the agents can compute exact distances and angles between two points in its visibility, and one in which agents can only compare distances and angles. In the stronger model, we provide a deterministic $O(n)$ round algorithm to compute such a cooperative guard set while not requiring more than $\frac{n + h}{2}$ agents and $O(\log n)$ bits of persistent memory per agent. In the weaker model, we provide an $O(n^4)$ round algorithm, that does not require more than $\frac{n+2h}{2}$ agents.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Recurrent Problems in the LOCAL model

The paper considers the SUPPORTED model of distributed computing introduced by Schmid and Suomela [HotSDN'13], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply, 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 overcome locality-based time lower bounds. A first contribution of the current paper is expanding the spectrum of problem types to which the SUPPORTED model applies. In addition to subnetwork-defined recurrent problems, we introduce also recurrent problems of two additional types: (i) instances defined by partial client sets, and (ii) instances defined by partially fixed outputs. Our second contribution is illustrating the versatility of the SUPPORTED framework by examining recurrent variants of three classical graph problems. The first problem is Minimum Client Dominating Set (CDS), a recurrent version of the classical dominating set problem with each recurrent instance requiring us to dominate a partial client set. We provide a constant time approximation scheme for CDS on trees and planar graphs. The second problem is Color Completion (CC), a recurrent version of the coloring problem in which each recurrent instance comes with a partially fixed coloring (of some of the vertices) that must be completed. We study the minimum number of new colors and the minimum total number of colors necessary for completing this task. The third problem we study is a recurrent version of Locally Checkable Labellings (LCL) on paths of length $n$. We show that such problems have complexities that are either $Θ(1)$ or $Θ(n)$, extending the results of Foerster et al. [INFOCOM'19].

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Distributed Graph Realizations

We study graph realization problems from a distributed perspective 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 both of which result in overlay network realizations. 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. An $\tilde{O}(\min\{\sqrt{m},Δ\})$ time algorithm for implicit realization of a degree sequence. Here, $Δ= \max_v d(v)$ is the maximum degree and $m = (1/2) \sum_v d(v)$ is the number of edges in the final realization. An $\tilde{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 $\tilde{O}(Δ)$ additional rounds. 2. An $\tilde{O}(Δ)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{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. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$. Additionally, we provide algorithms for realizing trees and an $\tilde{O}(1)$ round algorithm for approximate degree sequence realization.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Guarding a Polygon Without Losing Touch

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Latency, Capacity, and Distributed MST

We study the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links of the communication network, while capacity captures their throughput (in this case, the rate at which messages can be sent). Depending on how the edge latencies relate to the edge weights, we provide several tight bounds on the time and messages required to construct an MST. When edge weights exactly correspond with the latencies, we show that, perhaps interestingly, the bottleneck parameter in determining the running time of an algorithm is the total weight $W$ of the MST (rather than the total number of nodes $n$, as in the standard CONGEST model). That is, we show a tight bound of $\tildeΘ(D + \sqrt{W/c})$ rounds, where $D$ refers to the latency diameter of the graph, $W$ refers to the total weight of the constructed MST and edges have capacity $c$. The proposed algorithm sends $\tilde{O}(m+W)$ messages, where $m$, the total number of edges in the network graph under consideration, is a known lower bound on message complexity for MST construction. We also show that $Ω(W)$ is a lower bound for fast MST constructions. When the edge latencies and the corresponding edge weights are unrelated, and either can take arbitrary values, we show that (unlike the sub-linear time algorithms in the standard CONGEST model, on small diameter graphs), the best time complexity that can be achieved is $\tildeΘ(D+n/c)$. However, if we restrict all edges to have equal latency $\ell$ and capacity $c$ while having possibly different weights (weights could deviate arbitrarily from $\ell$), we give an algorithm that constructs an MST in $\tilde{O}(D + \sqrt{n\ell/c})$ time. In each case, we provide nearly matching upper and lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Largest Empty Circle Centered on a Query Line

The Largest Empty Circle problem seeks the largest circle centered within the convex hull of a set $P$ of $n$ points in $\mathbb{R}^2$ and devoid of points from $P$. In this paper, we introduce a query version of this well-studied problem. In our query version, we are required to preprocess $P$ so that when given a query line $Q$, we can quickly compute the largest empty circle centered at some point on $Q$ and within the convex hull of $P$. We present solutions for two special cases and the general case; all our queries run in $O(\log n)$ time. We restrict the query line to be horizontal in the first special case, which we preprocess in $O(n α(n) \log n)$ time and space, where $α(n)$ is the slow growing inverse of the Ackermann's function. When the query line is restricted to pass through a fixed point, the second special case, our preprocessing takes $O(n α(n)^{O(α(n))} \log n)$ time and space. We use insights from the two special cases to solve the general version of the problem with preprocessing time and space in $O(n^3 \log n)$ and $O(n^3)$ respectively.

0 citations0 reviewsNo code linkedOpen access