This paper studies the feasibility of reaching consensus in an anonymous dynamic network. In our model, n anonymous nodes proceed in synchronous rounds. We adopt a hybrid fault model in which up to$f$nodes may suffer crash or Byzantine faults, and the dynamic message adversary chooses a communication graph for each round. We introduce a stability property of the dynamic network - (T, D)-dynaDegree for$T$≥ 1 and$n$- 1 ≥$D$≥1 - which requires that for every$T$consecutive rounds, any fault-free node must have incoming directed links from at least$D$distinct neighbors. These links might occur in different rounds during a$T$- round interval. (1,$n$-1) -dynaDegree means that the graph is a complete graph in every round. (1, 1) -dynaDegree means that each node has at least one incoming neighbor in every round, but the set of incoming neighbor(s) at each node may change arbitrarily between rounds. We show that exact consensus is impossible even with (1,$n$- 2) -dynaDegree. For an arbitrary T, we show that for crash-tolerant approximate consensus, (T, ⌊ n/2 ⌋)-dynaDegree and$n$> 2$f$are together necessary and sufficient, whereas for Byzantine approximate consensus, (T, ⌊(n + 3f)/2⌋)-dynaDegree and$n$> 5f are together necessary and sufficient.

We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our algorithm ensures $(\alpha,\alpha\rho^2/2)$-Renyi differential privacy and finds a $(\delta,\epsilon)$-stationary point so long as $M=\tilde\Omega(\frac{d}{\delta\epsilon^3} + \frac{d^{3/2}}{\rho\delta\epsilon^2})$. This matches the optimal complexity found in its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' when $\rho \ge \sqrt{d}\epsilon$.

Training neural networks requires optimizing a loss function that may be highly irregular, and in particular neither convex nor smooth. Popular training algorithms are based on stochastic gradient descent with momentum (SGDM), for which classical analysis applies only if the loss is either convex or smooth. We show that a very small modification to SGDM closes this gap: simply scale the update at each time point by an exponentially distributed random scalar. The resulting algorithm achieves optimal convergence guarantees. Intriguingly, this result is not derived by a specific analysis of SGDM: instead, it falls naturally out of a more general framework for converting online convex optimization algorithms to non-convex optimization algorithms.

This paper studies the power of the "abstract MAC layer" model in a single-hop asynchronous network. The model captures primitive properties of modern wireless MAC protocols. In this model, Newport [PODC '14] proves that it is impossible to achieve deterministic consensus when nodes may crash. Subsequently, Newport and Robinson [DISC '18] present randomized consensus algorithms that terminate with O(n³ log n) expected broadcasts in a system of n nodes. We are not aware of any results on other fault-tolerant distributed tasks in this model. We first study the computability aspect of the abstract MAC layer. We present a wait-free algorithm that implements an atomic register. Furthermore, we show that in general, k-set consensus is impossible. Second, we aim to minimize storage complexity. Existing algorithms require Ω(n log n) bits. We propose two wait-free approximate consensus and two wait-free randomized binary consensus algorithms that only need constant storage complexity (except for the phase index). One randomized algorithm terminates with O(n log n) expected broadcasts. All our algorithms are anonymous, meaning that at the algorithm level, nodes do not need to have a unique identifier.

We develop a new reduction that converts any online convex optimization algorithm suffering $O(\sqrt{T})$ regret into an $\epsilon$-differentially private stochastic convex optimization algorithm with the optimal convergence rate $\tilde O(1/\sqrt{T} + 1/\epsilon T)$ on smooth losses in linear time, forming a direct analogy to the classical non-private ``online-to-batch'' conversion. By applying our techniques to more advanced adaptive online algorithms, we produce adaptive differentially private counterparts whose convergence rates depend on apriori unknown variances or parameter norms.

This paper explores fault-tolerant algorithms in the abstract MAC layer [7] in a single-hop network. The model captures the basic properties of modern wireless MAC protocols. Newport [11] proves that it is impossible to achieve deterministic fault-tolerant consensus, and Newport and Robinson [10] present randomized crash-tolerant consensus algorithms. We are not aware of any study on the computability in this model.

Industry 5.0 is emerging as a result of the advancement in networking and communication technologies, artificial intelligence, distributed computing, and beyond 5G. Among the important enabling technologies, federated learning, industrial edge computing, and Byzantine-tolerant machine learning (ML) are key accelerators in Industry 5.0. We propose a framework to integrate these key components. Recent works have designed various Byzantine-tolerant ML algorithms for a datacenter or a cluster. However, these algorithms are difficult to be applied to industrial edge computing paradigms. In this article, a novel Byzantine-tolerant federated learning algorithm, CRACAU, is designed for the popular three-level edge computing architecture. In this algorithm, edge devices jointly learn an ML model using the data collected at each device, and their private data are never shared with others. Under standard assumptions, we formally prove that CRACAU converges to the optimal point, i.e., CRACAU finds the optimal parameters of the ML model. We also implement CRACAU in the MXNet framework and evaluate it on the popular benchmark MNIST and CIFAR-10 image classification datasets. Experimental results show that CRACAU achieves satisfying accuracy.

This paper studies a fundamental distributed primitive - approximate consensus - in connected things using wireless networks. It has been extensively studied in different disciplines, such as fault-tolerant computing, distributed computing, control, and robotics communities. To our surprise, we have not found any practical algorithm that is appropriate for our target scenario - a system of small things that have limited computation and storage capability, and use lossy wireless links to communicate with each other.

Fault-tolerant distributed consensus is an important primitive in many large-scale distributed systems and applications. The consensus problem has been investigated under various fault models in the literature since the seminal work by Lamport et al. in 1982. In this paper, we study the exact consensus problem in a new faulty link model, namely global asymmetric Byzantine (GAB) link model. Our link-fault model is simple, yet to our surprise, not studied before. In our system, all the nodes are fault-free and each pair of nodes can communicate directly with each other. In the GAB link model, up to f directed links may become Byzantine, and have arbitrary behavior. Non-faulty links deliver messages reliably. In our model, it is possible that the link from node a to node b is faulty, but the link from node b to node a is fault-free. Unlike some prior models with a local constraint, which enforced a local upper bound on the number of failure links attached to each node, we adopt the global constraint, which allows any link to be corrupted in the GAB model. These global and asymmetric features distinguish our model from all prior faulty link models. In our GAB model, we study the consensus problem in both synchronous and asynchronous systems. We show that 2f + 1 nodes is both necessary and sufficient for solving synchronous consensus, whereas 2f+2 nodes is the tight condition on resilience for solving asynchronous consensus. We also study the models where faulty links are mobile (or transient), i.e., the set of faulty links might change from round to round. We show that 2f + 3 nodes is necessary and sufficient for a family of algorithms that update local state in an iterative fashion.

In the past few years, many Byzantine-tolerant distributed machine learning (DML) algorithms have been proposed in the point-to-point communication model. In this paper, we focus on a popular DML framework - the parameter server computation paradigm and iterative learning algorithms that proceed in rounds, e.g., [11, 8, 6]. One limitation of prior algorithms in this domain is the high communication complexity. All the Byzantine-tolerant DML algorithms that we are aware of need to send n d-dimensional vectors from worker nodes to the parameter server in each round, where n is the number of workers and d is the number of dimensions of the feature space (which may be in the order of millions). In a wireless network, power consumption is proportional to the number of bits transmitted. Consequently, it is extremely difficult, if not impossible, to deploy these algorithms in power-limited wireless devices. Motivated by this observation, we aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network [1, 3, 14].

Fault-tolerant consensus is of great importance in distributed systems. This paper studies the asynchronous approximate consensus problem in the crash-recovery model with fair-loss links. In our model, up to f nodes may crash forever, while the rest may crash intermittently. Each node is equipped with a limited-size persistent storage that does not lose data when crashed. We present an algorithm that only stores three values in persistent storage - state, phase index, and a counter.