Pinwheel Scheduling is a fundamental scheduling problem, in which each task \(i\) is associated with a positive integer deadline \(d_i\), and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every \(d_i\) time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP.

We study the standard communication problem of broadcast for mobile agents moving in a network, where a single agent called source, has to transmit a vital information to all other agents in the network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modeled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of all agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine the minimum value of k > 0 , such that the broadcast from a source agent to k other agents can be solved in dynamic networks. While k = 2 agents are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes k ≥ n − 2 agents are necessary and sufficient. We show lower bounds on the number of agents and provide algorithms for solving broadcast using the minimum number of agents, for various topologies. These results show how the connectivity of the underlying graph affects the communication capability of a team of mobile agents in constantly connected dynamic networks.

We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes at least n-2 agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies.

Abstract A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this article we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial‐time approximable within any constant factor less than$389 \over 388$ (unlessP=NP). We give a 6‐approximation algorithm, thus improving on the 9.3‐approximation algorithm from (Czyzowicz et al., Fundamenta Informaticae 71 (2006), 229–242). We also prove APX‐hardness for a restricted version of the problem, in which only the starting node is initially known to be safe. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008