Afficher la notice abrégée

Allowing Each Node to Communicate Only Once in a Distributed System: Shared Whiteboard Models

hal.structure.identifierLaboratoire d'Informatique Fondamentale d'Orléans [LIFO]
dc.contributor.authorBECKER, Florent
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierAlgorithms, simulation, combinatorics and optimization for telecommunications [MASCOTTE]
dc.contributor.authorNISSE, Nicolas
hal.structure.identifierDepartamento de Ingeniería Matemática [Santiago] [DIM]
hal.structure.identifierCentre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago] [CMM]
dc.contributor.authorRAPAPORT, Ivan
hal.structure.identifierFacultad de Ingeniería y Ciencias [Santiago]
dc.contributor.authorSUCHAN, Karol
dc.date.accessioned2024-04-15T09:45:19Z
dc.date.available2024-04-15T09:45:19Z
dc.date.issued2012
dc.date.conference2012
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197907
dc.description.abstractEnIn this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that {\it separate} these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.
dc.language.isoen
dc.source.titleACM
dc.title.enAllowing Each Node to Communicate Only Once in a Distributed System: Shared Whiteboard Models
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
dc.description.sponsorshipEuropeExperimental UpdateLess Evolutive Routing
bordeaux.page7
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSPAA - 24th ACM Symposium on Parallelism in Algorithms and Architectures
bordeaux.countryUS
bordeaux.title.proceedingACM
bordeaux.peerReviewedoui
hal.identifierhal-00704200
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00704200v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=ACM&rft.date=2012&rft.spage=7&rft.epage=7&rft.au=BECKER,%20Florent&KOSOWSKI,%20Adrian&NISSE,%20Nicolas&RAPAPORT,%20Ivan&SUCHAN,%20Karol&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée