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 diameter ⋮ Binary linear programming models for robust broadcasting in communication networks ⋮ Broadcasting multiple messages in simultaneous send/receive systems ⋮ Hierarchical broadcast networks ⋮ On optimal broadcasting in faulty hypercubes ⋮ Fast gossiping with short unreliable messages ⋮ Broadcasting in \(m\)-dimensional grid graphs with a given neighborhood template ⋮ Optimal algorithms for dissemination of information in generalized communication modes ⋮ Methods and problems of communication in usual networks ⋮ Reliable broadcasting ⋮ Broadcasting on recursively decomposable Cayley graphs ⋮ Broadcasting in butterfly and deBruijn networks ⋮ Minimum \(k\)-broadcast graphs ⋮ Traffic-light scheduling on the grid ⋮ A minimum broadcast graph on 63 vertices ⋮ Broadcasting on \([0,L\)] ⋮ Broadcasting multiple messages in a grid ⋮ Optimal scheduling of peer-to-peer file dissemination ⋮ Note on optimal gossiping in some weak-connected graphs ⋮ Broadcasting multiple messages in the 1-in port model in optimal time ⋮ On the number of broadcast schemes in networks ⋮ On the communication complexity of polling ⋮ The exact gossiping problem ⋮ The structure of information networks ⋮ Robust gossiping with an application to consensus ⋮ An online distributed gossiping protocol for mobile networks ⋮ Periodic gossiping in back-to-back trees ⋮ Better bounds for perpetual gossiping ⋮ A tight upper bound on acquaintance time of graphs ⋮ \(k\)-path partitions in trees ⋮ Optimal odd gossiping ⋮ Broadcast and gossip in line-communication mode ⋮ A generalized broadcasting schema for the mesh structures ⋮ A note on the acquaintance time of random graphs ⋮ Reliable broadcasting in product networks ⋮ Spanning subgraphs with applications to communication of a subclass of the Cayley-graph-based networks ⋮ Minimum time broadcast in faulty star networks ⋮ Broadcasting with linearly bounded transmission faults ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Broadcasting and gossiping on de Bruijn, shuffle-exchange and similar networks ⋮ All-to-all broadcast problem of some classes of graphs under the half duplex all-port model ⋮ A PTAS for geometric 2-FTP ⋮ On the complexity of the shortest-path broadcast problem ⋮ All-to-all broadcast problems on Cartesian product graphs ⋮ Deterministic broadcasting time with partial knowledge of the network. ⋮ Messy broadcasting - decentralized broadcast schemes with limited knowledge ⋮ Knowledge-based multi-criteria optimization to support indoor positioning ⋮ Gossiping and routing in second-kind Frobenius graphs ⋮ Spreading of messages in random graphs ⋮ Optimal broadcast for fully connected processor-node networks ⋮ Parallel algorithms for gossiping by mail ⋮ The epistemic gossip problem ⋮ Algorithms for graphs with small octopus ⋮ Upper bounds on the broadcast function using minimum dominating sets ⋮ Gossiping 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 trees ⋮ The worst case behavior of randomized gossip protocols ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ Parsimonious flooding in dynamic graphs ⋮ Broadcasting in complete networks with faulty nodes using unreliable calls ⋮ Rooted level-disjoint partitions of Cartesian products ⋮ The minimum broadcast time problem for several processor networks ⋮ Epistemic protocols for dynamic gossip ⋮ Sparse broadcast graphs ⋮ Odd gossiping ⋮ Efficient broadcast trees for weighted vertices ⋮ Minimum multiple originator broadcast graphs ⋮ Optimal total exchange for a 3-D torus of processors ⋮ Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2 ⋮ Broadcasting in DMA-bound bounded degree graphs ⋮ Minimum broadcast digraphs ⋮ Set to set broadcasting in communication networks ⋮ Broadcasting from multiple originators ⋮ Fast information sharing in a complete network ⋮ Broadcasting on networks of workstations ⋮ On maximal instances for the original syntenic distance ⋮ Cooperative TSP ⋮ Rapid almost-complete broadcasting in faulty networks ⋮ Optimal algorithms for dissemination of information in some interconnection networks ⋮ Perfect broadcasting in unlabeled networks ⋮ Optimal sequential gossiping by short messages ⋮ An approximation algorithm and dynamic programming for reduction in heterogeneous environments ⋮ Spreading messages ⋮ On broadcasting in unicyclic graphs ⋮ Minimizing broadcast costs under edge reductions in tree networks ⋮ On the structure of minimum broadcast digraphs ⋮ Efficient collective communciation in optical networks ⋮ The generalized hierarchical product of graphs ⋮ Cayley graphs as classifiers for data mining: the influence of asymmetries ⋮ Symmetric flows and broadcasting in hypercubes ⋮ Compound constructions of broadcast networks ⋮ Optimal point-to-point broadcast algorithms via lopsided trees ⋮ Fast gossiping on square mesh computers ⋮ Verifiable broadcasting and gossiping in communication networks ⋮ On the construction of regular minimal broadcast digraphs ⋮ Quick gossiping by telegraphs ⋮ Graph theoretical issues in computer networks ⋮ Hierarchical broadcast and gossip networks ⋮ Information flows on hypergraphs ⋮ The multiple originator broadcasting problem in graphs ⋮ Gossiping and broadcasting versus computing functions in networks ⋮ Broadcast time and connectivity ⋮ Oriented hypercubes ⋮ Degree- and time-constrained broadcast networks ⋮ The total acquisition number of random graphs ⋮ Propositional gossip protocols ⋮ Effective systolic algorithms for gossiping in cycles and two-dimensional grids ⋮ A SURVEY ON UNDIRECTED CIRCULANT GRAPHS ⋮ Asymptotically optimal gossiping in radio networks ⋮ Kernels of minimum size gossip schemes ⋮ Optimal gossiping in square 2D meshes ⋮ The complexity of finding a broadcast center ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ The partial gossiping problem ⋮ Unnamed Item ⋮ The total acquisition number of random geometric graphs ⋮ Everyone knows that everyone knows ⋮ Gossiping with multiple sends and receives ⋮ Bounded depth broadcasting ⋮ Colouring paths in directed symmetric trees with applications to WDM routing ⋮ Reordered gossip schemes ⋮ Designing broadcasting algorithms in the postal model for message-passing systems ⋮ Improved upper and lower bounds fork-broadcasting ⋮ Broadcasting in butterfly and debruijn networks ⋮ Dynamic gossip ⋮ Path 3-(edge-)connectivity of lexicographic product graphs ⋮ On the radius of nonsplit graphs and information dissemination in dynamic networks ⋮ Stateless Information Dissemination Algorithms ⋮ Time-Optimal Broadcasting of Multiple Messages in 1-in Port Model ⋮ Token transfer in a faulty network ⋮ Spreading Messages ⋮ Minimal number of calls in propositional protocols ⋮ Broadcast Graphs Using New Dimensional Broadcast Schemes for Knödel Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The broadcast median problem in heterogeneous postal model ⋮ NETWORK PROPERTIES OF DOUBLE AND TRIPLE FIXED STEP GRAPHS ⋮ Justifying the small-world phenomenon via random recursive trees ⋮ The logic of gossiping ⋮ Unnamed Item ⋮ Unnamed Item ⋮ More broadcast graphs ⋮ Optimal multiple message broadcasting in telephone-like communication systems ⋮ An analytical model for Pedestrian content distribution in a grid of streets ⋮ Keeping track of the latest gossip in a distributed system ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ Sparse networks supporting efficient reliable broadcasting ⋮ A decentralized model of information pricing in networks ⋮ The Pleasure of Gossip ⋮ The complexity of systolic dissemination of information in interconnection networks ⋮ Constructing edge-disjoint Steiner paths in lexicographic product networks ⋮ A lightweight epistemic logic and its application to planning ⋮ Fast gossiping by short messages ⋮ An algorithm for constructing minimalc-broadcast networks ⋮ Efficient communication in unknown networks ⋮ Concurrent multicast in weighted networks ⋮ Gossiping by energy-constrained mobile agents in tree networks ⋮ A model for learning the news in social networks ⋮ Lower bounds on systolic gossip ⋮ Minimum linear gossip graphs and maximal linear (?,k)-gossip graphs ⋮ k-Broadcasting in trees ⋮ A note on line broadcast in digraphs under the edge-disjoint paths mode ⋮ Sublogarithmic approximation for telephone multicast ⋮ Broadcast in the rendezvous model ⋮ The shortest path problem in the Knödel graph ⋮ Reliable Broadcasting in Hypercubes with Random Link and Node Failures ⋮ Deterministic Models of Communication Faults ⋮ Communication complexity of gossiping by packets ⋮ Modelling simultaneous broadcasting by level-disjoint partitions ⋮ Acquaintance Time of Random Graphs Near Connectivity Threshold ⋮ Path-connectivity of lexicographic product graphs ⋮ Central Limit Theorem for Time to Broadcast in Radio Networks ⋮ Optimal computation of census functions in the postal model ⋮ Multicommodity Multicast, Wireless and Fast ⋮ The unit acquisition number of binomial random graphs ⋮ Nonadaptive broadcasting in trees ⋮ Sparse hypercube -- a minimal \(k\)-line broadcast graph. ⋮ Time-stamped graphs and their associated influence digraphs ⋮ Expected value expansions in rooted graphs ⋮ Randomized rumor spreading in poorly connected small-world networks ⋮ A general multi-agent epistemic planner based on higher-order belief change ⋮ Discordant voting protocols for cyclically linked agents ⋮ On the hierarchical product of graphs and the generalized binomial tree ⋮ Asynchronous Broadcasting with Bivalent Beeps ⋮ Time-Efficient Broadcast in Radio Networks ⋮ Improved Bounds for Minimum Fault-Tolerant Gossip Graphs ⋮ On Decidability of a Logic of Gossips ⋮ Optimal gossiping in paths and cycles ⋮ AT-free graphs: Linear bounds for the oriented diameter ⋮ Simple multi-party set reconciliation ⋮ FAST BROADCASTING WITH BYZANTINE FAULTS ⋮ Quasirandom Rumor Spreading on Expanders ⋮ Distributed probabilistic polling and applications to proportionate agreement ⋮ Broadcasting in unlabeled hypercubes with a linear number of messages. ⋮ Broadcasting in hypercubes and star graphs with dynamic faults. ⋮ Neighborhood Communications in Networks ⋮ The acquaintance time of (percolated) random geometric graphs ⋮ Gossip Latin square and the meet-all gossipers problem ⋮ Unnamed Item ⋮ On the Push&Pull Protocol for Rumor Spreading ⋮ Communication pattern logic: epistemic and topological views ⋮ Broadcasting in split graphs ⋮ A matheuristic approach for the minimum broadcast time problem using a biased random‐key genetic algorithm ⋮ Data transmission in processor networks ⋮ Broadcasting in hypercubes with randomly distributed Byzantine faults ⋮ Approximation algorithms in graphs with known broadcast time of the base graph ⋮ Broadcast graphs using new dimensional broadcast schemes for Knödel graphs ⋮ Gossiping in vertex-disjoint paths mode in interconnection networks ⋮ Diameter of General Knödel Graphs ⋮ The limits to gossip: second-order shared knowledge of all secrets is unsatisfiable ⋮ Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks ⋮ Connectivity and inference problems for temporal networks ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Communication in the two-way listen-in vertex-disjoint paths mode ⋮ A minimum broadcast graph on 26 vertices ⋮ New bounds on the minimum number of calls in failure‐tolerant gossiping ⋮ A linear algorithm for finding the k‐broadcast center of a tree ⋮ Efficient line broadcasting in a \(d\)-dimensional grid ⋮ Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks ⋮ Power domination with bounded time constraints ⋮ Broadcasting in weighted trees under the postal model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ CONTINGENCY AND KNOWING WHETHER ⋮ TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective*
Cites Work