Costas Busch

TCS Journal 2023 Journal Article

Flexible scheduling of transactional memory on trees

• Costas Busch
• Bogdan S. Chlebus
• Maurice Herlihy
• Miroslav Popovic
• Pavan Poudel
• Gokarna Sharma

We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a static network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions and their requested objects to move simultaneously among the nodes in the tree. Given a batch of transactions and shared objects, the goal is to produce a schedule of executing the transactions that minimizes the cost of moving the transactions and the objects in the tree. We consider both techniques for accessing a remote object with respect to a transaction movement. In the first technique, instead of moving, transactions send control messages to remote nodes where the requested objects are gathered. In the second technique, the transactions migrate to the remote nodes where the objects are gathered to access them. When all the transactions use a single object, we give an offline algorithm that produces optimal schedules for both techniques. For the general case of multiple objects per transaction, in the first technique, we obtain a schedule with a constant-factor approximation of optimal. In the second technique, with transactions migrating, we give a k factor approximation where k is the maximum number of objects per transaction.

FOCS Conference 2023 Conference Paper

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree

• Costas Busch
• Da Qi Chen
• Arnold Filtser
• Daniel Hathcock
• D. Ellis Hershkowitz
• Rajmohan Rajaraman

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions. We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

I&C Journal 2022 Journal Article

Load balanced distributed directories

• Shishir Rai
• Gokarna Sharma
• Costas Busch
• Maurice Herlihy

We present LB-Spiral, a novel distributed directory protocol for shared objects, suitable for large-scale distributed shared memory systems. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requests. The value of an object can be read by other nodes with lookup requests. The distinctive feature of LB-Spiral is that it balances the processing load on nodes in addition to minimizing the communication cost in general network topologies. In contrast, the existing distributed directory protocols for general network topologies only minimize the communication cost. In particular, LB-Spiral achieves poly-log approximation for both load and communication cost in general networks with respect to the problem parameters. Simulation results show that the established theoretical results translate well in practice.

ICRA Conference 2018 Conference Paper

How to Make Fat Autonomous Robots See all Others Fast?

• Gokarna Sharma
• Costas Busch
• Supratik Mukhopadhyay

The coordination problems arising in a team of autonomous mobile robots have received a lot of attention in the distributed robotics community. Along those lines, we study in this paper the problem of coordinating autonomous mobile robots to reposition on a convex hull so that each robot sees all others. In particular, we consider non-transparent fat robots operating in the 2-dimensional plane. They are abstracted as unit discs and they make local decisions with vision being the only mean of coordination among them. We develop a (deterministic) distributed algorithm that solves the problem for a team of N ≥ 3 fat robots in O(N) time avoiding collisions under the semi-synchronous scheduler. The main idea is to enforce the robots to reach a configuration in which (i) the robots' centers form a convex hull; (ii) all robots are on the convex hull's boundary; and (iii) each robot can see all other robots. The result is achieved assuming some reasonable conditions on the input configuration and showing that starting from any input configuration that satisfies our conditions, robots reach such a configuration in linear time and terminate.

TAAS Journal 2017 Journal Article

Tight Analysis of a Collisionless Robot Gathering Algorithm

• Gokarna Sharma
• Costas Busch
• Supratik Mukhopadhyay
• Charles Malveaux

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane that have a physical extent and hence cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem with minimum time objective has applications in many real-world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011) gave a local greedy algorithm in a fully synchronous setting and proved that, for the discrete version of the problem where robots’ movements are restricted to the positions on an integral grid, their algorithm solves this problem in O ( nR ) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this article, we improve significantly the round complexity of their algorithm to R + 2 · ( n - 1) rounds. This round complexity is obtained in the following modified model: (1) the viewing range of the robots is increased to three hops and (2) robots can additionally move to the diagonally opposite corner to a grid cell in one step—that is, they can traverse the two corresponding grid edges in one time step. We also prove that there are initial configurations of n robots in this problem where at least R +(n-1)/2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + ( n - 1) rounds for the algorithm of Cord-Landwehr et al. These results altogether provide a tight runtime analysis of their algorithm.

TCS Journal 2015 Journal Article

Optimal nearest neighbor queries in sensor networks

• Gokarna Sharma
• Costas Busch

Given a set of m mobile objects in a sensor network, we consider the problem of finding the nearest object among them from any node in the network at any time. These mobile objects are tracked by nearby sensors called proxy nodes. This problem requires an object tracking mechanism which typically relies on two basic operations: query and update. A query is invoked by a node each time when there is a need to find the closest object from it in the network. Updates of an object's location are initiated when the object moves from one location (proxy node) to another. We present a scalable distributed algorithm for tracking these mobile objects such that both the query cost and the update cost are small. The main idea in our algorithm is to maintain a virtual tree of downward paths pointing to the objects. Our algorithm guarantees an asymptotically optimal O ( 1 ) approximation for query cost and an O ( min ⁡ { log ⁡ n, log ⁡ D } ) approximation for update cost in the constant-doubling graph model, where n and D, respectively, are the number of nodes and the diameter of the network. We also give polylogarithmic approximations for both query and update cost in the general graph model. Our algorithm requires only polylogarithmic bits of memory per node. To the best of our knowledge, this is the first algorithm that is asymptotically optimal in handling nearest neighbor queries with low update cost in a distributed setting.

IROS Conference 2015 Conference Paper

Tight analysis of a collisionless robot gathering algorithm

• Gokarna Sharma
• Costas Busch
• Supratik Mukhopadhyay
• Charles Malveaux

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al. . These results altogether provide a tight runtime analysis of their algorithm.

FOCS Conference 2012 Conference Paper

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs

• Costas Busch
• Chinmoy Dutta
• Jaikumar Radhakrishnan
• Rajmohan Rajaraman
• Srinivasagopalan Srivathsan

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all terminal sets X, of the cost of the minimal sub-tree T X of T that connects X to r to the cost of an optimal Steiner tree connecting X to r in G. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. graphs with 2 O(√log n) -stretch. We also give a polynomial time We provide a polynomial time UST construction for general polylog(n)-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch (o(n ε ) for any ε >; 0) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

TCS Journal 2010 Journal Article

An efficient counting network

• Costas Busch
• Marios Mavronicolas

We present a novel counting network construction, where the number of input wires w is smaller than or equal to the number of output wires t. The depth of our network is Θ ( lg 2 w ), which depends only on w. In contrast, the amortized contention of the network depends on the number of concurrent processes n and the parameters w and t. This offers more flexibility than all previously known networks, with the same number w of input and output wires, whose contention depends only on two parameters, w and n. In case n > w lg w, by choosing t > w lg w the contention of our network is O ( n lg w / w ), which improves by a logarithmic factor of w over all previously known networks with w wires.

TCS Journal 2010 Journal Article

Concurrent counting is harder than queuing

• Costas Busch
• Srikanta Tirthapura

We compare the complexities of two fundamental distributed coordination problems, distributed counting and distributed queuing, in a concurrent setting. In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each participating processor receives the rank of its operation in the total order, where as in queuing, a processor receives the identity of its predecessor in the total order. Many coordination applications can be solved using either distributed counting or queuing, and it is useful to know which of counting or queuing is the easier problem. Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high and low diameter graphs. For all these topologies, we show that the concurrent delay complexity of a particular solution to queuing, the arrow protocol, is asymptotically smaller than a lower bound on the complexity of any solution to counting.

TCS Journal 2009 Journal Article

Atomic routing games on maximum congestion

• Costas Busch
• Malik Magdon-Ismail

We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, P o A, is determined by topological properties of the network. In particular, P o A = O ( ℓ + log n ), where ℓ is the length of the longest path in the player strategy sets, and n is the size of the network. Further, κ − 1 ≤ P o A ≤ c ( κ 2 + log 2 n ), where κ is the length of the longest cycle in the network, and c is a constant.

TCS Journal 2005 Journal Article

The cost of concurrent, low-contention Read&Modify&Write

• Costas Busch
• Marios Mavronicolas
• Paul Spirakis

This work addresses the possibility or impossibility, and the corresponding costs, of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system. A natural class of monotone RMW operations associated with monotone groups, a certain class of algebraic groups introduced here, is considered. The popular Fetch&Add and Fetch&Multiply operations are examples from the class. A Monotone Linearizability Lemma is proved and employed as a chief combinatorial instrument in this work; it establishes inherent ordering constraints of linearizability for a certain class of executions of any distributed system implementing a monotone RMW operation. The end results of this work specifically apply to implementations of (monotone) RMW operations that are based on switching networks, a recent class of concurrent, low-contention data structures that generalize counting networks (J. ACM 41(5) (1994) 1020–1048) (which implemented the traditional Fetch&Increment operation). These results are negative; they are shown through the Monotone Linearizability Lemma. In particular, the first lower bounds on size (the number of switches in the network) for any (non-trivial) switching network implementing a monotone RMW operation are derived. It is proven that if the network incurs low contention, then its size must be infinite, no matter whether the number of states of each switch is finite or infinite. Since Fetch&Increment is implementable with counting networks of finite-size (J. ACM 41(5) (1994) 1020–1048), these lower bounds imply a space complexity separation between Fetch&Increment and any monotone RMW operation in the model of switching networks. The presented lower bounds provide a mathematical explanation for the observed inability of researchers over the last thirteen years to extend counting networks, while keeping their finite-size, high-concurrency and low-contention, in order to perform tasks more complex than Fetch&Increment but yet as simple as Fetch&Add.

TCS Journal 2002 Journal Article

Threshold counters with increments and decrements

• Costas Busch
• Neophytos Demetriou
• Maurice Herlihy
• Marios Mavronicolas

A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value ⌊v/w⌋, where v is the current counter value and w is a fixed constant. Thus, the Read operation returns the “approximate” value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a Decrement operation that changes the counter value from v to v−1.

STOC Conference 2000 Conference Paper

Hard-Potato routing

• Costas Busch
• Maurice Herlihy
• Roger Wattenhofer

SODA Conference 2000 Conference Paper

Randomized greedy hot-potato routing

• Costas Busch
• Maurice Herlihy
• Roger Wattenhofer