Transaction scheduling is crucial to efficiently allocate shared resources in a conflict-free manner in distributed systems. We investigate the efficient scheduling of transactions in a network of fog-cloud computing model, where transactions and their associated shared objects can move within the network. The schedule may require objects to move to transaction nodes, or the transactions to move to the object nodes. Moreover, the schedule may determine intermediate nodes where both objects and transactions meet. Our goal is to minimize the total combined cost of the schedule. We focus on networks of constant doubling dimension, which appear frequently in practice. We consider a batch problem where an arbitrary set of nodes has transactions that need to be scheduled. First, we consider a single shared object required by all the transactions and present a scheduling algorithm that gives an $O(\log n \cdot \log D)$ approximation of the optimal schedule, where $n$ is the number of nodes and $D$ is the diameter of the network. Later, we consider transactions accessing multiple shared objects (at most $k$ objects per transaction) and provide a scheduling algorithm that gives an $O(k \cdot \log n \cdot \log D)$ approximation. We also provide a fully distributed version of the scheduling algorithms where the nodes do not need global knowledge of transactions.

We study distributed directory protocols for accessing shared objects in large-scale distributed systems under the recently proposed framework of learning-augmentation. 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 existing directory protocols were designed in the online model where both the arrival time of requests and the nodes issuing requests are not known a priori. We consider the learned-augmented framework that involves a priori knowledge on nodes that issue requests; the arrive time of requests as well as whether in fact predicted nodes issue those requests are unknown (i.e., the predictions may be error-prone). We design two distributed directory protocols, one tree-based and another cluster-based, and provide better guarantees that were known in the literature in the online model, when predictions are perfect (no prediction error). We additionally show that the guarantees degrade gracefully with prediction error but do not get worse than the guarantees in the online model even with maximum prediction error. To the best of our knowledge, this is the first study of distributed directory protocols under learning-augmented framework.

We consider the distributed setting of N autonomous mobile robots operating on graphs following Look-Compute-Move cycles and communicating with other robots using colored lights under the robots with lights model. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We introduce and study the fundamental problem of repositioning N robots on the nodes of a graph so that each robot has a path to all others without visiting an intermediate node that is occupied by any other robot (which we call the Complete Visitability problem). This problem is of interest due to its relationship to the problems of information collection, scattering, flocking, and dispersion on graphs. This problem generalizes the Complete Visitability problem studied in the literature, where the goal was to reposition the robots on a plane so that each robot sees all others. We have the following four results: We first show that it is impossible to solve Complete Visitability on arbitrary graphs, irrespective of the number of colors, time, and the robot activation setting (fully synchronous, semi-synchronous, or asynchronous). We then give an algorithm that solves Complete Visitability on grid graphs using 7 colors in the semi-synchronous setting. The algorithm uses 6 colors in the fully synchronous setting. The algorithm is collision-free. We then show that the total number of moves by any robot is O(h) and the runtime is O(h2) in our algorithm, where h denotes the number of layers of robots in the initial configuration. We also show that the number of moves bound is asymptotically tight and any Complete Visitability algorithm has runtime Ω(h) in grid graphs. We finally show that the algorithm and bounds for grid graphs extend to hexagonal tessellation graphs under chirality - robots agree on left and right directions.