Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power
| hal.structure.identifier | Laboratoire d'Informatique Fondamentale d'Orléans [LIFO] | |
| dc.contributor.author | BECKER, Florent | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | KOSOWSKI, Adrian | |
| hal.structure.identifier | Algorithms, simulation, combinatorics and optimization for telecommunications [MASCOTTE] | |
| dc.contributor.author | NISSE, Nicolas | |
| hal.structure.identifier | Departamento de Ingeniería Matemática [Santiago] [DIM] | |
| hal.structure.identifier | Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago] [CMM] | |
| dc.contributor.author | RAPAPORT, Ivan | |
| hal.structure.identifier | Facultad de Ingeniería y Ciencias [Santiago] | |
| dc.contributor.author | SUCHAN, Karol | |
| dc.date.accessioned | 2024-04-15T09:46:53Z | |
| dc.date.available | 2024-04-15T09:46:53Z | |
| dc.date.issued | 2011 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198047 | |
| dc.description.abstractEn | In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the second, and so on. Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models. | |
| dc.language.iso | en | |
| dc.title.en | Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power | |
| dc.type | Rapport | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Théorie de l'information [cs.IT] | |
| dc.subject.hal | Mathématiques [math]/Théorie de l'information et codage [math.IT] | |
| dc.description.sponsorshipEurope | EUropean software defined radio for WireLEss in joint secuRity operations. | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.type.institution | INRIA | |
| bordeaux.type.report | rr | |
| hal.identifier | inria-00627910 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00627910v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011&rft.au=BECKER,%20Florent&KOSOWSKI,%20Adrian&NISSE,%20Nicolas&RAPAPORT,%20Ivan&SUCHAN,%20Karol&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||