Fast Rendezvous on a Cycle by Agents with Different Speeds  Ofer Feinerman 1 , Amos Korman 2 , Shay Kutten 3 , and Yoav Rodeh 4  1   The Shlomo and Michla Tomarin Career Development Chair, Weizmann Institute of Science, Rehovot, Israel.  2   CNRS and University Paris Diderot, Paris, France.  3   Faculty of IR&M, Technion, Haifa 32000, Israel.  4   Jerusalem College of Engineering.  Abstract.   The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achieve- ment of cooperative goals more difficult. In this work, we aim to highlight potential   benefits   of such asynchrony phenomena to tasks involving sym- metry breaking. Specifically, in this paper, identical (except for their speeds) mobile agents are placed at arbitrary locations on a (continuous) cycle of length   n   and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some   c >   1. (An agent does not know whether it is the slower agent or the faster one.) The straightforward   distributed-race ( DR )   algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of   DR   is   n/ ( c − 1). Note that in the interesting case, where  c   is very close to 1 (e.g.,   c   = 1 + 1 /n k   ), this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks (the   white board   model), even assuming sense of direction, and even assuming   n   and   c   are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least  n  2( c − 1)   if   c   6   3 and slightly larger (specifically,   n c +1   ) if   c >   3. We then manage to construct an algorithm that precisely matches the lower bound for the case   c   6   2, and almost matches it when   c >   2. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark (a pebble) and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for   c   6   2, and almost tight bounds for  c >   2.  Keywords:   rendezvous; asynchrony; heterogeneity; speed; cycle; pebble; white board; mobile agents  arXiv:1211.5787v2 [cs.DC] 13 Sep 2015
1   Introduction  1.1   Background and Motivation  The difference between the speed of the actions of different entities is typically considered disruptive in real computing systems. In this paper, we illustrate some advantages of such phenomena in cases where the difference remains   fixed  throughout the execution 5 . We demonstrate the   usefulness   of this manifestation of asynchrony to tasks involving symmetry breaking. More specifically, we show how two mobile agents, identical in every aspect save their speed, can lever their speed difference in order to achieve fast rendezvous. Symmetry breaking is a major issue in distributed computing that is com- pletely absent from traditional sequential computing. Symmetry can often prevent different processes from reaching a common goal. Well known examples include leader election [ 3   ], mutual exclusion [ 14   ], agreement [   4 , 25   ] and renaming [ 6 ]. To address this issue, various differences between processes are exploited. For exam- ple, solutions for leader election often rely on unique identifiers assumed to be associated with each entity (e.g., a process) [   3 ]. Another example of a difference is the location of the entities in a network graph. Entities located in different parts of a non-symmetric graph can use this knowledge in order to behave differently; in such a case, a leader can be elected even without using unique identifiers [   26   ]. If no differences exist, breaking symmetry deterministically becomes impossible (see, e.g., [ 3 , 27   ]) and one must resort to randomized algorithms, assuming that different entities can draw different random bits [19]. We consider mobile agents aiming to rendezvous. See, e.g., [   7   , 13   , 22 , 23   , 24   , 27   ]. As is the case with other symmetry breaking problems, it is well known that if the agents are completely identical then rendezvous is, in some cases, impossible. In fact, a large portion of the research about rendezvous dealt with identifying the conditions under which rendezvous was possible, as a result of some asymmetries. Here, the fact that agents have different speeds implies that the mere feasibility of rendezvous is trivial, and our main concern is therefore the time complexity, that is, the time to reach a rendezvous. More specifically, we study the case where the agents are identical except for the fact that they have different speeds of motion. Moreover, to isolate the issue of the speed difference, we remove other possible differences between the agents. That is, the agents are assumed to be anonymous. To avoid solutions of the kind of [ 26 ], that are based on the underlying graph being asymmetric, we consider a symmetric topological object, that is, specifically, a cycle topology. We denote by   n   the length of the cycle.  1.2   The Model and the Problem  The problem of rendezvous on a cycle:   Consider two identical deterministic   agents  placed on a cycle of length   n   (in some distance units). To ease the description,  5   Advantages can also be exploited in cases where the difference in speed follows some stochastic distribution, however, in this initial study, we focus on the simpler fully deterministic case. That is, we assume a speed heterogeneity that is arbitrary but fixed throughout the execution.
we name these agents   A   and   B   but these names are not known to the agents. Each agent is initially placed in some location on the cycle by an adversary and both agents start the execution of the algorithm simultaneously. An agent can move on the cycle at any direction. Specifically, at any given point in time, an agent can decide to either start moving, continue in the same direction, stop, or change its direction. The agents’ goal is to   rendezvous , namely, to get to be co-located somewhere on the cycle 6 . We consider continuous movement, so this rendezvous can occur at any location along the cycle. An agent can detect the presence of another agent at its location and hence detect a rendezvous. When agents detect a rendezvous, the rendezvous task is considered completed.  Orientation issues:   We distinguish between two models based on orientation. The first assumes that agents have the   sense of direction   [   8 ], that is, we assume that the agents can distinguish clockwise from the anti-clockwise. In the second model, we do not assume this orientation assumption. Instead, each agent has its own perception of which direction is clockwise and which is anti-clockwise, but there is no guarantee that these perceptions are globally consistent. (Hence, e.g., in this model, if both agents start walking in their own clockwise direction, they may happen to walk in opposite directions, i.e., towards each other).  The   pebble   and the   white board   models:   Although the agents do not hold any direct means of communication, in some cases we do assume that an agent can leave marks in its current location on the cycle, to be read later by itself and by the other agent. In the   pebble   model, an agent can mark its location by dropping a pebble   [ 10 ,   11   ]. Both dropping and detecting a pebble are local acts taking place only on the location occupied by the agent. We note that in the case where pebbles can be dropped, our upper bound employs agents that drop a pebble only once and only at their initial location [ 1 , 9   , 24 ]. On the other hand, our corresponding lower bound holds for any mechanism of (local) pebble dropping. Moreover, this lower bound holds also for the seemingly stronger ’ white board   model, in which an agent can change a memory associated with its current location such that it could later be read and further manipulated by itself or the other agent [20,16,17].  Speed:   Each agent moves at the same fixed speed at all times; the   speed   of an agent  A , denoted   s ( A ), is the inverse of the time   t α   it takes agent   A   to traverse one unit of length. For agent   B , the time   t β   and speed   s ( B ) are defined analogously. Without loss of generality, we assume that agent   A   is faster, i.e.,   s ( A )   > s ( B ) but emphasize that this is unknown to the agents themselves. Furthermore, for simplicity of presentation, we normalize the speed of the slower agent   B   to one,  6   In a sense, this rendezvous problem is also similar to the   cow-path   problem, see, e.g., [ 5   ]. Here, the agents (the cow and the treasure she seeks to find) are both mobile (in the cow-path problem only one agent, namely, the cow, is mobile). It was shown in [   5 ] that if the cow is initially located at distance   D   from the treasure on the infinite line then the time to find the treasure can be 9 D , and that 9 is the best multiplicative constant (up to lower order terms in   D ).
that is,   s ( B ) = 1 and denote   s ( A ) =   c   where   c >   1. We stress that the more interesting cases are when   c   is a function of   n   and arbitrarily close to 1 (e.g.,  c   = 1 + 1 /n k , for some constant   k ). We assume that each agent has a pedometer that enables it to measure the distance it travels. In some cases, agents are assumed to posses some knowledge regarding   n   and  c ; whenever used, this assumption will be mentioned explicitly.  Time complexity:   The   rendezvous time   of an algorithm is defined as the worst case time bound until rendezvous, taken over all pairs of initial placements of the two agents on the cycle. Note, a lower bound for the rendezvous time that is established assuming sense of direction holds trivially for the case where no sense of direction is assumed. All our lower bounds hold assuming sense of direction.  The   Distributed Race   ( DR ) algorithm:   Let us consider a trivial algorithm, called  Distributed Race   ( DR ), in which an agent starts moving in an arbitrary direction, and continues to walk in that direction until reaching rendezvous. Note that this algorithm does not assume knowledge of   n   and   c , does not assume sense of direction and does not leave marks on the cycle. The worst case for this algorithm is that both agents happen to walk on the same direction. Without loss of generality, assume this direction is clockwise. Let   d   denote the the clockwise distance from the initial location of   A   to that of   B . The rendezvous time   t   thus satisfies   t   ·   s ( A ) =   t   ·   s ( B ) +   d . Hence, we obtain the following.  Observation 1   The rendezvous time of   DR   is   d/ ( c   −   1)   < n/ ( c   −   1) .  Note that in the cases where   c   is very close to 1, e.g.,   c   = 1 + 1 /n k , for some constant   k , the bound on the rendezvous time of   DR   is very large.  1.3   Our Results  Our first result is a lower bound showing that, up to a multiplicative approxima- tion factor of 2, the bound of   DR   mentioned in Observation 1 is unavoidable, even in the white board model, even assuming sense of direction, and even assuming  n   and   c   are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least   n  2( c − 1)   if   c   6   3 and slightly larger (specifically,   n c +1   ) if   c >   3. We then manage to construct an algorithm that matches the lower bound precisely for the case   c   6   2, and almost matches it when  c >   2. Specifically, when   c   6   2, our algorithm runs in time   n  2( c − 1)   and when   c >   2, the rendezvous time is   n/c   (yielding a (2   −   2  c   )-approximation when 2   < c   6   3, and a (   c +1  c   )-approximation when   c >   3). Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and allows agents to leave only a single mark (a pebble) and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for   c   6   2, and almost tight bounds for   c >   2. Specifically, for this case, we establish a tight bound of   cn c 2 − 1   for the rendezvous time, in case
agents have sense of direction. With the absence of sense of direction, the same lower bound of   cn c 2 − 1   holds, and we obtain an algorithm matching this bound for the case   c   6   2, and rather efficient algorithms for the case   c >   2. Specifically, the rendezvous time for the case   c   6   2 is   cn c 2   − 1   , for the case 2   < c   6   3, the rendezvous time is   2 n c +1   , and for the case   c >   3, the rendezvous time is   n c − 1   .  2   A Lower Bound for the White Board Model  The following lower bound implies that   DR   is a 2-approximation algorithm, and it becomes close to optimal when   c   goes to infinity.  Theorem 1.   Any rendezvous algorithm in the white board model requires at least  max {   n  2( c − 1)   ,   n c +1   }   time, even assuming sense of direction and even assuming   n  and   c   are known to the agents. Proof.   We assume that agents have sense of direction; hence, both agents start walking at the same direction. We first show that any algorithm in the white board model requires   n  2( c − 1)   time. Consider the case that the adversary locates the agents at   symmetric locations   of the cycle, i.e., they are at distance   n/ 2 apart. Now consider any algorithm used by the agents. Let us fix any   c ′   such that 1   < c ′   < c , and define the (continuous) interval  I   :=  [  0 ,   nc ′  2( c   −   1)  ]  .  For every (real)   i   ∈   I , let us define the following (imaginary) scenario   S i . In scenario   S i , each agent executes the algorithm for   i   units of distance (not neces- sarily in the same direction) and terminates 7 . We claim that for every   i   ∈   I , the situation at the end of scenario   S i   is completely symmetric: that is, the white board at symmetric locations contain the same information and the two agents are at symmetric locations. We prove this claim by induction. The basis of the induction, the case   i   = 0, is immediate. Let us assume that the claim holds for scenario   S i , for (real)   i   ∈   I , and consider scenario   S i +  , for any positive      such that      <   n  4   (1   −   c ′  c   ) .   Our goal is to show that the claim holds for scenario   S i +  8 . Consider scenario   S i +  . During the time interval [0 ,   i c   ), both agents perform the same actions as they do in the corresponding time interval in scenario   S i . Let  a   denote the location of agent   A   at time   i/c . Now, during the time period [   i c   ,   i +  c   ], agent   A   performs some movement all of which is done at distance at most      from  a   (during this movement it may write information at various locations it visits); then, at time   i +  c   , agent   A   terminates.  7   We can think of this scenario as if each agent executes another algorithm   B , in which it simulates precisely   i   units of distance of the original algorithm and then terminates.  8   Note that for some   i   ∈   I   and some      <   n  4   (1   −   c ′  c   ), we may have that   i   +    / ∈   I . Our proof will show that the claim for   S i +    holds also in such cases. However, since we wish to show that the claim holds for   S j   , where   j   ∈   I , we are not really interested in those cases, and are concerned only with the cases where   i   +      ∈   I   and   i   ∈   I .
Let us focus on agent   B   (in scenario   S i +  ) during the time period [   i c   , i ]. We claim that during this time period, agent   B   is always at distance at least      from  a . Indeed, as long as it is true that agent   B   is at distance at least      from   a , it performs the same actions as it does in scenario   S i   (because it is unaware of any action made by agent   A   in scenario   S i +  , during the time period [   i c   ,   i +  c   ]). Therefore, if at some time   t ′   ∈   [   i c   , i ], agent   B   is (in scenario   S i +  ) at distance less than      from   a   then the same is true also for scenario   S i . However, in scenario   S i , by the induction hypothesis, agent   B   was at time   i   at    ̄ a , the symmetric location of   a , that is, at distance   n/ 2 from   a . Thus, to get from a distance less than     from   a   to    ̄ a , agent   B   needs to travel a distance of   n/ 2   −    , which takes   n/ 2   −     time (see figure 1 for the argument up to this point). This is impossible since  i   −   i/c   6   nc ′  2 c   <   n  2   −   ,  where the first inequality follows from the definition of   I   and the second follows from the definition of    . It follows that during the time period from [   i c   , i ), agent  B   behaves (in scenario   S i +  ) the same as it does in the corresponding time period in scenario   S i . Therefore, according to the induction hypothesis, in scenario   S i +  , when completing   i   units of distance, agent   B   is at distance   n/ 2 from where agent  A   is after completing   i   units of distance (recall, at that point agent   A   is at   a ), and the cycle configuration (including the white boards) is completely symmetric. Now, since    < n/ 4, during the time period [ i, i   +    ], agent   B   is still at a distance more than      from   a   and remains unaware of any action made by agent   A , during the time period [   i c   ,   i +  c   ]. (Similarly, agent   A , during the time period [   i c   ,   i +  c   ], is unaware of any action made by agent   B   during this time period.) Hence, at each time   i ′   ∈   [ i, i   +    ], agent   B   takes the same action as agent   A   in the corresponding time   i ′ /c . This establishes the induction proof. To sum up, we have just shown that for any   i   ∈   I , the cycle configuration at the end of scenario   S i   is completely symmetric. Now assume by contradiction that the rendezvous time   t   is less than the claimed one, that is,   t <   n  2( c − 1)   . At time   t , both agents meet at some location  u . Since   t   ∈   I , the above claim holds for   S t . Hence, at time   t/c , agent   A   is at    ̄ u , the symmetric location of   u . Since rendezvous happened at time   t , this means that agent   A   traveled from    ̄ u   to   u   (i.e., a distance of   n/ 2) during the time period [   t c   , t ]. Therefore   t (1   −   1  c   ) c   >   n/ 2, contradicting the assumption that   t <   n  2( c − 1)   . This establishes that any algorithm requires   n  2( c − 1)   time. We now show the simpler part of the theorem, namely, that the rendezvous time of any algorithm in the white board model is at least   n c +1   . Let us represent the cycle as the reals modulo   n , that is, we view the cycle as the continuous collection of reals [0 , n ], where   n   coincides with 0. Assume that the starting point of agent   A   is 0. Consider the time period   T   = [0 ,   n c +1   −    ], for some small positive   . In this time period, agent   A   moves a total length of less than   nc c +1   . Let   r   (and   ` , correspondingly) be the furthest point from 0 on the cycle that   A   reached while going clockwise (or anti-clockwise, correspondingly), during that time period. Note that there is a gap of length larger than   n   −   nc c +1   =   n c +1   between   `   and   r .
This gap corresponds to an arc not visited by agent   A   during this time period. On the other hand, agent   B   walks a total distance of less than   n c +1   during the time period   T   . Hence, the adversary can locate agent   B   initially at some point in the gap between   r   and   ` , such that during the whole time period   T   , agent   B  remains in this gap. This establishes the   n c +1   time lower bound, and concludes the proof of the theorem.   u t  Fig. 1.   For   B   to be influenced by   A ’s last moves, it must be    -near to   A   between times  i   and   i c   but it must also be able to reach   a   at time   i   by the induction hypothesis.  3   An Upper Bound for the Pebble Model  In this section, we consider the pebble model. For this model, we identify the following algorithm which turns out to be extremely efficient, especially for small values of   c .  Algorithm   Pebble .   Each agent (1) leaves a pebble at its initial position and then starts walking in an arbitrary direction while counting the distance travelled. If (2) an agent reaches a location with a pebble for the first time and (3) the distance it walked is strictly less than   τ   :=   min { n/ 2 , n/c } , then (4) the agent turns around and walks continuously in the other direction. Note that Algorithm   Pebble   does not assume sense of direction, uses only one pebble and drops it only once: at the initial position of the agent. The algorithm assumes that agents know the values of   n   and   c . Note that the assumptions of the pebble model are weaker than the white board model. Hence, in view of Theorem 1, the following theorem establishes a tight bound for the case where   c   6   2, a (2   −   2  c   )-approximation for the case 2   < c   6   3, and a ( c   + 1) /c -approximation for the case   c >   3.  Theorem 2.   The rendezvous time of Algorithm   Pebble   is   max {   n  2( c − 1)   ,   n c   } .
Proof.   Consider Algorithm   Pebble . First note that if both agents happen to start walking in opposite directions (due to lack of sense of direction), then they walk until they meet. In this simple case, their relative speed is   c   + 1, hence rendezvous happens in time at most   n c +1   <   max {   n  2( c − 1)   ,   n c   } . For the remaining of the proof, we consider the case that both agents start walking at the same direction, which is without loss of generality, the clockwise direction. Let   d   be the initial clockwise distance from   A   to   B , and recall that   τ   =   min { n/ 2 , n/c } . Consider three cases. 1.   d   =   τ   (see Figure 2). Here, no agent turns around. In other words, they behave exactly as in   DR . If  d   =   n/ 2, Observation 1 implies that the rendezvous time is   n  2( c − 1)   . Otherwise,  c >   2 and   d   =   n/c . By Observation 1, the rendezvous is reached earlier, specifically, by time   d c − 1   =   n c ( c − 1)   .  Fig. 2.   If   d   =   τ   both agents won’t turn and rendezvous will take   d c − 1   <   n  2( c − 1)   time.  2.   d < τ   (see Figure 3). In this case, Agent   A   will reach   B ’s starting point   v B   , at time   d/c , before  B   reaches   A ’s starting point   v A . Moreover, agent   B   does not turn, since its initial distance to   A ’s starting point is at least   τ   . At time   d/c , agent   B   is at distance   d/c   clockwise from   v B   . By the algorithm, Agent   A   then turns and walks anti-clockwise. The anti-clockwise distance from   A   to   B   is then   n   −   d/c . Their relative speed is   c   + 1. Hence, they will rendezvous in an additional time of   n − d/c  1+ c   , since no agent may turn around after time   d/c . Hence, the total time for reaching rendezvous is at most  d/c   +   n   −   d/c  1 +   c   =   d   +   n  1 +   c .  This function is maximized when   d   =   τ   where it is   τ   + n  1+ c   . Now, if   c   6   2, we have   τ   =   n/ 2 and the rendezvous time is therefore   3 n  2(1+ c )   . Since   c   6   2, the later bound is at most   n  2( c − 1)   . On the other hand, if   c >   2, we have   τ   =   n/c  and the rendezvous time is   n/c .
Fig. 3.   If   d < τ   only   A   will turn and rendezvous will take   n + d c +1   time.  3.   d > τ   . In this case,   A   doesn’t turn when it hits   B ’s initial position. Consider the following sub-cases. (a) (see Figure 4) The agents meet before   B   reaches   A ’s initial position. In this case, the rendezvous time (as in   DR ) is   d/ ( c   −   1). On the other hand, the rendezvous time is at most   n   −   d   since   B   did not reach   A ’s initial position. So   d/ ( c   −   1)   6   n   −   d . A simple calculation now implies that the rendezvous time   d/ ( c   −   1) is at most   n/c .  Fig. 4.   If   d > τ   and rendezvous happens before   B   reaches   A ’s pebble, it will take   d c − 1  time.  (b) (Figure 5) Agent   B   reaches   A ’s initial position before rendezvous. In this case, Agent   B   walks for   d ′   =   n   −   d   time to first reach   A ’s initial position. We first claim that   d ′   < τ   . One case is that   c   6   2, and thus,  τ   =   n/ 2. Since   d > τ   , we have   d ′   < n/ 2 =   τ   . The other case is that   c >   2, so   τ   =   n/c . We claim that also in this case, we have   d ′   < τ   . Otherwise, we would have had   d ′   >   n/c , which would have meant that the faster agent   A   would have had, at least,   n/c   time before   B   reached the initial position of   A . So much time would have allowed it to cover the whole cycle. This contradicts the assumption that   B   reached   A ’s initial position before rendezvous. This establishes the fact that, regardless of the value of   c , we have   d ′   < τ   . This fact implies that when agent   B   reaches   A ’s
initial position, it turns around and both agents go towards each other. By the time   B   turns around,   A   has walked a distance of   cd ′ . Hence, at that point in time, they are   n   −   cd ′   apart. This implies to the following rendezvous time:  d ′   +   n   −   cd ′  1 +   c   =   2 n   −   d  1 +   c .  Now recall that we are in the case that agent   B   reaches   A ’s initial position before they rendezvous. This implies that   n − d < n/c . Hence, the running time is at most   2 n   −   d  1 +   c   < n   +   n c  1 +   c   =   n c .  Fig. 5.   If   d > τ   and   B   reaches   A ’s pebble, then it will always turn and rendezvous will take   2 n − d  1+ c   time.  u t  4   Rendezvous without Communication  In this section, we consider the case that agents cannot use marks (e.g., pebbles) to mark their location. More generally, the agents cannot communicate in any way (before rendezvous). In Section 4.1 we by show a lower bound of   cn c 2   − 1   for the rendezvous time of any algorithm, even assuming sense of direction. Then, in Section 4.2 we show that when assuming a sense of direction this latter bound is tight. Finally, we conclude by showing several upper bounds for the case where there is no sense of direction.  4.1   A Lower Bound for the Case Without Communication Theorem 3.   Consider the case that agents cannot communicate at all. The rendezvous time of any algorithm is, at least,   cn c 2 − 1   , even assuming sense of direction.
Proof.   Given an algorithm, let   ˆ t   denote the rendezvous time of the algorithm, that is, the maximum time (over all initial placements and all cycles of length  n ) for the agents (executing this algorithm) to reach rendezvous. Recall, in this part of the theorem, we assume that agents have sense of direction. Without loss of generality, we assume that the direction an agent starts walking is clockwise. Consider, first, two identical cycles   C A   and   C B   of length   n   each. Let us mark a location   v   ∈   C A   and a location   u   ∈   C B   . Let us examine the (imaginary) scenario in which agent   A   (respectively,   B ) is placed on the cycle   C A   (respectively,   C B   ) alone, that is, the other agent is not on the cycle. Furthermore, assume that agent   A   is placed at   v   and agent   B   is placed at   u . In this imaginary scenario, agents   A   and   B   start executing the protocol at the same time, separately, on each of the corresponding cycles. Viewing   u   as homologous to   v , a homologous location   h ( x )   ∈   C B   can be defined for each location in   x   ∈   C A   in a natural way (in particular,   h ( v ) =   u ). For each time   t   ∈   [0 ,   ˆ t ], let   d ( t ) denote the clockwise distance between the location   b t   ∈   C B   of the slower agent   B   at time   t   and the homologous location  h ( a t )   ∈   C B   of the location   a t   ∈   C A   of the faster agent   A   at time   t . Note that  d ( t ) is a real value in [0 , n ). Initially, we assume that all reals in [0 , n ) are colored  white . As time passes, we   color   the corresponding distances by black, that is, at every time   t , we color the distance   d ( t )   ∈   [0 , n ) by black. Note that the size of the set of black distances is monotonously non-decreasing with time. We first claim that, by time   ˆ t , the whole range [0 , n ) is colored black. To prove by contradiction, assume that there is a real   d   ∈   [0 , n ) that remains white. Now, consider the execution on a single cycle of length   n , where agent   A   is initially placed at anti-clockwise distance   d   from agent   B . In such a case, rendezvous is not reached by time   ˆ t , contrary to the assumption that it is. This implies that the time   T   it takes until all reals in [0 , n ) are colored black in the imaginary scenario, is a lower bound on the rendezvous time, that is,   T   6   ˆ t . It is left to analyze the time   T   . With time, the change in the distance   d ( t ) has to follow two rules:  – R1.   After one time unit, the distance can change by at most 1 +   c   (the sum of the agents’ speeds).  – R2.   At time   x , the distance, in absolute value is, at most,   x ( c   −   1). To see why Rule R2 holds, recall that the programs of the agents are identical. Hence, if agent   A   is at some point   a   ∈   C A , after completing   x   units of distance, then agent   B   is at point   b   =   h ( a ) when completing its own   x   units of distance. This happens for agent   B   at time   x   and for agent   A   at time   x/c . Since   A ’s speed is   c , the maximum it can get away from point   a   during the time period from   x/c  until   x   is   c ( x   −   x/c ) =   x ( c   −   1). Consider the path   P   :=   d ( t ) covering the range [0 , n ) in   T   time. First, note that this path   P   may go several times through the zero point (i.e., when   d ( t ) = 0). At a given time   s , we say that the path is   on the right   side, if the last time it left the zero point before time   s   was while going towards 1. Similarly, the path is  on the left , if the last time it left the zero point before time   s   was while going towards   n   −   1. Let   x   denote the largest point on the range [0 , n ) reached by the
path while the path was on the right side. Let   y   =   n   −   x . By time   T   , path   P  had to go left to distance   y   from the zero point. Assume, w.l.o.g. that   x < y . (In particular,   x   may be zero.) The fastest way to color these two points (and all the rest of the points, since those lie between them), would be to go from zero to the right till reaching   x , then return to zero and go to distance   y   on the left. Hence,   T   will be at least:   T   >   x c − 1   +   n c +1   .   Indeed, Rule R2, applied to the time of reaching distance   x , implies the first term above. The second term uses Rule R1 to capture the time that starts with the distance reaching   x , proceeds with the distance reaching the zero point and ends when the distance reaches   y   when going left. Since   c >   1, we obtain  x   6  (  T   −   n c   + 1  )  ( c   −   1) .   (1) On the other hand, applying Rule R2 to the final destination   y , we have   T   ( c − 1)   >  y   =   n   −   x.   This implies that:  x   >   n   −   T   ( c   −   1) .   (2) Combining Equations 1 and 2, we get   T   >   cn c 2   − 1   , establishing the theorem.   u t  4.2   Upper Bounds for the Case Without Communication  To establish the upper bounds, we consider a revised version of the   DR   algorithm, called   Turn ( k ), which consists of two stages.  Algorithm   Turn ( k ) .   At the first stage, the agent walks over its own clockwise direction for   k   units of distance. Subsequently (if rendezvous hasn’t occurred yet), the agent executes the second stage of the algorithm: it turns around and goes in the other direction until rendezvous.  Assuming Sense of Direction.   We first consider the case that agents have a sense of direction. Recall that for this case Theorem 3 establishes a lower bound of   cn c 2 − 1   . We now show this this bound is tight.  Theorem 4.   Assuming sense of direction, the rendezvous time of algorithm  Turn (   cn c 2   − 1   )   is   cn c 2   − 1   . Proof.   Note that algorithm   DR   does not assume sense of direction, and its com- plexity is the one required by the third part of the theorem for the case   c >   3. Recall that   Turn ( k ) consists of two stages. At the first stage, the agent walks over its own clockwise direction for   k   units of distance. Subsequently (if rendezvous hasn’t occurred yet), the agent executes the second stage of the algorithm: it turns around and goes in the other direction until rendezvous. Consider now Algorithm   Turn ( k ), with parameter   k   =   cn c 2   − 1   . Since we assume sense of direction, both agents walk initially in the same direction (clockwise). Assume by contradiction that rendezvous hasn’t occurred by time   k . By that
time, agent   B   travelled   k   units of distance. Agent   A   has travelled those   k   units of distance by time   k/c . At that time, agent   A   turns. (However, agent   B   will turn only at time   k ). Hence, between those two turning times, there is a time duration  k (1   −   1  c   ) where the two agents walk towards each other. Hence, at each time unit they shorten the distance between them by 1 +   c . Let   d ′   denote the maximum distance between the agents at time   k/c . It follows that   d ′   > k (1   −   1  c   )(   1 +   c ) =   n . A contradiction.   u t  Operating Without a Sense of Direction. Theorem 5.   Without assuming sense of direction, the following rendezvous time can be achieved: 1.   cn c 2 − 1   , for   c   6   2   (achieved by algorithm   Turn (   cn c 2 − 1   ) ), 2.   2 n c +1   , for   2   < c   6   3   (achieved by algorithm   Turn (   cn c +1   ) ), 3.   n c − 1   , for   c >   3   (achieved by algorithm   DR ). Proof.   Let us first consider the case   c   6   2. Here we apply the same algorithm above, namely Algorithm   Turn ( k ), with parameter   k   =   cn c 2 − 1   . As proved before, if the two agents happen to start at the same direction then rendezvous occurs by time   cn c 2 − 1   . Hence, let us consider the case that both agents walk initially at opposite directions. Assume by contradiction, that rendezvous hasn’t occurred by time   k/c . In this case, by time   k/c   the faster agent   A   walked   k   units of distance toward   B , and the slower agent   B   walked   k/c   units of distance towards   A . Hence, the initial distance between them must be greater than   k (1+1 /c ) =   n/ ( c − 1)   > n , a contradiction. This proves the first item of the Theorem. Note that Algorithm   DR   establishes the third item of the Theorem. Hence, it is left to prove the second item, namely, the case 2   < c   6   3. For this case, we apply Algorithm   Turn ( k ), with parameter   k   =   cn c +1   . First note, if the two agents happen to start walking towards each other they continue to do that until time   k/c   =   n c +1   , hence they would meet by this time. Therefor, we may assume that initially, both agents start in the same direction. In this case, if rendezvous hasn’t occurred by time   k/c , then at this time agent   A   turns around, and both agents walk towards each other for at least   k (1   −   1 /c ) more time (the time when agent   B   is supposed to turn). Since   c >   2, we have   k (1   −   1 /c )   > k/c , and hence, from the time agent   A   turns, both agents walk towards each other for at least  k c   =   n c +1   time, which means they must meet by this time. Altogether, the time to rendezvous is   2 k c   =   2 n c +1   , as desired.   u t  5   Discussion and Future Work  We show how some form of asynchrony could be useful for solving a symmetry breaking problem efficiently. Our study could be considered as a first attempt to harness the (unknown) heterogeneity between individuals in a cooperative population towards more efficient functionality.
There are many natural ways of further exploring this idea in future work. First, we have studied the exploitation of asynchrony for a specific kind of problems. It seems that it can be useful for other symmetry breaking problems as well. Another generalization: the “level” of asynchrony considered in this paper is very limited: the ratio   c   between the speeds of the agents is the same throughout the execution, and is known to the agents. Exploiting a higher level of asynchrony should also be studied, for example, the case that the speed difference is stochastic and changes through time. Our main interest was the exploitation of asymmetry, rather than the specific problem of rendezvous. Still, even for the rendezvous problem, this current study leaves many open questions. First, even for the limited case we study, not all our bounds are completely tight, and it would be interesting to close the remaining gaps between our lower and upper bounds (these gaps hold for some cases when  c >   2). In addition, it would be interesting to study further the uniform case [ 21 ], in which   n   and   c   are not known to agents. Another direction is to generalize the study to multiple agents (more than two, see, e.g., [   15 ,   18   ]) and to other topological structures. This would also allow one to study interactions between various means of breaking symmetry (such as different speeds together with different locations on a graph).  6   Acknowledgement  O.F., incumbent of the Shlomo and Michla Tomarin Career Development Chair, was supported by the Clore Foundation, the Israel Science Foundation (FIRST grant no. 1694/10) and the Minerva Foundation. A.K. was supported by the ANR project DISPLEXITY, and by the INRIA project GANG. S.K. was supported in part by the ISF and by the Technion TASP center. This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 648032).  References  1.   Steve Alpern. Rendezvous Search: A Personal Perspective. LSE Research Report, CDAM-2000-05, London School of Economics, 2000. 2.   Steve Alpern and Shmuel Gal. The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, 2003. 3.   Dana Angluin. Local and global properties in networks of processors. ACM STOC ’80: 82–93, 1980. 4.   Hagit Attiya, Alla Gorbach, and Shlomo Moran. Computing in Totally Anonymous Asynchronous Shared Memory Systems. Information and Computation, Volume 173, Issue 2, 15 March 2002, Pages 162–183. 5.   Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching in the plane.   Inform. and Comput. , 106(2):234–252, 1993. 6.   Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, Volume 37, Issue 3, July 1990, Pages 524 - 548.
7.   Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, and Arnaud Labourel. Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids. DISC 2010: 297-311. 8.   Lali Barri ́ ere, Paola Flocchini, Pierre Fraigniaud, and Nicola Santoro. Rendezvous and Election of Mobile Agents: Impact of Sense of Direction. Theory Comput. Syst. 40(2): 143-162 (2007). 9.   Vic Baston and Shmuel Gal. Rendezvous search when marks are left at the starting points. Naval Research Logistics, 48(8):722–731, 2001. 10.   Michael A. Bender, Antonio Fernandez, Dana Ron, Amit Sahai, and Salil Vadhan. The power of a pebble: Exploring and mapping directed graphs. In Proc. 30th ACM Symp. on Theory of Computing (STOC), pages 269–287, 1998. 11.   Manuel Blum and Dexter Kozen. On the power of the compass (or, why mazes are easier to search than graphs). 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), October 16-October 18. 12.   Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis, and Danny Krizanc. The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring. SOFSEM 2008: 234-246. 13.   Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, and Andrzej Pelc. Asynchronous deterministic rendezvous in bounded terrains. Theor. Comput. Sci. 412(50): 6926– 6937 (2011). 14.   Edsger W. Dijkstra: Self-stabilizing systems in spite of distributed control. Commu- nications of the ACM, Volume 17 Issue 11, Nov. 1974 Pages 643 - 644. 15.   Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Multiple Agents RendezVous in a Ring in Spite of a Black Hole. OPODIS 2003: 34–46. 16.   Paola Flocchini, Amiya Nayak, and Arno Schulz. Cleaning an Arbitrary Regu- lar Network with Mobile Agents. Distributed Computing and Internet Technol- ogy, Lecture Notes in Computer Science, 2005, Volume 3816/2005, 132-142, DOI: 10.1007/11604655 17. 17.   Paola Flocchini, David Ilcinkas, and Nicola Santoro. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles. Algorithmica 62(3-4): 1006-1033 (2012). 18.   Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro and Cindy Sawchuk. Multiple Mobile Agent Rendezvous in a Ring. LATIN 2004: 599–608. 19.   Alon Itai and Michael Rodeh. Symmetry Breaking in Distributive Networks. FOCS 1981: 150-158. 20.   Ephraim Korach, Shay Kutten, and Shlomo Moran. A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms. ACM PODC 1985: 163-174. 21.   Amos Korman, Jean-S ́ ebastien Sereni, and Laurent Viennot. Toward More Localized Local Algorithms: Removing Assumptions Concerning Global Knowledge. In ACM PODC 2011: 49–58. 22.   Evangelos Kranakis, Danny Krizanc, and Euripides Markou. The Mobile Agent Rendezvous Problem in the Ring. Morgan & Claypool Publishers 2010. 23.   Evangelos Kranakis, Danny Krizanc, and Sergio Rajsbaum. Mobile Agent Ren- dezvous: A Survey. Structural Information and Communication Complexity Lecture Notes in Computer Science, 2006, Volume 4056/2006, 1-9, DOI: 10.1007/11780823 1. 24.   Evangelos Kranakis, Nicola Santoro, and Cindy Sawchuk. Mobile Agent Rendezvous in a Ring. ICDCS’03, pp. 592 - 599. 25.   Ichiro Suzuki and Masafumi Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM J. Computing. Vol. 28, No. 4, pp. 1347-1363, 1999.
26.   Masafumi Yamashita and Tiko Kameda. Computing on an Anonymous Network. ACM PODC 1988: 117-130. 27.   Xiangdong Yu and Moti Yung. Agent Rendezvous: A Dynamic Symmetry-Breaking Problem. ICALP 1996: 610-621.