Computing the   k -resilience of a Synchronized Multi-Robot System ∗  Sergey Bereg †   Luis-Evaristo Caraballo ‡   José-Miguel Díaz-Báñez ‡  Mario A. Lopez §  Abstract  We study an optimization problem that arises in the design of covering strategies for multi-robot systems. Consider a team of   n   cooperating robots traveling along predetermined closed and disjoint trajectories. Each robot needs to periodically communicate information to nearby robots. At places where two trajectories are within range of each other, a commu- nication link is established, allowing two robots to exchange information, provided they are “synchronized”, i.e., they visit the link at the same time. In this setting a communication graph is defined and a system of robots is called   synchronized   if every pair of neighbors is synchronized. If one or more robots leave the system, then some trajectories are left unattended. To handle such cases in a synchronized system, when a live robot arrives to a communication link and detects the absence of the neighbor, it shifts to the neighboring trajectory to assume the unattended task. If enough robots leave, it may occur that a live robot enters a state of  starvation , failing to permanently meet other robots during flight. To measure the tolerance of the system under this phenomenon we define the   k -resilience   as the minimum number of robots whose removal may cause   k   surviving robots to enter a state of starvation. We show that the problem of computing the   k -resilience is NP-hard if   k   is part of the input, even if the communication graph is a tree. We propose algorithms to compute the   k -resilience for constant values of   k   in general communication graphs and show more efficient algorithms for systems whose communication graph is a tree.  1   Introduction  Recently, there has been a growing interest in systems composed of multiple autonomous mo- bile robots that exhibit some kind of cooperative behavior.   Many interesting algorithmic and combinatorial problems arise naturally in the design of coordinated multi-robot systems [1, 2, 7, 9, 10, 13, 14, 15]. Scalability, fault-tolerance, and failure-recovery are important concerns of distributed sys- tems. In recent papers, [12, 11] consider a scenario consisting of   n   robots each of which periodi- cally travels along a predetermined closed trajectory (the trajectories are pairwise disjoint) while  ∗ A 4-page abstract of this paper appeared in the informal and non-selective workshop EuroCG17 [3].   This research has received funding from the projects GALGO (Spanish Ministry of Economy and Competitiveness, MTM2016-76272-R AEI/FEDER,UE) and CONNECT (EU-H2020/MSCA under grant agreement 2016-734922).  † Department of Computer Science, University of Texas at Dallas, 800 West Campbell Road. Richardson, TX 75080. USA  ‡ Higher Technical School of Engineering, University of Seville, Camino de los Descubrimientos.   E-41092 Seville. Spain  § Department of Computer Science, University of Denver, 2360 South Gaylord Street.   Denver, CO 80208. USA  1  arXiv:1707.07083v1 [cs.RO] 22 Jul 2017
C 1   C 2  C 4   C 3 (a) C 1   C 2  C 4   C 3   (b) C 1   C 2  C 4   C 3   (c) C 1   C 2  C 4   C 3   (d)  Figure 1 – Synchronized system of robots following circular trajectories. The robots are repre- sented as solid points in the circles. Arrows represent the movement direction of the robots in the trajectories. In this example the graph of potential links is a cycle of four nodes. performing an assigned task. Each robot needs to communicate information about its operation to other robots, but the communication interfaces have a limited range. Hence, when two robots are within range, a communication link is established, and information is exchanged. Accord- ingly, the set of potential communication links determines a graph with trajectories as nodes and links as edges. Two trajectories are   neighboring   if they are adjacent in the graph of potential links. Two robots are   neighbors   if they occupy neighboring trajectories. Two neighboring robots are   synchronized   if they can exchange information by periodically being within communication range of each other.   Given the robot trajectories in the plane and the communication range of the robots, the   synchronization problem   is to schedule (if possible) the movement of robots along trajectories so that every pair of neighboring robots is synchronized, in which case it is said that the system is   synchronized . Figure 1 shows a synchronized system where every pair of neighboring robots are moving in opposite directions (one clockwise and the other counterclockwise) at the same constant speed along congruent circular trajectories 1 .   We show in light gray the pairs of neighboring robots with an established communication link between them. Each part of the figure represents the state of the system at every quarter of the period required to complete a trajectory, starting with the state shown in Figure 1a. This scenario arises naturally in missions of surveillance or monitoring [1, 17] and during structure assembly while robots are loading and placing parts in a structure [4], to name but two examples. However, the synchronization problem is an interesting problem in robotics and its proper solution will likely find applications beyond the ones considered here. [12] solve the synchronization problem for a simplified model where all robots reliably travel around unit circles at uniform speed (as in Figure 1). They also discuss how to adapt the theory behind a simplified, not entirely practical model, to more general and realistic scenarios.   [11] further addresses techniques to apply this synchronization model in realistic scenarios. In these papers ([12, 11]), the authors also consider the possibility of a small number of dropouts and propose a protocol to minimize the detrimental effect that such failures may have on global system performance. In their proposal, the surviving robots handle a limited number of failures by “shifting” to a neighboring trajectory whenever the neighbor fails to arrive (see Figure 2 for an illustration). For synchronization reasons, when a robot enters a neighboring trajectory   C , it must follow the initial movement direction assigned to   C . Also, during the shifting process, it must accelerate to maintain the schedule.   Due to the kinematic constraints imposed by real scenarios, applying this recovery strategy, [12, 11] propose to assign opposite movement directions in neighboring trajectories, one clockwise (CW) and one counterclockwise (CCW). Consequently, the underlying communication graph must be bipartite.  1 In practice, the trajectories need not be congruent provided they are not too different in length and a suitable range of speeds is available to the robots.  2
C i   C j  φ ij  φ ji  u Figure 2 – A robot shifts to a neighboring trajectory when it detects that the corresponding neighboring robot has left the system.   The robot   u   follows the path drawn with bold solid stroke. There were no robots on the trajectory   C j   when   u   is arriving at the link position in   C i . C 1   C 2  C 4   C 3  u 1  u 3  (a) C 1   C 2  C 4   C 3  u 1  u 3   (b) C 1   C 2  C 4   C 3  u 1  u 3   (c) C 1   C 2  C 4   C 3  u 3  u 1   (d)  Figure 3 – When the two robots represented by hollow points leave the system, the surviving robots (solid points) follow the paths drawn with bold solid stroke. In some cases, if enough robots leave the team, an undesirable phenomenon may occur: a robot, independent of how much longer stays in flight, it permanently fails to encounter other robots every time it arrives at a link, causing it to repeatedly shift to neighboring trajectories. In this case, we say that the robot is   starving   or in   starvation   mode. Figure 3 shows a synchro- nized system where two robots leave and the remaining robots,   u 1   and   u 3 , permanently fail to encounter other robots at the link positions, so they enter the starvation state.  1.1   Contribution and Organization  [5] introduces the notion of   k -resilience in a synchronized system of mobile robots as a measure of the system’s ability to gather information from a set of mobile robots with communication constraints.   More formally, the   k -resilience   is defined as the smallest cardinality of a set of robots whose failure results in at least   k   starving robots.   Obviously, the larger the resilience, the more fault tolerant the system is.   An   O ( n 2 )   algorithm for computing the 1-resilience is proposed in [5]. In this paper we address the problem of computing the   k -resilience by formally establishing the concepts introduced by [5] and [12, 11].   For simplicity, we focus on the combinatorial problem of computing the   k -resilience of a synchronized system in the circular model (unit circles trajectories) considered by [12].   However, our results can be extended using the same arguments exposed by [12, 11]. The contributions of this paper are summarized as follows:  •   The next section states the problem of computing the   k -resilience and describes useful properties of synchronized systems.  •   In Section 3, we show that, when   k   is part of the input, computing the   k -resilience of a synchronized system of robots for arbitrary communication graphs is NP-hard and show that the corresponding decision problem is NP-complete. 3
•   Section 4 shows how to efficiently compute the   k -resilience of a general synchronized system for small values of   k . Our time-complexity is   O ( kn k +1 ) .  •   In the same Section we prove that the   1 -resilience problem can be solved in almost linear time.  •   In Section 5 we include algorithms for the case in which the communication graph is a tree. This includes a linear algorithm for the   1 -resilience problem, an   O ( t 2 ) -time algorithm for the   2 -resilience problem and an   O ( tn k − 1 ) -time algorithm for the general problem, where  √ πn/ 2   −   1   ≤   t   ≤   n   −   1   is a parameter that depends on the topology of the tree.  •   Finally, in Section 6 we state two new open problems in the design of algorithms whose subquadratic solutions will imply more efficient algorithms for the resilience problems.  2   Problem statement and preliminaries  The simple model introduced by [12] is presented in this section using some formalisms that we will require later. Let   T   =   { C 1 , . . . , C n }   be a set of pairwise disjoint unit circles (trajectories). Let    <   0 . 5   be the communication range of each robot in a team of   n   robots, one per trajectory. The robots move at the same constant speed in the circles. The   graph of potential links   of   T   is the geometric graph   G  ( T   ) = ( V, E  )   whose nodes are the centers of the circles in   T   and whose edges are given by the pairs of circles centers at distance   2 +      or less. The edge that connects a pair of adjacent trajectories   C i   and   C j   in   G  ( T   )   is denoted by   { i, j } . Since communication is an important issue in cooperative scenarios, this work focuses on sets of trajectories whose graph of potential links is connected. Assume for the rest of the paper that we are working with a given set of trajectories  T   and a fixed communication range    <   0 . 5   such that the geometric graph   G  ( T   )   is connected. For convenience, the position of a point in a circle is denoted by the angle measured from the positive horizontal axis. Assume, without loss of generality, that a trajectory can be covered by a robot in one time unit. The notion of   schedule   was introduced in [12]. Below, we present a formal definition of this concept.  Definition 1   (Schedule) .   Let   T   =   { C 1 , . . . , C n }   be a set of trajectories. A   schedule   on   T   is a pair of functions   ( f, g ) ,   f   :   T   →   [0 ,   2 π )   and   g   :   T   → {− 1 ,   1 } , where   f   ( C i )   is the starting position in the circle   C i   and   g ( C i )   is the movement direction in the circle   C i , 1 corresponds to CCW and  − 1   to CW. At an arbitrary time   t , a robot’s position in circle   C i   is:  f   ( C i ) + 2 π   ·   g ( C i )   ·   t.   (1) Let   T   be a set of trajectories.   A   communication graph   G   = ( V, E )   on   T   is a connected subgraph of   G  ( T   )   with the same set of nodes and a subset of the edges ( E   ⊆   E  ).   Two trajectories   C i   and   C j   are   neighboring   in   G   if   { i, j } ∈   E . The   link position   of   C i   with respect to   C j   , denoted by   φ ij   , is the point of   C i   closest to   C j   (see Figure 2). The following definition presents the notion of synchronization using a schedule.  Definition 2   ( G -synchronized schedule) .   Let   T   =   { C 1 , . . . , C n }   be a set of trajectories.   Let  G   = ( V, E )   be a communication graph on   T   . A schedule   ( f, g )   on   T   is   G -synchronized   if for all  { i, j } ∈   E   there exists a value   t   such that:  f   ( C i ) +   g ( C i )   ·   2 π   ·   t   =   φ ij   ⇔   f   ( C j   ) +   g ( C j   )   ·   2 π   ·   t   =   φ ji .  The shifting protocol is formalized in terms of schedule as follows: 4
Definition 3   (Shifting-protocol) .   Let   T   =   { C 1 , . . . , C n }   be a set of trajectories. Let   G   = ( V, E )  be a communication graph on   T   and let   ( f, g )   be a   G -synchronized schedule on   T   . Let   C i   and   C j  be neighboring trajectories in   G . When a robot   u   in   C i   arrives at the link position   φ ij   at time   t  and detects that there is no robot at   φ ji , then   u   shifts   to   C j   in order to assume the unattended task in   C j   .   During the shifting process it accelerates, such that, after a small time interval   δ , the robot will be in   C j   at position   f   ( C j   ) + 2 π   ·   g ( C j   )   ·   ( t   +   δ ) . After that,   u   moves following the schedule in   C j   , i.e.,   u   moves at the programmed constant speed in direction   g ( C j   ) .  Considering the kinematic constraints imposed by real scenarios in which the shifting- protocol is applied, [12] propose to use synchronized schedules where the neighboring robots are moving in opposite directions.  Definition 4   (Synchronized communication system) .   Let   T   =   { C 1 , . . . , C n }   be a set of trajec- tories. A   synchronized communication system   (SCS) with communication graph   G   = ( V, E )   on  T   is a team of   n   robots using a   G -synchronized schedule   ( f, g )   such that   g ( C i ) =   − g ( C j   )   for all  { i, j } ∈   E . An   m -partial SCS,   0   < m   ≤   n , is a synchronized communication system in which  n   −   m   robots have left the team and the   m   remaining robots apply the shifting strategy.  Notice that a SCS is only possible if the communication graph is bipartite and fulfills other properties exposed by [12].   Also, for every set of trajectories   T   there exists a communication graph   G   = ( V, E )   such that it is possible to make a   G -synchronized schedule where   g ( C i ) =  − g ( C j   )   for all   { i, j } ∈   E . One possibility is to use the spanning tree of the graph of potential links of   T   as the underlying communication graph. Note that a SCS is a type of partial SCS where no robots have left. Thus, any claims about partial SCSs holds for SCSs as well.  Definition 5   (Starvation) .   In an   m -partial SCS, a robot   starves   or is in   starvation   if every time that it arrives at a link position the corresponding neighbor is not there, causing it to shift to the neighboring trajectory.  Definition 6   ( k -resilience) .   The   k -resilience   of a SCS ( k   ≥   1 ) is the minimum number of robots whose removal may cause the starvation of at least   k   surviving robots.   If it is not possible to obtain   k   starving robots then the   k -resilience is stated as infinity.  This paper focuses on the following problem:  Problem 7.   Given a SCS and a natural number   k , determine the   k -resilience of the SCS.  Note that higher resilience values correspond to increased fault tolerance.   To tackle this problem we need the notion of a   ring , first introduced in [5].   In the sequel, we give useful properties of rings.  Definition 8   (Ring) .   Let   T   =   { C 1 , . . . , C n }   be a set of trajectories.   A   ring   in a SCS with communication graph   G   on   T   , is the locus of points visited by a starving robot following the assigned movement direction in each trajectory and always shifting to the neighboring trajectory (in   G ) at the corresponding link positions.  Each ring is a closed path composed of sections of various trajectories and has a direction of travel determined by the movement direction in the participating trajectories. Each section of a trajectory between two consecutive link positions participates in exactly one ring, thus, the rings in a SCS are pairwise disjoint.   Figure 4 shows various SCSs with different numbers of rings. 5
(a)   (b)   (c)  Figure 4 – SCSs with two rings (a); one ring (b) and three rings (c). A 1  A 2  σ  (a) p  q  C s  C s − 1  C 1   C 2  C 3 A 1  A 2  A 3  A s − 1  A s   (b) C  p  q   (c)  Figure 5 – (a) The length of a section   σ   of a ring is the sum of the lengths of the arcs   A 1   and  A 2 . (b) Path from a robot at position   p   to a robot at position   q   in the same ring. The second endpoint of   A i   and the first endpoint of   A i +1   are marked with a common non-solid point for all  1   ≤   i < s . (c) A simple path between two robots in a ring that has two arcs in the trajectory   C .  Definition 9   (Path in a ring) .   A   path   in a ring   r   from a point   p   ∈   r   to a point   q   ∈   r   is the ordered set of visited points from   p   to   q   following the travel direction of   r   (it may contain tours on   r ). If a path does not contain any tour in the ring then we say that it is a   simple path .  As suggested by the examples in Figure 4, the lengths of rings in a system varies from ring to ring.   In discussing the length of a ring, it is convenient to ignore the effect on distance arising from shifting between neighboring trajectories, i.e., to proceed as if neighboring circular trajectories were tangent to each other.  Definition 10   (Length of a ring) .   The   length of a ring   is defined as the sum of the lengths of the trajectory arcs forming the ring. Analogously, the   length of a path in a ring   is defined as the sum of the lengths of the trajectory arcs (as many times as they are traversed) forming the path.  Figure 5 illustrates the above definitions.   The following proposition is a technical result needed to describe the length of a simple path between two robots in the same ring.  Proposition 11.   Let   σ   be a simple path between two robots in a ring in an   m -partial SCS at time   t . Let   A 1 , . . . , A s   denote the directed arcs traversed in   σ   when following the travel direction of the ring, and let   C i   denote the trajectory containing   A i . 2  Then, for all   1   ≤   j   ≤   s ,  f   ( C j   ) +   g ( C j   )   ·   2 π   ·   ( t   +  j ∑  i =1  t i ) =   θ j   .   (2)  where   t i   is the required time by a robot to traverse   A i   and   θ j   is the angle position of the second endpoint of   A j   in   C j   .  2 Note that a path between two robots may have two arcs in the same trajectory, see Figure 5c for an example. Therefore, distinct indexes   i   and   j   may exist such that   C i   =   C j   .   This does not affect the proof of the claim because it is not required that the arcs belong to different trajectories.  6
Proof.   We prove Equation (2) by induction on   j . For   j   = 1 , by Equation (1), we have the base case  f   ( C 1 ) +   g ( C 1 )   ·   2 π   ·   ( t   +   t 1 ) =   θ 1 .  Induction step .   Suppose that Equation (2) holds for some   j < s .   By the definition of the synchronization schedule we have  f   ( C j +1 ) +   g ( C j +1 )   ·   2 π   ·  (  t   +  j ∑  i =1  t i  )  =   θ ′  j +1 ,  where   θ ′  j +1   is the position of the first endpoint of   A j +1   in   C j +1 . Since   θ j +1   =   θ ′  j +1   +   g ( C j +1 )   ·  2 π   ·   t j +1 , we have  f   ( C j +1 ) +   g ( C j +1 )   ·   2 π   ·  (  t   +  j +1 ∑  i =1  t i  )  =   θ j +1 ,  and the claim follows. The following lemma is established in [5] with a slightly different argument.  Lemma 12.   In a partial SCS, the length of a path between any two robots in the same ring is in   2 π N . Proof.   Let   p   and   q   be the angle positions of two robots in the same ring at time   t   and let   σ   be the simple path in the ring from   p   to   q   as denoted in the above claim and shown in Figure 5b. Thus, if   ( f, g )   is the synchronization schedule on the system, then we have  f   ( C 1 ) +   g ( C 1 )   ·   2 π   ·   t   =   p   (3)  f   ( C s ) +   g ( C s )   ·   2 π   ·   t   =   q   (4) Then  f   ( C s ) +   g ( C s )   ·   2 π   ·  (  t   +  s ∑  i =1  t i  )  =   q   (by Proposition 11)  f   ( C s ) +   g ( C s )   ·   2 π   ·   t   +   g ( C s )   ·   2 π  s ∑  i =1  t i   =   q b   +   g ( C s )   ·   2 π  s ∑  i =1  t i   =   q   (by Equation (4))  g ( C s )   ·   2 π  s ∑  i =1  t i   = 0  Therefore, the angle   2 π   ∑ s i =1   t i   is in   2 π Z . Since   2 π   ∑ s i =1   t i   is the length of the path   σ , the lemma follows.  Corollary 13.   The length of every ring in a SCS is in   2 π N . Proof.   Let   r   be a ring. If   r   consists of a simple trajectory, then its length is   2 π . Suppose that  r   consists of arcs from multiple trajectories.   Let   p   be a position of a robot in the ring, then the ring can be viewed as a closed path from   p   to   p . By Lemma 12 the length of the ring is in  2 π N . 7
u   u ′  u  ⇒  r   r ′   r   r ′  u ′ (a) u  ⇒  r   r ′   r   r ′  u   (b)  Figure 6 – Transition of the position of the robots (represented by solid points) in the neighbor- hood of a communication link. (a) Two robots   u   and   u ′   arrive at a communication link at the same time, then they keep their trajectories. (b) Robot   u   arrives at the link position and there is no robot in the neighboring trajectory, then   u   shifts to the neighboring trajectory. The following remark is very useful to study the behavior of an   m -partial SCS.  Remark 1.   Consider an   m -partial SCS on a set of trajectories   T   =   { C 1 , . . . , C n } . Let   `   be a link between two neighboring trajectories   C i   and   C j   where two rings   r   and   r ′   cross ( r   and   r ′  could be the same ring). When a robot   u   arrives at   `   on   r , there are two scenarios:  •   If there is another robot   u ′   in the neighboring circle then, due to synchronization,   u ′   arrives at   `   on   r ′   at the same time, and each robot keeps its trajectory but switches rings, see Figure 6a.  •   If there is no robot in the neighboring circle then the robot   u   shifts to the neighboring trajectory but remains in the same ring   r , see Figure 6b.  Lemma 14.   In an   m -partial SCS the number of robots in a given ring remains invariant.   If the length of the ring is   2 lπ   then it has at most   l   robots. Furthermore, in a SCS where no robots have left the system, a ring of length   2 lπ   has exactly   l   robots, each at distance   2 π   from the next. Proof.   Notice that in an   m -partial SCS a robot may change its ring only at the link positions, then from Remark 1, the number of robots in a ring remains invariant.   From Lemma 12 and Corollary 13 we deduce that a ring of length   2 lπ   has at most   l   robots. We now prove the third claim. Consider a system of   n   trajectories and   m   rings. Suppose that the   i -th ring has length  2 l i π   and   x i   robots,   1   ≤   i   ≤   m .   Then   x i   ≤   l i , for all   i , and   n   =   ∑ m i =1   x i .   Since the rings are disjoint,   ∑ m i =1   l i   =   n . Then  n   =  m ∑  i =1  x i   ≤  m ∑  i =1  l i   =   n,  and we conclude that   l i   =   x i   for all   i . The following notion gives us a useful tool to address the hardness of computing the   k - resilience of a SCS.  Definition 15   (Starvation number) .   The   starvation number   of a SCS is the maximum possible number of starving robots in a partial SCS.  The following result is deduced directly from the definitions of starvation number and   k - resilience.  Corollary 16.   If the starvation number of a SCS is   s , then the   k -resilience of the system is  infinity   for all   k > s .  Lemma 17.   If the starvation number of a SCS is   s   then the   s -resilience of the system is   n   −   s .  8
Proof.   Let   R   be the   s -resilience of the system, by definition   R   ≤   n   −   s .   Thus, there exists a set of   R   robots whose removal induces the starvation of   s   robots. Suppose   R < n   −   s   then, in the resultant partial SCS, the set of non-starving live robots is not empty and its cardinality is greater than 1 by definition of starvation. Therefore the removal of all but one non-starving live robots results in a new partial SCS with   s   + 1   starving robots, a contradiction.  3   Hardness of Computing the   k -Resilience in General Graphs  In this Section we prove that computing the   k -resilience of a SCS is NP-hard in general. First, we introduce some notation. The middle point of the edge connecting the two closest points of two neighboring circles   C i   and   C j   is called a   crossing point . A starving robot may pass it in two possible directions, one following the ring from   C i   to   C j   and other following the ring from   C j   to  C i   (these two rings could be one and the same), see Figure 6. We call them   crossing directions . Let   p   be a point of a ring   r . Let   d   be a non-negative real number. The point   p   +   d   of   r   is the point reached by traveling distance   d   from   p   in the travel direction of   r . We say that the position   p   +   d   is   d   units   ahead   of   p . Analogously, the point   p   −   d   of   r   is the point   q   such that   p  is   d   units ahead of   q   in   r . We say that the position   p   −   d   is   d   units   behind   p . Note that   d   could be greater than the length of the ring   r . In this case, the positions   p   +   d   and   p   −   d   are reached after one or more round trips in the ring. The following result is established in [5].  Lemma 18.   Let   p   be a point in a ring   r   in an   m -partial SCS and let   t >   0   be a real number. If there is a robot at   p   at some time, then after time   t   there will be a robot, not necessarily the same, at point   p   + 2 tπ   of   r . Also,   t   units of time earlier there was a robot, not necessarily the same, at point   p   −   2 tπ   of   r . Proof.   To prove the first claim, consider the path   σ   from   p   to   p   + 2 tπ   in   r .   At each crossing point, there are two possible scenarios (see Remark 1). If the neighbor does not appear at the crossing point, then the same robot continues along the ring, as shown in Figure 6b. Otherwise, the neighboring robot will continue in   σ   (in the neighboring trajectory) as shown in Figure 6a. After time   t , there will be a robot at point   p   + 2 tπ   of   r . To prove the second claim, we apply the same argument backward. Let   σ   be the path from  p   −   2 tπ   to   p   in   r . If   σ   does not contain crossing points, then the robot at   p   was at   p   −   2 tπ t   units of time earlier. If   σ   contains crossing points then they can be traversed back similarly: either the same robot or the neighbor will be before each crossing point at position   p   −   2 tπ   in   σ   at   t  units of time earlier.  Lemma 19.   In an   m -partial SCS, let   r   and   r ′   be rings (not necessarily distinct) that cross each other at a point   c . Let   u   and   u ′   be two robots in   r   and   r ′ , respectively. If there are two paths of equal lengths, one from   u   to   c   in   r   (possibly longer than   r ) and other from   u ′   to   c   in   r ′   (possibly longer than   r ′ ), then   u   and   u ′   are not starving. Proof.   Let   l   be the length of the paths. After traveling distance   l   from the current position of  u , the resulting position is the point   c . Traveling distance   l   from the current position of   u ′ , the resulting position is   c   as well. We focus on proving that   u   does not starve as the analysis for   u ′  is analogous. Let   t   be the required time to travel   l   units of length. If during the next   t   units of time   u   meets some robot, then   u   is not starving. If after   t   units of time   u   did not meet any robot, then   u   arrives at point   c , by Lemma 18, another robot in   r ′   arrives at   c   too. Therefore,  u   does not starve. The above lemma leads us to the following definition: 9
C i   C j  (i) (ii)  u  c Figure 7 – Ring that crosses itself. The directions of movement through the crossing point   c   are represented with bold solid strokes.  Definition 20.   In an   m -partial SCS, let   u   and   u ′   be two robots in rings   r   and   r ′   (not necessarily distinct), respectively.   We say that   u ′   prevents   u   from starving if there is a crossing point   c  between   r   and   r ′   such that there are two paths of equal lengths, one from   u   to   c   in   r   (possibly longer than   r ) and other from   u ′   to   c   in   r ′   (possibly longer than   r ′ ).  Observe that if   u ′   prevents   u   from starving then   u   prevents   u ′   from starving. The following is claimed without a proof in [5].  Corollary 21.   In an   m -partial SCS, a robot is starving if and only if all the robots that prevent it from starving have failed. Proof.   ( ⇒ ) For the first implication, if a robot is in starvation then all the robots that prevent it from starving have failed, follows directly from Lemma 19. ( ⇐ ) We prove the second implication by contradiction. Let   u   be a robot on a ring   r   such that, at some point in time   t 0 , all the robots that prevent it from starving have failed.   Suppose that after traveling for   t   units of time   u  meets a robot   u ′   in a crossing point   c   of   r   with another ring   r ′   (the rings could be the same). By Lemma 18 there was a robot at position   c   −   2 tπ   of the ring   r ′   at time   t 0 , and this robot prevents   u   from starving, a contradiction. We have mentioned the fact that the two rings meeting at a crossing point could be one and the same, i.e., it is possible for a ring to “cross itself”. Thus, we say that a ring   r   crosses itself  if there is a crossing point which is traversed by   r   in the two crossing directions, see Figure 7. The following results focus on rings that cross themselves.  Lemma 22.   Let   r   be a ring that crosses itself at a point   c   between circles   C i   and   C j   .   Every starving robot in   r   passes through   c   periodically and alternating the crossing directions. Proof.   Let   r   be a ring that crosses itself at   c   between   C i   and   C j   (see Figure 7). We show that if a starving robot   u   in   r   crosses   c   from   C i   to   C j   , then the next time that   u   crosses   c , it will do so from   C j   to   C i , and vice versa. Suppose that   u   crosses   c   from   C i   to   C j   following direction (i) in Figure 7. Note that the ring may have other crossing points with itself. Obviously   u   will return to the crossing point   c   (because rings are closed paths), and there are only two ways to cross through   c , (i) from   C i   to   C j   and (ii) from   C j   to   C i . Suppose, for contradiction, that the next time   u   crosses   c   it follows direction (i) again.   Then, since a ring is a closed path,   u   has completed a tour in the ring without using the crossing direction (ii). Therefore   r   does not cross itself at   c . This is a contradiction and the result follows.  Definition 23   (Tie of a ring) .   A   tie   of a ring is a closed path that starts and ends at a crossing point of the ring with itself (without passing through this crossing point).  10
C (a) C   (b)  Figure 8 – (a) Ring corresponding to   T   ′ . (b) Ring corresponding to   T   . v   u  c  (a) u v  c  l  l  d  τ  ︷   ︸︸   ︷   (b)  Figure 9 – (a) The length of the tie to the left of the dash-dotted vertical line is equal to the length of the section of ring from   u   to   v . (b) The robots   u   and   v   prevent each other from starving because the distance between them is equal to the length of a tie in the same ring. From the synchronization between robots in neighboring circles and using Lemma 12 the following corollary is deduced:  Corollary 24.   A crossing point of a ring with itself determines two ties. Moreover, the length of a tie is in   2 π N .  Figure 7 shows the two ties determined by the crossing point   c : the one represented with dashes follows direction (i) and the other (shown with dots) follows direction (ii).  Lemma 25.   If the communication graph of a SCS is a tree then there is a single ring. Proof.   We prove the lemma by induction on the number of trajectories. Clearly, if there is only one trajectory, the ring is unique. Suppose that the claim holds for any tree with   n   trajectories.   We show that it also holds for any tree   T   with   n   + 1   trajectories. Let   C   be a trajectory corresponding to a leaf in   T   , see Figure 8a. Let   T   ′   be the tree obtained by deleting trajectory   C . Then there is exactly one ring corresponding to   T   ′ . Adding   C   to the system, the ring changes by adding a loop covering   C   as shown in Figure 8b and the lemma follows. From Lemma 25 and Corollary 24 we have:  Corollary 26.   In a SCS of   n   trajectories whose communication graph is a tree, a crossing point determines two ties of lengths   2 lπ   and   2( n   −   l ) π   respectively, where   l   ∈   N .  Lemma 27.   Let   u   and   v   be robots on a ring   r   of an   m -partial SCS. Then   u   prevents   v   from starving if and only if   r   has a tie whose length is equal to the length of a simple path between   u  and   v . Proof.   ( ⇒ ) Suppose that   u   prevents   v   from starving and assume that we remove all live robots in the system except for   u   and   v . Then   u   and   v   must meet each other after a while at a crossing point   c   of   r   with itself. Observe that the path from   u   to   v   is one of the ties determined by   c , see Figure 9a, so the length of this tie is equal to the length of the path between   u   and   v . ( ⇐ ) Suppose   r   has a tie whose length is equal to the length   l   of the path from   u   to   v . Let   c   be a 11
p 1  p 2  0   1  2  3  4 5  6  7  8  (a)   (b) Figure 10 – (a) Example of a SCS. With bold solid stroke a ring that crosses itself twice in   p 1  and   p 2 . (b) The circulant graph that models the relation “prevent from starving” corresponding to the ring in (a). crossing point that determines a tie   τ   of length   l , see Figure 9b. There are two ways to reach  c , one entering and the other leaving   τ   .   Let   d   be the length of the path from   v   to   c   entering  τ   . The point obtained by traveling   l   +   d   units of length from the current positions of   u   and   v , respectively, is   c   in both cases. Consequently,   u   and   v   prevent each other from starving. From lemmas 27 and 25, and Corollary 21 we deduce:  Corollary 28.   In an   m -partial SCS whose communication graph is a tree, a robot   u   is starving if and only if the distance between   u   and any other live robot is different from the lengths of all ties in the single ring of the system.  We now show that rings are related to   circulant graphs . A graph on   n   nodes is   circulant   if the nodes of the graph can be numbered from 0 to   n   −   1   such that, if two nodes   x   and   ( x   +   d ) mod   n  are adjacent, then two nodes   z   and   ( z   +   d ) mod   n   are adjacent for any   z . We call such a node numbering a   c-order . Let   r   be a ring of length   2 mπ   containing the   m   surviving robots of an   m -partial SCS. Let  0 ,   1 , . . . , m   −   1   be a circular enumeration of the robots in   r , following the travel direction of the ring.   Lemma 14 implies that robot   i   is   2 π   units ahead of robot   i   −   1   (mod   m , as usual). Let   2 l 1 π, . . . ,   2 l t π   be the lengths of all ties in   r .   By Lemma 27, robot   i   starves if and only if  all   the robots that prevent it from starving fail. Note that these are the robots with indices in  { i   +   l 1 , . . . , i   +   l t } . The relation “prevent from starving” between the robots of   r   can be modeled using an undirected graph whose nodes correspond to the robots in the ring and, for all   i   6   =   j , there is an edge between nodes   i   and   j   if and only if robots   i   and   j   prevent each other from starving. The resulting graph is circulant. Figure 10a shows a SCS with a ring in bold stroke of length   18 π . It has two crossing points with itself:   p 1   determines ties of length   4 π   and   14 π , and   p 2   determines ties of length   8 π   and  10 π .   Therefore, enumerating the robots of this ring from   0   to   8   in the travel direction of the ring, we see that robot   i   is prevented from starving by robots   i   + 2 , i   + 4 , i   + 5   and   i   + 7 , (mod  9 ). Figure 10b shows the corresponding circulant graph. From Lemma 27 and Corollary 21 the following result is obtained:  Corollary 29.   The maximum possible number of starving robots in a ring is equal to the cardi- nality of the maximum   independent set 3   in the corresponding circulant graph.  In the following, we define an auxiliary operation to transform a circulant graph into another circulant graph with some interesting properties for us.  3 Subset of nodes in a graph that does not contain two adjacent nodes.  12
Definition 30   ( K n,n -augmentation) .   Let   G   = ( V, E )   be a graph with   n   nodes. A graph   G ′   = ( V   ′ , E ′ )   is a   clone   of   G   if   G ′   and   G   are isomorphic and   V   ∩   V   ′   =   ∅ . The   K n,n -augmentation   of  G , denoted by   G   = ( V , E ) , is the graph resulting from a graph join operation between   G   and a clone   G ′ , i.e   V   =   V   ∪   V   ′   and   E   =   E   ∪   E ′   ∪ {{ v, w } |   v   ∈   V, w   ∈   V   ′ } .  From now on we denote a vertex in a graph of   n   vertices by   v i   with   i   ∈ { 0 , . . . , n   −   1 } . In general, the vertex indices are taken modulo   n . The following result can be deduced directly from the definition of circulant graphs.  Lemma 31.   A graph is circulant if and only if all its connected components are isomorphic to the same circulant graph. Proof.   ( ⇐ )   Let   G   = ( V, E )   be a circulant graph of   n   nodes and let   v 0 , . . . , v n − 1   be a c-order of   G . Construct a graph   G ′   as the union of   m   disjoint clones of   G   and let   v ( i ) 0   , . . . , v ( i )  n − 1   be the c-order of   i th clone corresponding to the c-order of   G . It is easy to see that  v (1) 0   , v (2) 0   , . . . , v ( m ) 0   , v (1) 1   , v (2) 1   , . . . , v ( m ) 1   , . . . , v (1)  n − 1 , v (2)  n − 1 , . . . , v ( m )  n − 1  is a c-order of   G ′ . Therefore   G ′   is circulant.  ( ⇒ )   Let   G   = ( V, E )   be a circulant graph and let   v 0 , . . . , v n − 1   be its c-order.   Let   C   be a connected component of   G   containing   v 0 .   Let   m >   0   be the lowest value such that   v m   ∈   C . Then the nodes   v 2 m , v 3 m , . . .   are in   C . It can be proven that   m   divides   i   for all   v i   ∈   C . It can also be proven that   m   divides   n . Therefore   C   =   { v 0 , v m , v 2 m , . . . , v n − m } . From here, it is easy to see that   G   has   m   isomorphic connected components of the form   { v i , v i + m , v i +2 m , . . . , v n − m + i }  for all   0   ≤   i < m .  Lemma 32.   Let   G   = ( V, E )   and   G   = ( V , E )   be a graph and its   K n,n -augmentation, respectively.  G   is a circulant graph if and only if   G   is a circulant graph. Proof.   Let   G ′   = ( V, E )   be the clone of   G   used in the creation of   G . ( ⇒ ) Let   v 0 , . . . , v n − 1   be a c-order of   G   and   v ′  0 , . . . , v ′  n − 1   be the corresponding c-order of   G ′ . Consider the ordering   L   = ( v 0 , v ′  0 , v 1 , v ′  1 , . . . , v n − 1 , v ′  n − 1 )   of   V   . We show that   L   is a c-order of   G . Indeed, if   d   is odd then, for any   i ,   ( v i , v i + d )   is an edge of   G . If   d   is even, then both   v i   and   v i + d  are in the same graph   G   or   G ′ . Then   ( v i , v i + d )   ∈   E   if and only if   ( v 0 , v i + d/ 2 )   ∈   E . Therefore the graph   G   is circulant.  ( ⇐ )   If   G   is circulant then its complement graph   ¬ G   is circulant.   By Lemma 31,   ¬ G   has  m   isomorphic components.   Since   ¬ G   is the union of   ¬ G   and   ¬ G ′ ,   ¬ G   has   m/ 2   isomorphic components that are circulant graphs. Thus,   G   is a circulant graph by Lemma 31.  Lemma 33.   Let   G   = ( V, E )   and   G   = ( V , E )   be a graph and its   K n,n -augmentation, respectively. The maximum independent set of   G   and the maximum independent set of   G   have the same cardinality. Proof.   Let   H   ⊆   V   and   H   ⊆   V   be maximum independent sets in   G   and   G , respectively. Notice that the vertices in   H   also form an independent set in   G , thus   | H | ≤ | H | .   Since   G   is the  K n,n -augmentation,   H   cannot contain a vertex from   V   and a vertex from   V   ′ . So, either   H   ⊆   V  or   H   ⊆   V   ′ . Then   | H | ≤ | H |   and   | H |   =   | H | .  Note 1.   A circulant graph   G   = ( V, E )   of   n   nodes labeled   v 0 , . . . , v n − 1   can be shortly denoted as  C n S   where   S   =  {  d   ∈   N  ∣ ∣ ∣ { v i , v i + d } ∈   E,   1   ≤   d   ≤  ⌊   n  2  ⌋}  is the set of “jumps” adjacent vertices. See Figure 11, for two examples of this notation.  13
(a)   (b)  Figure 11 – (a) Circulant graph   C 6 { 2 } .   (b) Circulant graph   C 12 { 1 ,   3 ,   4 ,   5 }   which is the  K 6 , 6 -augmentation of   C 6 { 2 } , with solid points denoting the nodes of the original graph, and non-solid ones, the vertices of its clone. Original and cloned vertices are connected with dashed edges. Notice that for every pair of values   i   and   j   such that   0   ≤   i < j < n , if   { v i , v j   } ∈   E   then there exists   d   ∈   S   such that   i   +   d   =   j   or   j   +   d   ≡   i   (mod   n ) .   Thus the   K n,n -augmentation of  C n S   can be denoted by   C 2 n S   where  S   =   { 2 d   |   d   ∈   S } ∪  {  2 i   −   1  ∣ ∣ ∣ ∣   1   ≤   i   ≤  ⌊   n   + 1 2  ⌋}  .  Figure 11 shows an example of a circulant graph and its   K n,n -augmentation. Notice that the set of jumps of the   K n,n -augmentation of   C n S   contains all the odd numbers in the interval   [1 , n ] . We are ready to prove the main result of this section.  Theorem 34.   The problem of computing the starvation number of a SCS (SN-SCS) is NP-hard, even, if the communication graph of the SCS is a   caterpillar tree 4 . Proof.   We use a reduction from the problem of computing the maximum independent set in a cir- culant graph   (MIS-CG)   which is NP-hard [8]. Let   C n S   be a circulant graph with   n   ≥   2 , as input to the MIS-CG problem. For convenience we work with   C 2 n S   which is the   K n,n -augmentation of the given circulant graph   C n S . Recall that the problem of computing a maximum independent set for   C n S   is equivalent to the problem of computing a maximum independent set for   C 2 n S  and that   S   contains all odd numbers in   [1 , n ] . By Corollary 29, it suffices to transform   C 2 n S   into a SCS of   2 n   circles whose communication graph is a caterpillar tree such that  d   ∈   S   if and only if   there is a tie of length   2 dπ   in the SCS .   (5) We place the circles on three horizontal lines with coordinates in 1, 0 and   − 1   as illustrated in Figure 12. First, place the circle   C 0   on the 0-line. Then place   C i , i   = 1 , . . . , n   as follows. Let  C j   be the last circle placed on the 0-line. 1. If   i   ∈   S   then add the circle   C i   to the 0-line touching   C j   , see Figure 12a. 2. If   i / ∈   S   then add the circle   C i   touching   C j   but alternating between centered on the 1-line and centered on the   − 1 -line. In other words, if the last added circle not centered on the 0-line is centered on the 1-line, then center   C i   on the   − 1 -line, and vice-versa. see Figures 12b and 12c, respectively. Notice that   i   in the second case is even since   S   contains all odd numbers in   [1 , n ] . Thus, the next circle   C i +1   will be placed on the 0-line. Since the lines 1 and   − 1   alternate,   C i   touches only one circle,   C j   . 14
C 0 C i 0 1 -1 C j C 0 C i C j C 0 C m C i C j (a) (b) (c) Figure 12 – Addition of   C i   to the SCS. The ring of the SCS is shown with bold stroke. The case of   i   ∈   S   is shown in (a). The case of   i / ∈   S   is shown in (b) and (c). (b)   C i   is added to the 1-line if   i   is the smallest number not in   S   or   C m   is centered on the   − 1 -line.   (c)   C i   is added to the  − 1 -line if   C m   is centered on the 1-line. 0  -1  1  C 0   C n − 1   C n C j   C 0   C n − 1   C n C j   C ′  0 C ′  j  (a) 0  -1  1  C 0   C n − 1 C j   C 0   C j   C ′  0 C ′  j  C n  C n − 1  C n  C n   C n  (b) 0  -1  1  C 0   C n − 2 C j   C 0   C j   C ′  0 C ′  j  C n − 1  C n − 1  C n   C n − 2  C n − 1  C n − 1  C n  C ′  n − 1  C ′  n − 1  (c)  Figure 13 – Instructions of how to add the   n   −   1   remaining circles. (a) If   C n − 1   and   C n   are both on the 0-line, then apply symmetry about the vertical line between   C n − 1   and   C n . (b) If   C n − 1  is on the 0-line but   C n   is not, then apply symmetry about the vertical line passing through the center of   C n − 1 .   (c) In the remaining case apply symmetry about the touching point of   C n − 2  and   C n . 15
We have placed   n   + 1   circles   C 0 , . . . , C n .   In order to add the   n   −   1   remaining circles we proceed as follows:  •   if   n   is even then:  –   if   n   ∈   S   then we proceed as shown in Figure 13a.  –   if   n / ∈   S   then we proceed as shown in Figure 13b.  •   if   n   is odd then:  –   if   ( n   −   1)   ∈   S   then we proceed as shown in Figure 13a.  –   if   ( n   −   1)   / ∈   S   then we proceed as shown in Figure 13c. Now, we are ready to prove statement (5) on the obtained SCS. ( ⇒ ) If   d   ∈   S , then   C d   is centered on the   0 -line and the tie determined by the crossing point between   C d   and the previous circle centered on the 0-line covers the   d   circles to the left of   C d . Consequently, the length of this tie is   2 dπ . ( ⇐ ) Every crossing point between circles centered on the same vertical line determines two ties of length   2 π   and   2(2 n   −   1) π , respectively, and 1 is in   S . Consider the crossing point between two circles centered on the 0-line. By symmetry, we can assume that the circles are   C j   and   C i  where   0   ≤   j < i   ≤   n . The crossing point determines a tie of length   2 iπ   covering the   i   circles to the left of   C i . Since   C i   is on the 0-line,   i   ∈   S . This argument completes the proof. Figure 14 shows some examples of the SCS construction. The following result is deduced from Theorem 34 and Lemma 17.  Corollary 35.   The problem of computing the   k -resilience of a SCS is NP-hard.  In the rest of this section we focus on how to count the number of starving robots in an   m - partial SCS in order to prove that the decision version of   k -resilience problem is NP-Complete. Lemma 27 gives us a method to check if two robots prevent each other from starving if they are in the same ring. But, how does one check if two robots prevent each other from starving if they are in different rings?  Theorem 36.   In an   m -partial SCS, let   p   and   p ′   be the positions of two robots   u   and   u ′   in different rings   r   and   r ′ , respectively. Let   c   be a crossing point between   r   and   r ′ . Let   d   and   d ′  denote the lengths of the simple paths from   p   and   p ′   to   c , respectively. Let   2 lπ   and   2 l ′ π   be the lengths of   r   and   r ′   respectively. Then:  •   d   −   d ′   is in   2 π Z .  •   Let   s   ∈   Z   such that   d   −   d ′   = 2 πs .   Then, the robots   u   and   u ′   prevent each other from starving if and only if the   greatest common divisor   of   l   and   l ′   divides   s . Proof.   Figure 15 shows the positions of the robots. First, we prove that   ( d − d ′ )   ∈   2 π Z . Suppose, w.l.o.g., that   d   ≤   d ′ .   Consider the time when the robot in   r   reaches   c .   The robot in   r ′   has distance   d ′   −   d   to   c . By Lemma 12 the distance between the two robots in   r ′   is   d ′   −   d   ∈   2 π N . We focus now on the second claim. If   u   and   u ′   prevent each other from starving then there are two paths of equal length, say   L , from   p   and   p ′   to   c . The path from   p   (resp.   p ′ ) to   c   can be decomposed in the section from   p   (resp.   p ′ ) to   c   and zero or more round trips in   r   (resp.   r ′ ).  4 A caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.  16
C 0   C 1  C 2  C 3   C 4   C 5  C 6  C ′  4   C ′  3   C ′  1  C ′  2  C ′  0 (a) SCS obtained from the circulant graph   C 12 { 1 ,   3 ,   4 ,   5 }   shown in Figure 11b.  (b)   C 4 { 2 }   and its   K 4 , 4 -augmentation:   C 8 { 1 ,   3 ,   4 } . C 0   C 1  C 2  C 3   C 4   C ′  1  C ′  2  C ′  0  (c) SCS obtained from   C 8 { 1 ,   3 ,   4 } .  (d)   C 9 { 3 }   and its   K 9 , 9 -augmentation:   C 18 { 1 ,   3 ,   5 ,   6 ,   7 ,   9 } . C 0   C 1  C 2  C 3  C 4  C 5   C 6   C 7  C 8  C 9  C ′  8  C ′  0 C ′  1  C ′  2  C ′  3  C ′  4  C ′  5 C ′  6  (e) SCS obtained from   C 18 { 1 ,   3 ,   5 ,   6 ,   7 ,   9 } .  Figure 14 – Examples of construction of a SCS from the   K n,n -augmentation of some circulant graphs. The samples in (a) and (c) are obtained by applying the steps illustrated in Figure 13b and 13a, respectively.   The example in (e) is obtained by applying the steps illustrated in Figure 13c. c p p ′ ︷   ︸︸   ︷ d ︷   ︸︸   ︷ d ′ r r ′  Figure 15 – Illustration of Theorem 36. 17
Let   x   and   y   denote the number of round trips of the paths in   r   and   r ′ , respectively. Therefore  L   =   d   +   x   ·   2 πl   and   L   =   d ′   +   y   ·   2 πl ′   where   ( x, y )   ∈   N   ×   N . Then:  d   +   x   ·   2 πl   =   d ′   +   y   ·   2 πl ′  d   −   d ′   =   y   ·   2 πl ′   −   x   ·   2 πl  2 πs   =   y   ·   2 πl ′   −   x   ·   2 πl s   =   y   ·   l ′   −   x   ·   l   (6) Considering   x   and   y   variables, this is a   Diophantine equation   and has a solution where   x   and   y  are integers if and only if   gcd( l, l ′ )   |   s . ( ⇒ ) If   u   and   u ′   prevent each other from starving, then there exists a solution   ( x 1 , y 1 )   ∈   N × N  for Equation (6). Therefore,   gcd( l, l ′ )   |   s . ( ⇐ ) If   gcd( l, l ′ )   |   s   then there exist infinitely many solutions for Equation (6) in   Z   ×   Z . Observe that the line represented by Equation (6) has positive slope.   Therefore, there exist infinite solutions in   N   ×   N . Taking any of these solutions in   N   ×   N , we can obtain two paths, one from   p   to   c   and the other from   p ′   to   c   of equal lengths. Therefore,   u   and   u ′   prevent each other from starving. Given an   m -partial SCS, the problem of counting how many of the   m   robots are in starvation takes polynomial time. This can be done using a   starving-prevention test   between every pair of live robots   u   and   u ′   in the system.  Starving-prevention test:   Given two robots   u   and   u ′ , are they preventing each other from starving?  Lemma 37.   Given an   m -partial SCS, the   starving-prevention test   between two robots   u   and  u ′   in the system takes   O ( nT gcd ( n ))   time, where   T gcd ( n )   is the time 5   to compute the greatest common divisor between any two numbers less than or equal to   n . Proof.   The first thing to do is a preprocessing in order to find the rings of the system and their lengths. During this process we can also obtain the ties and their lengths. This preprocessing step takes   O ( | E | )   time where   E   is the set of edges of the communication graph. Since this graph is planar,the preprocessing step takes   O ( n )   time. After that, we proceed as follows in order to perform the prevention test between every pair of robots in the system.   Let   u   and   u ′   be two robots in the system. If   u   and   u ′   are in the same ring, the test can be done in   O ( n )   time by checking ties of the ring (Lemma 27). If they are in different rings,   r   and   r ′   respectively, then there are two options. (i) If   r   and   r ′   have no common crossing points then they do not prevent each other from starving.   (ii) Otherwise, for every crossing point   c   between   r   and   r ′   check if  u   and   u ′   meet each other at   c   using Theorem 36. This can be done in   O ( T gcd ( n ))   time, where  T gcd ( n )   is the time to compute   gcd ( l, l ′ )   and   2 lπ   and   2 l ′ π   are the lengths of rings   r   and   r ′ , respectively. Thus, the prevention test takes   O ( nT gcd ( n ))   time.  Corollary 38.   Given an   m -partial SCS, the total time to count the number of starving robots is   O ( m 2 nT gcd ( n )) .  As a consequence of the above results, we arrive at the following result:  Corollary 39.   The decision problems: determining if the   k -resilience of a SCS is smaller than a given value   s   and determining if the starvation number of a SCS is greater than a given value  s   are both NP-complete, even if the communication graph is a caterpillar tree.  5 T gcd ( n ) =   O (log   n (log log   n ) 2   log log log   n )   according to [18].  18
4   Computing   k -resilience  The problem of computing the   k -resilience of a SCS is NP-hard but one may still want to compute the   k -resilience for a given (presumably small) SCS. Let   S   =   { u 1 , . . . , u n }   be a set of   n  robots in the initial state of the system. One approach is to select a set   S k   ⊂   S   of   k   robots and (i) for each robot   u i   in   S k , find the set of robots   Q i   ⊂   S   preventing   u i   from starving, (ii) find   Q   =   ⋃  u i ∈ S k  Q i . Then, the   k -resilience will be the cardinality of the smallest set   Q   satisfying   Q   ∩   S k   =  ∅   computed over every possible set   S k .   The sets   Q i   can be computed using the   starving- prevention test   between every pair of robots in   S k   ×   S .   Therefore, the total time to obtain  Q   is   O ( kn 2 T gcd ( n )) . The time for computing the   k -resilience is   O ( kn k +2 T gcd ( n )) . We show that the running time can be improved by a factor of   O ( nT gcd ( n )) .  4.1   Meeting Graph  We define a   meeting graph   G m   = ( V m , E m )   using robots as vertices and an edge between nodes if the corresponding robots prevent each other from starving. This graph is useful in computing the   k -resilience. We show that it can be computed in   O ( n 2 )   time.  Same ring . For each robot   u   in a ring   r , find robots in   r   at positions   p   +   l 1 , p   +   l 2 , . . .   where  p   is the position of   u   and   { l 1 , l 2   . . . }   is the set of the lengths of the ties in   r . Add edges to   E m  between   u   and every found robot. The running time of this step is   O ( n )   for one robot   u   and  O ( n 2 )   in total.  Distinct rings . For each crossing point   c   between two different rings   r   and   r ′   do the following. Compute   g   =   gcd ( l, l ′ ) , where   2 lπ   and   2 l ′ π   are the lengths of   r   and   r ′   respectively.   For each robot   u   in   r   at distance   d   from   c , find all robots in   r ′   at distance   d   +   i   ·   g, i   = 0 ,   1 ,   2 , . . .   . Add edges between   u   and these robots to   E m . This can be done in   O ( n   +   I ) =   O ( n )   time per crossing point where   I   is the number of edges found for crossing point   c . The total time is   O ( n 2 ) .  4.2   Faster Algorithm  We show that   k   robots can be selected in a way that we spend   O ( n )   time for each robot. Let  A   be the list of available robots. In the beginning   A   =   { u 1 , . . . , u n }   contains all   n   robots. In general, if   A   is empty, we cannot select a new robot and we check another set of   k   robots. When a robot   u i   is selected from   A , we remove its neighbors in   G m   from   A . If   u i   is not the last ( k th selected) robot then   A   contains candidate robots to select next. If   u i   is the last selected robot then   | A |   is the number of remaining robots. Let   A max   be the largest set   A   of remaining robots over all selections of   k   robots. Then   n   −   k   − | A max |   is the   k -resilience of the system. This implies the following result.  Theorem 40.   The   k -resilience of a SCS can be computed in   O ( kn k +1 )   time.  4.3   Computing 1-resilience  Theorem 41.   The   1 -resilience of a SCS can be computed in   O ( nT gcd ( n )) =  ̃ O ( n )   time 6 .  6    ̃ O   notation hides polylogarithmic factors.  19
Proof.   Denote by   ρ ( u )   the number of robots that prevent robot   u   from starving. By definition, the value of   1 -resilience is   min   { ρ ( u ) | u   ∈   S }   where   S   is the set of the   n   robots in the system. In a preprocessing step, find the rings and their lengths, also, obtain the ties and their lengths. This preprocessing takes   O ( n )   time. For each ring   r , pick a single robot   u   from it. Let  r 1 , r 2 , . . .   be the rings crossing   r . For each ring   r i   crossing   r , compute a list   D i   of distances from  u   to every crossing point between   r   and   r i . Also, in   T gcd ( n )   time, compute   g i   =   gcd ( l, l i )   where  2 lπ   and   2 l i π   are the lengths of   r   and   r i , respectively. For each distance   d   ∈   D i , we compute   d r , the remainder of dividing   d   by   g i . Let   n i   be the number of distinct   d r   for a ring   r i . Compute  ρ ( u ) =   t ( r ) +   ∑  i   n i   ·   l i /g i   where   t ( r )   is the distinct lengths of ties in   r . This is the number of robots preventing   u   from starvation (Lemma 27 and Theorem 36). Let   v   be another robot laid  2 bπ   behind   u   in   r . Notice that if a robot   u ′   in a ring   r ′   is preventing   u   from starving, then the robot   v ′   laid   2 bπ   behind   u ′   in   r ′   prevents   v   from starving. From this observation we have that for every two robots   u   and   v   in the same ring,   ρ ( u ) =   ρ ( v ) . Let   % ( r )   be the value   ρ ( u )   of an arbitrary robot in the ring   r . Computing   % ( r )   takes   O ( e r   ·   T gcd ( n ))   time where   e r   is the number of crossing points traversed by   r . Find the smallest   ρ ( r )   by computing it for all rings   r   in the system. The total running time is   O ( nT gcd ( n )) =  ̃ O ( n )   because every crossing point is analyzed two times, one per each traversing ring (the same ring twice in ties) and the number of crossing points is   O ( n ) .  5   Computing   k -resilience for trees  Trees constitute an important family of graphs for computing   k -resilience. For instance, spanning trees can be used to enforce synchronization on non-planar communication graphs. Furthermore, the communication graph of a tree has only ring.  Lemma 42.   In a SCS whose communication graph is a tree the 1-resilience can be computed in  O ( n )   time. Proof. 1-resilience . Recall that there is only one ring if   G   is a tree. We can pick any robot   u  for starvation. The robots preventing   u   from starvation can be found from the ties. Compute all tie lengths   l 1   < .. < l t   using the computation of rings. Then, the 1-resilience of   G   is   t .  Lemma 43.   In a SCS whose communication graph is a tree the 2-resilience can be computed in  O ( t 2 )   time where   t   is the number of distinct tie lengths. Proof.   Compute tie lengths   L   =   { l 1 , . . . , l t }   using the computation of rings. Compute the mode  m   of multiset   S +   ∪   S −   where   S +   and   S −   are the multisets:  { l i   +   l j   < n, l i   +   l j   / ∈   L }   and   { l i   −   l j   >   0 , l i   −   l j   / ∈   L } , respectively .  Then the 2-resilience is   2 t   −   f   where   f   is the frequency of   m   in   S +   ∪   S − . We show that the algorithm is correct. For convenience we use a circular numbering of the   n  robots in the system   0 ,   1 , . . . , n   −   1   such that two robots   i   and   j   ( j > i ) prevent each other from starving if and only if   j   −   i   ∈   L . Consider an optimal solution. W.l.o.g. assume that 2 starving robots are at positions 0 and   d .   There are   t   robots preventing robot 0 from starving.   Their positions are   S 0   =   L . There are   t   robots preventing robot   d   from starving. Their positions are  S d   =   { d   +   l 1 , . . . , d   +   l t }   using modulo   n . The number of robots preventing robot 0 or   d   from starving is   2 t   − | S 0   ∩   S d |   which is 2-resilience. The number of robots preventing both robots 0 and   d   is   | S 0   ∩   S d | . Consider a robot from  S 0   ∩   S d   at position   x .   Clearly   x   ∈   L .   If   x < d   then   d   =   x   +   l j   and   d   ∈   S + .   If   x > d   then 20
d   =   x   −   l j   and   d   ∈   S − . Therefore   | S 0   ∩   S d |   is equal to the frequency of   d   in   S +   ∪   S −   and the 2-resilience is equal to   2 t   −   f   . The running time is   O ( t 2   +   n )   time. By Lemma 44, this is simply   O ( t 2 ) .  Lemma 44.   In a SCS whose communication graph is a tree, if there are   t   distinct tie lengths then  √ πn  2   −   1   ≤   t   ≤   n   −   1 . Proof.   To show the upper bound, we observe that each tie has length   2 πa, a   ∈ { 1 ,   2 , . . . , n   −   1 } . We use a packing argument for the lower bound. Let   s n   be side length of the smallest square containg   n   unit circles. Since every circle has area   π , we have   s n   >   √ πn . There are better lower bounds for small   n   (up to 100) [6, 16, 19]. Szabo et.al. [19] provide the following bound  m n   ≤   1 +  √  1 + 2( n   −   1) / √ 3  n   −   1   ,  where   m n   is the largest value of   min i<j   | p i p j   |   for any set of points   p 1 , . . . , p n   in the unit square. Clearly,   s n   = 2 + 2 /m n . Compute   x min , x max , y min , y max   for the centers of the trajectories.   Then   | x max   −   x min | ≥  s n   −   2   or   | y max   −   y min | ≥   s n   −   2 . Let   T   be the communication graph of the system. Then the diameter   δ   of   T   is at least   ( s n   −   2) / 2 + 1 =   s n / 2 . Let   C 1 , .., C δ   be the sequence of trajectories in the system forming the diameter of   T   .   It has   δ   −   1   edges.   Each edge determines two ties. There are   2( δ   −   1)   ties. Clearly at most two ties have the same length. So, we have at least   δ   −   1  distinct tie lengths. The lower bound follows since   δ   ≥   s n / 2   >   √ πn/ 2 . For any   n , there is an instance of a tree of size   n   with   Ω( √ n )   tie lengths. If   n   =   a 2   then the tree is built of   a   paths of length   a   which are connected as shown in Figure 16. The number of tie lengths (not the number of ties!) is   a   + 2( a   −   1) = 3 a   −   2 . In general, we take   a   =   b√ n c   and add   n   −   a 2   trajectories in the middle of the tree. ︷   ︸︸   ︷ ︷   ︸︸   ︷ a a   −   1 ︷   ︸︸   ︷ a   −   1 ︷   ︸︸   ︷ a  Figure 16 – A tree for   n   =   a 2 . There are   n − 1   ties and they have lengths   1 ,   2 , . . . , a,   2 a,   3 a, . . . , n −  a, a   −   a   + 1 , . . . , n . Notice that if the number   t   of distinct tie lengths in the tree is   O ( √ n )   then the 2-resilience can be computed in linear time. In the worst case, when   t   is   Ω( n ) , the 2-resilience can be computed in   O ( n 2 )   time.   The last complexity can be improved if the problem   mode-of-differences  (described in Section 6) can be solved in subquadratic time.  Theorem 45.   In a SCS whose communication graph is a tree, the   k -resilience,   k   ≥   3 , can be computed in   O ( n k − 2 t   ·   min( n, kt )) =   O ( tn k − 1 )   time, where   t   is the number of distinct tie lengths.  21
Proof.   Compute tie lengths   L   =   { l 1 , . . . , l t }   of the ring.   For convenience we use a circular numbering of the   n   robots in the system   0 ,   1 , . . . , n   −   1   such that two robots   i   and   j   ( j > i ) prevent each other from starving if and only if   j   −   i   ∈   L . Place one robot at position 0 (this can be done without loss of generality). Choose   k   −   2   robots making a set   S ′   of   k   −   1   robots. This can be done as in the algorithm from Theorem 40 (using the list   A   of available robots).   The running time for testing   k   −   1   robots is   O (( k   −   1) t ) =   O ( kt ) . Now the task is to find a robot in   A   with the minimum number of robots in   A   preventing it from starving. Let   F   =   { f 1 , f 2 , . . . , f z   }   be the set of robots preventing at least one robot in  S ′   from starving. Clearly,   F   =   { 0 ,   1 ,   2 , . . . , n   −   1 } −   ( A   ∪   S ′ ) . Compute the mode   m   of multiset  S +   ∪   S −   where  S +   =   { f i   +   l j   , f i   +   l j   ∈   A }   and   S −   =   { f i   −   l j   , f i   −   l j   ∈   A } .  Compute   ρ ( S ′ ) =   | F   |   +   t   −   f   where   f   is the frequency of   m   in   S +   ∪   S − . Compute the   k -resilience as minimum of   ρ ( S ′ )   over all possible sets   S ′ . Clearly,   | F   | ≤   min( n, kt )   and the algorithm has the running time   O ( n k − 2 t   ·   min( n, kt )) . The algorithm is correct by an argument similar to the proof of Lemma 43.  6   Concluding remarks  In this work we have studied a combinatorial optimization problem related to the robustness of synchronized systems composed of robots that cooperate to cover an area with constrained communication range. We stated the concept of   starvation   as a phenomenon that can appear when a set of robots leaves a synchronized system.   This phenomenon is characterized by the permanent loss of communication of one or more surviving agents when a number of robots leave a synchronized system. Also, we present the   starvation state   of a system as an extreme case of communication breakdown, where all the surviving robots in the system are permanently isolated. Then we addressed the main topic of this work, the   k -resilience   of a system, defined as the cardinality of a smallest set of robots whose failure suffices to cause that at least   k   surviving robots become incommunicado. We prove that the problem is NP-complete when   k   is part of the input and propose efficient algorithms for small values of   k . A possible research line is to improve the time complexity for constant values of   k .   A possibility is to follow our approach and solve in sub-quadratic time the following basic questions that we state here as new open problems in algorithm design, related to 2- and   k -resilience, respectively.  The mode-of-differences problem:   Let   0   < l 1   < l 2   <   · · ·   < l t   < n   be   t   integer numbers,  t   ∈   Ω( n ) . For each   0   < i < n , let   R i   is the number of times that   i   is the difference of two of the given numbers. Compute   max   R i .  The mode-of-differences-of-two-sets problem:   Let   A   and   B   be two subsets of   { 1 ,   2 , . . . , n −  1 }   whose cardinalities are in   Ω( n ) . For each   0   < i < n , let   R i   be the number of times   i   appears in the multiset   A   −   B . Compute   max   R i .  References  [1] J.J. Acevedo, B. C. Arrue, J.M. Díaz-Báñez, I. Ventura, I. Maza, and A. Ollero. One-to-one coordination algorithm for decentralized area partition in surveillance missions with a team of aerial robots.   Journal of Intelligent and Robotic Systems , 74(1-2):269–285, 2014. 22
[2] D. Alejo, J.M. Díaz-Báñez, J.A. Cobano, P. Pérez-Lantero, and A. Ollero.   The velocity assignment problem for conflict resolution with multiple aerial vehicles sharing airspace.  Journal of Intelligent   &   Robotic Systems , 69(1-4):331–346, 2013. [3] S. Bereg, L.E. Caraballo, J.M. Díaz-Báñez, and M.A. López. Computing the   k -resilience of a synchronized multi-robot system. In   33 rd   European Workshop on Computational Geometry (EuroCG17) , pages 65–68, 2017. [4] M. Bernard, K. Kondak, I. Maza, and A. Ollero.   Autonomous transportation and de- ployment with aerial robots for search and rescue missions.   Journal of Field Robotics , 28(6):914–931, 2011. [5] A.P. Brunner. Isolation in synchronized drone formations, 2015. Master Thesis, University of Denver. [6] L. G. Casado, I. García, P. G. Szabó, and T. Csendes.   Packing Equal Circles in a Square II. — New Results for up to 100 Circles Using the TAMSASS-PECS Algorithm , pages 207–224. Springer US, Boston, MA, 2001. [7] Y. Chevaleyre.   Theoretical analysis of the multi-agent patrolling problem.   In   Intelligent Agent Technology, 2004. (IAT 2004). Proceedings. IEEE/WIC/ACM International Confer- ence on , pages 302–308, 2004. [8] B. Codenotti, I. Gerace, and S. Vigna. Hardness results and spectral techniques for com- binatorial problems on circulant graphs.   Linear Algebra and its Applications , 285(1):123 – 142, 1998. [9] T.W. Cusick. View-obstruction problems.   aequationes mathematicae , 9(2-3):165–170, 1973. [10] J. Czyzowicz, L. Gąsieniec, A. Kosowski, and E. Kranakis. Boundary patrolling by mobile agents with distinct maximal speeds.   In Camil Demetrescu and MagnúsM. Halldórsson, editors,   Algorithms - ESA 2011 , volume 6942 of   Lecture Notes in Computer Science , pages 701–712. Springer Berlin Heidelberg, 2011. [11] J.M. Díaz-Báñez, L.E. Caraballo, M. Lopez, S. Bereg, I. Maza, and A. Ollero. A general framework for synchronizing a team of robots under communication constraints.   IEEE Transactions on Robotics , PP(99):1–8, 2017. [12] J.M. Díaz-Báñez, L.E. Caraballo, M.A. López, S. Bereg, I. Maza, and A. Ollero. The syn- chronization problem for information exchange between aerial robots under communication constraints. In   Robotics and Automation (ICRA), 2015 International Conference on . IEEE, 2015. [13] A. Dumitrescu, A. Ghosh, and C.D. Tóth.   On fence patrolling by mobile agents.   The Electronic Journal of Combinatorics , 21(3):P3–4, 2014. [14] A. Kawamura and Y. Kobayashi. Fence patrolling by mobile agents with distinct speeds.  Distributed Computing , 28(2):147–154, 2015. [15] A. Kawamura and M. Soejima. Simple strategies versus optimal schedules in multi-agent pa- trolling. In Vangelis Th. Paschos and Peter Widmayer, editors,   Algorithms and Complexity , volume 9079 of   Lecture Notes in Computer Science , pages 261–273. Springer International Publishing, 2015. 23
[16] Costas D. Maranas, Christodoulos A. Floudas, and Panos M. Pardalos. New results in the packing of equal circles in a square.   Discrete Mathematics , 142(1):287 – 293, 1995. [17] F. Pasqualetti, A. Franchi, and F. Bullo.   On cooperative patrolling:   Optimal trajecto- ries, complexity analysis, and approximation algorithms.   Robotics, IEEE Transactions on , 28(3):592–606, 2012. [18] Damien Stehlé and Paul Zimmermann. A binary recursive gcd algorithm. In   Algorithmic number theory , volume 3076 of   Lecture Notes in Comput. Sci. , pages 411–425. Springer, Berlin, 2004. [19] P. G. Szabó, T. Csendes, L. G. Casado, and I. García.   Packing Equal Circles in a Square I. — Problem Setting and Bounds for Optimal Solutions , pages 191–206. Springer US, Boston, MA, 2001. 24