Title

Sum-Networks from Incidence Structures: Construction and Capacity Analysis

Abstract

A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.

Department(s)

Computer Science

Comments

This work was supported by the National Science Foundation under Grant CCF-1149860, Grant CCF-1320416, Grant CCF-1718470, and Grant DMS-1120597.

This paper was presented in part at the 2014 52nd Allerton Conference on Communication, Control, and Computing and the 2015 IEEE International Symposium on Information Theory.

Keywords and Phrases

Characteristic; Function Computation; Incidence Structures; Network Coding; Sum-Networks

International Standard Serial Number (ISSN)

0018-9448; 1557-9654

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2018 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 May 2018

Share

 
COinS