Byzantine Fault Tolerance (BFT) protocols enable reliable consensus in distributed systems, even with malicious nodes. Synchronous BFT protocols provide the strongest fault tolerance, ensuring security as long as more than half the nodes are honest, leveraging cryptographic signatures implemented via asymmetric algorithms. This paper studies the possibility of eliminating the reliance on cryptographic signatures and trusted third parties to distribute public and private keys for synchronous BFT. We formulated a synchronous BFT problem where each node has an unbounded computational power and can have a private observation of a random variable. The joint distribution of all the random variables is known to all nodes. We call this problem Information-Theoretic BFT (IT-BFT). To maintain liveness, we partition the nodes into two layers, with Layer 1 containing at most one malicious node. The performance of a secure IT-BFT protocol is quantified using the consensus rate defined as the entropy of the consensus information gained per consensus round, and the consensus capacity of an IT-BFT problem is the supermum of consensus rate of all secure IT-BFT protocols. For a system with$n$nodes and$f$malicious nodes, we show that the Gács-Körner (GK) common information of the Layer 1 nodes is a lower bound on the consensus capacity, which is tight for a family of secure IT-BFT protocols when$n=2 f+1$. When$n \geq 2 f+2$, a better lower bound on the consensus capacity is obtained, which can be strictly higher than the GK common information bound.

An$(n,M)$code refers to a binary code with blocklength n and codebook size M. Such codes are studied in the context of memoryless binary symmetric channels (BSCs) with maximum likelihood (ML) decoding. Previous research has characterized some optimal codes among the linear$(n,4)$codes for any$n \geq 2$. However, it was unknown whether these optimal codes among linear codes were better than all nonlinear codes. In this paper, we first demonstrate that for any$n \geq 2$, there exists an optimal code among all$(n,4)$codes that is either linear or belongs to a subset of nonlinear codes called Class-I codes. We identify all the optimal codes among the linear$(n,4)$codes for each blocklength$n \geq 2$and discover some that were not previously reported in the literature. For any n from 2 to 8, all the optimal$(n,4)$codes are identified. Except for$n=3$, all the optimal$(n,4)$codes are equivalent to linear codes. There exist optimal$(3,4)$codes that are not equivalent to linear codes. Furthermore, we introduce a subset of nonlinear codes called Class-II codes and show that for any$n \gt 3$, the set composed of linear, Class-I, and Class-II codes and their equivalent codes contains all the optimal$(n,4)$codes. Both Class-I and Class-II codes are close to linear codes in the sense that they involve only one type of column that is not included in linear codes. We derive a sufficient condition such that all the optimal$(n,4)$codes are equivalent to linear codes, which can be evaluated by computer with a computation cost$O(n^{6})$.

Wireless communications are often affected by out-age events caused by fading and interference. This paper focuses on investigating the communication throughput and latency in a line-topology, multi-hop network where outages may occur on network links. We focus on three types of intermediate network node schemes: random linear network coding (RLNC), store-and-forward (SF), and hop-by-hop retransmission. The analytical formulas for the maximum throughput and the end-to-end latency are provided for each scheme. To gain a more explicit understanding, we conducted a scalability analysis of the maximum throughput and latency as the network length$L$increases. We observed that the same order of throughput/latency holds across a wide range of outage functions for each scheme. Specifically, the SF scheme achieves at most$\Theta(\frac{1}{L})$throughput, while retransmission and RLNC achieve a constant throughput. However, the retransmission scheme relies on ideal feedback, which is rarely satisfied in practice, whereas RLNC does not. We conducted latency comparisons among various schemes under several constraints regarding the volume of data for transmission.

To better understand the wireless network design with a large number of hops, we investigate a line network formed by general discrete memoryless channels (DMCs), which may not be identical. Our focus lies on Generalized Batched Network Coding (GBNC) that encompasses most existing schemes as special cases and achieves the min-cut upper bounds as the parameters batch size and inner block length tend to infinity. The inner blocklength of GBNC provides upper bounds on the required latency and buffer size at intermediate network nodes. By employing a “bottleneck status” technique, we derive new upper bounds on the achievable rates of GBNC. These bounds surpass the min-cut bound for large network lengths when the inner blocklength and batch size are small. For line networks of canonical channels, certain upper bounds hold even with relaxed inner blocklength constraints. Additionally, we employ a “channel reduction” technique to generalize the existing achievability results for line networks with identical DMCs to networks with non-identical DMCs. For line networks with packet erasure channels, we make refinement in both the upper bound and the coding scheme, and showcase their proximity through numerical evaluations.

We study the problem of adversarial combinatorial bandit with a switching cost λ for a switch of each selected arm in each round, considering both the bandit feedback and semi-bandit feedback settings. In the oblivious adversarial case withKbase arms and time horizonT, we derive lower bounds for the minimax regret and design algorithms to approach them. To prove these lower bounds, we design stochastic loss sequences for both feedback settings, building on an idea from previous work in Dekel et al. (2014). The lower bound for bandit feedback is Ω((λK)1/3(TI)2/3) while that for semi-bandit feedback is Ω ( (λKI)1/3T2/3whereIis the number of base arms in the combinatorial arm played in each round. To approach these lower bounds, we design algorithms that operate in batches by dividing the time horizon into batches to restrict the number of switches between actions. For the bandit feedback setting, where only the total loss of the combinatorial arm is observed, we introduce the BATCHED-EXP2 algorithm which achieves a regret upper bound of Õ ( (λK)1/3T2/3I4/3asTtends to infinity. In the semi-bandit feedback setting, where all losses for the combinatorial arm are observed, we propose the BATCHED-BROAD algorithm which achieves a regret upper bound of Õ ( (λK)1/3(TI)2/3).

The search for optimal finite-length binary block codes is a long-standing open problem for memoryless binary symmetric channels (BSCs) with the maximum likelihood decoding. A recent work studied the optimal codes among all binary codes of size four, including both linear codes and nonlinear codes, and showed the existence of optimal codes in the set composed of linear codes and Class-I codes for any given blocklength. Furthermore, for blocklength up to 300, it has been shown that there exists a linear code that is optimal among all the codes of size four. However, it is unknown whether there are optimal codes outside the set of linear codes and Class-I codes for a general blocklength. In this paper, we derive a subset of nonlinear codes called Class-II codes and justify that the set composed of linear, Class-I and Class-II codes and their equivalent codes includes all the optimal codes of size four when the blocklength is not equal to 3. For blocklength 3, we verify that there are nonlinear codes (not equivalent to linear, Class-I or Class-II codes) that are optimal. For the blocklength from 2 to 300 and not equal 3, our computer evaluations show that no nonlinear code is optimal except for the ones that are equivalent to linear codes. Moreover, we characterize all the best codes among all linear codes of size four for any given blocklength.

Network utility maximization (NUM) is studied for multihop wireless networks employing an efficient random linear network coding scheme called BATS codes. Compared with the classical random linear network coding scheme, BATS codes have lower computational and storage costs at the intermediate network nodes, and can achieve close-to-optimal end-to-end throughput and latency for multihop networks with packet loss. We formulate a NUM problem that optimizes the total utility of multiple communication flows under certain link scheduling constraints. Our problem employs a practical throughput measure induced by BATS codes and hence can provide realistic guidelines about network protocol designs for multihop wireless networks. Our problem in general has a non-convex objective function with integer variables, so that the algorithms of solving existing network utility maximization problems cannot be directly applied to our problem. We discuss a modified dual-based algorithm for solving our problem and evaluate its performance numerically.

The communication capacity of a network of line topology is studied, where only two adjacent nodes are connected by communication channels, and the intermediate network nodes have a buffer size constraint. Let L be the number of hops from the source node to the destination node. For general channels, we provide schemes to achieve Ω(1/ ln L) rates using a buffer of size B1+ B2bits, where B1does not change with L and B2= O(ln ln L). In particular, B1bits of the buffer are used to store the data generated from the communication messages, and the other B2bits of the buffer are used to store the status of counters with the maximum value O(ln L).