A survey of gossiping and broadcasting in communication networks

From MaRDI portal
Publication:3795460

DOI10.1002/net.3230180406zbMath0649.90047OpenAlexW2058322021MaRDI QIDQ3795460

Stephen T. Hedetniemi, Sandra M. Hedetniemi, Arthur L. Liestman

Publication date: 1988

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230180406




Related Items

Orientations of digraphs almost preserving diameterBinary linear programming models for robust broadcasting in communication networksBroadcasting multiple messages in simultaneous send/receive systemsHierarchical broadcast networksOn optimal broadcasting in faulty hypercubesFast gossiping with short unreliable messagesBroadcasting in \(m\)-dimensional grid graphs with a given neighborhood templateOptimal algorithms for dissemination of information in generalized communication modesMethods and problems of communication in usual networksReliable broadcastingBroadcasting on recursively decomposable Cayley graphsBroadcasting in butterfly and deBruijn networksMinimum \(k\)-broadcast graphsTraffic-light scheduling on the gridA minimum broadcast graph on 63 verticesBroadcasting on \([0,L\)] ⋮ Broadcasting multiple messages in a gridOptimal scheduling of peer-to-peer file disseminationNote on optimal gossiping in some weak-connected graphsBroadcasting multiple messages in the 1-in port model in optimal timeOn the number of broadcast schemes in networksOn the communication complexity of pollingThe exact gossiping problemThe structure of information networksRobust gossiping with an application to consensusAn online distributed gossiping protocol for mobile networksPeriodic gossiping in back-to-back treesBetter bounds for perpetual gossipingA tight upper bound on acquaintance time of graphs\(k\)-path partitions in treesOptimal odd gossipingBroadcast and gossip in line-communication modeA generalized broadcasting schema for the mesh structuresA note on the acquaintance time of random graphsReliable broadcasting in product networksSpanning subgraphs with applications to communication of a subclass of the Cayley-graph-based networksMinimum time broadcast in faulty star networksBroadcasting with linearly bounded transmission faultsThe complexity of broadcasting in planar and decomposable graphsBroadcasting and gossiping on de Bruijn, shuffle-exchange and similar networksAll-to-all broadcast problem of some classes of graphs under the half duplex all-port modelA PTAS for geometric 2-FTPOn the complexity of the shortest-path broadcast problemAll-to-all broadcast problems on Cartesian product graphsDeterministic broadcasting time with partial knowledge of the network.Messy broadcasting - decentralized broadcast schemes with limited knowledgeKnowledge-based multi-criteria optimization to support indoor positioningGossiping and routing in second-kind Frobenius graphsSpreading of messages in random graphsOptimal broadcast for fully connected processor-node networksParallel algorithms for gossiping by mailThe epistemic gossip problemAlgorithms for graphs with small octopusUpper bounds on the broadcast function using minimum dominating setsGossiping and broadcasting versus computing functions in networks.Dynamic faults have small effect on broadcasting in hypercubes.A survey on Knödel graphs.On linear-time data dissemination in dynamic rooted treesThe worst case behavior of randomized gossip protocolsA polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problemParsimonious flooding in dynamic graphsBroadcasting in complete networks with faulty nodes using unreliable callsRooted level-disjoint partitions of Cartesian productsThe minimum broadcast time problem for several processor networksEpistemic protocols for dynamic gossipSparse broadcast graphsOdd gossipingEfficient broadcast trees for weighted verticesMinimum multiple originator broadcast graphsOptimal total exchange for a 3-D torus of processorsMinimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2Broadcasting in DMA-bound bounded degree graphsMinimum broadcast digraphsSet to set broadcasting in communication networksBroadcasting from multiple originatorsFast information sharing in a complete networkBroadcasting on networks of workstationsOn maximal instances for the original syntenic distanceCooperative TSPRapid almost-complete broadcasting in faulty networksOptimal algorithms for dissemination of information in some interconnection networksPerfect broadcasting in unlabeled networksOptimal sequential gossiping by short messagesAn approximation algorithm and dynamic programming for reduction in heterogeneous environmentsSpreading messagesOn broadcasting in unicyclic graphsMinimizing broadcast costs under edge reductions in tree networksOn the structure of minimum broadcast digraphsEfficient collective communciation in optical networksThe generalized hierarchical product of graphsCayley graphs as classifiers for data mining: the influence of asymmetriesSymmetric flows and broadcasting in hypercubesCompound constructions of broadcast networksOptimal point-to-point broadcast algorithms via lopsided treesFast gossiping on square mesh computersVerifiable broadcasting and gossiping in communication networksOn the construction of regular minimal broadcast digraphsQuick gossiping by telegraphsGraph theoretical issues in computer networksHierarchical broadcast and gossip networksInformation flows on hypergraphsThe multiple originator broadcasting problem in graphsGossiping and broadcasting versus computing functions in networksBroadcast time and connectivityOriented hypercubesDegree- and time-constrained broadcast networksThe total acquisition number of random graphsPropositional gossip protocolsEffective systolic algorithms for gossiping in cycles and two-dimensional gridsA SURVEY ON UNDIRECTED CIRCULANT GRAPHSAsymptotically optimal gossiping in radio networksKernels of minimum size gossip schemesOptimal gossiping in square 2D meshesThe complexity of finding a broadcast centerAn Introduction to Temporal Graphs: An Algorithmic PerspectiveThe partial gossiping problemUnnamed ItemThe total acquisition number of random geometric graphsEveryone knows that everyone knowsGossiping with multiple sends and receivesBounded depth broadcastingColouring paths in directed symmetric trees with applications to WDM routingReordered gossip schemesDesigning broadcasting algorithms in the postal model for message-passing systemsImproved upper and lower bounds fork-broadcastingBroadcasting in butterfly and debruijn networksDynamic gossipPath 3-(edge-)connectivity of lexicographic product graphsOn the radius of nonsplit graphs and information dissemination in dynamic networksStateless Information Dissemination AlgorithmsTime-Optimal Broadcasting of Multiple Messages in 1-in Port ModelToken transfer in a faulty networkSpreading MessagesMinimal number of calls in propositional protocolsBroadcast Graphs Using New Dimensional Broadcast Schemes for Knödel GraphsUnnamed ItemUnnamed ItemThe broadcast median problem in heterogeneous postal modelNETWORK PROPERTIES OF DOUBLE AND TRIPLE FIXED STEP GRAPHSJustifying the small-world phenomenon via random recursive treesThe logic of gossipingUnnamed ItemUnnamed ItemMore broadcast graphsOptimal multiple message broadcasting in telephone-like communication systemsAn analytical model for Pedestrian content distribution in a grid of streetsKeeping track of the latest gossip in a distributed systemInterval routing schemes allow broadcasting with linear message-complexitySparse networks supporting efficient reliable broadcastingA decentralized model of information pricing in networksThe Pleasure of GossipThe complexity of systolic dissemination of information in interconnection networksConstructing edge-disjoint Steiner paths in lexicographic product networksA lightweight epistemic logic and its application to planningFast gossiping by short messagesAn algorithm for constructing minimalc-broadcast networksEfficient communication in unknown networksConcurrent multicast in weighted networksGossiping by energy-constrained mobile agents in tree networksA model for learning the news in social networksLower bounds on systolic gossipMinimum linear gossip graphs and maximal linear (?,k)-gossip graphsk-Broadcasting in treesA note on line broadcast in digraphs under the edge-disjoint paths modeSublogarithmic approximation for telephone multicastBroadcast in the rendezvous modelThe shortest path problem in the Knödel graphReliable Broadcasting in Hypercubes with Random Link and Node FailuresDeterministic Models of Communication FaultsCommunication complexity of gossiping by packetsModelling simultaneous broadcasting by level-disjoint partitionsAcquaintance Time of Random Graphs Near Connectivity ThresholdPath-connectivity of lexicographic product graphsCentral Limit Theorem for Time to Broadcast in Radio NetworksOptimal computation of census functions in the postal modelMulticommodity Multicast, Wireless and FastThe unit acquisition number of binomial random graphsNonadaptive broadcasting in treesSparse hypercube -- a minimal \(k\)-line broadcast graph.Time-stamped graphs and their associated influence digraphsExpected value expansions in rooted graphsRandomized rumor spreading in poorly connected small-world networksA general multi-agent epistemic planner based on higher-order belief changeDiscordant voting protocols for cyclically linked agentsOn the hierarchical product of graphs and the generalized binomial treeAsynchronous Broadcasting with Bivalent BeepsTime-Efficient Broadcast in Radio NetworksImproved Bounds for Minimum Fault-Tolerant Gossip GraphsOn Decidability of a Logic of GossipsOptimal gossiping in paths and cyclesAT-free graphs: Linear bounds for the oriented diameterSimple multi-party set reconciliationFAST BROADCASTING WITH BYZANTINE FAULTSQuasirandom Rumor Spreading on ExpandersDistributed probabilistic polling and applications to proportionate agreementBroadcasting in unlabeled hypercubes with a linear number of messages.Broadcasting in hypercubes and star graphs with dynamic faults.Neighborhood Communications in NetworksThe acquaintance time of (percolated) random geometric graphsGossip Latin square and the meet-all gossipers problemUnnamed ItemOn the Push&Pull Protocol for Rumor SpreadingCommunication pattern logic: epistemic and topological viewsBroadcasting in split graphsA matheuristic approach for the minimum broadcast time problem using a biased random‐key genetic algorithmData transmission in processor networksBroadcasting in hypercubes with randomly distributed Byzantine faultsApproximation algorithms in graphs with known broadcast time of the base graphBroadcast graphs using new dimensional broadcast schemes for Knödel graphsGossiping in vertex-disjoint paths mode in interconnection networksDiameter of General Knödel GraphsThe limits to gossip: second-order shared knowledge of all secrets is unsatisfiableMaximizing reachability in a temporal graph obtained by assigning starting times to a collection of walksConnectivity and inference problems for temporal networksThe complexity of broadcasting in planar and decomposable graphsCommunication in the two-way listen-in vertex-disjoint paths modeA minimum broadcast graph on 26 verticesNew bounds on the minimum number of calls in failure‐tolerant gossipingA linear algorithm for finding the k‐broadcast center of a treeEfficient line broadcasting in a \(d\)-dimensional gridConstructing Internally Disjoint Pendant Steiner Trees in Cartesian Product NetworksPower domination with bounded time constraintsBroadcasting in weighted trees under the postal modelUnnamed ItemUnnamed ItemCONTINGENCY AND KNOWING WHETHERTOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTIONAn Introduction to Temporal Graphs: An Algorithmic Perspective*



Cites Work