We consider the distributed setting of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the real plane. Robots may be without lights (the classic oblivious robots model) or equipped with lights (the robots with lights model). Under obstructed visibility, a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them, but it is not the case under unobstructed visibility. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. In this paper, we introduce and study Doorway Egress, the problem of robots exiting through a doorway from one side of a wall to the other; initially, the robots are positioned at distinct positions on one side of a wall.We study time-efficient solutions where time is measured using a standard notion of epochs – an epoch is a duration in which each robot completes at least one LCM cycle. For solutions to Doorway Egress with only 1 epoch, we: design an asynchronous algorithm if collisions are allowed; prove that an asynchronous algorithm is impossible if collisions are not allowed; and design a semi-synchronous algorithm without collisions. To further investigate asynchronous algorithms without collisions, we present algorithms with different combinations of robot abilities:•O(1) epochs with lights under obstructed visibility;•O(1) epochs without lights under unobstructed visibility; and•O(n) epochs without lights under obstructed visibility.Our results reveal dependencies and trade-offs among obstructed/unobstructed visibility, lights/no lights, and semi-synchronous/asynchronous settings.

We consider the distributed setting of$N$autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following either the robots with lights model or the classical oblivious robots model. For the lights model, we assume obstructed visibility so that a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In contrast, we assume unobstructed visibility in the classical model so that a robot sees all others irrespective of their positions. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot's movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The Arbitrary Pattern Formationproblem is to relocate the$N$robots (starting at arbitrary but distinct initial positions on a grid) to form an arbitrary target pattern given as input. In this paper, we provide two asynchronous algorithms for Arbitrary Pattern Formation, one on the lights model and another on the classical model. Key measures of the algorithms' performance include the time taken and the number of moves by each robot. Both algorithms run in$O(\max\{D^{i}, D^{p}\})$time with$O(\max\{D^{i}, D^{p}\})$moves by each robot, where$D^{i}$and$D^{p}$, respectively, are the diameters of the initial and pattern configurations. The algorithm for the lights model uses$O(1)$colors. We also prove a lower bound of$\Omega(\max\{D^{i}, D^{p}\})$for time for any Arbitrary Pattern Formationalgorithm if scaling is not allowed on the target pattern. Therefore, our algorithms are optimal w.r.t. time. Furthermore, our algorithms are also optimal w.r.t. the number of moves given the existing lower bound of$\Omega(\max\{D^{i}, D^{p}\})$on the number of moves. In sum, our results show that having lights provides a trade-off on the unobstructed visibility requirement in the classical model for Arbitrary Pattern Formation.

We consider the distributed setting of$n$autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (therobots with lightsmodel). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional euclidean plane. TheConvex Hull Formationproblem is to relocate the$n$robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this article, we provide a framework for solvingConvex Hull Formation. We then provide four asynchronous algorithms under this framework. Key measures of the algorithms’ performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first$O(\max \lbrace n^{2},D\rbrace)$-time,$O({n^{2}})$-perimeter, and$O({n^{3}})$-area algorithm serves to introduce key ideas, where$D$is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)$time with a perimeter of$O(n^{\frac{3}{2}})$and area of$O(n^{3})$. We also prove lower bounds of$\Omega (n^{\frac{3}{2}})$for time and perimeter and$\Omega (n^{3})$for area, for anyConvex Hull Formationalgorithm; i.e., our$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)-$time algorithm is optimal in time, perimeter, and area.

We consider the distributed setting of n autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using a constant number of colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The CONVEX HULL FORMATION problem is to relocate the n robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this paper, we provide two asynchronous algorithms for CONVEX HULL FORMATION, both using a constant number of colors. Key measures of the algorithms' performance include the time taken and the space occupied (measured as the perimeter of the smallest rectangle enclosing the convex hull formed). The first O(max{n2, D})-time and O(n2)-perimeter algorithm serves to introduce key ideas, where D is the diameter of the initial 3 configuration. The second algorithm runs in O(max{n3/2, D}) 3 time with a perimeter of O(n3/2). We also prove lower bounds of Ω(n2/3) for both the time and perimeter for any CONVEX HULL FORMATION algorithm; that is, we establish our second algorithm as optimal in both time and perimeter.

In massively multiplayer online games, computational load is often shared among and transferred between the servers that host the game world. It is important to keep this load balanced among those resources such that no one server becomes overloaded and leads to a subpar game experience or outright game failure. The system must balance is load subject to constraints as player satisfaction and maximum server computational capacity. We propose a novel periodic approach to this problem of load balancing along with a collection of heuristics to achieve balance in the system, and compare its performance against existing work in literature, finding that these new heuristics provide more system balance than those existing methods.

The Client Assignment Problem is an NP-hard problem applicable to online games in which a set of clients must be satisfactorily assigned to a subset of all available servers subject to various criteria. One particular variant of that problem we have defined as Offline CAP-Z separates the game world into zones and calls for heuristics to assign zones to servers such that a minimum fraction of players achieves a connection speed faster than a threshold of game quality known as QoS. We develop novel heuristics based on bin packing to find assignments much faster than previous solutions to CAP-Z while using a comparable number of servers.

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental problem of repositioning N autonomous robots on a plane sothat each robot is visible to all others (the Complete Visibility problem) on this model; a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. There exists an O(1) time, O(1) color algorithm for this problem in the semi-synchronous setting. In this paper, we provide the first O(log N) time, O(1) color algorithm for this problem in the asynchronous setting. This is a significant improvement over an O(N)-time translation of the semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free - robots do not share positions and their paths do not cross.

We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem), a robot cannot see another robot if there is a third robot positioned between them on the straight line joining them. Robots communicate using collared lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions(including deciding on a new-collar for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact that each robot has only a constant number of colours for its lights(symbols for communication) and no memory(except for the persistence of lights) between rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present the first logarithmic time complexity algorithm for Complete Visibility. The model we assume use sterility, is fully-synchronous and allows robot paths to cross.

Partially reconfigurable devices allow the execution of multiple tasks simultaneously on the same chip. To schedule a set of tasks in a small amount of time, the scheduling algorithm will need to represent the free space efficiently. A data structure to represent free space should allow the scheduler to identify free space in which to place a new task and admit efficient updates after placing or removing a task. In this paper, we review some existing data structures and analyze their time complexity. We propose a new structure using maximal horizontal and vertical strips to represent the free space. These strips start and stop at task boundaries. Simulation and time analysis showed that this method has better time complexity than many other free space data structures and at the same time has a very reasonable rejection ratio on real-time tasks compared to other methods.

Recently, many models using reconfigurable optically pipelined buses have been proposed in the literature. We present simulations for a number of these models and establish that they possess the same complexity, so that any of these models can simulate a step of one of the other models in constant time with a polynomial increase in size. Specifically, we determine the complexity of three optical models (the PR-Mesh, APPBS, and AROB) to be the same as the well known LR-Mesh and the cycle-free LR-Mesh.

This paper deals with the ability of a model to adapt algorithm instances of different sizes to run on a given model size without significant loss of efficiency. The overhead in simulating a step of a large instance of the model on a smaller instance can quantify this ability. A reconfigurable mesh (R-Mesh) can use its bus structure as a computational resource, presenting an obstacle to efficiently scaling down algorithms to run on a smaller R-Mesh. We construct a scaling simulation of a Fusing-Restricted Reconfigurable Mesh (FR-Mesh), a version of the R-Mesh. The overhead of this simulation depends only on the simulating machine size and not on the simulated machine size. Previously, the R-Mesh was not known to admit such a simulation overhead without significantly reducing its computational power. The small overhead holds importance for flexibility in algorithm design and for running algorithms with various input sizes on an available model of given size. The results of this paper extend to a variety of concurrent write rules and also translate to an improved scaling simulation of an unrestricted R-Mesh.

The distance transform is a basic operation in computer vision, pattern recognition and robotics. In this paper, we consider the city block (L1) distance metric. An algorithm for computing the city block distance transform on reconfigurable meshes is proposed in this paper. The time complexity and scalability of the algorithm are analysed. The results indicate that the algorithm is scalable and efficient.

The processor allocation problem requires recognizing and locating a free subcube that can accommodate a request for a subcube of a specified size for an incoming task. Methods reported in the literature fall into two strategies: bottom-up or bit mapped technique (BMT) and top-downer available cube technique (ACT). Our algorithm that solves the allocation problem in faulty hypercubes falls into the category of ACT's which offer the advantage over BMT's of quickly recognizing whether or not a requested subcube is available in the list of fault-free subcubes. We introduce new algebraic functions and the concept of separation factor to select a subcube for allocation. The notion of overlap-syndrome, defined in the text, quantifies the overlap among free subcubes. Our technique has full subcube recognition ability and thus recognizes more subcubes as compared to bit mapped techniques: Buddy, Gray code and its variants. The advantages of our approach over some of the existing ACT's in terms of fragmentation and overall completion time are described in the text and in simulation results.>

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. In this paper, vie present constant time RMBM algorithms for a collection of basic, graph problems that include, lowest common ancestors and Euler tour related problems (for trees) and shortest path and connectivity related problems (for general graphs). We also present results for some poset and lattice problems. All algorithms are at least as efficient or more efficient in terms of processors than corresponding PARBUS algorithms.

The hypercube topology, also known as the Boolean n-cube, has recently been used for multiprocessing systems. The paper considers two structural-reliability models, namely, terminal reliability (TR) and network reliability (NR), for the hypercube. Terminal (network) reliability is defined as the probability that there exists a working path connecting two (all) nodes. There are no known polynomial time algorithms for exact computation of TR or NR for the hypercube. Thus, lower-bound computation is a better alternative, because it is more efficient computationally, and the system will be at least as reliable as the bound. The paper presents algorithms to compute lower bounds on TR and NR for the hypercube considering node and/or link failures. These algorithms provide tighter bounds for both TR and NR than known results and run in time polynomial in the cube dimension n, specifically, within time O(n/sup 2/).>

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. We present constant time algorithms for list ranking, integer sorting and a number of fundamental graph problems on the RMBM. The algorithms are more efficient in terms of processors than the corresponding PARBS algorithms. The algorithms demonstrate some of the potential for computation available in the ability to manipulate communication paths as a vital part of computation.

Abstract A multistage interconnection network (MIN) uses switching elements for interconnecting processors to memory or processors. This paper first considers a stochastic model of a shuffle exchange network (of sizeN) with an extra stage and develops terminal, broadcast, andK‐terminal reliability evaluation algorithms that run in timeO(log logN),O(logN), andO(klogN), respectively, wherek= |K|. Second, a deterministic model for the MIN is considered and decision problems in which one is interested in evaluating whether a network can effect a specified set of connections with a given set of failures are solved. We develop a set of approaches for the SENE for the terminal decision, broadcast decision, and network decision problems and for the generalS, Tdecision problem for an input setSand output setT. Each algorithm runs within time polynomial in the size of the SENE and the number of faults and, in some cases, logarithmic in the size of the SENE and polynomial in the number of faults. These approaches are based on either testing for the existence of an appropriate pathset or testing for the nonexistence of an appropriate cutset. ©1993 by John Wiley & Sons, Inc.