Afficher la notice abrégée

hal.structure.identifierLaboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]
dc.contributor.authorFRAIGNIAUD, Pierre
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
dc.date.accessioned2024-04-15T09:50:27Z
dc.date.available2024-04-15T09:50:27Z
dc.date.issued2010
dc.identifier.issn0022-0000
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198342
dc.description.abstractEnWe study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherElsevier
dc.subject.enAlgorithm
dc.subject.enBroadcasting
dc.subject.enWakeup
dc.subject.enSize of advice
dc.subject.enMessage complexity
dc.subject.enNetwork
dc.subject.enGraph
dc.title.enCommunication algorithms with advice
dc.typeArticle de revue
dc.identifier.doi10.1016/j.jcss.2009.07.002
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalJournal of Computer and System Sciences
bordeaux.page222-232
bordeaux.volume76
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue3-4
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00412058
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00412058v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Journal%20of%20Computer%20and%20System%20Sciences&rft.date=2010&rft.volume=76&rft.issue=3-4&rft.spage=222-232&rft.epage=222-232&rft.eissn=0022-0000&rft.issn=0022-0000&rft.au=FRAIGNIAUD,%20Pierre&ILCINKAS,%20David&PELC,%20Andrzej&rft.genre=article


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