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

Worst-case asymmetric distributed function computation

INTERNATIONAL JOURNAL OF GENERAL SYSTEMS 2013年第3期42卷 268-293页

作者： Agnihotri, Samar Venkatachalapathy, Rajesh Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China Portland State Univ Portland OR 97207 USA

We consider a distributed function computation problem where an information sink communicates with N correlated information sources to compute a given deterministic function of source data. A data-vector is drawn from a discrete and finite probability distribution and component x i is revealed to ith, , source. We address this problem in asymmetric communication scenarios where only the sink knows the distribution P. We are interested in computing the minimum number of source bits required, in the worst-case, to solve this problem. We propose the notion of functional ambiguity to carry out the worst-case information-theoretic analysis of distributed function computation problems. We establish its various characteristics and prove that it leads to a valid information measure. Then, we provide a constructive solution for the distributed function computation problem in terms of an interactive communication protocol and prove its optimality. Finally, we establish two equivalence classes of compressible and incompressible functions to classify the set of all computable multivariate functions based on the minimum number of source bits needed in the worst-case to compute a function in the distributed function computation set-up.

关键词： distributed function computation interactive communication wireless sensor networks neural information processing systems information measures

来源：评论

学校读者我要写书评

暂无评论

Information-Theoretic Lower Bounds for distributed function computation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第4期63卷 2314-2337页

作者： Xu, Aolin Raginsky, Maxim Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

We derive information-theoretic converses (i.e., lower bounds) for the minimum time required by any algorithm for distributed function computation over a network of point-to-point channels with finite capacity, where each node of the network initially has a random observation and aims to compute a common function of all observations to a given accuracy with a given confidence by exchanging messages with its neighbors. We obtain the lower bounds on computation time by examining the conditional mutual information between the actual function value and its estimate at an arbitrary node, given the observations in an arbitrary subset of nodes containing that node. The main contributions include the following. First, a lower bound on the conditional mutual information via so-called small ball probabilities, which captures the dependence of the computation time on the joint distribution of the observations at the nodes, the structure of the function, and the accuracy requirement. For linear functions, the small ball probability can be expressed by Levy concentration functions of sums of independent random variables, for which tight estimates are available that lead to strict improvements over existing lower bounds on computation time. Second, an upper bound on the conditional mutual information via strong data processing inequalities, which complements and strengthens existing cutset-capacity upper bounds. Finally, a multi-cutset analysis that quantifies the loss (dissipation) of the information needed for computation as it flows across a succession of cutsets in the network. This analysis is based on reducing a general network to a line network with bidirectional links and self-links, and the results highlight the dependence of the computation time on the diameter of the network, a fundamental parameter that is missing from most of the existing lower bounds on computation time.

关键词： distributed function computation computation time small ball probability Levy concentration function strong data processing inequality cutset bound multi-cutset analysis

来源：评论

学校读者我要写书评

暂无评论

Extremal Problem with Network-Diameter and -Minimum-Degree for distributed function computation

引用

SN Computer Science 2020年第4期1卷 1-14页

作者： Dai, H.K. Toulouse, M. Computer Science Department Oklahoma State University Stillwater 74078 OK United States School of Information and Communication Technology Hanoi University of Science and Technology Hanoi Viet Nam

distributed function computation has a wide spectrum of major applications in distributed systems. distributed computation over a network-system proceeds in a sequence of time-steps in which vertices update and/or exchange their values based on the underlying algorithm constrained by the time-(in)variant network-topology. distributed computing network-systems are modeled as directed/undirected graphs with vertices representing compute elements and adjacency-edges capturing their uni- or bi-directional communication. To quantify an intuitive tradeoff between two graph-parameters: minimum vertex-degree and diameter of the underlying graph, we formulate an extremal problem with the two parameters: for all positive integers n and d, the extremal value ∇ (n, d) denotes the least minimum vertex-degree among all connected order-n graphs with diameters of at most d. We prove matching upper and lower bounds on the extremal values of ∇ (n, d) for various combinations of n- and d-values. © 2020, Springer Nature Singapore Pte Ltd.

关键词： distributed function computation Finite convergence Graph-parameter Information dissemination Linear iterative schemes Vertex-eccentricity

来源：评论

学校读者我要写书评

暂无评论

Lower Bound on Network Diameter for distributed function computation 6th

Lower Bound on Network Diameter for Distributed Function Com...

引用

6th International Conference on Future Data and Security Engineering (FDSE)

作者： Dai, H. K. Toulouse, M. Oklahoma State Univ Comp Sci Dept Stillwater OK 74078 USA Vietnamese German Univ Comp Sci Dept Binh Duong New City Vietnam

ISBN: (纸本)9783030356538;9783030356521

Parallel and distributed computing network-systems are modeled as graphs with vertices representing compute elements and adjacency-edges capturing their uni- or bi-directional communication. distributed function computation covers a wide spectrum of major applications, such as quantized consensus and collaborative hypothesis testing, in distributed systems. distributed computation over a networksystem proceeds in a sequence of time-steps in which vertices update and/or exchange their values based on the underlying algorithm constrained by the time-(in)variant network-topology. For finite convergence of distributed information dissemination and function computation in the model, we study lower bounds on the number of time-steps for vertices to receive (initial) vertex-values of all vertices regardless of underlying protocol or algorithmics in time-invariant networks via the notion of vertex-eccentricity in a graph-theoretic framework. We prove a lower bound on the maximum vertex-eccentricity in terms of graph-order and -size in a strongly connected directed graph, and demonstrate its optimality via an explicitly constructed family of strongly connected directed graphs.

关键词： distributed function computation Linear iterative schemes Information dissemination Finite convergence Vertex-eccentricity

来源：评论

学校读者我要写书评

暂无评论

Information-Theoretic Lower Bounds for distributed function computation

Information-Theoretic Lower Bounds for Distributed Function ...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Xu, Aolin Raginsky, Maxim Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

关键词： distributed function computation computation time small ball probability Levy concentration function strong data processing inequality cutset bound multi-cutset analysis

来源：评论

学校读者我要写书评

暂无评论

Lower-Bound Study for function computation in distributed Networks via Vertex-Eccentricity

引用

SN Computer Science 2020年第1期1卷 10页

作者： Dai, H.K. Toulouse, M. Computer Science Department Oklahoma State University Stillwater 74078 OK United States Computer Science Department Vietnamese-German University Binh Duong New City Viet Nam

distributed computing network-systems are modeled as graphs with vertices representing compute elements and adjacency-edges capturing their uni- or bi-directional communication. distributed function computation has a wide spectrum of major applications in distributed systems. distributed computation over a network-system proceeds in a sequence of time-steps in which vertices update and/or exchange their values based on the underlying algorithm constrained by the time-(in)variant network-topology. For finite convergence of distributed information dissemination and function computation in the model, we present a lower bound on the number of time-steps for vertices to receive (initial) vertex-values of all vertices regardless of underlying protocol or algorithmics in time-invariant networks via the notion of vertex-eccentricity in a graph-theoretic framework. We also address lower bounds on vertex-eccentricity and its maximum version in terms of common graph-parameters such as maximum degree, and order and size. © 2019, Springer Nature Singapore Pte Ltd.

关键词： distributed function computation Finite convergence Information dissemination Linear iterative schemes Vertex-eccentricity

来源：评论

学校读者我要写书评

暂无评论

Lower Bound for function computation in distributed Networks 1

引用

5th International Conference on Future Data and Security Engineering (FDSE)

作者： Dai, H. K. Toulouse, M. Oklahoma State Univ Dept Comp Sci Stillwater OK 74078 USA Vietnamese German Univ Dept Comp Sci Binh Duong New City Vietnam

ISBN: (数字)9783030031923

ISBN: (纸本)9783030031923;9783030031916

distributed computing network systems are modeled as graphs with which vertices represent compute elements and adjacency-edges capture their uni- or bi-directional communication. distributed computation over a network system proceeds in a sequence of time-steps in which vertices update and/or exchange their values based on the underlying algorithm constrained by the time-(in)variant network topology. For finite convergence of distributed information dissemination and function computation in the model, we present a lower bound on the number of time-steps for vertices to receive (initial) vertex-values of all vertices regardless of underlying protocol or algorithmics in time-invariant networks via the notion of vertex-eccentricity.

关键词： distributed function computation Linear iterative schemes Information dissemination Finite convergence Vertex-eccentricity

来源：评论

学校读者我要写书评

暂无评论

Linear Coding Schemes for the distributed computation of Subspaces

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2013年第4期31卷 678-690页

作者： Lalitha, V. Prakash, N. Vinodh, K. Kumar, P. Vijay Pradhan, S. Sandeep Indian Inst Sci Dept ECE Bangalore 560012 Karnataka India Univ Michigan Dept EECS Ann Arbor MI 48109 USA

Let X-1,..., X-m be a set of m statistically dependent sources over the common alphabet F-q, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an s-dimensional subspace W spanned by the elements of the row vector [X-1,..., X-m]Gamma in which the (m x s) matrix Gamma has rank s. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute W. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace U of W. The superspace is identified by showing that the joint distribution of the {X-i} induces a unique decomposition of the set of all linear combinations of the {X-i}, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the {X-i} and any W, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, W is computed by first recovering each of the {X-i}. For a large class of joint distributions and subspaces W, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal.

关键词： distributed function computation nested codes normalized entropy source compression linear encoders

来源：评论

学校读者我要写书评

暂无评论

On Communication for distributed Babai Point computation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第10期67卷 6408-6424页

作者： Bollauf, Maiara F. Vaishampayan, Vinay A. Costa, Sueli I. R. Univ Estadual Campinas Inst Math Stat & Comp Sci BR-13083859 Campinas SP Brazil CUNY Dept Engn Sci & Phys Coll Staten Isl Staten Isl NY 10314 USA

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector X is an element of R-n in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of X are mutually independent. We then investigate the error probability, i. e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for X are considered-uniform and Gaussian. For the uniform model, in dimensions two and three, the error probability is seen to grow with the packing density, and we demonstrate that the densest lattice in dimension two presents the worst error probability. For higher dimensions, we develop probabilistic concentration bounds as well as bounds based on geometric arguments for the error probability. The probabilistic bounds lead to the conclusion that for lattices which generate suitably thin coverings of R-n (which includes lattices that meet Rogers' bound on the covering radius), the error probability goes to unity as n grows. Probabilistic and geometric bounds are also used to estimate the error probability under the uniform model for various lattices including the A(n) family and the Leech lattice, Lambda(24). On the other hand, for the Gaussian model, the error probability goes to zero as the lattice dimension tends to infinity, provided the noise variance is sufficiently small.

关键词： Lattices data compression distributed function computation Babai point nearest lattice point communication complexity error probability

来源：评论

学校读者我要写书评

暂无评论

Interactive Nearest Lattice Point Search in a distributed Setting: Two Dimensions

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第8期70卷 5128-5139页

作者： Vaishampayan, Vinay A. Bollauf, Maiara F. CUNY Coll Staten Isl Dept Elect Engn Staten Isl NY 10314 USA Simula UiB N-5006 Bergen Norway

The nearest lattice point problem in R-n is formulated in a distributed network with n nodes. The objective is to minimize the probability that an incorrect lattice point is found, subject to a constraint on inter-node communication. Algorithms with a single as well as an unbounded number of rounds of communication are considered for the case n = 2. For the algorithm with a single round, expressions are derived for the error probability as a function of the total number of communicated bits. We observe that the error exponent depends on the lattice structure and that zero error requires an infinite number of communicated bits. In contrast, with an infinite number of allowed communication rounds, the nearest lattice point can be determined without error with a finite average number of communicated bits and a finite average number of rounds of communication. In two dimensions, the hexagonal lattice, which is most efficient for communication and compression, is found to be the most expensive in terms of communication cost.

关键词： Lattices lattice quantization nearest lattice point problem communication complexity distributed function computation distributed compression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：