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

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

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Precoder Design for Communication-Efficient distributed MIMO Receivers With Controlled Peak-Average Power Ratio

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第7期69卷 4704-4716页

作者： Vaishampayan, Vinay A. CUNY Dept Engn & Environm Sci Coll Staten Isl New York NY 10314 USA

We consider the problem of communicating over a relay-assisted multiple-input multiple-output (MIMO) channel with additive noise, in which physically separated relays forward quantized information to a central decoder where the transmitted message is to be decoded. We assume that channel state information is available in the transmitter and show that the design of a rational-forcing precoder-a precoder which is matched to the quantizers used in the relays-is beneficial for reducing the symbol error probability. It turns out that for such rationalforcing precoder based systems, there is natural tradeoff between the peak to average power ratio in the transmitter and the rate of communication between the relays and the central decoder. The precoder design problem is formulated mathematically, and several algorithms are developed for realizing this tradeoff. Optimality of the decoder communication rate is shown based on a result in distributed function computation. Numerical and simulation results show that a useful tradeoff can be obtained between the excess decoder communication rate and the peakaverage power ratio in the transmitter.

关键词： MIMO communication peak to average power ratio precoder distributed function computation lattices lattice basis reduction LLL algorithm closest lattice point decision feedback equalization successive interference cancellation communication complexity

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：