Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles
| hal.structure.identifier | School of Electrical Engineering and Computer Science [EECS] | |
| dc.contributor.author | FLOCCHINI, Paola | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | ILCINKAS, David | |
| hal.structure.identifier | School of Computer Science [Ottawa] | |
| dc.contributor.author | SANTORO, Nicola | |
| dc.date.accessioned | 2024-04-15T09:44:44Z | |
| dc.date.available | 2024-04-15T09:44:44Z | |
| dc.date.issued | 2012-04 | |
| dc.identifier.issn | 0178-4617 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197869 | |
| dc.description.abstractEn | We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles. | |
| dc.description.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Springer Verlag | |
| dc.subject.en | Distributed computing | |
| dc.subject.en | Graph exploration | |
| dc.subject.en | Mobile agents | |
| dc.subject.en | Autonomous robots | |
| dc.subject.en | Dangerous graphs | |
| dc.title.en | Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1007/s00453-011-9496-3 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.journal | Algorithmica | |
| bordeaux.page | pages 1006-1033 | |
| bordeaux.volume | 62 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 3-4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00726790 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00726790v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Algorithmica&rft.date=2012-04&rft.volume=62&rft.issue=3-4&rft.spage=pages%201006-1033&rft.epage=pages%201006-1033&rft.eissn=0178-4617&rft.issn=0178-4617&rft.au=FLOCCHINI,%20Paola&ILCINKAS,%20David&SANTORO,%20Nicola&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||