Asymptotically optimal algorithms for approximate agreement

This paper introduces some algorithms to solve crash-failure, failure-by-omission and Byzantine failure versions of the Byzantine Generals or consensus problem, where non-faulty processors need only arrive at values that are close together rather than identical. For each failure model and each value ofS, we give at-resilient algorithm usingS rounds of communication. IfS=t+1, exact agreement is obtained. In the algorithms for the failure-by-omission and Byzantine failure models, each processor attempts to identify the faulty processors and corrects values transmited by them to reduce the amount of disagreement. We also prove lower bounds for each model, to show that each of our algorithms has a convergence rate that is asymptotic to the best possible in that model as the number of processors increases. Alan Fekete was born in Sydney Australia in 1959. He studied Pure Mathematics and Computer Science at the University of Sydney, obtaining a B.Sc.(Hons) in 1982. He then moved to Cambridge, Massachusetts, where he obtained a distributed Ph.D. degree, awarded by Harvard University's Mathematics department for work supervised by Nancy Lynch in M.I.T.'s Laboratory for Computer Science. He spend the year 1987–1988 at M.I.T. as a postdoctoral Research Associate, and is now Lecturer in Computer Science at the University of Sydney. His research concentrates on understanding the modularity in distributed algorithms, especially those used for concurrency control in distributed databases.A preliminary version of this paper has appeared in the Proceedings of the 5th ACM Symposium on Principles of Distributed Computing (August 1986). This work was begun in the Department of Mathematics, Harvard University, and completed at the Laboratory for Computer Science at Massachusetts Institute of Technology. The work was supported in part (through Professor N. Lynch) by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under contract DAAG29-84-K-0058, by the National Science Foundation under Grants MCS-8306854, DCR-83-02391, and CCR-8611442, and by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125     

Reaching agreement on processor-group membrship in synchronous distributed systems

Reaching agreement on the identity of correctly functioning processors of a distributed system in the presence of random communication delays, failures and processor joins is a fundamental problem in fault-tolerant distributed systems. Assuming a synchronous communication network that is not subject to partition occurrences, we specify the processor-group membership problem and we propose three simple protocols for solving it. The protocols provide all correct processors with consistent views of the processor-group membership and guarantee bounded processor failure detection and join delays. Flaviu Cristian is a computer scientist at the IBM Almaden Research Center in San Jose, California. He received his PhD from the University of Grenoble, France, in 1979. After carrying out research in operating systems and programming methodology in France and working on the specification, design, and verification of fault-tolerant software in England, he joined IBM in 1982. Since then he has worked in the area of fault-tolerant distributed systems and protocols. He has participated in the design and implementation of a highly available distributed system prototype at the Almaden Research Center, has reviewed and consulted for several fault-tolerant distributed system designs, both in Europe and the American divisions of IBM, and is now a technical leader in the design of a new Air Traffic Control System for the US which must satisfy very stringent availability requirements.     

Reaching fault diagnosis agreement on an unreliable general network

Recently, Siu et al. failed in their attempt to use the FDAMIX protocol to eliminate the fault diagnosis agreement (FDA) problem with mixed faults on the processors in a general network. Therefore, in this study, a new protocol, the FDAL protocol, is introduced to solve the FDA problem with mixed faults on the links. The FDAL is capable of detecting/locating faulty links to reconfigure the unreliable general network into a reliable network, and is able to increase the system performance and strengthen network integrity.     

Byzantine agreement in the presence of mixed faults on processorsand links

In early stage, the Byzantine agreement (BA) problem was studied with single faults on processors in either a fully connected network or a nonfully connected network. Subsequently, the single fault assumption was extended to mixed faults (also referred to as hybrid fault model) on processors. For the case of both processor and link failures, the problem has been examined in a fully connected network with a single faulty type, namely an arbitrary fault. To release the limitations of a fully connected network and a single faulty type, the problem is reconsidered in a general network. The processors and links in such a network can both be subjected to different types of fault simultaneously. The proposed protocol uses the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach an agreement     

Reaching with multi-referential dynamical systems

We study a reaching movement controller for a redundant serial arm manipulator, based on two principles believed to be central to biological motion control: multi-referential control and dynamical system control. The resulting controller is based on two concurrent dynamical systems acting on different, yet redundant variables. The first dynamical system acts on the end-effector location variables and the second one acts on the joint angle variables. Coherence constraints are enforced between those two redundant representations of the movement and can be used to modulate the relative influence of each dynamical system. We illustrate the advantages of such a redundant representation of the movement regarding singularities and joint angle avoidance.     

Reaching a goal with directional uncertainty

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle centered around the specified direction.

First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of . We prove that the maximum complexity of is O(n/⁵). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k³m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of . For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.     

Byzantine agreement with homonyms

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, $n$ processes use $\ell $ different identifiers, where $1 \le \ell \le n$ . In this paper, we ask how many identifiers are actually needed to reach agreement in a distributed system with $t$ Byzantine processes. We show that having $3t+1$ identifiers is necessary and sufficient for agreement in the synchronous case but, more surprisingly, the number of identifiers must be greater than $\frac{n+3t}{2}$ in the partially synchronous case. This demonstrates two differences from the classical model (which has $\ell =n$ ): there are situations where relaxing synchrony to partial synchrony renders agreement impossible; and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement. The impossibility proofs use the fact that a Byzantine process can send multiple messages to the same recipient in a round. We show that removing this ability makes agreement easier: then, $t+1$ identifiers are sufficient for agreement, even in the partially synchronous model, assuming processes can count the number of messages with the same identifier they receive in a round.     

From immediate agreement to eventual agreement: early stopping agreement protocol for dynamic networks with malicious faulty processors

With the rapid advancement of wireless networking technology, networks have evolved from static to dynamic. Reliability of dynamic networks has virtually become an important issue. Fortunately, a solution to the above issue can be derived from solutions to the Byzantine Agreement (BA) problem. BA problem can be solved by protocols that make processors reach an agreement through message exchange. Protocols used to solve the problem can be divided into Immediate Byzantine Agreement (IBA) protocols and Eventual Byzantine Agreement (EBA) protocols. In IBA protocols, the number of rounds of message exchange is determined by the total number of processors in the network. Even if no faulty processor is present in the network, IBA protocols still require a fixed number of rounds of message exchange, causing a waste of time. In contrast, EBA protocols dynamically adjust the number of rounds of message exchange according to the interference of faulty processors. In terms of efficiency, EBA protocols certainly outperform IBA protocols. Due to the fact that the existing EBA protocols have been designed for static networks, they cannot work on dynamic networks. In this paper, we revisit the EBA problem in dynamic networks to increase the reliability of dynamic networks. Simulations will be conducted to validate that the proposed protocol requires the minimum rounds of message exchange and can tolerate the maximum number of malicious faulty processors compared to other existing protocols.     

Experience with approximate reliability-based optimization methods

Traditional reliability-based design optimization (RBDO) requires a double loop iteration process. The inner optimization loop is to find the most probable point (MPP) and the outer is the regular optimization loop to optimize the RBDO problem with reliability objectives or constraints. It is well known that the computation can be prohibitive when the associated function evaluation is expensive. As a result, many approximate RBDO methods, which convert the double loop to a single loop, have been developed. In this work, several approximate RBDO methods are coded, discussed, and tested against a double loop algorithm through four design problems.     

考虑非线性执行器的补偿逼近模型控制

考虑执行器的非线性, 研究了一种带补偿的逼近模型控制系统. 该控制系统包含逼近模型控制器与补偿器.逼近模型控制器根据对象的输入输出线性化关系直接得出控制律, 并由支持向量机辨识对象模型来实现. 补偿部分采用反馈环节来提高系统的鲁棒稳定性, 并采用在线估计得到的逆模型来抵消执行器的非线性特征. 文章分析了该控制系统的稳定性, 针对励磁系统的仿真实验验证了其有效性能.     

Bayesian optimization with approximate set kernels

Machine Learning - We propose a practical Bayesian optimization method over sets, to minimize a black-box function that takes a set as a single input. Because set inputs are permutation-invariant,...     

一种匿名认证密钥协商协议*

大多数的认证密钥协商协议没有考虑用户的匿名性,在分析已有MAKAP协议的基础上,提出了一种具有用户匿名性的认证密钥协商协议AKAPA,为用户提供隐私保护。在随机预言机模型下证明其安全性,并就增强的安全属性进行了分析,表明AKAPA具有完美前向安全性,能够抗未知共享密钥攻击和完善拒绝服务攻击等。性能分析表明效率优于已有协议,具有较高的实用性。     

用于离散滑模重复控制的新型趋近律

针对不确定离散时间系统, 提出一种新型的离散趋近律, 构造理想切换动态, 并基于理想切换动态设计离散滑模重复控制器. 在消除系统颤振的同时, 完全抑制周期扰动带来的影响, 改善控制品质. 分别推导了切换函数的绝对收敛层、单调收敛层和拟滑模带的边界, 用于刻画在不同控制器参数下闭环系统的趋近过程和拟滑模运动. 数值仿真和在伺服装置上的实验结果证实了所提出控制方法的有效性.     

Reaching consensus in unbalanced networks with coarse information communication

This paper is concerned with the problem of seeking consensus for a network of agents under a fixed or switching directed communication topology. Each agent is modeled as discrete‐time first‐order dynamics and interacts with its neighbors via logarithmically quantized information. We assume that the digraph is not necessarily balanced and, thus, avoiding the double stochasticity requirement for the adjacency matrix. For the case of a fixed topology that is strongly connected, it is shown that the proposed protocol is admissible for arbitrarily coarse logarithmic quantization and the β‐asymptotic weighted‐average consensus is achieved. For the case of a switching topology that is periodically strongly connected, it is shown that the proposed protocol is admissible for arbitrarily coarse quantization and the β‐asymptotic consensus is achieved. Furthermore, for both cases, not only are the convergence rates for consensus specified but also the bounds on the consensus error that highlight their dependence on the sector bound β of the logarithmic quantizer are also provided. Copyright © 2015 John Wiley & Sons, Ltd.     

Edge-colored graphs with applications to homogeneous faults

In this paper, we use the concept of edge-colored graphs to model homogeneous faults in networks. We then use this model to study the minimum connectivity (and design) requirements of networks for being robust against homogeneous faults within certain thresholds. In particular, necessary and sufficient conditions for most interesting cases are obtained. For example, we will study the following cases: (1) the number of colors (or the number of non-homogeneous network device types) is one more than the homogeneous fault threshold; (2) there is only one homogeneous fault (i.e., only one color could fail); and (3) the number of non-homogeneous network device types is less than five.