PaperlayerView exact revision on arXiv

Source-linked AI summary

Rendezvous under Variable Disorientation:The Algorithmic Power of Fixed Unit Distance

Toshimitsu Masuzawa, Yuichi Sudo, Koichi Wada

arXiv:2610.09713v1cs.DC

TL;DR

The paper examines Rendezvous for two robots under changing local coordinate systems, limited light visibility, and varied scheduler constraints. It uses periodic distance classes under a fixed local unit to organize metric information into cyclic phases. The resulting algorithms and impossibility bounds characterize how these assumptions affect solvability and color complexity.

  • Problem

    The paper addresses the two-color barrier for L-algorithms and the broader Rendezvous boundaries under VD and VD+FUD.

    Source: §3.1 · p. 6, §5.4 · p. 10

  • Method

    It introduces periodic distance classes whose labels shift cyclically when physical distance is multiplied or divided by a fixed base.

    Source: §1 · p. 2, §2.4.3 · p. 6

  • Results

    2-color self-stabilizing non-L algorithms work for both FSTA and FCOM under Rsynch and R-Rsynch with Non-Rigid movement; Rigid settings also yield 3-, 4-, and 6-color algorithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A fixed local metric can serve as persistent cyclic memory, while the results distinguish Rendezvous solvability and color complexity across geometric and scheduler assumptions.

    Source: §7 · p. 14

    Open questions include closing the 3–6 color gap for non-quasi-self-stabilizing FCOM under full Rigid Asynch and extending Rigid constructions to Non-Rigid movement.

    Source: §7 · p. 15

Abstract

from arXiv · show

We study deterministic Rendezvous of two robots with lights under weak geometric and synchronization assumptions. Our focus is on Variable Disorientation (VD), where each robot may arbitrarily rotate, reflect, and rescale its local coordinate system at every \Look, and on VD+Fixed-Unit-Distance (FUD), where each robot's local unit distance remains fixed. We consider the one-sided visibility models FSTA and FCOM, and schedulers ranging from the energy-restricted RSYNCH and R-RSYNCH to fully asynchronous executions. Under VD, we prove color-independent impossibility results for FSTA under SSYNCH and for FCOM under ASYNCH, and establish sharp two-color boundaries under RSYNCH and R-RSYNCH. Under VD+FUD, we introduce periodic distance classes, which turn multiplicative changes of the physical distance into predictable cyclic phase shifts. This technique yields a two-color self-stabilizing non-$L$-Rendezvous algorithm for both FSTA and FCOM under RSYNCH and R-RSYNCH even with Non-Rigid movement. Under Rigid movement, periodic distance classes further yield an optimal three-color non-quasi-self-stabilizing algorithm for FSTA under SSYNCH, a four-color FSTA algorithm under $M$-atomic ASYNCH, and a four-color FCOM algorithm under CM-atomic ASYNCH. By guarding the latter phase mechanism with two additional colors and replacing its initial swap by passive initialization, we obtain a six-color FCOM algorithm under full ASYNCH, improving the previous twelve-color upper bound by a factor of two. These results show that a fixed local metric can serve as persistent cyclic memory, and clarify how metric stability, one-sided visibility, and scheduler atomicity jointly determine Rendezvous solvability and color complexity.

1 Introduction

The paper contrasts variable disorientation (VD) with VD plus a fixed local unit distance (FUD), across one-sided visibility models and schedulers. It establishes impossibility and color-complexity boundaries, then uses periodic distance classes to obtain new Rendezvous algorithms under VD+FUD.

1 Introduction

  • Under VD, Rendezvous is impossible regardless of color count for FSTA under Ssynch and FCOM under Asynch, with additional two-color boundaries under Rsynch and R-Rsynch.The paper also establishes 4-color algorithms for FSTA under M-atomic Asynch and FCOM under CM-atomic Asynch under VD+FUD and Rigid movement.Source: §1 · p. 2
  • Periodic (b, m)-distance classes label logarithmic distance bands cyclically, so multiplying or dividing distance by b shifts the class by one modulo m.Under VD+FUD, the fixed local unit supplies persistent cyclic metric information.Source: §1 · p. 2
  • 2 colors suffice for self-stabilizing non-L-Rendezvous under both FSTA and FCOM with Rsynch and R-Rsynch, even with Non-Rigid movement.With Rigid movement, the results include an optimal 3-color FSTA algorithm under Ssynch and a 6-color FCOM algorithm under full Asynch, improving the previous 12-color upper bound to six.Source: §1 · p. 2
  • Tables 1 and 2 situate the paper’s results within known and new color-complexity bounds for VD and VD+FUD, respectively.Table 2 includes the six-color FCOM-Asynch-NS upper bound under Rigid movement, improving the previous twelve-color upper bound.Source: Table 1 · p. 3, Table 2 · p. 3

2 Robot Model

The model specifies two deterministic robots with lights, their geometric assumptions and visibility, and the schedulers governing their LCM cycles. It also defines stabilization classes and the periodic distance-class notation used to describe algorithms.

2.1 Robots and Configurations

  • Robots are anonymous and execute deterministic Look–Compute–Move cycles; under VD, local frames can change arbitrarily at every Look, while FUD fixes each robot’s unit distance.FSTA exposes a robot’s own light and FCOM exposes the other robot’s light; Non-Rigid movement guarantees a minimum advance when the destination is sufficiently far away.Source: §2.1 · pp. 3–4

2.2 Schedulers

  • Executions are adversarial and fair; Rsynch and R-Rsynch combine finite prefixes of one activation pattern with infinite suffixes of the other, while Ssynch permits any nonempty activated subset.Asynchronous variants differ by atomicity: CM-atomic bars another Look during Compute–Move, M-atomic bars Looks during another robot’s Move, and full Asynch has no such constraint.Source: §2.2 · pp. 4–5

2.3 Rendezvous and Stabilization

  • Rendezvous requires the robots to meet permanently; self-stabilizing, quasi-self-stabilizing, and non-quasi-self-stabilizing algorithms differ by the allowed initial color configurations.An L-algorithm chooses movement and light updates from the observed color alone, independently of distance.Source: §2.3 · p. 5

2.4.1 Algorithmic graphs and standard destinations

  • A one-sided-visibility algorithm is represented by a directed graph whose color transitions are labeled with snapshot conditions, light updates, and destinations.The standard destinations are Stay, Midpoint, and Other, abbreviated S, H, and O; in FCOM the graph describes reactions to the other robot’s color.Source: §2.4.1 · pp. 5–6

2.4.2 Physical and locally measured distances

  • Under FUD, each robot’s local unit corresponds to a fixed physical length, although the two robots’ unit lengths need not agree.The locally measured distance is the physical separation divided by that robot’s unit length.Source: §2.4.2 · p. 6

2.4.3 Periodic distance classes

  • Periodic distance classes partition distances into logarithmic bands labeled modulo m; multiplying or dividing by b shifts the class cyclically.Under FUD, multiplying distance by b^h shifts the class by h modulo m.Source: §2.4.3 · p. 6
  • When robots at the same distance observe phase colors, their phase offsets are complementary modulo 3, yielding the listed offset pairs.The possible pairs are (0, 0), (1, 2), and (2, 1).Source: §2.4.3 · p. 6

3 Impossibility Results for Rendezvous

Under VD, deterministic Rendezvous is impossible in specified scheduler and visibility settings even without an L-algorithm restriction. The proof normalizes each nonmeeting view, allowing known color-based impossibility arguments to apply.

3.1 Impossibility under VD

  • VD lets the adversary normalize every nonmeeting snapshot so each robot sees the peer at (0, 1), making its deterministic behavior depend only on the observed color.This normalization lifts the corresponding L-algorithm impossibility argument to arbitrary deterministic algorithms.Source: §3.1 · pp. 6–7
  • Under VD, no deterministic non-quasi-self-stabilizing Rendezvous algorithm exists for FSTA under Ssynch or FCOM under Asynch, regardless of color count.This impossibility applies to arbitrary deterministic algorithms, not only L-algorithms.Source: §3.1 · pp. 6–7
  • For FSTA under Ssynch in VD+FUD, quasi-self-stabilization is impossible with any number of colors, while non-quasi-self-stabilizing Rendezvous is solvable with exactly three colors.The positive result must rely on a designated initial color.Source: §3.1 · p. 7

4 Two-Color Impossibility under Rsynch and R-Rsynch

With only two colors under VD, forced transitions create mixed-color executions that can avoid finite-time Rendezvous. The lower bounds distinguish Rsynch from R-Rsynch and depend on the stabilization requirement and movement model.

4 Two-Color Impossibility under Rsynch and R-Rsynch

  • The lower-bound argument reduces robot behavior at distinct positions to the observed color, classifying colors by whether they prescribe a midpoint or a move to the peer.Under VD, normalization makes the robot’s deterministic behavior depend only on the observed color.Source: §4 · p. 7
  • Under VD and Rsynch, no deterministic 2-color self-stabilizing Rendezvous algorithm exists in either FSTA or FCOM.The forced two-color transitions make a mixed-color Fsynch execution halve the distance every round without meeting in finite time.Source: §4 · pp. 7–8
  • Under VD and R-Rsynch, no deterministic 2-color quasi-self-stabilizing algorithm exists in either visibility model, and none is non-quasi-self-stabilizing with Non-Rigid movement.An RR prefix can create a mixed-color configuration whose Fsynch tail preserves positive distance indefinitely.Source: §4 · p. 8

5 Algorithms in the One-Sided Visibility Model under Rsynch and R-Rsynch

Under VD, the section establishes color-complexity boundaries for energy-restricted schedulers; under VD+FUD, periodic distance classes overcome the two-color L-algorithm barrier. The resulting algorithms cover both visibility models and, in some settings, Non-Rigid movement.

5.1 Reduction Principles

  • The reduction principles establish correctness under Rsynch and R-Rsynch from correctness under Fsynch and RR, and reduce Non-Rigid analysis to the effective Rigid regime where distance is at most δ.The latter reduction applies to the algorithms considered in this section.Source: §5.1 · p. 8

5.2 A Two-Color Quasi-Self-Stabilizing L-Algorithm

  • Under Rsynch, QS-L-2-color provides two-color quasi-self-stabilizing L-Rendezvous for both FSTA and FCOM in the Non-Rigid setting.With R-Rsynch, it also gives a two-color non-quasi-self-stabilizing L-algorithm under Rigid movement when B is the designated initial color.Source: §5.2 · pp. 8–9

5.3 An Optimal Three-Color Self-Stabilizing L-Algorithm for FSTA

  • Three colors are necessary and sufficient for self-stabilizing FSTA Rendezvous under VD and Rsynch.The three-color algorithm also works under R-Rsynch in the Non-Rigid setting.Source: §5.3 · p. 9

5.4 FUD Breaks the Two-Color L-Barrier

  • Two colors suffice for self-stabilizing non-L-Rendezvous under VD+FUD for both FSTA and FCOM under Rsynch and R-Rsynch, even with Non-Rigid movement.Periodic distance classes prevent the mixed-color cycle from repeating indefinitely.Source: §5.4 · p. 10

6 Non-Quasi-Self-Stabilizing Rendezvous under VD+FUD and Rigid Movement

Under VD+FUD and Rigid movement, periodic distance classes support non-quasi-self-stabilizing Rendezvous algorithms across synchronous and asynchronous scheduler variants. The section gives three-, four-, and six-color constructions, with the full-Asynch FCOM algorithm using guards and passive initialization.

6.1 A Three-Color Rendezvous Algorithm for FSTA under Ssynch

  • Three colors are necessary and sufficient for FSTA Rendezvous under Ssynch from designated initial color A.The construction uses periodic distance classes to record phase information across midpoint moves.Source: §6.1 · pp. 11–12

6.2 Four-Color Phase Algorithms under Atomic Asynchrony

  • Four-color algorithms solve FSTA Rendezvous under M-atomic Asynch and FCOM Rendezvous under CM-atomic Asynch from designated initial color I.The algorithms use the same three-phase mechanism, with reversed nonzero action mappings for FSTA and FCOM.Source: §6.2 · pp. 12–13

6.3 Extending the Four-Color Algorithm to Full Asynchrony

  • Six colors solve FCOM Rendezvous under full Asynch from designated initial color I, using movement guards and passive initialization.The moving guard prevents fresh peer Looks from generating new non-null moves while a move is in progress.Source: §6.3 · pp. 13–14

7 Concluding Remarks

The conclusion identifies a fixed local unit as the geometric resource behind the VD+FUD constructions, while listing unresolved cases. The appendix impossibility result shows that VD alone rules out deterministic non-quasi-self-stabilizing Rendezvous in specified visibility and scheduler settings.

7 Concluding Remarks

  • Periodic distance classes make each robot’s consistent local unit a source of cyclic metric information, without requiring shared units or stable orientations.The conclusion says extending the Rigid constructions to Non-Rigid movement and larger robot populations remains open.Source: §7 · pp. 14–15

A Unified One-Sided Visibility Notation

  • The unified one-sided visibility notation defines a robot’s observed color according to the model and lets the same algorithmic graph be read uniformly.In FSTA the robot observes its own color; in FCOM it observes the other robot’s color.Source: A Unified One-Sided Visibility Notation · p. 18

B Color-Independent Impossibility under VD

  • Under VD, no deterministic non-quasi-self-stabilizing Rendezvous algorithm exists for FSTA under Ssynch or FCOM under Asynch, regardless of the number of colors.The adversary can repeatedly preserve a non-gathered same-color configuration, yielding an infinite fair execution without Rendezvous.Source: B Color-Independent Impossibility… · pp. 18–19

C Two-Color Impossibility under Rsynch

Under VD and Rsynch, deterministic two-color self-stabilizing Rendezvous is impossible in both FSTA and FCOM. The obstruction is that the required same-color behavior forces actions that leave a mixed-color execution unable to rendezvous.

D Two-Color Impossibility under R-Rsynch

Under VD and R-Rsynch, two colors cannot achieve quasi-self-stabilizing Rendezvous in either FSTA or FCOM; with Non-Rigid movement, they cannot achieve non-quasi-self-stabilizing Rendezvous either.

E Scheduler Composition and Non-Rigid Distance Reduction

The section gives conditions for composing scheduler guarantees and reducing Non-Rigid analysis to small distances, then specifies the two-color algorithm used in later proofs.

E Scheduler Composition and Non-Rigid Distance Reduction

F Pseudocode for QS-L-2-color

G Correctness of QS-L-2-color under Rsynch

QS-L-2-color provides two-color quasi-self-stabilizing L-Rendezvous for both one-sided visibility models under Rsynch with Non-Rigid movement. The section also gives the transition rules for SS-L-3-color.

G Correctness of QS-L-2-color under Rsynch

H Pseudocode for SS-L-3-color

I Detailed Analysis of SS-L-3-color under Rsynch and R-Rsynch

SS-L-3-color achieves self-stabilizing L-Rendezvous with three colors for one-sided-visibility robots under Rsynch and R-Rsynch with Non-Rigid movement. Its FCOM interpretation also works under these schedulers, and the adjacent SS-non-L-2-color pseudocode uses distance-class-dependent moves.

I Detailed Analysis of SS-L-3-color under Rsynch and R-Rsynch

  • Under Fsynch, every initial observed-color configuration reaches Rendezvous within two rounds.Some configurations rendezvous in one round; the remaining listed cases do so in at most two.Source: I Detailed Analysis of SS-L-3-color… · p. 25
  • Under FSTA, observed colors progress toward C, whose move is to the peer; under FCOM, observing C prompts that direct move, yielding Rendezvous within three activations.For FCOM, observing B leads to a midpoint move and then the other robot observes C; observing A takes at most three activations.Source: I Detailed Analysis of SS-L-3-color… · p. 25
  • With three colors, SS-L-3-color solves self-stabilizing L-Rendezvous for FSTA under Rsynch and R-Rsynch with Non-Rigid movement; its supplementary FCOM interpretation also solves self-stabilizing Rendezvous.The FCOM result is stated for both schedulers and the Non-Rigid setting.Source: I Detailed Analysis of SS-L-3-color… · pp. 25–26

J Pseudocode for SS-non-L-2-color

  • The adjacent SS-non-L-2-color pseudocode uses qx=0/1 to choose B/A while moving to the midpoint, and sends observed B to A while moving to the peer.The pseudocode also includes a keep-and-stay branch.Source: J Pseudocode for SS-non-L-2-color · p. 26

K Correctness of SS-non-L-2-color under Rsynch and R-Rsynch

SS-non-L-2-color gives two-color self-stabilizing non-L-Rendezvous under VD+FUD in the stated one-sided-visibility scheduler settings, including Non-Rigid movement. The section also establishes an optimal three-color FSTA algorithm under Rigid movement from a designated initial color.

K Correctness of SS-non-L-2-color under Rsynch and R-Rsynch

  • Its periodic (4, 2)-distance class makes the EQI/OQI phase change predictable: after two midpoint moves, distance D/4 shifts EQI to OQI.That phase shift lets the proof return to an EQI case that triggers a move toward the peer.Source: K Correctness of SS-non-L-2-color… · pp. 26–27
  • Under VD+FUD, SS-non-L-2-color solves self-stabilizing non-L-Rendezvous with two colors under Fsynch and RR in the one-sided-visibility Non-Rigid setting.The section analyzes both FSTA and FCOM interpretations.Source: K Correctness of SS-non-L-2-color… · pp. 26–27
  • For FSTA, EQI leads to changing to B and moving to the midpoint before moving to the stationary peer; for FCOM, the peer observes B and moves directly to the active robot.In OQI cases, the robots use midpoint moves and distance-class-dependent color updates until a direct-to-peer move achieves Rendezvous.Source: K Correctness of SS-non-L-2-color… · p. 27

L Pseudocode for NS-FSTA-3-color

  • NS-FSTA-3-color uses color A to select a distance-class-indexed Bi and move to the peer, while a Bi state returns to A and moves to the midpoint.The pseudocode's color and movement branches define the algorithm analyzed in the following subsection.Source: L Pseudocode for NS-FSTA-3-color · p. 28

M Correctness and Optimality of NS-FSTA-3-color

  • With Rigid movement under VD+FUD and Ssynch, NS-FSTA-3-color solves Rendezvous from designated initial color A, and three colors are necessary and sufficient.The two-color impossibility supplies the matching lower bound.Source: M Correctness and Optimality of… · pp. 28–29
  • When both robots initially have color A and activate together, they exchange positions; if both next move to the midpoint, Rigid movement brings them together.The proof also treats executions in which only one robot is activated before the other's next non-null move.Source: M Correctness and Optimality of… · p. 28

N Applicability and Limitations of the FCOM Interpretation of NS-FSTA-3-color

This section examines FCOM algorithm interpretations and their assumptions, including the three-color graph interpretation’s common-unit-distance and CM-atomicity requirements, four-color periodic-phase algorithms under VD+FUD with rigid movement, and differences in how FSTA and FCOM colors map measurements. It also gives NS-FCOM-6-color pseudocode for asynchronous FCOM, with actions based on distance and observed colors.

N Applicability and Limitations of the FCOM Interpretation of NS-FSTA-3-color

  • Without a shared unit distance, the three-color graph’s direct FCOM interpretation can fail even under CM-atomic Asynch and rigid movement; common units restore correctness under CM-atomicity, but not M-atomicity.In FCOM, a displayed phase reports the other robot’s measured distance class, so differing units can make the phase indices disagree at the same physical distance.Source: N Applicability and Limitations of the… · p. 29

O Pseudocode for NS-FSTA-4-color

  • NS-FSTA-4-color reads its own light and uses modulo-3 offsets: offset 0 advances the phase and moves to the midpoint, offset 1 stays, and offset 2 moves to the peer.The pseudocode also keeps the robot stationary at zero distance.Source: O Pseudocode for NS-FSTA-4-color · p. 30, Asynch · p. 31

P Pseudocode for NS-FCOM-4-color

Asynch

  • Under VD+FUD and rigid movement, NS-FSTA-4-color solves Rendezvous for two FSTA robots under M-atomic Asynch from designated initial color I, with every fair execution reaching Rendezvous in finite time.Source: Asynch · pp. 32–33
  • Under VD+FUD with rigid movement, NS-FCOM-4-color achieves finite-time Rendezvous from the designated initial color under CM-atomic Asynch.It reverses the FSTA algorithm’s nonzero-offset actions: offset 1 moves to the peer, while offset 2 stays.Source: Asynch · pp. 33–34

R Pseudocode for NS-FCOM-6-color

  • At zero distance or when observing M, the robot keeps its state and stays; when observing N, it changes to M and moves to Other.Source: R Pseudocode for NS-FCOM-6-color · p. 35
  • For nonzero distance, the algorithm compares color indices modulo 3: matching indices trigger a guarded midpoint move, a difference of 1 a guarded move to Other, and a difference of 2 makes the robot an anchor.The corresponding colors are M for the guarded moves and N for the anchor state.Source: R Pseudocode for NS-FCOM-6-color · p. 35

S Correctness of NS-FCOM-6-color under Full Asynch

The proof establishes full-Asynch correctness by showing that the guard eventually initiates a non-null move, constrains compatible action pairs, and reaches Rendezvous in each case.

S Correctness of NS-FCOM-6-color under Full Asynch

  • A first M color appears after finitely many activations, and while M is visible fresh snapshots of the peer generate only null moves.Because each robot executes LCM cycles sequentially, at most one cycle based on a pre-M Look can remain incomplete.Source: S Correctness of NS-FCOM-6-color under… · pp. 35–36
  • Before the first M, the distance is unchanged, so any incomplete pre-M action is compatible with the first guarded move and the possible pairs are O/S, H/H, or H/S.The I and offset-2 phase rules are null before the first M.Source: S Correctness of NS-FCOM-6-color under… · pp. 35–36
  • In the H/S case, the midpoint robot stays there while displaying N until the peer reaches it, and the zero-distance rule keeps both robots together afterward.Rigidity ensures the peer reaches the midpoint robot.Source: S Correctness of NS-FCOM-6-color under… · pp. 36–37
  • Under VD+FUD and Rigid movement, NS-FCOM-6-color reaches Rendezvous in finite time in every fair full-Asynch execution from designated initial color I.The proof considers executions starting from (I, I) at positive physical distance.Source: S Correctness of NS-FCOM-6-color under… · pp. 36–37
  • The O/S pair moves one robot to the stationary peer, H/H sends both toward the same midpoint, and H/S makes the midpoint robot an N-anchor for the other robot.In the H/S case, the other robot eventually observes N, writes M, and moves to the midpoint robot.Source: S Correctness of NS-FCOM-6-color under… · pp. 36–37
Loading 2610.09713v1…