In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. Starting from any initial configuration, i.e., regardless of the initial states of the agent and all nodes, as well as the initial location of the agent, the algorithms ensure the agent visits all nodes. We evaluate the algorithms based on two metrics: the cover time , defined as the number of moves required to visit all nodes, and memory usage , defined as the storage needed for maintaining the states of the agent and each node. The first algorithm is randomized. Given an integer c = Ω ( n ) , its cover time is optimal, i.e., O ( m ) in expectation, and its memory requirements are O (log c ) bits for the agent and O ( log ( c + δ v ) ) bits for each node v , where n and m are the numbers of nodes and edges, respectively, and δ v is the degree of node v . For general c ≥ 2, its cover time is O ( m · min ( D , n c + 1 , D c + log n ) ) , where D is the diameter of a graph. The second algorithm is deterministic. It requires an input integer k ≥ max ( D, δ max ), where δ max is the maximum degree of the graph. The cover time of this algorithm is O ( m + n D ) , and it uses O (log k ) bits of memory for both the agent and each node.

Deep generative models, such as generative adversarial networks (GANs), have been employed for de~novo molecular generation in drug discovery. Most prior studies have utilized reinforcement learning (RL) algorithms, particularly Monte Carlo tree search (MCTS), to handle the discrete nature of molecular representations in GANs. However, due to the inherent instability in training GANs and RL models, along with the high computational cost associated with MCTS sampling, MCTS RL-based GANs struggle to scale to large chemical databases. To tackle these challenges, this study introduces a novel GAN based on actor-critic RL with instant and global rewards, called InstGAN, to generate molecules at the token-level with multi-property optimization. Furthermore, maximized information entropy is leveraged to alleviate the mode collapse. The experimental results demonstrate that InstGAN outperforms other baselines, achieves comparable performance to state-of-the-art models, and efficiently generates molecules with multi-property optimization. The code is available at: https://github.com/tang777777/InstGAN.

We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).

Abstract We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is $O(n(L+l))$ steps, where $n$ is the number of nodes and $L$ and $l$ are the grid dimensions.

Summary The domination problem is one of the fundamental graph problems, and there are many variations. In this article, we propose a new problem called the minus ‐domination problem where , and are integers such that , , and . The problem is to assign a value from for each vertex in a graph such that the local summation of values is greater than or equal to . We also propose a framework named the bounded lattice domination for a class of domination problems, including the minus ‐domination problem. Then, we present a self‐stabilizing distributed algorithm under the distance‐2 model for the bounded lattice domination. Here, self‐stabilization is a class of fault‐tolerant distributed algorithms that tolerate transient faults. The time complexity for convergence is , where is the number of processes in a network if the cardinality of the domain of process values is finite and constant. Otherwise, the time complexity for convergence is .

Summary Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is steps and the space complexity is bits, where is the number of processes. Finally, we extend the notion of 1‐MIS to ‐MIS for each nonnegative integer , and compare the set sizes of ‐MIS () and the maximum independent set.

Summary A metamorphic robotic system (MRS) is composed of anonymous, memoryless, and autonomous modules that execute an identical distributed algorithm to move while keeping the connectivity of the modules. For an MRS, the number of modules required to solve a given task is an important complexity measure. Here, we consider evacuation from a finite two‐dimensional square grid field by an MRS. This study aims to establish the minimum number of modules required to solve the evacuation problem under several conditions. We consider a rectangular field surrounded by walls with at least one exit. Our results show that two modules are necessary and sufficient for evacuation from any rectangular field if equipped with a global compass, which provides the modules with a common sense of direction. After that, we focus on the case of modules without a global compass and show that four (resp. seven) modules are necessary and sufficient for restricted (resp. any) initial shapes of an MRS. We also show that two modules are sufficient when an MRS is touching a wall in an initial configuration. Then, we clarify the condition to stop an MRS after evacuation of a rectangular field. Finally, we extend these results to mazes and convex fields.

Summary In this article, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane.

We propose a silent self-stabilizing asynchronous distributed algorithm to find a 2-minimal dominating set (2-MDS) in networks of girth at least 7. Given a graph$G=(V, E)$, a 2-MDS of$G$is a minimal dominating set$D\subseteq V$such that$D\backslash \{p_{i},p_{j}\}\cup\{p_{z}\}$is not a dominating set for any nodes$p_{i},p_{j}\in L (p_{i}\neq p_{j})$and$p_{z}\ /{\!\!\!\in} D$. The girth is the length of the shortest cycles in the graph. We assume that the processes have unique identifiers. The proposed algorithm constructs a 2-MDS in the networks of girth at least 7 under the weakly fair distributed daemon. The time complexity is$O(nH)$rounds, and the space complexity is$O(\log n)$bits per process, where$n$is the number of processes and$H$is the diameter of the network.

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Summary We consider the local (1,|Ni|)‐critical section (CS) problem where Ni is the set of neighboring processes for each process Pi. It dynamically maintains two disjoint dominating sets and is one of the generalizations of the mutual exclusion problem. The problem is one of controlling the system in such a way that, for each process, among its neighbors and itself, at least one process must be in the CS and at least one process must be out of the CS at each time. That is, in the system G=(V,E), there are always two disjoint dominating sets A1(⊂V) and A2(=V\A1) and each process alternates between its rule A1 and A2 infinitely. It is useful for sleep scheduling or cluster head scheduling in sensor networks. In this paper, first, we show the necessary and sufficient conditions to solve the problem without any deadlock detection. To discuss the conditions, we consider an inefficient (costly) self‐stabilizing algorithm for the local (1,|Ni|)‐CS problem. After that, an efficient self‐stabilizing algorithm for the local (1,|Ni|)‐CS problem is proposed under an additional assumption that the graph does not have a special matching, which we call unpreventable colorable maximal matching. The convergence time of the proposed algorithm is O(n) rounds under the weakly fair distributed daemon.

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.

If a graph G = (V, E) has no isolated nodes and D ⊂ V is a minimal dominating set, then V D is a dominating set [1]. In such graphs, there are two disjoint minimal dominating sets A and B. In this paper, we propose an asynchronous self-stabilizing distributed algorithm for finding such a pair of sets with safe convergence. We assume that the first feasible safe configuration satisfies A is a dominating set. The second feasible safe configuration satisfies A is a minimal dominating set. The third feasible safe configuration satisfies A is a minimal dominating set, B is a dominating set and A and B are disjoint. Finally, the legitimate configuration satisfies A and B are disjoint minimal dominating sets.

A connected dominating set (CDS) is useful in forming a virtual backbone in wireless ad hoc or sensor networks because these networks lack a fixed infrastructure and centralized management. Self-stabilization guarantees that the system tolerates any finite number of transient faults and does not need any initialization. The safe convergence property guarantees that the system quickly converges to a feasible safe configuration, and subsequently converges to a legitimate configuration without violating safety. A previous publication on a safely converging algorithm for the minimum CDS assumed a phase clock synchronizer, which is a very strong assumption. In this paper, we propose the first asynchronous self-stabilizing (6+ϵ)-approximation algorithm with safe convergence for the minimum CDS in networks modeled by unit disk graphs (UDGs). We assume that the feasible safe configuration satisfies the condition that a dominating set is constructed. The convergence time to a feasible safe configuration is one round, and the convergence time to a legitimate configuration in which an approximated minimum CDS is constructed is O(max⁡{d2,n}) rounds, and O(n6) steps.

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter critical section. For reducing message complexity, it uses coterie as a communication structure when a process sends a request messages. Informally, coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is O(|Q|) in the worst case, where |Q| is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. Especially, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in critical section simultaneously.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 8 |Dopt| + 1, where Dopt is a minimum connected dominating set. The time complexity is O(n2) steps.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing solution to the problem. Our solution is based on the pruned-MST technique, a heuristic technique to find a minimal cost Steiner tree by pruning unnecessary nodes and edges in a minimum cost spanning tree, provided that a minimum spanning tree is available. Finally we propose an algorithm to reduce the cost of the solution.