How to Distribute Computation in Networks
How to Distribute Computation in Networks
复制标题
DOI：
10.1109/infocom41043.2020.9155442
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Derya Malak;Alejandro Cohen;M. Médard
中科院分区：
文献类型：
--
作者：
Derya Malak;Alejandro Cohen;M. Médard
在网络功能计算是作为一种手段，以减少所需的通信流量方面的比特数发送每个源符号。然而，在一般拓扑结构中的函数计算问题的速率区域是一个开放的问题，并且仅在某些限制性假设（例如树网络、线性函数等）下被考虑。在本文中，我们提出了一个新的角度分布计算，并制定了一个基于流的延迟成本最小化问题，共同捕捉通信和计算的成本。我们引入了熵满射性的概念，作为一种度量来确定函数的稀疏程度和理解计算的极限。利用小的固定系统的法律，我们提供了一个连接这个新的概念和计算处理因素，反映了流量的比例，需要通信。这种连接使我们了解一个节点（孤立地）应该计算多少才能在网络中传递所需的功能，而无需对拓扑结构进行任何假设。我们的分析特征的功能，只有通过他们的熵满射性，并提供洞察如何分配计算。我们数值测试我们的搜索，MapReduce和分类任务的技术，并推断每个任务的处理因素的熵满射性是多么敏感。
In network function computation is as a means to reduce the required communication flow in terms of number of bits transmitted per source symbol. However, the rate region for the function computation problem in general topologies is an open problem, and has only been considered under certain restrictive assumptions (e.g. tree networks, linear functions, etc.). In this paper, we propose a new perspective for distributing computation, and formulate a flow-based delay cost minimization problem that jointly captures the costs of communications and computation. We introduce the notion of entropic surjectivity as a measure to determine how sparse the function is and to understand the limits of computation. Exploiting Little’s law for stationary systems, we provide a connection between this new notion and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network without putting any assumptions on the topology. Our analysis characterizes the functions only via their entropic surjectivity, and provides insight into how to distribute computation. We numerically test our technique for search, MapReduce, and classification tasks, and infer for each task how sensitive the processing factor to the entropic surjectivity is.