The Range of Topological Effects on Communication

DOI10.1007/978-3-662-47666-6_43zbMATH Open1440.68011arXiv1504.06602OpenAlexW2131378629MaRDI QIDQ3449503FDOQ3449503

Authors: Arkadev Chattopadhyay, Atri Rudra 

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: We continue the study of communication cost of computing functions when inputs are distributed among $k$ processors, each of which is located at one vertex of a network/graph called a terminal. Every other node of the network also has a processor, with no input. The communication is point-to-point and the cost is the total number of bits exchanged by the protocol, in the worst case, on all edges. Chattopadhyay, Radhakrishnan and Rudra (FOCS'14) recently initiated a study of the effect of topology of the network on the total communication cost using tools from $L_1$ embeddings. Their techniques provided tight bounds for simple functions like Element-Distinctness (ED), which depend on the 1-median of the graph. This work addresses two other kinds of natural functions. We show that for a large class of natural functions like Set-Disjointness the communication cost is essentially $n$ times the cost of the optimal Steiner tree connecting the terminals. Further, we show for natural composed functions like $extEDcircextXOR$ and $extXORcircextED$, the naive protocols suggested by their definition is optimal for general networks. Interestingly, the bounds for these functions depend on more involved topological parameters that are a combination of Steiner tree and 1-median costs. To obtain our results, we use some new tools in addition to ones used in Chattopadhyay et. al. These include (i) viewing the communication constraints via a linear program; (ii) using tools from the theory of tree embeddings to prove topology sensitive direct sum results that handle the case of composed functions and (iii) representing the communication constraints of certain problems as a family of collection of multiway cuts, where each multiway cut simulates the hardness of computing the function on the star topology.

Full work available at URL: https://arxiv.org/abs/1504.06602

Recommendations

• On the topology of the domain of outer communication
• The topology of wireless communication
• The topology of wireless communication
• scientific article; zbMATH DE number 5155071
• The topology of wireless communication on a line
• A new approach for data transmission system on topological surfaces
• Communication-Based on Topology Preservation of Chaotic Dynamics
• Communicability angle and the spatial efficiency of networks

Mathematics Subject Classification ID

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

Cites Work

• The geometry of graphs and some of its algorithmic applications
• Title not available (Why is that?)
• Three XOR-lemmas -- an exposition
• Lower bounds on the multiparty communication complexity
• How to compress interactive communication
• On Yao's XOR-lemma
• On Lipschitz embedding of finite metric spaces in Hilbert space
• The Range of Topological Effects on Communication
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
• Title not available (Why is that?)
• Separating AC\(^0\) from depth-2 majority circuits
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• On the power of the congested clique model
• Communication steps for parallel query processing
• Lower bounds on communication complexity in distributed computer networks
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Communication complexity of approximate matching in distributed graphs
• An optimal lower bound for distinct elements in the message passing model
• Tight bounds for distributed functional monitoring
• Tribes is hard in the message passing model
• Optimal Function Computation in Directed and Undirected Graphs

Cited In (6)

• The Range of Topological Effects on Communication
• Title not available (Why is that?)
• Isolation effects in a system of two mutually communicating identical patches
• Testing equality under the local broadcast model
• A new approach for data transmission system on topological surfaces
• The topology of wireless communication on a line

This page was built for publication: The Range of Topological Effects on Communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449503)