In this work, we focus on solving a decentralized consensus problem in a private manner. Specifically, we consider a setting in which a group of nodes, connected through a network, aim at computing the mean of their local values without revealing those values to each other. The distributed consensus problem is a classic problem that has been extensively studied and its convergence characteristics are well-known. However, state-of-the-art consensus methods build on the idea of exchanging local information with neighboring nodes which leaks information about the users’ local values. We propose an algorithmic framework that is capable of achieving the convergence limit and rate of classic consensus algorithms while keeping the users’ local values private. The key idea of our proposed method is to carefully design noisy messages that are passed from each node to its neighbors such that the consensus algorithm still converges precisely to the average of local values, while a minimum amount of information about local values is leaked. We formalize this by precisely characterizing the mutual information between the private message of a node and all the messages that another adversary collects over time. We prove that our method is capable of preserving users’ privacy for any network without a so-called generalized leaf, and formalize the trade-off between privacy and convergence time. Unlike many private algorithms, any desired accuracy is achievable by our method, and the required level of privacy only affects the convergence time.

We present a low-complexity and low-latency decoding algorithm for a class of Reed-Muller (RM) subcodes that are defined based on the product of smaller RM codes. More specifically, the input sequence is shaped as a multi-dimensional array, and the encoding over each dimension is done separately via a smaller RM encoder. Similarly, the decoding is performed over each dimension via a low-complexity decoder for smaller RM codes. The proposed construction is of particular interest to low-capacity channels that are relevant to emerging low-rate communication scenarios. We present an efficient soft-input soft-output (SISO) iterative decoding algorithm for the product of RM codes and demonstrate its superiority compared to hard decoding over RM code components. The proposed coding scheme has decoding (as well as encoding) complexity of ${\mathcal{O}}(n\log n)$ and latency of ${\mathcal{O}}(\log n)$ for blocklength n. This research renders a general framework toward efficient decoding of RM codes.

Coding for random access communication is a key challenge in Internet of Things applications. In this paper, the well-known scheme of Coded Slotted Aloha (CSA) is considered and its performance is analyzed in the non-asymptotic regime where the frame length and the number of users are finite. A density evolution framework is provided to describe the dynamics of decoding, and fundamental limits are found on the maximum channel load (i.e., the number of active users per time slot) that allows reliable communication (successful decoding). Finally, scaling laws are established, describing the non-asymptotic relation between the probability of error, the number of users, and the channel load.

Low-capacity scenarios have become increasingly important in the technology of Internet of Things (IoT) and the next generation of mobile networks. Such scenarios require efficient and reliable transmission of information over channels with an extremely small capacity. Within these constraints, the performance of state-of-the-art coding techniques is far from optimal in terms of either rate or complexity. Moreover, the current non-asymptotic laws of optimal channel coding provide inaccurate predictions for coding in the low-capacity regime. In this paper, we provide the first comprehensive study of channel coding in the low-capacity regime. We will investigate the fundamental non-asymptotic limits for channel coding as well as challenges that must be overcome for efficient code design in low-capacity scenarios.