A tight lower bound for semi-synchronous collaborative grid exploration
Abstract: Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative.
In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Anmerkungen
-
32nd International Symposium on Distributed Computing : DISC 2018. - Wadern, 2018. - 13:1-13:17, ISBN: 978-3-95977-092-7
- Ereignis
-
Veröffentlichung
- (wo)
-
Freiburg
- (wer)
-
Universität
- (wann)
-
2022
- Urheber
- Beteiligte Personen und Organisationen
- DOI
-
10.4230/LIPIcs.DISC.2018.13
- URN
-
urn:nbn:de:bsz:25-freidok-2263514
- Rechteinformation
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
15.08.2025, 07:31 MESZ
Datenpartner
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
Entstanden
- 2022
Ähnliche Objekte (12)
A tight lower bound for semi-synchronous collaborative grid exploration
Tight WCRT analysis of synchronous C programs
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
An asymptotically tight bound for the Davenport constant
Tight Bounds for Double Coverage Against Weak Adversaries
Tight bounds for blind search on the integers
A Tight Lower Bound for Planar Steiner Orientation
Improved virtual synchronous control for grid-connected VSCs under grid voltage unbalanced conditions
Synchronous collaborative L2 writing with technology : interaction and learning
Mobile virtual synchronous machine for vehicle-to-grid applications
Mobile virtual synchronous machine for vehicle-to-grid applications
A tight lower bound for semi-synchronous collaborative grid exploration
Tight WCRT analysis of synchronous C programs
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
An asymptotically tight bound for the Davenport constant
Tight Bounds for Double Coverage Against Weak Adversaries
Tight bounds for blind search on the integers
A Tight Lower Bound for Planar Steiner Orientation
Improved virtual synchronous control for grid-connected VSCs under grid voltage unbalanced conditions
Synchronous collaborative L2 writing with technology : interaction and learning
Mobile virtual synchronous machine for vehicle-to-grid applications
Mobile virtual synchronous machine for vehicle-to-grid applications
A tight lower bound for semi-synchronous collaborative grid exploration
Tight WCRT analysis of synchronous C programs
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
An asymptotically tight bound for the Davenport constant
Tight Bounds for Double Coverage Against Weak Adversaries
Tight bounds for blind search on the integers
A Tight Lower Bound for Planar Steiner Orientation
Improved virtual synchronous control for grid-connected VSCs under grid voltage unbalanced conditions
Synchronous collaborative L2 writing with technology : interaction and learning
Mobile virtual synchronous machine for vehicle-to-grid applications