检索结果-内蒙古大学图书馆

Communication Cost for Updating Linear functions When Message Updates Are Sparse: Connections to Maximally Recoverable Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第12期64卷 7557-7576页

作者： Prakash, N. Medard, Muriel MIT Elect Res Lab Cambridge MA 02139 USA

We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where neither the source nor the receiver(s) is aware of the exact difference vector, but only know the amount of sparsity that is present in the difference vector. Under this setting, we are interested in devising linear encoding and decoding schemes that minimize the communication cost involved. We show that the optimal solution to this problem is closely related to the notion of maximally recoverable codes (MRCs), which were originally introduced in the context of coding for storage systems. In the context of storage, MRCs guarantee optimal erasure protection when the system is partially constrained to have local parity relations among the storage nodes. In our problem, we show that optimal solutions exist if and only if MRCs of certain kind (identified by the desired linear functions) exist. We consider point-to-point and broadcast versions of the problem and identify connections to MRCs under both these settings. For the point-to-point setting, we show that our linear-encoder-based achievable scheme is optimal even when non-linear encoding is permitted. The theory is illustrated in the context of updating erasure coded storage nodes. We present examples based on modern storage codes, such as the minimum bandwidth regenerating codes.

关键词： function computation maximally recoverable codes distributed storage locally recoverable codes characteristic graphs communication cost

来源：评论

学校读者我要写书评

暂无评论

Data Privacy for a ρ-Recoverable function

Data Privacy for a <i>ρ</i>-Recoverable Function

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Nageswaran, Ajaykrishnan Narayan, Prakash Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Inst Syst Res College Pk MD 20742 USA

ISBN: (纸本)9781538647813

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, that provide maximum privacy to the user. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

关键词： Chernoff radius function computation privacy recoverability

来源：评论

学校读者我要写书评

暂无评论

Information-Theoretic Caching: The Multi-User Case

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第11期63卷 7018-7037页

作者： Lim, Sung Hoon Wang, Chien-Yi Gastpar, Michael Korea Institute of Ocean Science and Technology Ansan South Korea MediaTek Inc. Hsinchu Taiwan School of Computer and Communication Sciences EPFL Lausanne Switzerland

In this paper, we consider a cache aided network in which each user is assumed to have individual caches, while upon users' requests, an update message is sent through a common link to all users. First, we formulate a general information theoretic setting that represents the database as a discrete memoryless source, and the users' requests as side information that is available everywhere except at the cache encoder. The decoders' objective is to recover a function of the source and the side information. By viewing cache aided networks in terms of a general distributed source coding problem and through information theoretic arguments, we present inner and outer bounds on the fundamental tradeoff of cache memory size and update rate. Then, we specialize our general inner and outer bounds to a specific model of content delivery networks: file selection networks, in which the database is a collection of independent equal-size files and each user requests one of the files independently. For file selection networks, we provide an outer bound and two inner bounds (for centralized and decentralized caching strategies). For the case when the user request information is uniformly distributed, we characterize the rate versus cache size tradeoff to within a multiplicative gap of 4. By further extending our arguments to the framework of Maddah-Ali and Niesen, we also establish a new outer bound and two new inner bounds in which it is shown to recover the centralized and decentralized strategies, previously established by Maddah-Ali and Niesen. Finally, in terms of rate versus cache size tradeoff, we improve the previous multiplicative gap of 72 to 4.7 for the average case with unitbrm requests.

关键词： Coded caching function computation multi terminal source coding source coding with side information

来源：评论

学校读者我要写书评

暂无评论

Some Results on Distributed Source Coding for Interactive function computation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第9期57卷 6180-6195页

作者： Ma, Nan Ishwar, Prakash Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA

A two-terminal interactive distributed source coding problem with alternating messages for function computation at both locations is studied. For any number of messages, a computable characterization of the rate region is provided in terms of single-letter information measures. While interaction is useless in terms of the minimum sum-rate for lossless source reproduction at one or both locations, the gains can be arbitrarily large for function computation even when the sources are independent. For a class of sources and functions, interaction is shown to be useless, even with infinite messages, when a function has to be computed at only one location, but is shown to be useful, if functions have to be computed at both locations. For computing the Boolean AND function of two independent Bernoulli sources at both locations, an achievable infinite-message sum-rate with infinitesimal-rate messages is derived in terms of a 2-D definite integral and a rate-allocation curve. The benefit of interaction is highlighted in multiterminal function computation problem through examples. For networks with a star topology, multiple rounds of interactive coding is shown to decrease the scaling law of the total network rate by an order of magnitude as the network grows.

关键词： Distributed source coding function computation interactive coding rate-distortion region Slepian-Wolf coding two-way coding Wyner-Ziv coding

来源：评论

学校读者我要写书评

暂无评论

Time and Energy Complexity of function computation Over Networks

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第12期57卷 7671-7684页

作者： Karamchandani, Nikhil Appuswamy, Rathinakumar Franceschetti, Massimo Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

This paper considers the following network computation problem: n nodes are placed on a root n x root n grid, each node is connected to every other node within distance r(n) of itself, and it is assigned an arbitrary input bit. Nodes communicate with their neighbors and a designated sink node computes a function f of the input bits, where f is either the identity or a symmetric function. We first consider a model where links are interference and noise-free, suitable for modeling wired networks. Then, we consider a model suitable for wireless networks. Due to interference, only nodes which do not share neighbors are allowed to transmit simultaneously, and when a node transmits a bit, all of its neighbors receive an independent noisy copy of the bit. We present lower bounds on the minimum number of transmissions and on the minimum number of time slots required to compute f. We also describe efficient schemes that match both of these lower bounds up to a constant factor and are thus jointly (near) optimal with respect to the number of transmissions and the number of time slots required for computation. At the end of the paper, we extend results on symmetric functions to general network topologies, and obtain a corollary that answers an open question posed by El Gamal in 1987 regarding the computation of the parity function over ring and tree networks.

关键词： Communication complexity error correction function computation information theory sensor networks

来源：评论

学校读者我要写书评

暂无评论

Energy-Latency Tradeoff for In-Network function computation in Random Networks

Energy-Latency Tradeoff for In-Network Function Computation ...

引用

IEEE INFOCOM Conference

作者： Balister, Paul Bollobas, Bela Anandkumar, Animashree Willsky, Alan Univ Memphis Dept Math Memphis TN 38152 USA Math Statistics Dept Pure Math Cambridge England Univ California Dept EECE Irvine CA USA MIT Dept EECE Cambridge MA USA

ISBN: (纸本)9781424499212

The problem of designing policies for in-network function computation with minimum energy consumption subject to a latency constraint is considered. The scaling behavior of the energy consumption under the latency constraint is analyzed for random networks, where the nodes are uniformly placed in growing regions and the number of nodes goes to infinity. The special case of sum function computation and its delivery to a designated root node is considered first. A policy which achieves order-optimal average energy consumption in random networks subject to the given latency constraint is proposed. The scaling behavior of the optimal energy consumption depends on the path-loss exponent of wireless transmissions and the dimension of the Euclidean region where the nodes are placed. The policy is then extended to computation of a general class of functions which decompose according to maximal cliques of a proximity graph such as the k-nearest neighbor graph or the geometric random graph. The modified policy achieves order-optimal energy consumption albeit for a limited range of latency constraints.

关键词： function computation latency-energy tradeoff Euclidean random graphs minimum broadcast problem

来源：评论

学校读者我要写书评

暂无评论

Information-Theoretic Caching: Sequential Coding for Computing

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第11期62卷 6393-6406页

作者： Wang, Chien-Yi Lim, Sung Hoon Gastpar, Michael Univ Paris Saclay Telecom ParisTech Commun & Elect Dept F-75013 Paris France Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

Under the paradigm of caching, partial data are delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users' requests. For the single-user case, a single-letter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyner's common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray-Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.

关键词： Coded caching function computation Gray-Wyner system information bottleneck multi-terminal source coding source coding with side information successive refinement

来源：评论

学校读者我要写书评

暂无评论

Capacity of Sum-networks for Different Message Alphabets

Capacity of Sum-networks for Different Message Alphabets

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Tripathy, Ardhendu Ramamoorthy, Aditya Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA

ISBN: (纸本)9781467377041

A sum-network is a directed acyclic network in which all terminal nodes demand the 'sum' of the independent information observed at 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 instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.

关键词： capacity function computation linear network coding network coding sum-network

来源：评论

学校读者我要写书评

暂无评论

computation Over Gaussian Networks With Orthogonal Components

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第12期60卷 7841-7861页

作者： Jeon, Sang-Woon Wang, Chien-Yi Gastpar, Michael Andong Natl Univ Dept Informat & Commun Engn Andong 760749 South Korea Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

function computation over Gaussian networks with orthogonal components is studied for arbitrarily correlated discrete memoryless sources. Two classes of functions are considered: 1) the arithmetic sum function and 2) the type function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of the sources and estimating each of the sources as special cases. The type or frequency histogram function counts the number of occurrences of each argument, which yields various fundamental statistics, such as mean, variance, maximum, minimum, median, and so on. The proposed computation coding first abstracts Gaussian networks into the corresponding modulo sum multiple-access channels via nested lattice codes and linear network coding and then computes the desired function using linear Slepian-Wolf source coding. For orthogonal Gaussian networks (with no broadcast and multiple-access components), the computation capacity is characterized for a class of networks. For Gaussian networks with multiple-access components (but no broadcast), an approximate computation capacity is characterized for a class of networks.

关键词： Distributed averaging function computation joint source-channel coding lattice codes linear source coding network coding sensor networks

来源：评论

学校读者我要写书评

暂无评论

Computing Linear functions by Linear Coding Over Networks

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第1期60卷 422-431页

作者： Appuswamy, Rathinakumar Franceschetti, Massimo IBM Res Almaden San Jose CA 95120 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

We consider the scenario in which a set of sources generates messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.

关键词： function computation linear coding network coding network computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：