Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Exploring The Borderlands Of The Gathering Problem
 
research article

Exploring The Borderlands Of The Gathering Problem

El Mhamdi, El Mahdi  
•
Guerraoui, Rachid  
•
Maurer, Alexandre  
Show more
October 1, 2019
Bulletin of The European Association for Theoretical Computer Science

Problems of pattern formation have been extensively studied in distributed computing. One of this problems is the gathering problem: agents must gather at a same position in a distributed manner. When gathering is not possible, a close problem is the convergence problem. In this article, we investigate the two following questions: (1) Can processes gather when each process cannot see more that one other process at the same time? (2) Can a gathering behavior be learned by processes? Regarding the first point, we introduce a new model with an extremely restricted visibility: each process can only see one other process (its closest neighbor). Our goal is to see if (and to what extent) the gathering and convergence problems can be solved in this setting. We first show that, surprisingly, the problem can be solved for a small number of processes (at most 5), but not beyond. This is due to indeterminacy in the case where there are several "closest neighbors" for a same process. By removing this indeterminacy with an additional hypothesis (choosing the closest neighbor according to an order on the positions of processes), we then show that the problem can be solved for any number of processes. We also show that up to one crash failure can be tolerated for the convergence problem. Regarding the second point, we present the first experimental evidence that a gathering behavior can be learned without explicit communication in a partially observable environment. The learned behavior has the same properties as a self-stabilizing distributed algorithm, as processes can gather from any initial state (and thus tolerate any transient failure). Besides, we show that it is possible to scale and then tolerate the brutal loss of up to 90% of agents without significant impact on the behavior.

  • Details
  • Metrics
Type
research article
Web of Science ID

WOS:000493923500005

Author(s)
El Mhamdi, El Mahdi  
Guerraoui, Rachid  
Maurer, Alexandre  
Tempez, Vladislav
Date Issued

2019-10-01

Published in
Bulletin of The European Association for Theoretical Computer Science
Issue

129

Start page

121

End page

167

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

oblivious mobile robots

•

convergence

•

algorithms

•

patterns

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
November 16, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/163174
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés