Curation and studies series – Byzantine Multi-Agent Optimization: Part I

I will present for the following days and weeks a series of curated papers, video series and some more short posts on the issues that The Information Age cares about. Today I start with a topic of interest, for various reasons and motivations. The recent hype surrounding distributed computing, the blockchain and related subjects does not leave anyone neutral, but a real understanding of the details surrounding these technologies is quite scarce. So this Blog will try, from now and then, to provide some light to the readers on what it is all about distributed computing and the blockchain, trying to be attentive to recent relevant developments.

I’ve realised that the content of the posts I submit in this site isn’t accessible to everyone, and I must strive to convey the topics I choose to cover in as simple as possible way, so that the main points are understood by as much readership as possible. I recommend all readers to post comments and provide their feedback on the posts, with tips in the way of improvement, and if anyone wants to participate with further suggestions, they will be more than welcomed. I know that blogging and publishing can be a very lonely and frustrating experience, and it is only enriched when readers collaborate with each other. Barring the unutterable or uneducated comments and/or suggestions, the rest will be given the proper deserved feedback.

Getting back to the paper I want to cover today, I’ve chosen the first in a series of papers describing the topic of Byzantine fault-tolerant systems, but with the analysis of applied multi-agent optimization to those systems. These systems are an important feature of distributed computing, designed to provide distributed computing a robust framework for the transmission of information or sensitive data. Byzantyne fault-tolerant systems (BFT) play a role in the performance of the most popular application of the blockchain technology, which is the cryptocurrency named Bitcoin. From the Wikipedia page:

One example of BFT in use is bitcoin, a peer-to-peer digital currency system. The bitcoin network works in parallel to generate a chain of Hashcash style proof-of-work. The proof-of-work chain is the key to overcome Byzantine failures and to reach a coherent global view of the system state.



The paper:


Byzantine Multi-Agent Optimization: Part I


We study Byzantine fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input/ouput. In particular, the goal is to optimize a global cost function |N|iNhi(x), where N is the set of non-faulty agents, and hi(x) is agent i‘s local cost function, which is initially known only to agent i. In general, when some of the agents may be Byzantine faulty, the above goal is unachievable, because the identity of the faulty agents is not necessarily known to the non-faulty agents, and the faulty agents may behave arbitrarily. Since the above global cost function cannot be optimized exactly in presence of Byzantine agents, we define a weaker version of the problem.
The goal for the weaker problem is to generate an output that is an optimum of a function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, for some choice of weights αi for iN such that αi0 and iNαi=1, the output must be an optimum of the cost function iNαihi(x). Ideally, we would like αi=1/|N| for all iN — however, this cannot be guaranteed due to the presence of faulty agents. In fact, we show that the maximum achievable number of nonzero weights (αi‘s) is |N|f, where f is the upper bound on the number of Byzantine agents. In addition, we present algorithms that ensure that at least |N|f agents have weights that are bounded away from 0. We also propose a low-complexity suboptimal algorithm, which ensures that at least n/2ϕ agents have weights that are bounded away from 0, where n is the total number of agents, and ϕ (ϕf) is the actual number of Byzantine agents.

The Motivation


In distributed computing one of the main issues that arises concerns the coordination and communication between computers or servers within a network, that may be small or large but the large type is more common and increasingly so. This coordination and communication must reach consensus in order for the different machines compute the information or data flowing through them. That consensus is better achieved when faults or errors are minimized; otherwise if it is not possible to minimize further errors and faults, due to nodes that do not comply to the rules governing the network protocol, then if the systems in the network could somehow agree on an fault-tolerant system that enables the desired consensus, the computation follows efficiently and rapidly. Byzantine fault-tolerant systems are one such approach. From the paper, the authors note:

Fault-tolerant consensus is a special case of the optimization problem considered in this report. There is a significant body of work on fault-tolerant consensus. The optimization algorithms presented in this report use Byzantine consensus as a component.

And by studying the implications of using convex optimization, specifically distributed convex optimization, when applied to a multi-agent framework, this research aims for a newer, more robust distributed consensus in a network of Byzantine agents:

Convex optimization, including distributed convex optimization, also has a long history. However, we are not aware of prior work that obtains the results presented in this report. Primal and dual decomposition methods that lend themselves naturally to a distributed paradigm are well-known. There has been significant research on a variant of distributed optimization problem, in which the global objective h(x) is a summation of n convex functions, i.e, h(x) = ∑ (n j=1) hj (x), with function hj (x) being known to the j-th agent. The need for robustness for distributed optimization problems has received some attentions recently. In particular, Duchi et al. studied the impact of random communication link failures on the convergence of a distributed variant of dual averaging algorithm. Specifically, each realizable link failure pattern considered is assumed to admit a doubly stochastic matrix which governs the evolution dynamics of local estimates of the optimum. In other related work, significant attempts have been made to solve the problem of distributed hypothesis testing in the presence of Byzantine attacks, where Byzantine sensors may transmit fictitious observations aimed at confusing the decision maker to arrive at a judgment that is in contrast with the true underlying distribution. Consensus based variant of distributed event detection, where a centralized data fusion center does not exist, is considered in a referenced paper. In contrast, in this paper, we focus on the Byzantine attacks on the multi-agent optimization problem.



After a lengthy, advanced mathematical presentation of theorems and algorithms supporting the research and its arguments, the authors conclude in this way:

Many extensions of these results are possible. The results obtained in this technical report can be extended to the case when the functions are sub-differentiable, with slightly more involved analysis. This generalization will be presented in another technical report. We have also obtained a comparable set of results for the case when the cost functions are redundant in some manner (e.g., cost function of agent 3 may equal a convex combination of cost functions of agents 1 and 2), or the optimal sets of the local cost functions are guaranteed to overlap. These results will also be presented elsewhere. Finally, if the underlying communication channel is a broadcast channel (over which all transmissions are received correctly and identically by all agents), then the results presented in this report can be proved for n ≥ 2f + 1

In this paper, we introduce the problem of Byzantine fault-tolerant optimization, and obtain an impossibility result for the problem. The impossibility result provides an upper bound on the number of local cost function of non-faulty nodes that can non-trivially affect the output of a weighted optimization function. We also present algorithms that matches this upper bound. In addition, a low-complexity suboptimal algorithm is presented.

The authors have three parts on the topic of Byzantine multi-agent optimization; presented here is the first part. Following will be the remaining two parts.

Featured Image: An Erlang Stack Game

3 thoughts on “Curation and studies series – Byzantine Multi-Agent Optimization: Part I

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s