A Class of Optimal Structures for Node Computations in Message Passing Algorithms

DOI10.1109/TIT.2021.3119952MaRDI QIDQ5030271zbMATHOpenAlexFDO

Authors Xuan He, Kui Cai, Liang Zhou

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.02535

zbMATH Keywords

message passing algorithmsminimum complexityminimum latency

Mathematics Subject Classification ID

Cryptography (94A60) Source coding (94A29)

Abstract: Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages $mathbfx=(x_1,x_2,ldots,x_n)$ and $mathbfy=(y_1,y_2,ldots,y_n)$, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing $mathbfy$ from $mathbfx$, where each $y_j,j=1,2,ldots,n$ is computed via a binary tree with leaves $mathbfx$ excluding $x_j$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is $3n-6$, and if a structure has such complexity, its minimum latency is $delta+lceillog(n-2^{delta})ceil$ with $delta=lfloorlog(n/2)floor$, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is $lceillog(n-1)ceil$, and if a structure has such latency, its minimum complexity is $nlog(n-1)$ when $n-1$ is a power of two. Third, given $(n,au)$ with $augeqlceillog(n-1)ceil$, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most $au$. Our construction method runs in $O(n^{3}lo{g}^2(n))$ time, and the obtained structure has complexity at most (generally much smaller than) $nlceillog(n)ceil-2$.

Recommendations

• Round- and message-optimal distributed graph algorithms
• A Simple Message Passing Algorithm for Graph Partitioning Problems
• scientific article; zbMATH DE number 2013827
• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• scientific article; zbMATH DE number 867692
• Message-Passing Algorithms: Reparameterizations and Splittings
• A linear-time optimal-message distributed algorithm for minimum spanning trees

Cited in

(1)

• scientific article; zbMATH DE number 6253910 (Why is no real title available?)

This page was built for publication: A Class of Optimal Structures for Node Computations in Message Passing Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030271)