9 July 2020 in IEEE Transactions on Automatic Control
We consider the problem of multi-agent optimization wherein an unknown subset of agents suffer Byzantine faults and thus behave adversarially. We assume that each agent $i$ has a local cost function $f_i$, and the overarching goal of the good agents is to collaboratively minimize a global objective that properly aggregates these local cost functions. To the best of our knowledge, we are among the first to study Byzantine-resilient optimization where no central coordinating agent exists, and we are the first to characterize the structures of the convex coefficients of the achievable global objectives. Dealing with Byzantine faults is very challenging. For example, in contrast to fault-free networks, reaching Byzantine-resilient agreement even in the simplest setting is far from trivial. We take a step towards solving the proposed Byzantine-resilient multi-agent optimization problem by focusing on scalar local cost functions. Our results might provide useful insights for the general local cost functions.
30 June 2020 in IEEE Control Systems Letters
We present a distributed optimization protocol that preserves statistical privacy of agents' local cost functions against a passive adversary that corrupts some agents in the network. The protocol is a composition of a distributed “zero-sum” obfuscation protocol that obfuscates the agents' local cost functions, and a standard non-private distributed optimization method. We show that our protocol protects the statistical privacy of the agents' local cost functions against a passive adversary that corrupts up to t arbitrary agents as long as the communication network has (t+1 )-vertex connectivity. The “zero-sum” obfuscation protocol preserves the sum of the agents' local cost functions and therefore ensures accuracy of the computed solution.
16 January 2023 in IEEE Transactions on Control of Network Systems
We consider the problem of Byzantine fault-tolerance in federated machine learning. In this problem, the system comprises multiple agents each with local data, and a trusted centralized coordinator. In fault-free setting, the agents collaborate with the coordinator to find a minimizer of the aggregate of their local cost functions defined over their local data. We consider a scenario where some agents ( $f$ out of $N$ ) are Byzantine faulty. Such agents need not follow a prescribed algorithm correctly, and may communicate arbitrary incorrect information to the coordinator. In the presence of Byzantine agents, a more reasonable goal for the non-faulty agents is to find a minimizer of the aggregate cost function of only the non-faulty agents. This particular goal is commonly referred as exact fault-tolerance . Recent work has shown that exact fault-tolerance is achievable if only if the non-faulty agents satisfy the property of $2f$-redundancy . Now, under this property, techniques are known to impart exact fault-tolerance to the distributed implementation of the classical stochastic gradient-descent (SGD) algorithm. However, we do not know of any such techniques for the federated local SGD algorithm - a more commonly used method for federated machine learning. To address this issue, we propose a novel technique named comparative elimination (CE). We show that, under $2f$ -redundancy, the federated local SGD algorithm with CE can indeed obtain exact fault-tolerance in the deterministic setting when the non-faulty agents can accurately compute gradients of their local cost functions. In the general stochastic case, when agents can only compute unbiased noisy estimates of their local gradients, our algorithm achieves approximate fault-tolerance with approximation error proportional to the variance of stochastic gradients and the fraction of Byzantine agents.
23 January 2006 in IEEE Transactions on Mobile Computing
To reduce medium access control (MAC) overhead and improve channel utilization, there has been extensive research on dynamically adjusting the channel access behavior of a contending station based on channel feedback information. This paper explores an alternative approach, named pipelined packet scheduling, to reduce the MAC overhead. MAC overheads can be divided into bandwidth-dependent and bandwidth-independent components and these overheads can both be reduced by using split-channel pipelining mechanisms, as demonstrated in this paper. In the past, pipelining mechanisms have not been well studied. This paper introduces two total pipelining schemes that attempt to fully pipeline contention resolution with data transmission. Further, the paper identifies shortcomings of total pipelining in the wireless environment and proposes a partial pipelining approach to overcome these shortcomings. Simulation results show that substantial performance improvement in channel utilization, average packet access delay, and access energy cost can be achieved with a properly designed scheme.