Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximate Byzantine Fault-Tolerance in Distributed Optimization
95
0
0.0
(
0
)
Added by
Shuo Liu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function, and in the fault-free case, the goal is to design a distributed algorithm that allows all the agents to find a minimum point of all the agents aggregate cost function. We consider a scenario where some agents might be Byzantine faulty that renders the original goal of computing a minimum point of all the agents aggregate cost vacuous. A more reasonable objective for an algorithm in this scenario is to allow all the non-faulty agents to compute the minimum point of only the non-faulty agents aggregate cost. Prior work shows that if there are up to $f$ (out of $n$) Byzantine agents then a minimum point of the non-faulty agents aggregate cost can be computed exactly if and only if the non-faulty agents costs satisfy a certain redundancy property called $2f$-redundancy. However, $2f$-redundancy is an ideal property that can be satisfied only in systems free from noise or uncertainties, which can make the goal of exact fault-tolerance unachievable in some applications. Thus, we introduce the notion of $(f,epsilon)$-resilience, a generalization of exact fault-tolerance wherein the objective is to find an approximate minimum point of the non-faulty aggregate cost, with $epsilon$ accuracy. This approximate fault-tolerance can be achieved under a weaker condition that is easier to satisfy in practice, compared to $2f$-redundancy. We obtain necessary and sufficient conditions for achieving $(f,epsilon)$-resilience characterizing the correlation between relaxation in redundancy and approximation in resilience. In case when the agents cost functions are differentiable, we obtain conditions for $(f,epsilon)$-resilience of the distributed gradient-descent method when equipped with robust gradient aggregation.
rate research
Read More
In this note, we observe a safety violation in Zyzzyva and a liveness violation in FaB. To demonstrate these issues, we require relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.
The robustness of distributed optimization is an emerging field of study, motivated by various applications of distributed optimization including distributed machine learning, distributed sensing, and swarm robotics. With the rapid expansion of the scale of distributed systems, resilient distributed algorithms for optimization are needed, in order to mitigate system failures, communication issues, or even malicious attacks. This survey investigates the current state of fault-tolerance research in distributed optimization, and aims to provide an overview of the existing studies on both fault-tolerant distributed optimization theories and applicable algorithms.
Miniaturized satellites are currently not considered suitable for critical, high-priority, and complex multi-phased missions, due to their low reliability. As hardware-side fault tolerance (FT) solutions designed for larger spacecraft can not be adopted aboard very small satellites due to budget, energy, and size constraints, we developed a hybrid FT-approach based upon only COTS components, commodity processor cores, library IP, and standard software. This approach facilitates fault detection, isolation, and recovery in software, and utilizes fault-coverage techniques across the embedded stack within an multiprocessor system-on-chip (MPSoC). This allows our FPGA-based proof-of-concept implementation to deliver strong fault-coverage even for missions with a long duration, but also to adapt to varying performance requirements during the mission. The operator of a spacecraft utilizing this approach can define performance profiles, which allow an on-board computer (OBC) to trade between processing capacity, fault coverage, and energy consumption using simple heuristics. The software-side FT approach developed also offers advantages if deployed aboard larger spacecraft through spare resource pooling, enabling an OBC to more efficiently handle permanent faults. This FT approach in part mimics a critical biological systemss way of tolerating and adjusting to failures, enabling graceful ageing of an MPSoC.
Consider a distributed system with $n$ processors out of which $f$ can be Byzantine faulty. In the approximate agreement task, each processor $i$ receives an input value $x_i$ and has to decide on an output value $y_i$ such that - the output values are in the convex hull of the non-faulty processors input values, - the output values are within distance $d$ of each other. Classically, the values are assumed to be from an $m$-dimensional Euclidean space, where $m ge 1$. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph $G$ and the goal is to output vertices that are within distance $d$ of each other in $G$, but still remain in the graph-induced convex hull of the input values. For $d=0$, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any $d ge 1$, we show that the task is solvable in asynchronous systems when $G$ is chordal and $n > (omega+1)f$, where $omega$ is the clique number of~$G$. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
The practical Byzantine fault tolerant (PBFT) consensus mechanism is one of the most basic consensus algorithms (or protocols) in blockchain technologies, thus its performance evaluation is an interesting and challenging topic due to a higher complexity of its consensus work in the peer-to-peer network. This paper describes a simple stochastic performance model of the PBFT consensus mechanism, which is refined as not only a queueing system with complicated service times but also a level-independent quasi-birth-and-death (QBD) process. From the level-independent QBD process, we apply the matrix-geometric solution to obtain a necessary and sufficient condition under which the PBFT consensus system is stable, and to be able to numerically compute the stationary probability vector of the QBD process. Thus we provide four useful performance measures of the PBFT consensus mechanism, and can numerically calculate the four performance measures. Finally, we use some numerical examples to verify the validity of our theoretical results, and show how the four performance measures are influenced by some key parameters of the PBFT consensus. By means of the theory of multi-dimensional Markov processes, we are optimistic that the methodology and results given in this paper are applicable in a wide range research of PBFT consensus mechanism and even other types of consensus mechanisms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
