Gossiping and broadcasting versus computing functions in networks.

DOI10.1016/S0166-218X(03)00257-9zbMath1062.68018MaRDI QIDQ1427193

Martin Dietzfelbinger

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Lower boundsSynchronisationCommunication in networksDissemination of informationParallel random access machines

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A linear algorithm for finding the k‐broadcast center of a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properties of complexity measures for PRAMs and WRAMs
• ERCW PRAMs and optical communication
• Fast information sharing in a complete network
• Optimal algorithms for dissemination of information in some interconnection networks
• Methods and problems of communication in usual networks
• Broadcasting in butterfly and deBruijn networks
• Exploiting storage redundancy to speed up randomized shared memory simulations
• Generalizations of broadcasting and gossiping
• Trade-Offs between Depth and Width in Parallel Computation
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• A survey of gossiping and broadcasting in communication networks
• CREW PRAM<scp>s</scp> and Decision Trees
• Gossiping in Minimal Time
• An Optical Simulation of Shared Memory
• Parallel Information Dissemination by Packets
• Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers
• Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines