# Partial gathering of mobile agents in dynamic rings111The conference version
of this paper is published in the proceedings of 22nd International Symposium
on Stabilization, Safety, and Security of Distributed Systems (SSS
2021).222This work was partially supported by JSPS KAKENHI Grant Number
18K18029, 18K18031, 20H04140, 20KK0232, 21K17706, and 22K11971; the Hibi
Science Foundation; and Foundation of Public Interest of Tatematsu.

Masahiro Shibata<EMAIL_ADDRESS>Yuichi Sudo<EMAIL_ADDRESS>Junya Nakamura<EMAIL_ADDRESS>Yonghwan Kim<EMAIL_ADDRESS>Graduate
school of Computer Science and Systems Engineering, Kyushu Institute of
Technology
680-4 Kawazu, Iizuka, Fukuoka 820-8502, Japan  Graduate School of Computer and
Information Sciences, Hosei University
3-7-2 Kajino-cho, Koganei-shi, Tokyo, 184-8584, Japan  Information and Media
Center, Toyohashi University of Technology
1-1 Hibarigaoka, Tempaku-cho, Toyohashi, Aichi, 441-8580, Japan  Graduate
School of Computer Science and Engineering, Nagoya Institute of Technology
Gokiso-cho, Showa-ku, Nagoya, Aichi, 466-8555 Japan

###### Abstract

In this paper, we consider the partial gathering problem of mobile agents in
synchronous dynamic bidirectional ring networks. The partial gathering problem
is a generalization of the (well-investigated) total gathering problem, which
requires that all $k$ agents distributed in the network terminate at a non-
predetermined single node. The partial gathering problem requires, for a given
positive integer $g\,(<k)$, that agents terminate in a configuration such that
either at least $g$ agents or no agent exists at each node. When $k\geq 2g$,
the requirement for the partial gathering problem is strictly weaker than that
for the total gathering problem, and thus it is interesting to clarify the
difference in the move complexity between them. So far, the partial gathering
problem has been considered in static graphs. In this paper, we start
considering partial gathering in dynamic graphs. As a first step, we consider
this problem in 1-interval connected rings, that is, one of the links in a
ring may be missing at each time step. In such networks, focusing on the
relationship between the values of $k$ and $g$, we fully characterize the
solvability of the partial gathering problem and analyze the move complexity
of the proposed algorithms when the problem can be solved. First, we show that
the $g$-partial gathering problem is unsolvable when $k\leq 2g$. Second, we
show that the problem can be solved with $O(n\log g)$ time and the total
number of $O(gn\log g)$ moves when $2g+1\leq k\leq 3g-2$. Third, we show that
the problem can be solved with $O(n)$ time and the total number of $O(kn)$
moves when $3g-1\leq k\leq 8g-4$. Notice that since $k=O(g)$ holds when
$3g-1\leq k\leq 8g-4$, the move complexity $O(kn)$ in this case can be
represented also as $O(gn)$. Finally, we show that the problem can be solved
with $O(n)$ time and the total number of $O(gn)$ moves when $k\geq 8g-3$.
These results mean that the partial gathering problem can be solved also in
dynamic rings when $k\geq 2g+1$. In addition, agents require a total number of
$\Omega(gn)$ (resp., $\Omega(kn)$) moves to solve the partial (resp., total)
gathering problem. Thus, when $k\geq 3g-1$, agents can solve the partial
gathering problem with the asymptotically optimal total number of $O(gn)$
moves, which is strictly smaller than that for the total gathering problem.

###### keywords:

distributed system, mobile agent, partial gathering problem, dynamic ring

††journal: Theoretical Computer Science

##  1 Introduction

###  1.1 Background and Related Work

A distributed system comprises a set of computing entities (nodes) connected
by communication links. As a promising design paradigm of distributed systems,
(mobile) agents have attracted much attention [1, 2]. The agents can traverse
the system, carrying information collected at visited nodes, and execute an
action at each node using the information to achieve a task. In other words,
agents can encapsulate the process code and data, which simplifies the design
of distributed systems [3, 4].

The total gathering problem (or the rendezvous problem) is a fundamental
problem for agents’ coordination. When a set of $k$ agents are arbitrarily
placed at nodes, this problem requires that all the $k$ agents terminate at a
non-predetermined single node. By meeting at a single node, all agents can
share information or synchronize their behaviors. The total gathering problem
has been considered in various kinds of networks such as rings [5, 6, 7, 8],
trees [9, 10], tori [11], and arbitrary networks [12, 13].

Recently, a variant of the total gathering problem, called the $g$-partial
gathering problem [14], has been considered. This problem does not require all
agents to meet at a single node, but allows agents to meet at several nodes
separately. Concretely, for a given positive integer $g\,(<k)$, this problem
requires that agents terminate in a configuration such that either at least
$g$ agents or no agent exists at each node. From a practical point of view,
the $g$-partial gathering problem is still useful especially in large-scale
networks. That is, when $g$-partial gathering is achieved, agents are
partitioned into groups each of which has at least $g$ agents, each agent can
share information and tasks with agents in the same group, and each group can
partition the network and then patrol its area that it should monitor
efficiently. The $g$-partial gathering problem is interesting also from a
theoretical point of view. Clearly, if $k<2g$ holds, the $g$-partial gathering
problem is equivalent to the total gathering problem. On the other hand, if
$k\geq 2g$ holds, the requirement for the $g$-partial gathering problem is
strictly weaker than that for the total gathering problem. Thus, there exists
possibility that the $g$-partial gathering problem can be solved with strictly
smaller total number of moves (i.e., lower costs) compared to the total
gathering problem.

As related work, Shibata et al. considered the $g$-partial gathering problem
in rings [14, 15, 16], trees [17], and arbitrary networks [18]. In [14, 15],
they considered it in unidirectional ring networks with whiteboards (or memory
spaces that agents can read and write) at nodes. They mainly showed that, if
agents have distinct IDs and the algorithm is deterministic, or if agents do
not have distinct IDs and the algorithm is randomized, agents can achieve
$g$-partial gathering with the total number of $O(gn)$ moves (in expectation),
where $n$ is the number of nodes. Notice that in the above results agents do
not have any global knowledge such as $n$ or $k$. In [16], they considered
$g$-partial gathering for another mobile entity called mobile robots that have
no memory but can observe all nodes and robots in the network. In the case of
using mobile robots, they also showed that $g$-partial gathering can be
achieved with the total number of $O(gn)$ moves. In addition, the $g$-partial
(resp., the total) gathering problem in ring networks requires a total number
of $\Omega(gn)$ (resp., $\Omega(kn)$) moves. Thus, the above results are
asymptotically optimal in terms of the total number of moves, and the number
$O(gn)$ is strictly smaller than that for the total gathering problem when
$g=o(k)$. In tree and arbitrary networks, they also proposed algorithms to
solve the $g$-partial gathering problem with strictly smaller total number of
moves compared to the total gathering problem for some settings.

While all the above work on the total gathering problem and the $g$-partial
gathering problem are considered in static graphs where a network topology
does not change during an execution, recently many problems involving agents
have been studied in dynamic graphs, where a topology changes during an
execution. For example, the total gathering problem [19], the exploration
problem [20, 21], the compact configuration problem [22], the patrolling
problem [23], and the uniform deployment problem [24] are considered in
dynamic graphs. In [19], Luna et al. considered the total gathering problem in
1-interval connected rings, that is, one of the links in a ring may be missing
at each time step. In such networks, they considered the trade-off between the
existence of agent ability (chirality and cross detection) and the algorithm
performances. However, to the best of our knowledge, there is no work for
$g$-partial gathering in dynamic graphs.

Figure 1: An example of the $g$-partial gathering problem in a dynamic ring
($g=3$).

###  1.2 Our Contribution

In this paper, we consider the $g$-partial gathering problem of mobile agents
in 1-interval connected rings [19, 20, 22, 24]. An example is given in Fig. 1.
We assume that the ring is bidirectional and each node has a whiteboard. In
addition, we assume that agents have distinct IDs, chirality, knowledge of $n$
and $k$, and behave fully synchronously. In such settings, focusing on the
relationship between the values of $k$ and $g$, we fully characterize the
solvability of the $g$-partial gathering problem and analyze the time and move
complexities of the proposed algorithms when the problem can be solved.

We summarize our results and the existing result [14] for agents with distinct
IDs in static rings in Table 1. First, we show that the $g$-partial gathering
problem is unsolvable when $k\leq 2g$. Second, we show that the problem can be
solved with $O(n\log g)$ time and the total number of $O(gn\log g)$ moves when
$2g+1\leq k\leq 3g-2$. Third, we show that the problem can be solved with
$O(n)$ time and the total number of $O(kn)$ moves when $3g-1\leq k\leq 8g-4$.
Notice that since $k=O(g)$ holds when $3g-1\leq k\leq 8g-4$, the move
complexity $O(kn)$ in this case can be represented also as $O(gn)$. Finally,
we show that the problem can be solved with $O(n)$ time and the total number
of $O(gn)$ moves when $k\geq 8g-3$. These results mean that the $g$-partial
gathering problem can be solved also in dynamic rings when $k\geq 2g+1$. In
particular, when $k\geq 3g-1$, the time complexity $O(n)$ of the proposed
algorithms is asymptotically optimal and the total number of $O(gn)$ moves is
also asymptotically optimal, which is strictly smaller than the move
complexity for the total gathering problem. Moreover, it is worthwhile to
mention that, total gathering, which is equivalent to $g$-partial gathering
with $k<2g$, cannot be solved in 1-interval connected rings [19]. Thus, Luna
et al. [19] solve the total gathering problem by relaxing the problem
specification: they regard that gathering is achieved when every agent stays
at one of the two neighboring nodes. On the other hand, $g$-partial gathering
with $k>2g$, which we address in this paper, does not require such relaxation.

Table 1: Results of $g$-partial gathering for agents with distinct IDs in ring networks for the case of $k\geq 2g$ ($n$: #nodes, $k$: #agents). | Result in [14] | Results of this paper
---|---|---
|  Result 1 (Sec. 3) |  Result 2 (Sec. 4) |  Result 3 (Sec. 5) |  Result 4 (Sec. 6)
Static/Dynamic ring | Static | Dynamic | Dynamic | Dynamic | Dynamic
Knowledge of $n$ and $k$ | No | Available | Available | Available | Available
Relation between $k$ and $g$ | No condition | $k\leq 2g$ | $2g+1\leq k\leq 3g-2$ | $3g-1\leq k\leq 8g-4$ | $k\geq 8g-3$
Solvable/Unsolvable | Solvable | Unsolvable | Solvable | Solvable | Solvable
Time complexity | $\Theta(n)$ | - | $O(n\log g)$ | $\Theta(n)$ | $\Theta(n)$
Agent moves | $\Theta(gn)$ | - | $O(gn\log g)$ | $O(kn)(=O(gn))$ | $\Theta(gn)$

##  2 Preliminaries

###  2.1 System Model

We basically follow the model defined in [19]. A dynamic bidirectional ring
$R$ is defined as 2-tuple $R=(V,E)$, where
$V=\\{v_{0},v_{1},\ldots,v_{n-1}\\}$ is a set of $n$ nodes and
$E=\\{e_{0},e_{1},\ldots,e_{n-1}\\}$ $(e_{i}$=$\\{v_{i}$, $v_{(i+1)\bmod
n}\\})$ is a set of links. For simplicity, we denote $v_{(i+j)\mod n}$ (resp.,
$e_{(i+j)\mod n}$) by $v_{i+j}$ (resp., $e_{i+j}$). We define the direction
from $v_{i}$ to $v_{i+1}$ (resp., $v_{i}$ to $v_{i-1}$) as the forward or
clockwise (resp., backward or counterclockwise) direction. In addition, one of
the links in a ring may be missing at each time step, and the missing link is
chosen by an adversarial scheduler. Such a dynamic ring is known as a
1-interval connected ring. The distance from node $v_{i}$ to $v_{j}$ is
defined to be $\min\\{(j-i)\mod n,(i-j)\mod n\\}$. Notice that this definition
of the distance is correct when no link from $v_{i}$ to $v_{j}$ (resp.,
$v_{j}$ to $v_{i}$) is missing when the distance is $(j-i)\mod n$ (resp.,
$(i-j)\mod n$). Moreover, we assume that nodes are anonymous, i.e., they do
not have IDs. Every node $v_{i}\in V$ has a whiteboard that agents at node
$v_{i}$ can read from and write on.

Let $A=\\{a_{0},a_{1},\ldots$ $,a_{k-1}\\}$ be a set of $k\,(\leq n)$ agents.
Agents can move through directed links, that is, they can move from $v_{i}$ to
$v_{i+1}$ (i.e., move forward) or from $v_{i}$ to $v_{i-1}$ (i.e., move
backward) for any $i$. Agents have distinct IDs and knowledge of $n$ and $k$.
Agents have chirality, that is, they agree on the orientation of clockwise and
counterclockwise direction in the ring. In addition, agents cannot detect
whether other agents exist at the current node or not. An agent $a_{i}$ is
defined as a deterministic finite automaton $(S$, $W$, $\delta$,
$s_{\textit{initial}}$, $s_{\textit{final}}$, $w_{\textit{initial}}$,
$w^{\prime}_{\textit{initial}})$. The first element $S$ is the set of all
states of an agent, including two special states, initial state
$s_{\textit{initial}}$ and final state $s_{\textit{final}}$. The second
element $W$ is the set of all states (contents) of a whiteboard, including two
special initial states $w_{\textit{initial}}$ and
$w^{\prime}_{\textit{initial}}$. We explain $w_{\textit{initial}}$ and
$w^{\prime}_{\textit{initial}}$ in the next paragraph. The third element
$\delta:S\times W\mapsto S\times W\times M$ is the state transition function
that decides, from the current state of $a_{i}$ and the current node’s
whiteboard, the next states of $a_{i}$ and the whiteboard, and whether $a_{i}$
moves to its neighboring node or not. The last element $M=\\{-1,0,1\\}$ in
$\delta$ represents whether $a_{i}$ makes a movement or not. The value $1$
(resp., $-1$) means moving forward (resp., backward) and 0 means staying at
the current node. We assume that
$\delta\,(s_{\textit{final}},w_{j})=(s_{\textit{final}},w_{j},0)$ holds for
any state $w_{j}\in W$, which means that $a_{i}$ never changes its state,
updates the contents of a whiteboard, or leaves the current node once it
reaches state $s_{\textit{final}}$. We say that an agent terminates when its
state changes to $s_{\textit{final}}$. Notice that
$S,\delta,s_{\textit{initial}}$, and $s_{\textit{final}}$ can be dependent on
the agent’s ID.

In an agent system, (global) configuration $c$ is defined as a product of the
states of all agents, the states (whiteboards’ contents) of all nodes, and the
locations (i.e., the current nodes) of all agents. We define $C$ as a set of
all configurations. In an initial configuration $c_{0}\in C$, we assume that
agents are deployed arbitrarily at mutually distinct nodes (or no two agents
start at the same node), and the state of each whiteboard is
$w_{\textit{initial}}$ or $w^{\prime}_{\textit{initial}}$ depending on the
existence of an agent. That is, when an agent exists at node $v$ in the
initial configuration, the initial state of $v^{\prime}$s whiteboard is
$w_{\textit{initial}}$. Otherwise, the state is
$w^{\prime}_{\textit{initial}}$.

During an execution of the algorithm, we assume that agents move
instantaneously, that is, agents always exist at nodes (do not exist on
links). Each agent executes the following four operations in an atomic action:
1) reads the contents of its current node’s whiteboard, 2) executes local
computation (or changes its state), 3) updates the contents of the current
node’s whiteboard, and 4) moves to its neighboring node or stays at the
current node. If several agents exist at the same node, they take atomic
actions interleavingly in an arbitrary order. In addition, when an agent tries
to move to its neighboring node (e.g., from node $v_{j}$ to $v_{j+1}$) but the
corresponding link (e.g., link $e_{j}$) is missing, we say that the agent is
blocked, and it still exists at $v_{j}$ at the beginning of the next atomic
action.

In this paper, we consider a synchronous execution, that is, in each time step
called round, all agents perform atomic actions. Then, an execution starting
from $c_{0}$ is defined as $E=c_{0},c_{1},\ldots$ where each $c_{i}\ (i\geq
1)$ is the configuration reached from $c_{i-1}$ by atomic actions of all
agents. An execution is infinite, or ends in a  final configuration where the
state of every agent is $s_{\textit{final}}$.

###  2.2 The Partial Gathering Problem

The requirement for the partial gathering problem is that, for a given integer
$g$, agents terminate in a configuration such that either at least $g$ agents
or no agent exists at each node. Formally, we define the $g$-partial gathering
problem as follows.

######  Definition 1.

An algorithm solves the $g$-partial gathering problem in dynamic rings when
the following conditions hold:

  * 1.

Execution $E$ is finite (i.e., all agents terminate in state
$s_{\textit{final}}$).

  * 2.

In the final configuration, at least $g$ agents exist at any node where an
agent exists.

In this paper, we evaluate the proposed algorithms by the time complexity (the
number of rounds required for agents to solve the problem) and the total
number of agent moves. In [14], the lower bound on the total number of agent
moves for static rings is shown to be $\Omega(gn)$. This theorem clearly holds
also in dynamic rings.

######  Theorem 1.

A lower bound on the total number of agent moves required to solve the
$g$-partial gathering problem in dynamic rings is $\Omega(gn)$ if $g\geq 2$.

On the time complexity, the following theorem holds.

######  Theorem 2.

A lower bound on the time complexity required to solve the $g$-partial
gathering problem in dynamic rings is $\Omega(n)$.

###### Proof.

We assume that $k<o(n)$ holds, agent $a_{0}$ is placed at node $v_{0}$ and
agents $a_{1},a_{2},\ldots,a_{k-1}$ are respectively placed at nodes
$v_{(n-1)-(k-1)+1}$, $v_{(n-1)-(k-1)+2}$, $\ldots$ , $v_{n-1}$ in the initial
configuration, and link $e_{n-1}$ (link connecting $v_{n-1}$ and $v_{0}$) is
missing throughout the execution. Then, the nearest agent of $a_{0}$ is
$a_{1}$ and the distance is $\Omega(n)$. Hence, $a_{0}$ requires at least
$\Omega(n)$ rounds to meet with other agents, and the theorem follows. ∎

##  3 The case of $k\leq 2g$

In this section, we show the impossibility result in the case of $k\leq 2g$.

######  Theorem 3.

When $k\leq 2g$ holds, the $g$-partial gathering problem cannot be solved in
dynamic rings.

###### Proof.

When $k<2g$ holds, the $g$-partial gathering problem is equivalent to the
total gathering problem, and it is shown that total gathering requiring all
the $k$ agents to meet at the same node is impossible in 1-interval connected
rings [19]. Hence, in the following we show the impossibility in the case
$k=2g$. We show this by contradiction, that is, we assume that there exists an
algorithm $\cal{A}$ to solve the $g$-partial gathering problem with $k=2g$
agents in dynamic rings. Let $c_{t}$ be the first configuration from which no
agent moves anymore, that is, agents termite the algorithm execution in the
final configuration $c_{t^{\prime}}$ for some $t^{\prime}\geq t$ and the
placement of agents in $c_{t^{\prime\prime}}$ for any $t^{\prime\prime}$
($t^{\prime\prime}\geq t$) achieves $g$-partial gathering. In addition, let an
agent node be a node where an agent exists. In the following, we consider the
cases where the number of agent nodes in $c_{t-1}$ is (i) two and (ii) at
least three and we show that agents cannot achieve $g$-partial gathering from
any case.

First, we consider the case that (i) there exist exactly two agent nodes in
$c_{t-1}$. Let $v_{a}$ and $v_{b}$ be the agent nodes and $k_{a}$ (resp.,
$k_{b}$) be the number of agents at $v_{a}$ (resp., $v_{b}$). Without loss of
generality, in $c_{t-1}$, we assume that $k_{a}>k_{b}$ holds and there exist
$g+c$ agents and $g-c$ agents at $v_{a}$ and $v_{b}$, respectively, for some
positive integer $c\,(1\leq c\leq g-1$). Then, since $k=2g$ holds, the
$g$-partial gathering-achieved placement of agents in $c_{t}$ is either that
(a) all the $k$ agents gather at a single node or (b) some $g$ agents gather
at some node and the other $g~{}(=k-g)$ agents gather at another node. To
reach configuration (a) or (b) from $c_{t-1}$, obviously at least $c$ agents
in total need to move through a link between $v_{a}$ and $v_{b}$. However, the
adversary can make the link between $v_{a}$ and $v_{b}$ be missing in
$c_{t-1}$, which means that $g$-partial gathering is not achieved in $c_{t}$.
Hence, agents cannot achieve $g$-partial gathering in case (i).

Next, we consider the case that (ii) there exist at least three agent nodes in
$c_{t-1}$. Since $k=2g$ holds, there exist at least two agent nodes
$v_{a}^{\textit{less}}$ and $v_{b}^{\textit{less}}$ with less than $g$ agents
each in $c_{t-1}$. Let $e_{a}^{f}$ (resp., $e_{a}^{b}$) be the link connecting
$v_{a}^{\textit{less}}$ and $v_{a}^{\textit{less}}$’s forward (resp.,
backward) neighboring node. We define $e_{b}^{f}$ and $e_{b}^{b}$ similarly.
Then, from $c_{t-1}$, to achieve $g$-partial gathering (i.e., reach
configuration (a) or (b) in the previous paragraph), it is obviously necessary
that at least two links of either $e_{a}^{f}$ or $e_{a}^{b}$, and either
$e_{b}^{f}$ or $e_{b}^{b}$, are passed by an agent. However, the adversary can
make $e_{a}^{f}$, $e_{a}^{b}$, $e_{b}^{f}$, or $e_{b}^{b}$ be missing in
$c_{t-1}$, which means agents cannot reach configuration (a) or (b) in $c_{t}$
and they cannot achieve $g$-partial gathering also from in case (ii).
Therefore, the theorem follows. ∎

##  4 The case of $2g+1\leq k\leq 3g-2$

In this section, when $2g+1\leq k\leq 3g-2$, we proposed an algorithm to solve
the $g$-partial gathering problem in dynamic rings with $O(n\log g)$ rounds
and the total number of $O(gn\log g)$ moves. In this algorithm, all agents try
to travel once around the ring to get IDs of all agents, and then determine a
single common node where all agents should gather. However, it is possible
that some agent cannot travel once around the ring and get IDs of all agents
due to missing links. Agents treat this by additional behaviors explained by
the following subsections. The algorithm comprises two phases: the selection
phase and the gathering phase. In the selection phase, agents move in the ring
and determine the gathering node where they should gather. In the gathering
phase, agents try to stay at the gathering node.

###  4.1 Selection phase

The aim of this phase is that each agent achieves either of the following two
goals: (i) It travels once around the ring and gets IDs of all agents, or (ii)
it detects that all agents stay at the same node. To this end, we use an idea
similar to [19] which considers total gathering in dynamic rings. First, each
agent $a_{i}$ writes its ID on the current whiteboard and then tries to move
forward for $3n$ rounds. During the movement, $a_{i}$ memorizes values of
observed IDs to array $a_{i}.\textit{ids}$[ ]. After the $3n$ rounds, the
number $a_{i}.\textit{nVisited}$ of nodes that $a_{i}$ has visited is (a) at
least $n$ or (b) less than $n$ due to missing links. In case (a), $a_{i}$ must
have completed traveling once around the ring. Thus, $a_{i}$ can get IDs of
all $k$ agents (goal (i) is achieved). Then, $a_{i}$ (and the other agents)
select the gathering node $v_{\textit{gather}}$ as the node where the minimum
ID min is written.

In case (b) (i.e., $a_{i}$ has visited less than $n$ nodes during the $3n$
rounds), we show in Lemma 1 that all $k$ agents stay at the same node (goal
(ii) is achieved). This situation means that agents already achieve
$g$-partial (or total) gathering, and they terminate the algorithm execution.

Table 2: Global variables used in proposed algorithms. Variables for agent
$a_{i}$
---
Type | Name | Meaning | Initial value
int | $a_{i}.\textit{rounds}$ |  | number of rounds from some round
---
1
int | $a_{i}.\textit{nIDs}$ |  |  number of different IDs that $a_{i}$ has observed from some round
---
0
int | $a_{i}.\textit{nVisited}$ |  |  number of nodes that $a_{i}$ has ever visited
---
0
int | $a_{i}.\textit{rank}$ |  | ordinal number of how its ID is small
---
among IDs of agents at the same node
0
int | $a_{i}.\textit{dir}$ |  |  direction to which $a_{i}$ tries to move (1: forward, -1: backward)
---
0
array | $a_{i}.\textit{ids}[]$ |  |  sequence of IDs that $a_{i}$ has observed
---
$\perp$
Variables for node $v_{j}$
Type | Name | Meaning | Initial value
int | $v_{j}.{id}$ |  |  ID stored by $v_{j}$
---
$\perp$
int | $v_{j}.\textit{nAgents}$ |  |  number of agents staying at $v_{j}$
---
0
int | $v_{j}.\textit{dir}$ |  |  direction to which an agent group that visited $v_{j}$
---
for the first time tries to move (1: forward, -1: backward)
0
boolean | $v_{j}.{\textit{waiting}}$ |  |  whether some agents that keep staying at $v_{j}$ exist or not
---
false
boolean | $v_{j}.{\textit{fMarked}}$ |  |  whether $v_{j}$ is visited by a forward group or not
---
false
boolean | $v_{j}.{\textit{bMarked}}$ |  |  whether $v_{j}$ is visited by a backward group or not
---
false
boolean | $v_{j}.{\textit{candi}}$ |  |  whether $v_{j}$ is a gathering-candidate node or not
---
false

The pseudocode of the selection phase is described in Algorithm 1. Global
variables are summarized in Table 2 (several variables are used in other
sections). Note that, during the selection phase, an agent $a_{i}$ may visit
more than $n$ nodes and observe more than $k$ IDs when it is blocked less than
$2n$ times. In this case, $a_{i}$ memorizes only the first $k$ IDs to memorize
the location of the gathering node correctly (line 8). In addition, even if
$a_{i}$ has visited at least $n$ nodes and got IDs of all $k$ agents, it is
possible that another agent $a_{j}$ has blocked at least $2n+1$ times and it
does not get IDs of all $k$ agents. In this case, all agents stay at the same
node $v_{j}$ (Lemma 1), and $a_{i}$ detects the fact when the number
$v_{j}.\textit{nAgents}$ at the current node $v_{j}$ is equal to the number
$a_{i}.\textit{nIDs}$ of different IDs that $a_{i}$ has ever observed (these
values are equal to $k$). Then, $a_{i}$ (and the other agents) terminate the
algorithm execution since $g$-partial (or total) gathering is already achieved
(line 14).

1

Main Routine of Agent $a_{i}$:

2 $v_{j}.\textit{id}:=a_{i}.\textit{id}$,
$a_{i}.\textit{ids}[a_{i}.\textit{nIDs}]:=v_{j}.\textit{id}$

3 $a_{i}.\textit{nIDs}:=a_{i}.\textit{nIDs}+1$,
$v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

4 while  _$a_{i}.\textit{rounds}\leq 3n$_ do

5 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

6 Try to move from the current node $v_{j}$ to the forward node $v_{j+1}$

7 if  _$a_{i}$ reached $v_{j+1}$ (that becomes new $v_{j}$)_ then

8 $a_{i}.\textit{nVisited}:=a_{i}.\textit{nVisited}+1$

9 if  _$(v_{j}.\textit{id}\neq\perp)\land(a_{i}.\textit{nIDs} <k)$_ then

10 $a_{i}.\textit{ids}[a_{i}.\textit{nIDs}]:=v_{j}.\textit{id}$,
$a_{i}.\textit{nIDs}:=a_{i}.\textit{nIDs}+1$

11

12

13 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$,
$a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

14

15if $a_{i}.\textit{nVisited}<n$ then terminate the algorithm execution // all
$k$ agents stay at the current node

16

17if  _$a_{i}.\textit{nVisited}\geq n$_ then

18 // $a_{i}$ traveled once around the ring and got IDs of all $k$ agents

19 if $v_{j}.\textit{nAgents}=a_{i}.\textit{nIDs}$ then terminate the
algorithm execution // all $k$ agents stay at the current node

20 Let min be the minimum ID among $a_{i}.\textit{ids}[\,]$ and select the
gathering node $v_{\textit{gather}}$ as a node where min is written

21 Terminate the selection phase and enter the gathering phase

22

Algorithm 1 The behavior of agent $a_{i}$ in the selection phase ($v_{j}$ is
the current node of $a_{i}$.)

Concerning the selection phase, we have the following lemma.

######  Lemma 1.

After finishing Algorithm 1, each agent achieves either of the following two
goals: (i) It travels once around the ring and gets IDs of all agents, or (ii)
it detects that all agents stay at the same node.

###### Proof.

We use a proof idea similar to that in [19], which considers total gathering
in dynamic rings and shows that agents achieve goal (i) or (ii) after the
movement. We consider the cases that the value of $a_{i}.\textit{nVisited}$
after executing Algorithm 1 is (a) at least $n$ (line 12), and (b) less than
$n$ (line 11) in this order. First, if $a_{i}.\textit{nVisited}\geq n$ holds,
clearly $a_{i}$ travels at least once around the ring and gets IDs of all the
$k$ agents. Thus, $a_{i}$ achieves goal (i). Next, we consider the case that
(b) $a_{i}.\textit{nVisited}<n$ holds. In this case, we show that all agents
stay at the same node. We show this by contradiction, that is, we assume that
some agents $a_{i}$ and $a_{j}$ exist at different nodes after executing
Algorithm 1. We consider the distance $\textit{d}_{\textit{ji}}$ from $a_{j}$
to $a_{i}$, that is, when $a_{i}$ is blocked and $a_{j}$ moves forward at some
round, the value of $d_{\textit{ji}}$ decreases by one and vice versa. Then,
if $a_{i}$ is not blocked at some round, the value of $d_{\textit{ji}}$
increases by at most one since all agents try to move forward. This happens at
most $n-1$ rounds because of $a_{i}.\textit{nVisited}<n$. On the other hand,
if $a_{i}$ is blocked at some round, $d_{\textit{ji}}$ decreases by one (or is
already 0). This happens at least $2n+1$ rounds. Then, since the value of
$d_{\textit{ji}}$ is at most $n-1$ in the initial configuration, the value of
$d_{\textit{ji}}$ after executing Algorithm 1 is
$\max\\{(n-1)+(n-1)-(2n+1),0\\}=0$. This means that $a_{i}$ and $a_{j}$ (and
the other agents) stay at the same node, which is a contradiction. Thus,
agents achieve goal (ii) and the lemma follows. ∎

###  4.2 Gathering phase

In this phase, agents aim to achieve $g$-partial (or total) gathering by
trying to visit the gathering node $v_{\textit{gather}}$. Concretely, for $3n$
rounds from the beginning of this phase, each agent $a_{i}$ tries to move
forward until it reaches $v_{\textit{gather}}$. If agents are blocked few
times, all agents can reach $v_{\textit{gather}}$ and they achieve $g$-partial
(or total) gathering. However, it is possible that some agent cannot reach
$v_{\textit{gather}}$ due to link-missings, resulting in a situation such that
there exists a node with only less than $g$ agents. To treat this, we
introduce a technique called splitting. Intuitively, in this technique, when
at least $g+c~{}(c\geq 2)$ agents exist at some node, from there some $c/2$
agents try to move forward and other $c/2$ agents try to move backward in
order to visit the node with less than $g$ agents, and the remaining $g$
agents stay at the current node. By repeating this behavior and additional
behaviors explained later, agents aim to reduce the gap between $g$ and the
number of agents at the node with less than $g$ agents, and eventually achieve
$g$-partial gathering.

Figure 2: An execution example of the gathering phase when $2g+1\leq k\leq
3g-2$ ($g=4$).

Concretely, after the $3n$ round from when agents tried to move forward to
reach $v_{\textit{gather}}$, by the similar discussion of the proof of Lemma
1, all agents that do not reach $v_{\textit{gather}}$ stay at the same node.
Letting $v^{\prime}$ be the node, there are at most two nodes
$v_{\textit{gather}}$ and $v^{\prime}$ where agents exist after the movement.
An example in the case of $g=4$ is given in Fig. 2(a) (we omit nodes unrelated
to the explanation). Then, when agents recognize by knowledge of $k$ and $g$
that at least $g$ agents exist at both $v_{\textit{gather}}$ and $v^{\prime}$,
they already achieve $g$-partial gathering and thus terminate the algorithm
execution. Otherwise, i.e., when $v_{\textit{gather}}$ or $v^{\prime}$ has
only less than $g$ agents, agents use the splitting technique and some agents
try to visit the node with less than $g$ agents. This technique comprises at
most $\lceil\log g\rceil$ subphases. Without loss of generality, at the
beginning of the splitting, we assume that there exist $g-c^{\prime}~{}(1\leq
c^{\prime}\leq g-1)$ agents at $v^{\prime}$. Then, letting
$c=k-2g+c^{\prime}$, there exist $k-(g-c^{\prime})=g+c$ agents at
$v_{\textit{gather}}$. Notice that $c>c^{\prime}$ and $c\geq 2$ hold. First,
each agent $a_{i}$ at $v_{\textit{gather}}$ calculates how small its ID is
among the $g+c$ agents. We denote the ordinal number by $a_{i}.\textit{rank}$.
Then, if $1\leq a_{i}.\textit{rank}\leq g$, $a_{i}$ stays at
$v_{\textit{gather}}$. If $g+1\leq a_{i}.\textit{rank}\leq\lfloor c/2\rfloor$,
it belongs to the forward agent group $A_{f}$. Otherwise, i.e., if $\lfloor
c/2\rfloor+1\leq a_{i}.\textit{rank}\leq g+c$, it belongs to the backward
agent group $A_{b}$. Thereafter, for $n$ rounds, the forward agent group
$A_{f}$ (resp., the backward group $A_{b}$) tries to move forward (resp.,
backward) until visiting $v^{\prime}$ (Fig. 2(b)). Then, since at most one
link is missing at each round, $A_{f}$ or $A_{b}$ can move to the next node
during the movement and either of them can reach $v^{\prime}$ (Fig. 2(c)).

After the $n$ rounds, since $A_{f}$ or $A_{b}$ can reach $v^{\prime}$, the
number of agents at $v^{\prime}$ increases by at least $\lfloor c/2\rfloor$.
Without loss of generality, we assume that $A_{f}$ could reach $v^{\prime}$
but $A_{b}$ had been blocked and could not reach $v^{\prime}$. Thereafter, all
agents at $v_{\textit{gather}}$ and all agents at $v^{\prime}$ try to move in
the ring and visit the node where $A_{b}$ is currently staying. Concretely,
let $A_{\textit{fb}}$ be the agent group comprising all agents that stayed at
$v_{\textit{gather}}$ for the previous $n$ rounds and $A_{\textit{bf}}$ be the
agent group comprising all agents in $A_{f}$ and all agents that stayed at
$v^{\prime}$ for the previous $n$ rounds. Then, for $n$ rounds,
$A_{\textit{fb}}$ (resp., $A_{\textit{bf}}$) tries to move forward (resp.,
backward) until visiting the node where $A_{b}$ is staying (Fig. 2(d)). After
that, if $A_{\textit{fb}}$ (resp., $A_{\textit{bf}}$) could not reach the node
with $A_{b}$, for $n$ rounds, it switches the direction and tries to move
backward (resp., forward) until visiting the node with $A_{b}$. By there
behaviors, if we assume that there does not exist the node with $A_{b}$, every
node is visited by $A_{\textit{fb}}$ or $A_{\textit{bf}}$ for this $2n$
rounds. Thus, $A_{\textit{fb}}$ or $A_{\textit{bf}}$ can visit the node with
$A_{b}$ (Fig. 2(e)). If $A_{\textit{bf}}$ could reach the node, there exist
$g$ agents at the node with $A_{\textit{fb}}$ and $g-c^{\prime}+c~{}(\geq g)$
agents at the node with $A_{\textit{bf}}$ (and $A_{b}$). Hence, they achieve
$g$-partial gathering and terminate the algorithm execution. Otherwise, i.e.,
if $A_{\textit{fb}}$ could reach the node with $A_{b}$, there exist $g+\lfloor
c/2\rfloor$ agents at the node with $A_{\textit{fb}}$ (and $A_{b}$) and
$g-c^{\prime}+\lceil c/2\rceil$ agents at the node with $A_{\textit{bf}}$.
Then, the gap between $g$ and the number of agents at the node with less than
$g$ agents halves. Thus, by executing such a subphase at most $\lceil\log
g\rceil$ times, agents can make a configuration such that at least $g$ agents
exist at every node where an agent exists ($g$-partial gathering is achieved).

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1$

3

4while  _$a_{i}.\textit{rounds}\leq 3n$_ do

5

6 if  _$v_{j}\neq v_{\textit{gather}}$_ then

7 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

8 Try to move from the current node $v_{j}$ to the forward node $v_{j+1}$
(that may become new $v_{j}$ depending on the existence of a missing link)

9 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

10

11 $a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

12

13if $(v_{j}.\textit{nAgents}\geq g)\land(k-v_{j}.\textit{nAgents}\geq g)$
then terminate the algorithm execution // at least $g$ agents already exist at
both nodes with agents

14 else if  $v_{j}.\textit{nAgents}\geq g+2$ then More()

15 else Less()

16

Algorithm 2 The behavior of agent $a_{i}$ in the gathering phase ($v_{j}$ is
the current node of $a_{i}$.)

1

Main Routine of Agent $a_{i}$:

2 Calculate $a_{i}.\textit{rank}$

3

4if $1\leq a_{i}.\textit{rank}\leq g$ then $a_{i}.\textit{dir}:=0$

5 else if $g+1\leq
a_{i}.\textit{rank}\leq\lfloor(v_{j}.\textit{nAgents}-g)/2\rfloor$ then
$a_{i}.\textit{dir}:=1$

6 else $a_{i}.\textit{dir}:=-1$

7

8Moving($a_{i}.\textit{dir}$)

9

10if $v_{j}.\textit{nAgents}<g$ then
$a_{i}.\textit{dir}:=0,v_{j}.\textit{waiting}:=\textit{true}$

11 else if $v_{j}.\textit{waiting}=\textit{false}$ then
$a_{i}.\textit{dir}:=1$

12 else $a_{i}.\textit{dir}:=-1,v_{j}.\textit{waiting}=\textit{false}$

13 LatterMove($a_{i}.\textit{dir}$)

14

Algorithm 3 Procedure More() ($v_{j}$ is the current node of $a_{i}$.)

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1,v_{j}.\textit{waiting}:=\textit{true}$

3 while  _$a_{i}.\textit{rounds}\leq n$_ do

4 Stay at the current node $v_{j}$

5 $a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

6

7$a_{i}.\textit{dir}:=-1,v_{j}.\textit{waiting}:=\textit{false}$

8 LatterMove($a_{i}.\textit{dir}$)

Algorithm 4 Procedure Less() ($v_{j}$ is the current node of $a_{i}$.)

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1$

3 while  _$a_{i}.\textit{rounds}\leq n$_ do

4 if  _$a_{i}.\textit{dir}:=0$_ then

5 stay at the current node $v_{j}$

6 else

7 while  _$v_{j}.\textit{waiting}=\textit{false}$_ do

8 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

9 Try to move from the current node $v_{j}$ to node $v_{j+a_{i}.\textit{dir}}$
(that may become new $v_{j}$ depending on the existence of a missing link)

10 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

11

12 $a_{i}.\textit{round}:=a_{i}.\textit{round}+1$

13

14

Algorithm 5 Procedure Moving($a_{i}.\textit{dir}$) ($v_{j}$ is the current
node of $a_{i}$.)

1

2Moving($a_{i}.\textit{dir}$)

3 $a_{i}.\textit{dir}:=a_{i}.\textit{dir}\times(-1)$

4 Moving($a_{i}.\textit{dir}$)

5

6if $(v_{j}.\textit{nAgents}\geq g)\land(k-v_{j}.\textit{nAgents}\geq g)$ then
terminate the algorithm execution

7 else if  $v_{j}.\textit{nAgents}\geq g+2$ then More()

8 else Less()

Algorithm 6 Procedure LatterMove($a_{i}.\textit{dir}$) ($v_{j}$ is the current
node of $a_{i}$.)

The pseudocode of the gathering phase is described in Algorithm 2. After
executing the first $3n$ rounds of this phase, each agent $a_{i}$ counts the
number of agents at the current node through $v_{j}.\textit{nAgents}$. If
$v_{j}.\textit{nAgents}\geq g+2$ and the number of agents at the other node
with an agent is less than $g$, $a_{i}$ executes procedure More() to decide
whether it belongs to $A_{f}$ or $A_{b}$, or keeps staying at $v_{j}$,
depending on $a_{i}.\textit{rank}$. The pseudocode of More() is described in
Algorithm 3. If $v_{j}.\textit{nAgents}<g$, $a_{i}$ executes procedure Less()
to keep staying at $v_{j}$ for $n$ rounds and then resume moving. The
pseudocode of Less() is described in Algorithm 4. In Algorithms 3 and 4, we
omit how $a_{i}$ calculates $a_{i}.\textit{rank}$ for simplicity, and agents
use procedures Moving() and LatterMove() to move in the ring, whose
pseudocodes are described in Algorithms 5 and 6, respectively.

Concerning the gathering phase, we have the following lemma.

######  Lemma 2.

After finishing Algorithm 2, agents achieve $g$-partial gathering.

###### Proof.

First, for $3n$ rounds from the beginning of the gathering phase, each agent
tries to move forward to reach $v_{\textit{gather}}$. Then, by the similar
discussion of the proof of Lemma 1, all agents that do not reach
$v_{\textit{gather}}$ stay at the same node $v^{\prime}$. When at least $g$
agents exist at both $v_{\textit{gather}}$ and $v^{\prime}$, they already
achieve $g$-partial gathering and can terminate the algorithm execution there
by the knowledge of $g$ and $k$. On the other hand, when only less than $g$
agents exist at $v^{\prime}$ (resp., $v_{\textit{gather}}$), at least $g+2$
agents exist at $v_{\textit{gather}}$ (resp., $v^{\prime}$) since we consider
the case of $2g+1\leq k\leq 3g-2$. Without loss of generality, we assume that
there exist $g-c^{\prime}~{}(1\leq c^{\prime}\leq g-1)$ agents at
$v^{\prime}$. Then, letting $c=k-2g+c^{\prime}$, there exist
$k-(g-c^{\prime})=k+c$ agents at $v_{\textit{gather}}$. Notice that
$c>c^{\prime}$ and $c\geq 2$ hold.

From such a situation, agents at $v_{\textit{gather}}$ execute More() and then
execute Moving(). In Procedure More(), $\lfloor c/2\rfloor$ agents belong to a
forward group $A_{f}$ and try to move forward and $\lceil c/2\rceil$ agents
belong to a backward group $A_{b}$ and try to move backward in order to visit
$v^{\prime}$ (lines 3 – 5). Since at most one link is missing, $A_{f}$ or
$A_{b}$ can move to the next node unless they already visit $v^{\prime}$, and
hence either of them can visit $v^{\prime}$ within $n$ rounds. Without loss of
generality, we assume that $A_{f}$ could reach $v^{\prime}$ but $A_{b}$ could
not do it due to link-missings. Thereafter, in order to visit the node with
$A_{b}$, by Procedure LatterMove(), agents that stayed at
$v_{\textit{gather}}$ (resp., $v^{\prime}$) belong to an agent group
$A_{\textit{fb}}$ (resp., $A_{\textit{bf}}$) and try to move forward (resp.,
backward) for $n$ rounds and then try to move backward (resp., forward) for
$n$ rounds. Then, when we assume that $A_{b}$ does not exist,
$A_{\textit{fb}}$ and $A_{\textit{bf}}$ can visit all nodes for this $2n$
rounds, and thus either of them can reach the node with $A_{b}$. When
$A_{\textit{bf}}$ reaches the node, at least $g$ agents exist at both nodes
with agents and the can terminate the algorithm there. When $A_{\textit{fb}}$
reaches the node, there exist $g+\lceil c/2\rceil$ agents at the node where
$A_{\textit{fb}}$ exists, and there exist $g-c^{\prime}+\lfloor c/2\rfloor$
agents exist at the node where $A_{\textit{bf}}$ exists (Fig. 2(e)). Since
$c>c^{\prime}$ holds, the gap between $g$ and the number of agents at the node
with less than $g$ agents halves by the above behaviors. Thus, by repeating
such behaviors at most $\lceil\log g\rceil$ times, agents can achieve
$g$-partial gathering. Therefore, the lemma follows. ∎

We have the following theorem for the proposed algorithm.

######  Theorem 4.

When $2g+1\leq k\leq 3g-2$ holds, the proposed algorithm solves the
$g$-partial gathering problem in dynamic rings with $O(n\log g)$ rounds and
the total number of $O(gn\log g)$ moves.

###### Proof.

By Lemmas 1 and 2, the proposed algorithm can solve the $g$-partial gathering
problem. In the following, we analyze the time complexity and the required
total number of agent moves.

First, in the selection phase, each agent tries to move forward for $3n$
rounds in order to determine the gathering node $v_{\textit{gather}}$. Since
$k=O(g)$ holds in this section, This requires $O(n)$ rounds and the total
number of $O(gn)$ moves. Next, in the gathering phase, for $3n$ rounds, each
agent first tries to move forward to reach $v_{\textit{gather}}$, which
requires $O(n)$ rounds and the total number of $O(gn)$ moves. Thereafter, (i)
by Procedure More(), for $n$ rounds, several agents from the node with at
least $g+2$ agents move forward or backward to visit the node with less than
$g$ agents, and (ii) by Procedure LatterMove(), for $2n$ rounds, agent groups
$A_{\textit{fb}}$ and $A_{\textit{bf}}$ move forward or backward to visit the
node with less than $g$ agents. The above behaviors require $O(n)$ rounds and
the total number of $O(gn)$ moves. Since agents repeat such behaviors at most
$\lceil\log g\rceil$ times until achieving $g$-partial gathering, the total
time complexity is $O(n\log g)$ and the total move complexity is $O(gn\log
g)$. Therefore, the theorem follows. ∎

##  5 The case of $3g-1\leq k\leq 8g-4$

In this section, when $3g-1\leq k\leq 8g-4$, we propose a naive algorithm to
solve the problem with $O(n)$ rounds and the total number of $O(kn)$ moves.
Since $k=O(g)$ holds in this case, this algorithm is asymptotically in terms
of both the time and move complexities, similar to the third algorithm
explained in Section 6. The algorithm tactics is the same as that in Section
4, that is, all agents try to travel once around the ring to get IDs of all
agents, and then try to gather at a common single gathering node
$v_{\textit{gather}}$. Hence, similarly to Section 4, the algorithm comprises
the selection phase and the gathering phase. The selection phase is exactly
the same as that in Section 4.1, and we revise the gathering phase to reduce
the total number of agent moves from $O(gn\log g)$ to $O(gn)$, explained by
the following paragraphs.

After agents finish the selection phase, by Lemma 1, (i) all agents travelled
once around the ring and get IDs of all agents (in this case all agents do not
stay at the same node), or (ii) all agents already stay at the same node. In
case (ii), agents already achieve $g$-partial gathering and terminate the
algorithm execution there. In case (i), similarly to Section 4.2, each agent
first tries to move forward for $3n$ rounds to visit the gathering node
$v_{\textit{gather}}$. Then, all agents that do not reach
$v_{\textit{gather}}$ stay at the same node $v^{\prime}$ similarly to Section
4.2. However, different from Section 4.2, when there exist only less than $g$
agents at $v^{\prime}$ (resp., $v_{\textit{gather}}$), there exist at least
$2g$ agents at $v_{\textit{gather}}$ (resp., $v^{\prime}$) since we consider
the case of $3g-1\leq k\leq 8g-4$ in this section. We call such a node with at
least $2g$ agents $v_{\textit{more}}$. Notice that it is possible that at
least $2g$ agents exist at both $v_{\textit{gather}}$ and $v^{\prime}$. Then,
we use this fact and modify (simplify) the splitting technique. Intuitively,
from $v_{\textit{more}}$, an agent group with at least $g$ agents tries to
move forward and another agent group with at least $g$ agents tries to move
backward. In addition, when an agent group with at least $g$ agents visits a
node where less than $g$ agents exist, the less than $g$ agents join the agent
group and try to move in the same direction as that of the group. By this
behavior, it does not happen that all agents are blocked, and agents can
eventually terminate in a configuration such that at least $g$ agents exist at
each node where an agent exists.

Concretely, let $k^{\prime}(\geq 2g)$ be the number of agents staying at
$v_{\textit{more}}$. Then, each agent $a_{i}$ at $v_{\textit{more}}$ first
calculates its $a_{i}.\textit{rank}$. If $1\leq a_{i}.\textit{rank}\leq g$
holds, it belongs to a forward agent group $A_{f}$ and tries to move forward.
Else if ($k^{\prime}<3g)\lor(g+1\leq a_{i}.\textit{rank}\leq 2g)$ holds, it
belongs to the backward agent group $A_{b}$ and tries to move backward. If
$a_{i}$ does not satisfy any of the above conditions, it terminates the
algorithm execution because there still exist at least $g$ agents even after
$A_{f}$ and $A_{b}$ leave $v_{\textit{more}}$. While $A_{f}$ and $A_{b}$ move
in the ring, if $A_{f}$ (resp., $A_{b}$) visits a new node $v_{j}$, it sets a
flag $v_{j}.\textit{fMarked}$ (resp., $v_{j}.\textit{bMarked}$) representing
that $v_{j}$ is visited by $A_{f}$ (resp., $A_{b}$). These flags are used for
an agent group $A$ to check whether or not the current node is visited by
another agent group and $A$ can stop moving in the ring. In addition, if
$A_{f}$ (resp., $A_{b}$) visits a node with less than $g$ agents, the less
than $g$ agents join $A_{f}$ (resp., $A_{b}$) and try to move forward (resp.,
backward). However, it is possible that the number num of agents in the
updated group is more than $2g$. In this case, using their IDs, only $g$
agents continue to try moving and the remaining $\textit{num}-g$ agents
terminate the algorithm execution at the current node. By this behavior, each
link is passed by at most $2g$ agents and the total number of moves for agent
groups can be reduced to $O(gn)$ (this technique is used in Section 6).
Moreover, since $A_{f}$ or $A_{b}$ can visit a next node at each round even
when some link is missing, when $A_{f}$ (resp., $A_{b}$) repeats such a
behavior for $n$ rounds or until it visits some node $v_{j}$ with
$v_{j}.\textit{bMarked}=\textit{true}$ (resp.,
$v_{j}.\textit{fMarked}=\textit{true}$), $A_{b}$ and $A_{f}$ can visit all the
nodes in the ring in total and $g$-partial gathering is achieved.

An example is given in Fig. 3 (we omit nodes unrelated to the explanation).
From (a) to (b), a backward group $A_{b}$ visits a node with two $(<g)$
agents, and the two agents join $A_{b}$. Then, since the number of agents in
the updated $A_{b}$ is $7~{}(>2g)$, only three agents continue to try moving
and the remaining four agents terminate the algorithm execution there ((b) to
(c)). From (c) to (d), we assume that a forward agent group $A_{f}$ continues
to be blocked due to a missing link. Even in this case, $A_{b}$ can continue
to move since there is only one missing link at each round. When $A_{f}$
(resp., $A_{b}$) visits a node with a flag set by $A_{b}$ (resp., $A_{f}$)
like (e), or $n$ rounds passed from when agent groups started trying to move,
agents achieve $g$-partial gathering.

Figure 3: An execution example of the gathering phase when $3g-1\leq k\leq
8g-4$ ($g=3$).

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1$

3

4while  _$a_{i}.\textit{rounds}\leq 3n$_ do

5

6 if  _$v_{j}\neq v_{\textit{gather}}$_ then

7 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

8 Try to move from the current node $v_{j}$ to the forward node $v_{j+1}$
(that may become new $v_{j}$ depending on the existence of a missing link)

9 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

10

11 $a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

12

13if $g\leq v_{j}.\textit{nAgents}\leq 2g-1$ then terminate the algorithm
execution

14 else if  $v_{j}.\textit{nAgents}\geq 2g$ then More2()

15 else Less2()

16

Algorithm 7 The behavior of agent $a_{i}$ in the gathering phase ($v_{j}$ is
the current node of $a_{i}$.)

The pseudocode of the gathering phase is described in Algorithm 7. After
executing the first $3n$ rounds of this phase, each agent $a_{i}$ counts the
number of agents at the current node through $v_{j}.\textit{nAgents}$. If the
number is at least $2g$ (i.e., $v_{j}$ is $v_{\textit{more}}$), $a_{i}$
executes procedure More2() and decides whether it belongs to $A_{f}$ or
$A_{b}$, or terminates the algorithm execution, depending on
$a_{i}.\textit{rank}$. The pseudocode of More2() is described in Algorithm 8.
If the number of agents at $v_{j}$ is less than $g$, $a_{i}$ executes
procedure Less2() and keeps staying at $v_{j}$ until a forward or backward
agent group visits $v_{j}$. The pseudocode of Less2() is described in
Algorithm 9. In Procedures 8 and 9, agents use procedure Moving2() to move in
the ring, whose pseudocode is described in Algorithm 10.

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1$

3 Calculate $a_{i}.\textit{rank}$

4

5if $1\leq a_{i}.\textit{rank}\leq g$ then $a_{i}.\textit{dir}:=1$

6 else if $(v_{j}.\textit{nAgents}<3g)\lor(g+1\leq a_{i}.\textit{rank}\leq
2g)$ then $a_{i}.\textit{dir}:=-1$

7 else Terminate the algorithm execution // There still exist at least $g$
agents even after the forward group and the backward group leave $v_{j}$

8 Moving2()

9

Algorithm 8 Procedure More2() ($v_{j}$ is the current node of $a_{i}$.)

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1$

3 $v_{j}.\textit{waiting}:=\textit{true}$

4 while  _true_ do

5 $a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

6 if
($v_{j}.\textit{fMarked}=\textit{true})\land(v_{j}.\textit{bMarked}=\textit{true})$
then terminate the algorithm execution // A forward group and a backward group
visited $v_{j}$ simultaneously

7 if  _(
$v_{j}.\textit{fMarked}=\textit{true})\lor(v_{j}.\textit{bMarked}=\textit{true})$_
then

8 Calculate $a_{i}.\textit{rank}$

9 if ($v_{j}.\textit{nAgents}\geq 2g$) $\land$ ($a_{i}.rank\geq g+1$) then
terminate the algorithm execution

10 else $a_{i}.\textit{dir}:=v_{j}.\textit{dir}$ and execute Moving2()

11

12

13

Algorithm 9 Procedure Less2() ($v_{j}$ is the current node of $a_{i}$.)

In addition, it is possible that a forward group and a backward group visit
some node simultaneously. This implies that all the nodes to be visited by the
forward and backward groups are already visited, and thus they terminate the
algorithm execution there (line 5 in Algorithm 9 and line 12 in Algorithm 10).
Moreover, it is possible that some link continues to be missing for a long
time when $A_{f}$ and $A_{b}$ are trying to move in the ring; $A_{f}$ and
$A_{b}$ continue to be blocked by the same missing link $e^{\prime}$ and
$A_{f}$ (resp., $A_{b}$) cannot observe a node $v_{j}$ with
$v_{j}.\textit{bMarked}=\textit{true}$ (resp.,
$v_{j}.\textit{fMarked}=\textit{true}$). Even in this case, before they are
blocked by $e^{\prime}$, $A_{f}$ or $A_{b}$ can visit a next node at each
round and they can visit all the $n$ nodes in total within $n$ rounds. Hence,
even if agents do not observe a flag for termination, they can terminate the
algorithm execution after the $n$ rounds from when they start trying to move
(lines 1 and 17 in Algorithm 10).

Concerning the gathering phase, we have the following lemma.

1

Main Routine of Agent $a_{i}$:

2

3while  _$a_{i}.\textit{rounds}\leq n$_ do

4 $a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

5 if ($a_{i}.\textit{dir}=1)\land(v_{j}.\textit{fMarked}=\textit{false})$ then
$v_{j}.\textit{fMarked}:=\textit{true}$

6 if ($a_{i}.\textit{dir}=-1)\land(v_{j}.\textit{bMarked}=\textit{false})$
then $v_{j}.\textit{bMarked}:=\textit{true}$

7

8 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

9 Try to move from the current node $v_{j}$ to node $v_{j+a_{i}.\textit{dir}}$
(that may become new $v_{j}$ depending on the existence of a missing link)

10 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

11

12 if  _$a_{i}$ reached $v_{j+a_{i}.\textit{dir}}$ (that becomes new $v_{j}$)_
then

13 if
$((a_{i}.\textit{dir}=1)\land(v_{j}.\textit{bMarked}=\textit{true}))\lor(a_{i}.\textit{dir}=-1)\land(v_{j}.\textit{fMarked}=\textit{true}))$
then terminate the algorithm execution

14 if ($a_{i}.\textit{dir}=1)$ then $v_{j}.\textit{fMarked}:=\textit{true}$

15 if ($a_{i}.\textit{dir}=-1$) then $v_{j}.\textit{bMarked}:=\textit{true}$

16 if
($v_{j}.\textit{fMarked}=\textit{true})\land(v_{j}.\textit{bMarked}=\textit{true})$
then terminate the algorithm execution // A forward group and a backward group
visited $v_{j}$ simultaneously

17 $v_{j}.\textit{dir}:=a_{i}.\textit{dir}$

18 if  _$v_{j}.\textit{waiting}=\textit{true}$_ then

19 Update $a_{i}.\textit{rank}$

20 if ($v_{j}.\textit{nAgents}\geq 2g$) $\land$ ($a_{i}.rank\geq g+1$) then
terminate the algorithm execution

21

22

23

24Terminate the algorithm execution

25

Algorithm 10 Procedure Moving2() ($v_{j}$ is the current node of $a_{i}$.)

######  Lemma 3.

After finishing Algorithm 7, agents achieve $g$-partial gathering.

###### Proof.

First, for $3n$ rounds from the beginning of the gathering phase, each agent
tries to move forward for reaching $v_{\textit{gather}}$. Then, by the similar
discussion of the proof of Lemma 1, all agents that do not reach
$v_{\textit{gather}}$ stay at the same node $v^{\prime}$. In addition, when
only less than $g$ agents exist at $v^{\prime}$ (resp.,
$v_{\textit{gather}}$), at least $2g$ agents exist at $v_{\textit{gather}}$
(resp., $v^{\prime}$) since we consider the case of $k\geq 3g-1$. Thus, agents
at $v_{\textit{gather}}$ or $v^{\prime}$ execute More2() and then execute
Moving2(). In addition, when some forward group $A_{f}$ or backward group
$A_{b}$ executing Moving2() visits a node with less than $g$ agents, the less
than $g$ agents join the group. If the number num of agents in the updated
group is more than $2g$, by using their IDs, only $g$ agents continue to try
moving, and the remaining $\textit{num}-g\,(\geq g)$ agents terminate the
algorithm execution there. Thus, even after $A_{f}$ or $A_{b}$ leaves node
$v_{j}$ where there originally exist less than $g$ agents, it is guaranteed
that (if any) $g$ agents exist at $v_{j}$. Moreover, since $A_{f}$ tries to
move forward and $A_{b}$ tries to move backward, $A_{f}$ or $A_{b}$ can visit
a next node at each round. Thus, within $n$ rounds, all nodes in the ring are
visited by $A_{f}$ or $A_{b}$ and hence there is no node where between 1 and
$g-1$ agents exist. Thus, agents achieve $g$-partial gathering and the lemma
follows. ∎

We have the following theorem for the proposed algorithm.

######  Theorem 5.

When $3g-1\leq k\leq 8g-4$ holds, the proposed algorithm solves the
$g$-partial gathering problem in dynamic rings with $O(n)$ rounds and the
total number of $O(kn)$ moves.

###### Proof.

By Lemmas 1 and 3, the proposed algorithm can solve the $g$-partial gathering
problem. In the following, we analyze the time complexity and the required
total number of agent moves.

First, in the selection phase, each agent tries to move forward for $3n$
rounds in order to determine the gathering node $v_{\textit{gather}}$. This
requires $O(n)$ rounds and the total number of $O(kn)$ moves. Next, in the
gathering phase, for $3n$ rounds, each agent first tries to move forward to
reach $v_{\textit{gather}}$, which requires $O(n)$ rounds and the total number
of $O(kn)$ moves. Thereafter, when at least $2g$ agents exist at some node,
from there a forward agent group $A_{f}$ and a backward agent group $A_{b}$
move in the ring to achieve $g$-partial gathering. As discussed in the proof
of Lemma 3, a forward group or a backward group can visit a next node at each
round, and thus the movement for agent groups finishes within $n$ rounds. In
addition, since the number of agents of $A_{f}$ and that of $A_{b}$ are
respectively at most $2g$ and $A_{f}$ and $A_{b}$ visit $n,n+1,$ or $n+2$
nodes in total, each link is passed by at most $4g$ times during the movement
for agent groups. Thus, the total number of agent moves in the movement for
the agent groups is $O(gn)$. Therefore, agents achieve $g$-partial gathering
with $O(n)$ rounds and the total number of $O(kn)$ moves, and the theorem
follows. ∎

##  6 The case of $k\geq 8g-3$

In this section, when $k\geq 8g-3$, we propose an algorithm to solve the
problem with $O(n)$ rounds and the total number of $O(gn)$ (i.e., optimal)
moves. Since the move complexity is not $O(kn)$ but $O(gn)$, it is not
possible that all agents try to travel once around the ring as in Sections 4
and 5. Hence, in this section agents aim to reduce the total number of moves
using distinct IDs and the fact of $k\geq 8g-3$. The algorithm comprises three
phases: the semi-selection phase, the semi-gathering phase, and the
achievement phase. In the semi-selection phase, agents select a set of
gathering-candidate nodes each of where at least $2g$ agents may gather. In
the semi-gathering phase, agents try to stay at a gathering-candidate node. As
a result, at least $2g$ agents gather at some node (the node may not be a
gathering-candidate node due to link-missings). In the achievement phase,
agents achieve $g$-partial gathering by the same method as that for the
gathering phase in Section 5.

###  6.1 Semi-selection phase

The aim of this part is to select a set of gathering-candidate nodes each of
where at least $2g$ agents may gather. A possible approach is that each agent
$a_{i}$ moves forward and backward for getting IDs of its 1-st, 2-nd,
$\ldots,(2g-1)$-st forward agents and IDs of its 1-st, 2-nd,
$\ldots,(2g-1)$-st backward agents, and then returns to its initial node.
Here, the $i$-th ($i\neq 0$) forward (resp., backward) agent ${a^{\prime}}$ of
agent $a$ represents the agent such that $i-1$ agents exist between $a$ and
$a^{\prime}$ in ${a}$’s forward (resp., backward) direction in the initial
configuration. Thereafter, $a_{i}$ compares its ID and the obtained $4g-2$
IDs. If its ID is the minimum, $a_{i}$ selects its initial node as a
gathering-candidate node $v_{\textit{candi}}$. Then, the $2g-1$ agents
existing in $a_{i}$’s backward direction try to move forward to stay at
$v_{\textit{candi}}$ and eventually $2g$ agents may gather at
$v_{\textit{gather}}$. However, since we consider 1-interval connected rings,
there are two problems: (1) it is possible that no gathering-candidate node is
selected since some agent may not be able to collect $4g-2$ IDs due to link-
missings, and (2) even if a gathering-candidate node $v_{\textit{candi}}$ is
selected, it is possible that some agent cannot reach $v_{\textit{candi}}$ due
to link-missings and only less than $2g$ agents gather at each node.

To treat these problems, each agent $a_{i}$ in this phase keeps trying to move
forward, tries to observe more than $4g-2$ IDs, and considers some observed ID
as its own ID when it observed the necessary number of IDs. Concretely, for
$3n$ rounds, each agent $a_{i}$ tries to move forward until it observes
$10g-4$ IDs or at least $2g$ agents exist at the current node. Thereafter,
$a_{i}$ determines its behavior depending on whether it observed at least
$8g-3$ IDs or not. If $a_{i}$ did not observe at least $8g-3$ IDs, we show in
Lemma 4 that at least $2g$ agents exist at some node $v_{j}$ and then a flag
$v_{j}.\textit{candi}$ is set to true to represent that $v_{j}$ is a
gathering-candidate node (problem (1) is solved). Intuitively, this is because
$a_{i}$ does not observe at least $(10g-4)-(8g-4)=2g$ IDs and this means that
at least $2g-1$ agents existing in $a_{i}$’s backward direction also do not
observe the necessary number of IDs and they eventually stay at $a_{i}$’s
node.

On the other hand, if $a_{i}$ observed at least $8g-3$ IDs, it uses the first
$8g-3$ IDs for comparison and considers the $(4g-1)$-st ID as its own ID.
Then, this situation is similar to one that $a_{i}$ compares its ID with
$4g-2$ forward IDs and $4g-2$ backward IDs. Hence, if the $(4g-1)$-st ID is
the minimum among the $8g-3$ IDs, $a_{i}$ sets
$v_{j}.\textit{{candi}}=\textit{true}$ at the current node $v_{j}$. Then,
since $k\geq 8g-3$ holds, all the $8g-3$ IDs are distinct and thus $4g-2$
agents existing in $a_{i}$’s backward direction can recognize $a_{i}$’s
staying node as the nearest gathering-candidate node $v_{\textit{candi}}$ in
the forward direction when they observed at least $8g-3$ IDs. Thus, the $4g-1$
agents in total ($a_{i}$ and the $4g-2$ agents) try to move forward and stay
at $v_{\textit{candi}}$ (the detail is explained in the next subsection).
Then, when some link continues to be missing, the $4g-1$ agents are
partitioned into two groups and at least one group has $2g$ agents (problem
(2) is solved).

The pseudocode of the semi-selection phase is described in Algorithm 11.
Concerning the semi-selection phase, we have the following lemma.

1

Main Routine of Agent $a_{i}$:

2 $v_{j}.\textit{id}:=a_{i}.\textit{id}$,
$a_{i}.\textit{ids}[a_{i}.\textit{nIDs}]:=v_{j}.\textit{id}$

3 $a_{i}.\textit{nIDs}:=a_{i}.\textit{nIDs}+1$,
$v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

4

5while  _$a_{i}.\textit{rounds}\leq 3n$_ do

6 if  _$(a_{i}.\textit{nIDs} <10g-4)\land(v_{j}.\textit{nAgents}<2g)$_ then

7 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

8 Try to move from the current node $v_{j}$ to the forward node $v_{j+1}$

9 if  _$(a_{i}$ reached $v_{j+1}$ (that becomes new $v_{j}$)) $\land$
$(v_{j}.\textit{id}\neq\perp)$_ then

10 $a_{i}.\textit{ids}[a_{i}.\textit{nIDs}]:=v_{j}.\textit{id}$,
$a_{i}.\textit{nIDs}:=a_{i}.\textit{nIDs}+1$

11

12 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$,
$a_{i}.\textit{rounds}:=a_{i}.\textit{rounds}+1$

13

14

15

16if  _$(v_{j}.\textit{nAgents}\geq 2g)\lor((a_{i}.\textit{nIDs}\geq
8g-3)\land(\forall h\in[0,8g-2]\setminus\\{4g-2\\};a_{i}.\textit{ids}[4g-2]
<a_{i}.\textit{id}[h]))$_ then

17 $v_{j}.\textit{candi}:=\textit{true}$

18 Terminate the semi-selection phase and enter the semi-gathering phase

19

20

Algorithm 11 The behavior of agent $a_{i}$ in the semi-selection phase
($v_{j}$ is the current node of $a_{i}$.)

######  Lemma 4.

After finishing Algorithm 11, there exists at least one node $v_{j}$ with
$v_{j}.\textit{candi}=\textit{true}$.

###### Proof.

Let $a_{\textit{min}}$ be the agent with minimum ID among all agents and
$a_{i}$ be the $(4g-2)$-nd backward agent of $a_{\textit{min}}$. We consider
the cases that the value of $a_{i}.\textit{nIDs}$ after executing Algorithm 11
is (a) less than $8g-3$ and (b) at least $8g-3$ in this order. First, (a) if
$a_{i}.\textit{nIDs}<8g-3$ holds, let $g^{\prime}=(10g-4)-a_{i}.\textit{nIDs}$
be the number of IDs that $a_{i}$ could not observe and
$a_{i-1},a_{i-2},\ldots,a_{i-(g^{\prime}-1)}$ be the 1-st, 2-nd, $\ldots$ ,
$(g^{\prime}-1)$-st backward agents of $a_{i}$. Then, since
$(g^{\prime}-1)+a_{i}.\textit{nIDs}=((10g-4)-a_{i}.\textit{nIDs})-1+a_{i}.\textit{nIDs}=10g-5<10g-4$,
agent $a_{i-(g^{\prime}-1)}$ does not observe the required number $10g-4$ of
IDs. Thus, $a_{i-1},a_{i-2},\ldots,a_{i-(g^{\prime}-1)}$ also observed less
than $10g-4$ IDs and they stay at the same node ($a_{i}^{\prime}$s node) by
the similar discussion of Lemma 1. Since
$g^{\prime}-1\geq(10g-4)-(8g-4)-1=2g-1$ holds, at least $2g$ agents (including
$a_{i}$) stay at the same node $v_{j}$ and thus $v_{j}.\textit{candi}$ is set
to true. Next, (b) if $a_{i}.\textit{nIDs}\geq 8g-3$ holds, $a_{i}$ recognizes
that $a_{\textit{min}}$’s ID is its own ID and the ID is the minimum among the
$8g-3$ IDs. Hence, $a_{i}$ sets $v_{j}.\textit{candi}=true$ at the current
node $v_{j}$. Therefore, the lemma follows. ∎

###  6.2 Semi-gathering phase

In this phase, agents aim to make a configuration such that at least $2g$
agents exist at some node. By Lemma 4, there exists at least one gathering-
candidate node $v_{j}$ with $v_{j}.\textit{candi}=\textit{true}$ at the end of
the semi-selection phase. In the following, we call such a candidate node
$v_{\textit{candi}}$. Then, if less than $2g$ agents exist at
$v_{\textit{candi}}$, $4g-2$ agents in total that already stay at
$v_{\textit{candi}}$ and exist in $v_{\textit{candi}}$’s backward direction
try to stay at $v_{\textit{candi}}$. Concretely, in this phase, for $3n$
rounds each agent tries to move forward until it stays $v_{\textit{candi}}$ or
at least $2g$ agents exist at the current node. Then, due to link-missings, it
is possible that only less than $2g$ agents gather at $v_{\textit{candi}}$
after the movement. In this case, we can show by the similar discussion of
Lemma 1 that all the agents that do not reach $v_{\textit{candi}}$ among the
$4g-2$ agents stay at the same node. Then, the $4g-1$ agents (the $4g-2$
agents and the agent originally staying at $v_{\textit{candi}}$) are
partitioned into two groups and at least one group has at least $2g$ agents in
any partition. Thus, agents can make a configuration such that at least $2g$
agents exist at some node.

The pseudocode of the semi-gathering phase is described in Algorithm 12. Note
that, during the movement, when agents are blocked few times and they do not
reach $v_{\textit{candi}}$, agents may require the total number of more than
$O(gn)$ moves. To avoid this, each agent stops moving when it observed $4g-1$
IDs even if it does not reach $v_{\textit{candi}}$ (line 2).

1

Main Routine of Agent $a_{i}$:

2 $a_{i}.\textit{rounds}:=1,a_{i}.\textit{nIDs}:=1$

3 while  _( $a_{i}.\textit{rounds}\leq 3n$) $\land$ ($a_{i}.\textit{nIDs}\neq
4g-1)$_ do

4 if  _$v_{j}.\textit{candi}=\textit{false}$_ then

5 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}-1$

6 Try to move from the current node $v_{j}$ to the forward node $v_{j+1}$

7 if ($a_{i}$ reached $v_{j+1}$ (that becomes new $v_{j}$)) $\land$
($v_{j}.\textit{id}\neq\perp$) then
$a_{i}.\textit{nIDs}:=a_{i}.\textit{nIDs}+1$

8

9 $v_{j}.\textit{nAgents}:=v_{j}.\textit{nAgents}+1$

10 if $v_{j}.\textit{nAgents}\geq 2g$ then
$v_{j}.\textit{candi}:=\textit{true}$

11

12 $a_{i}.\textit{rounds}=a_{i}.\textit{rounds}+1$

13

14Terminate the semi-gathering phase and enter the achievement phase

15

Algorithm 12 The behavior of agent $a_{i}$ in the semi-gathering phase
($v_{j}$ is the current node of $a_{i}$.)

Concerning the semi-gathering phase, we have the following lemma.

######  Lemma 5.

After finishing the semi-gathering phase, there exists at one node $v_{j}$
with $v_{j}.\textit{nAgents}\geq 2g$.

###### Proof.

We consider a configuration such that there exists no node with at least $2g$
agents at the beginning of the semi-gathering phase. By Lemma 4, there exists
at least one node $v_{j}$ with $v_{j}.\textit{candi}=\textit{true}$, and
$4g-2$ agents in total that already stay at $v_{j}$ and exist in $v_{j}$’s
backward direction try to stay at $v_{j}$ by Algorithms 11 and 12. Then, by
the similar discussion of the proof of Lemma 1, after executing Algorithm 12
for $3n$ rounds, all agents among the $4g-2$ agents that do not reach $v_{j}$
stay at the same node. Thus, the $4g-1$ agents (the $4g-2$ agents and the
agent originally staying at $v_{j}$) are partitioned into two groups and at
least one group has at least $2g$ agents in any partition. Therefore, the
lemma follows. ∎

###  6.3 Achievement phase

In this phase, agents aim to achieve $g$-partial gathering. By Lemma 5, there
exists at least one node with at least $2g$ agents as in Section 5. The
difference from Section 5 is that there may exist more than two nodes with
agents and there may exist several nodes each of which has at least $2g$
agents. Also from this situation, agents can achieve $g$-partial gathering
using the same method as that in Section 5, that is, (1) agents staying at a
node with at least $2g$ agents are partitioned into a forward group and a
backward group and they try to move forward and backward respectively, and (2)
when a forward group (resp., a backward group) visits a node with less than
$g$ agents, the less than $g$ agents join the forward group (resp., the
backward group).

An example is given in Fig. 4. In Fig. 4 (a), there exist two nodes $v_{p}$
and $v_{q}$ each of which has $6\,(=2g)$ agents. Hence, a forward group
$A_{f_{p}}$ and a backward group $A_{b_{p}}$ (resp., $A_{f_{q}}$ and
$A_{b_{q}}$) start moving from node $v_{p}$ (resp., from node $v_{q}$). From
(a) to (b), $A_{b_{p}}$ reaches node $v_{\ell}$ with less than $g$ agents, and
the less than $g$ agents join $A_{b_{p}}$ and try to move backward. From (b)
to (e), we assume that $A_{f_{q}}$ continues to be blocked by a missing link.
From (b) to (c), $A_{f_{p}}$ and $A_{b_{q}}$ crossed and they recognize the
fact by the existence of flags, and they terminate the algorithm execution.
From (c) to (d), $A_{b_{p}}$ reaches node $v_{m}$ with less than $g$ agents,
and the less than $g$ agents join $A_{b_{p}}$ and try to move backward. Then,
since the number num of agents in the updated $A_{b_{p}}$ is $7\,(>2g)$, by
using their IDs, only $g$ agents continue to try moving backward and the
remaining $\textit{num}-g$ agents terminate the algorithm execution there ((d)
to (e)). By this behavior, during this phase each link is passed by at most
$2g$ agents and the achievement phase can be achieved with the total number of
$O(gn)$ moves. From (e) to (f), $A_{f_{q}}$ and $A_{b_{p}}$ reach some node
simultaneously and recognize the fact by flags, and they terminate the
algorithm execution and agents achieve $g$-partial gathering.

Figure 4: An execution example of the achievement phase when $k\geq 8g-3$
($g=3$).

Concerning the achievement phase, we have the following lemma.

######  Lemma 6.

After executing the achievement phase, agents achieve $g$-partial gathering.

###### Proof.

By Lemma 5, at the beginning of the achievement phase, there exists at least
one node with at least $2g$ agents. Thus, the at least $2g$ agents can execute
More2() (Procedure 8) and start moving forward or backward. For the rest, we
can show the correctness by the exact same discussion of the proof of Lemma 3.
Therefore, the lemma follows. ∎

We have the following theorem for the proposed algorithm.

######  Theorem 6.

When $k\geq 8g-3$ holds, the proposed algorithm solves the $g$-partial
gathering problem in dynamic rings with $O(n)$ rounds and the total number of
$O(gn)$ moves.

###### Proof.

By Lemmas 4, 5, and 6, the proposed algorithm can solve the $g$-partial
gathering problem. In the following, we analyze the time complexity and the
required total number of agent moves.

First, in the semi-selection phase, for $3n$ rounds each agent $a_{i}$ tries
to move forward until it observes $10g-3$ IDs or at least $2g$ agents exist at
the current node, which requires $O(n)$ rounds. In addition, since $a_{i}$
stops moving when it observes $10g-3$ IDs, in this phase each link is passed
by at most $10g-3$ times. Hence, the move complexity of the semi-selection
phase is $O(gn)$.

Next, in the semi-gathering phase, for $3n$ rounds each agent at a node with
less than $2g$ agents tries to move forward until it stays at a gathering-
candidate node $v_{\textit{candi}}$, a node with at least $2g$ agents, or it
observes $4g-1$ IDs, which requires $O(n)$ rounds. In addition, since each
link is passed by at most $4g-1$ times, the move complexity of the semi-
gathering phase is $O(gn)$.

Finally, in the achievement phase, agents staying at a node with at least $2g$
agents move for achieving $g$-partial gathering. As discussed in Lemmas 3 and
6, a forward group of a backward group can visit a next node at each round,
and hence the achievement phase finishes within $n$ rounds. In addition, each
forward or backward group comprises at most $2g$ agents, and hence each link
is passed by at most $4g$ times. Thus, the move complexity of the achievement
phase is $O(gn)$. Therefore, agents can solve the $g$-partial gathering
problem with $O(n)$ rounds and the total number of $O(gn)$ moves, and the
theorem follows. ∎

##  7 Conclusion

In this paper, we considered the $g$-partial gathering problem in
bidirectional dynamic rings and considered the solvability of the problem and
the time and move complexity, focusing on the relationship between values of
$k$ and $g$. First, we showed that agents cannot solve the problem when $k\leq
2g$. Second, we showed that the problem can be solved with $O(n\log g)$ time
and the total number of $O(gn\log g)$ moves when $2g+1\leq k\leq 3g-2$. Third,
we showed that the problem can be solved with $O(n)$ time and the total number
of $O(kn)\,(=O(gn))$ moves when $3g-1\leq k\leq 8g-4$. Finally, we showed that
the problem can be solved with $O(n)$ time and the total number of $O(gn)$
moves when $k\geq 8g-3$. These results show that the partial gathering problem
can be solved also in dynamic rings when $k\geq 2g+1$. In particular, when
$k\geq 3g-1$, the time complexity $O(n)$ of the proposed algorithms is
asymptotically optimal and the total number $O(gn)$ moves is also
asymptotically optimal.

Future works are as follows. First, we consider whether or not agents can
solve the problem with the total number of moves smaller than $O(gn\log g)$ in
the case of $2g+1\leq k\leq 3g-2$. Also, we will consider the solvability of
the problem for agents with weaker capabilities, e.g., agents without distinct
IDs, without chirality, or agents that behave semi-synchronously or
asynchronously. In any of the above cases, we conjecture that agents cannot
solve the problem or require more total number of moves than the proposed
algorithms.

## References

  * [1] R. S. Gray, D. Kotz, G. Cybenko, and D. Rus.  D’agents: Applications and performance of a mobile-agent system.  Softw., Pract. Exper., 32(6):543–573, 2002.
  * [2] J. Baumann, F. Hohl, K. Rothermel, and M. Straßer.  Mole–concepts of a mobile agent system.  world wide web, 1(3):123–137, 1998.
  * [3] D. B. Lange and M. Oshima.  Seven good reasons for mobile agents.  CACM, 42(3):88–89, 1999.
  * [4] G. Cabri, L. Leonardi, and F. Zambonelli.  Mobile agent coordination for distributed network management.  Journal of Network and Systems Management, 9(4):435–456, 2001.
  * [5] E. Kranakis, D. Krizanc, and E. Markou.  The mobile agent rendezvous problem in the ring.  Synthesis lectures on distributed computing theory, 1(1):1–122, 2010.
  * [6] E. Kranakis, N. Santoro, C. Sawchuk, and D. Krizanc.  Mobile agent rendezvous in a ring.  Proc. of International Conference on Distributed Computing Systems, pages 592–599, 2003.
  * [7] P. Flocchini, E. Kranakis, D. Krizanc, N. Santoro, and C. Sawchuk.  Multiple mobile agent rendezvous in a ring.  Proc. of Latin American Symposium on Theoretical Informatics, pages 599–608, 2004.
  * [8] F. Ooshita, S. Kawai, H. Kakugawa, and T. Masuzawa.  Randomized gathering of mobile agents in anonymous unidirectional ring networks.  Transactions on Parallel and Distributed Systems, 25(5):1289–1296, 2014.
  * [9] P. Fraigniaud and A. Pelc.  Deterministic rendezvous in trees with little memory.  Proc. of International Symposium on Distributed Computing, pages 242–256, 2008.
  * [10] D. Baba, T. Izumi, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Linear time and space gathering of anonymous mobile agents in asynchronous trees.  Theoretical Computer Science, 478:118–126, 2013.
  * [11] E. Kranakis, D. Krizanc, and E. Markou.  Mobile agent rendezvous in a synchronous torus.  Proc. of Latin American Symposium on Theoretical Informatics, pages 653–664, 2006.
  * [12] Y. Dieudonné and A. Pelc.  Anonymous meeting in networks.  Algorithmica, 74(2):908–946, 2016.
  * [13] Y. Dieudonné, A. Pelc, and V. Villain.  How to meet asynchronously at polynomial cost.  SIAM Journal on Computing, 44(3):844–867, 2015.
  * [14] M. Shibata, S. Kawai, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Partial gathering of mobile agents in asynchronous unidirectional rings.  Theoretical Computer Science, 617:1–11, 2016.
  * [15] M. Shibata, N. Kawata, Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings.  Theoretical Computer Science, 822:92–109, 2020.
  * [16] M. Shibata and S. Tixeuil.  Partial gathering of mobile robots from multiplicity-allowed configurations in rings.  Proc. of International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 264–279, 2020.
  * [17] M. Shibata, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Move-optimal partial gathering of mobile agents in asynchronous trees.  Theoretical Computer Science, 705:9–30, 2018.
  * [18] M. Shibata, D. Nakamura, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Partial gathering of mobile agents in arbitrary networks.  IEICE Transactions on Information and Systems, 102(3):444–453, 2019\.
  * [19] Di GA. Luna, P. Flocchini, L. Pagli, G. Prencipe, N. Santoro, and G. Viglietta.  Gathering in dynamic rings.  Theoretical Computer Science, 811:79–98, 2018.
  * [20] Di GA. Luna, S. Dobrev, P. Flocchini, and N. Santoro.  Distributed exploration of dynamic rings.  Distributed Computing, 33(1):41–67, 2020.
  * [21] T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa.  Exploration of dynamic tori by multiple agents.  Theoretical Computer Science, 850:202–220, 2021.
  * [22] S. Das, Di GA. Luna, D. Mazzei, and G. Prencipe.  Compacting oblivious agents on dynamic rings.  PeerJ Computer Science, 7:1–29, 2021.
  * [23] S. Das, Di GA. Luna, and LA. Gasieniec.  Patrolling on dynamic ring networks.  Proc. of International Conference on Current Trends in Theory and Practice of Informatics, pages 150–163, 2019.
  * [24] M. Shibata, Y. Sudo, J. Nakamura, and Y. Kim.  Uniform deployment of mobile agents in dynamic rings.  Proc. of International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 248–263, 2020.