How to meet asynchronously at polynomial cost

DOI10.1145/2484239.2484245zbMath1323.68553arXiv1301.7119OpenAlexW2131588774MaRDI QIDQ5176086

Vincent Villain, Yoann Dieudonné, Andrzej Pelc

Publication date: 2 March 2015

Published in: SIAM Journal on Computing, Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.7119

zbMATH Keywords

networkgossipingrendezvousleader electiondeterministic algorithmrenamingasynchronous mobile agents

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Network protocols (68M12) Distributed algorithms (68W15)

Related Items (27)

Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ Byzantine gathering in networks ⋮ On asynchronous rendezvous in general graphs ⋮ Rendezvous in networks in spite of delay faults ⋮ Byzantine gathering in polynomial time ⋮ Price of asynchrony in mobile agents computing ⋮ Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings ⋮ Almost universal anonymous rendezvous in the plane ⋮ Fast rendezvous with advice ⋮ Rendezvous of heterogeneous mobile agents in edge-weighted networks ⋮ Deterministic rendezvous in infinite trees ⋮ Unnamed Item ⋮ Optimally reordering mobile agents on parallel rows ⋮ Deterministic treasure hunt and rendezvous in arbitrary connected graphs ⋮ Meeting in a polygon by anonymous oblivious robots ⋮ On deterministic rendezvous at a node of agents with arbitrary velocities ⋮ Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Gathering of oblivious robots on infinite grids with minimum traveled distance ⋮ Deterministic Rendezvous with Detection Using Beeps ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Linear rendezvous with asymmetric clocks ⋮ Asynchronous approach in the plane: a deterministic polynomial algorithm ⋮ Deterministic Meeting of Sniffing Agents in the Plane ⋮ Rendezvous in planar environments with obstacles and unknown initial distance ⋮ Deterministic polynomial approach in the plane ⋮ Anonymous meeting in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Gathering of asynchronous robots with limited visibility
• A single-version STM that is multi-versioned permissive
• How to meet in anonymous network
• Methods and problems of communication in usual networks
• The theory of search games and rendezvous.
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Asynchronous deterministic rendezvous in graphs
• Deterministic rendezvous in graphs
• Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences
• Decidability Classes for Mobile Agents Computing
• Delays Induce an Exponential Memory Gap for Rendezvous in Trees
• Distributed Computing by Mobile Robots: Gathering
• Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports
• Randomized rendezvous with limited memory
• How to meet asynchronously (almost) everywhere
• Tell Me Where I Am So I Can Meet You Sooner
• Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids
• Undirected connectivity in log-space
• Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements
• Two Dimensional Rendezvous Search
• Rendezvous search on a graph
• Rendezvous search when marks are left at the starting points
• Rendezvous search on labeled networks
• Minimax Rendezvous on the Line
• The Rendezvous Search Problem
• Gathering Despite Mischief
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Anonymous Meeting in Networks
• The rendezvous problem on discrete locations
• LATIN 2004: Theoretical Informatics

This page was built for publication: How to meet asynchronously at polynomial cost