Continuous consensus with ambiguous failures

Continuous consensus (CC) is the problem of maintaining up-to-date and identical copies of a “core” of information about the past at all correct processes in the system (Mizrahi and Moses, 2008 [6]). This is a primitive that supports simultaneous coordination among processes, and eliminates the need for issuing separate instances of consensus for different tasks. Recent work has presented new simple and efficient optimum protocols for continuous consensus in the crash and (sending) omissions failure models. For every pattern of failures, these protocols maintain at each and every time point a core that subsumes that maintained by any other continuous consensus protocol. This paper considers the continuous consensus problem in the face of harsher failures: general omissions and authenticated Byzantine failures. Computationally efficient optimum protocols for CC do not exist in these models if $P\ne NP$. A variety of CC protocols are presented. The first is a simple protocol that enters every interesting event into the core within $t+1$ rounds (where $t$ is the bound on the number of failures), provided there are a majority of correct processes. The second is a protocol that achieves similar performance so long as $n>t$ (i.e., there is always guaranteed to be at least one correct process). The final protocol makes use of active failure monitoring and failure detection to include events in the core much faster in many runs of interest. Its performance is established based on a nontrivial property of minimal vertex covers in undirected graphs. The results are adapted to the authenticated Byzantine failure model, in which it is assumed that faulty processes are malicious, but correct processes have unforgeable signatures. Finally, the problem of uniform CC is considered. It is shown that a straightforward version of uniform CC is not solvable in the setting under study. A weaker form of uniform CC is defined, and protocols achieving it are presented.     

Interacting with electronic mail can be a dream or a nightmare: a user''s point of view

Diffusion of electronic mail (e-mail) is not yet universal. So far, e-mail has been implemented successfully within organisations, but its implementation for communications between organisations has been rather limited. This situation is surprising, given the great potential of e-mail for interorganisational communication. E-mail encounters from a user's point of view, reviewed in this paper, suggest that users of BITNET, one of the predominant e-mail networks in the academic world, face difficulties while interacting with e-mail. These include addressing difficulties, unreliability issues, medium limitations, and interface problems. BITNET is just one of many interorganisational networks and may not be representative. Still, e-mail technology is unlikely to survive if human engineering and reliability are not uniformly satisfactory across all e-mail systems. Poorly engineered e-mail systems frustrate not only their users, but also users of other networks because of gateways between the networks. Therefore, e-mail users might resort to other communication media like facsimile or the telephone, and abandon e-mail altogether.

For e-mail to be competitive in the communication arena, an interdisciplinary effort should be directed toward standardisation of features like better addressing conventions, international user directories, uniform user interfaces, and sophisticated management of e-mail messages.     

Randomization for robot tasks: Using dynamic programming in the space of knowledge states

This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Further examples include tapping, vibrating, twirling, and random search. For instance, it is sometimes beneficial for a system to execute random motions purposefully when the precise motions required to perform an operation are unknown, as when they lie below the available sensor resolution.The purpose of this paper is to provide a theoretical framework for the planning and execution of randomized strategies for robot tasks. This framework is built on the standard backchaining approach of dynamic programming. Specifically, a randomizing planner backchains from the goal in a state space whose states describe the knowledge available to the system at run-time. By choosing random actions in a principled manner at run-time, a system can sometimes obtain a probabilistic strategy for accomplishing a task even when no guaranteed strategy exists for accomplishing that task. In other cases, the system may be able to obtain a speedup over an existing guaranteed strategy.The main result of this paper consists of two examples. One example shows that randomization can sometimes speed up task completion from exponential time to polynomial time. The other example shows that such a speedup is not always possible.The author is now with the School of Computer Science and the Robotics Institute at Carnegie-Mellon University. The work reported here was performed while at the MIT Artificial Intelligence Laboratory. This work was supported in part by the Office of Naval Research under the University Research Initiative Program through Contract N00014-86-K-0685, by an NSF Presidential Young Investigator Award to Tomás Lozano-Pérez, by a fellowship from NASA's Jet Propulsion Laboratory, and by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research Contract N00014-85-K-0124. Additional support at CMU was provided under NSF grant IRI-9010686.     

具有执行器故障的不确定多智能体系统自适应动态面控制

本文研究了一类具有输入量化、未建模动态和执行器故障的非线性多智能体系统的一致跟踪问题.引入一个可量测的动态信号消除未建模动态对系统的影响.利用Young’s不等式和高斯函数的性质,有效地处理了多智能体邻居节点在设计的第一步中对子系统的耦合作用.通过将滞回量化器表示为具有有界系数和有界扰动的输入线性函数,并利用动态面控制方法,提出一种自适应神经网络动态面控制方案,简化了控制器的设计,保证了闭环系统的所有信号都是半全局一致终结有界的,所有跟随者都能实现期望的一致性.最后,仿真结果验证了所提出的自适应控制策略的有效性.     

How exciting can a signal really be?

The rate of parameter convergence in a number of adaptive estimation schemes is related to the smallest eigenvalue of the average information matrix determined by the regression vector. Using a very simple examples, we illustrate that the input signals that maximize this minimum eigenvalue may be quite different from the input signals that optimize more classical input design criteria, e.g. D-optimal criterion.     

Partial consensus of identical feedforward dynamic systems with input saturations

This paper studies the partial consensus problem for identical feedforward dynamic systems with input saturations. We construct two consensus protocols using the partial‐state information and full‐state information, respectively. Applying a change of coordinates, feedforward system is transformed into the block diagonal form. Then, by utilizing the bounded real lemma and small gain theorem, we solve the partial consensus problem, and the existence of each protocol is derived. Copyright © 2015 John Wiley & Sons, Ltd.     

Design of a multi-hop dynamic consensus algorithm over wireless sensor networks

In the last few years great attention has been concentrated on the consensus algorithm in a network of agents. A consensus problem in which the agreement value is a distributed estimation of some non-constant quantity of interest is referred to as a dynamic consensus. In practical applications an effective network architecture to support sensing and communication between agents is based on a Wireless Sensor Network (WSN). This paper deals with the design of a fast dynamic consensus algorithm when it is implemented over the WSN. A sufficient stability condition of the dynamic consensus algorithm in the presence of heterogeneous time delays affecting communication through the multi hops of the WSN is introduced and used for consensus algorithm gain design. Moreover, the algorithm implementation by the standard AODV routing protocol is discussed and the best parameter setting to reduce the effect of packet collision phenomena on the performance of the consensus algorithm is indicated. Several trade-offs between network parameter setting, sensor node technology selection and application performance have to be taken into account by the designer in the implementation of the dynamic consensus algorithm. A representative simulation based design procedure is presented to validate through realistic simulation experiments the proposed design approach.     

Robust consensus tracking of a class of second-order multi-agent dynamic systems

In this paper, we study the problem of robust consensus tracking for a class of second-order multi-agent dynamic systems with disturbances and unmodeled agent dynamics. Contrary to previous approaches, we design continuous distributed consensus protocols to enable global asymptotic consensus tracking. Our focus is on consensus protocol design and stability analysis which also leads to the derivation of sufficient conditions for consensus tracking. We first consider the case of undirected information exchange with a symmetric and positive definite information-exchange matrix. We develop an identifier for each agent to estimate the unknown disturbances and unmodeled agent dynamics. Based on the identifier, we develop a consensus tracking protocol to enable global asymptotic consensus tracking using local information obtained from neighboring agents. The closed-loop stability is proven using Lyapunov analysis theory and an invariance-like theorem. We then extend the approach to the case of directed information exchange, whose information-exchange matrix is only of full rank so that the approach for undirected graphs cannot be directly applied. We show that global asymptotic consensus tracking can still be enabled under the new derived sufficient conditions by designing a new identifier, which utilizes the estimated information exchanged from neighboring agents, and constructing a new Lyapunov function. Examples and numerical simulations are provided to validate the effectiveness of the proposed robust consensus tracking method.     

Noise: How can the nuisance be controlled?

Aircraft noise is a major nuisance in residential communities around airports. If the air transport industries are to meet the ever increasing demand for air travel, determined efforts are required now to reduce the burden of noise upon these communities. Significant engine noise reductions have already been achieved in the latest generation of wide-bodied aircraft, and further reductions are being forcast by the engine manufacturers. Regardless of whether there are justifiable grounds for this optimism there are alternative steps to be taken. But the problem is basically an economic rather than a technological one — how much does noise reduction cost and how much can we afford to pay?The various costs of aircraft noise, both monetary and social, are discussed in relation to its effects upon people. Although an economic analysis of the problem is feasible, it is doubtful whether our understanding of the relationships between physical noise levels and human reaction is yet adequate for such purposes. Planning methods for estimating the extent of community noise nuisance are presented, and it is shown that consideration should be given to outlying regions exposed to relatively little aircraft noise.     

Quasi-random rumor spreading: Reducing randomness can be costly

We give a time-randomness tradeoff for the quasi-random rumor spreading protocol proposed by Doerr, Friedrich and Sauerwald [SODA 2008] on complete graphs. In this protocol, the goal is to spread a piece of information originating from one vertex throughout the network. Each vertex is assumed to have a (cyclic) list of its neighbors. Once a vertex is informed by one of its neighbors, it chooses a position in its list uniformly at random and then informs its neighbors starting from that position and proceeding in order of the list. Angelopoulos, Doerr, Huber and Panagiotou [Electron. J. Combin. 2009] showed that after rounds, the rumor will have been broadcasted to all nodes with probability 1−o(1).We study the broadcast time when the amount of randomness available at each node is reduced in natural way. In particular, we prove that if each node can only make its initial random selection from every ?-th node on its list, then there exists lists such that steps are needed to inform every vertex with probability at least . This shows that a further reduction of the amount of randomness used in a simple quasi-random protocol comes at a loss of efficiency.     

Fully dynamic distributed search trees can be balanced in O(lg2N) time

In this paper we consider the dictionary problem in a message-passing distributed environment. We introduce a new version, based on AVL-trees, of distributed search trees, the first to be fully scalable, that is, able to both grow and shrink as long as keys are inserted and deleted. We prove that in the worst case a key can be inserted, searched, or deleted with $\text{O(}\text{lg}{}^2\text{N)}$ messages. We show that for the introduced distributed search tree this bound is tight. Since the defined structure maintains the relative order of the keys, it can also support queries that refer to the linear order of keys, such as nearest neighbor or range queries.     

Fuzzy implication can be arbitrarily complicated: A theorem

In fuzzy logic, there are several methods of representing implication in terms of &, ∨, and ¬; in particular, explicit representations define a class of S implications, implicit representations define a class of R implications. Some reasonable implication operations have been proposed, such as Yager's a^b, that are difficult to represent as S or R implications. For such operations, a new class of representations has recently been proposed, called A implications, for which the relationship between implications and the basic operations &, ∨, and ¬ is even more complicated. A natural question is: Is this complexity really necessary? In other words, is it true that A operations cannot be described as S or R operations, or they can, but we simply have not found these representations? In this paper we show that yes, the complexity is necessary, because there are operations that cannot be represented in a simpler form. © 1998 John Wiley & Sons, Inc.     

Setting up an online database: Information can be a useful source of revenue

Holders of information can realise the value of their databases by offering computer access to it. The database can be held on an inhouse computer or on a bureau machine. There are a number of points which help to decide which option is best.     

Context-free languages can be accepted with absolutely no space overhead

We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits’ own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such overhead-free machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.     

A distributed event-triggered dynamic average consensus scheme with a time-varying threshold and its application in DC microgrid

We propose a distributed event-triggered dynamic average consensus (DAC) scheme with a time-varying threshold for a multi-agent system (MAS) in a directed graph. In this scheme, each agent is not required to monitor its neighbors in real time, and a threshold is chosen related to consensus performance directly in an MAS, where the threshold is adjusted adaptively according to average consensus performance. Also, we introduce a bounded and monotonically increasing function in a time-varying threshold, and this function is for guaranteeing the value of a threshold to locate in an appropriate range. Stability analysis shows that the tracking error is eventually bounded and the MAS achieves DAC without Zeno behaviors. Furthermore, the proposed event-triggered DAC scheme is applied to voltage restoration and adjustable current sharing in DC microgrid. The effectiveness of the proposed scheme is verified by two examples.     

Electing a leader in a ring with link failures

Summary We investigate the message complexity of electing a leader in a ring of asynchronous processors. Our work deviates from the previous works on electing a leader in that we consider the effect of link failures. A link is said to fail if some message sent through it never reaches its destination. We distinguish the case where n is known from the case n unknown. Our main result is a O(n · log n) algorithm for electing a leader on a n-processor ring (the case n is known).