OPTIMAL BROADCAST WITH PARTIAL KNOWLEDGE

Authors
AWERBUCH B CIDON I KUTTEN S MANSOUR Y PELEG D
Citation
B. Awerbuch et al., OPTIMAL BROADCAST WITH PARTIAL KNOWLEDGE, SIAM journal on computing (Print), 28(2), 1999, pp. 512-525
Citations number
22
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
2
Year of publication
1999
Pages
512 - 525
Database
ISI
SICI code
0097-5397(1999)28:2<512:OBWPK>2.0.ZU;2-O
Abstract
This work is concerned with the problem of broadcasting a large messag e efficiently when each processor has partial prior knowledge about th e contents of the broadcast message. The partial information held by t he processors might be out of date or otherwise erroneous, and consequ ently, different processors may hold conflicting information. Tight bo unds are established for broadcast under such conditions, and applicat ions of the broadcast protocol to other distributed computing problems are discussed.