Distributed control over structured and packet‐dropping networks

In this paper we consider distributed control of n dynamic agents to optimize an overall system performance metric. Due to limited communication resources, there exist structured interconnections among the agents and the interest is placed on synthesizing a suitably distributed control law to provide a given performance level. Based on a Youla–Kucera (Y–K) parameterization approach, the problem of designing a distributed controller to deliver given performance levels for different network topologies is shown to be convex in the Y–K parameter Q. Furthermore, if in addition to structured interconnections, packet drops exist in information transmission among the agents, we provide convex conditions to guarantee mean square (MS) stability and to optimize ℋ︁₂ system performance. The proposed method is also extended to deal with systems of triangular structure. Copyright © 2007 John Wiley & Sons, Ltd.     

面向agent的程序设计语言:DL-1

为适应协作分布式问题求解（ＣＤＰＳ）研究和应用的需要，我们研制了面向ａｇｅｎｔ的程序设计语言：ＤＬ－１语言。ＤＬ－１语言由二部分组成：ＤＬ－１／ｓｙｓｔｅｍ和ＤＬ－１／ａｇｅｎｔ。ＤＬ－１／ｓｙｓｔｅｍ主要用于显式地描述ＣＤＰＳ系统的行政管理结构。ＤＬ－１／ａｇｅｎｔ主要用于描述ＣＤＰＳ系统的ａｇｅｎｔ，并允许用户在描述ａｇｅｎｔ的同时，描述ＣＤＰＳ系统的问题求解结构。     

Distributed primal–dual stochastic subgradient algorithms for multi‐agent optimization under inequality constraints

We consider the multi‐agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal–dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as in the number of n agents. Copyright © 2012 John Wiley & Sons, Ltd.     

Distributed Monitoring of Concurrent and Asynchronous Systems*

In this paper we study the diagnosis of distributed asynchronous systems with concurrency. Diagnosis is performed by a peer-to-peer distributed architecture of supervisors. Our approach relies on Petri net unfoldings and event structures, as means to manipulate trajectories of systems with concurrency. This article is an extended version of the paper with same title, which appeared as a plenary address in the Proceedings of CONCUR2003.*This work was supported by the RNRT project MAGDA2, funded by the Ministère de la Recherche; other partners of the project are France Telecom R&D, Alcatel, Ilog, and Paris- Nord University.     

Reasoning about action and change

Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability.     

Building Scalable Electronic Market Places Using HyperQuery-Based Distributed Query Processing

Flexible distributed query processing capabilities are an important prerequisite for building scalable Internet applications, such as electronic Business-to-Business (B2B) market places. Architecting an electronic market place in a conventional data warehouse-like approach by integrating all the data from all participating enterprises in one centralized repository incurs severe problems: stale data, data security threats, administration overhead, inflexibility during query processing, etc. In this paper we present a new framework for dynamic distributed query processing based on so-called HyperQueries which are essentially query evaluation sub-plans sitting behind hyperlinks. Our approach facilitates the pre-materialization of static data at the market place whereas the dynamic data remains at the data sources. In contrast to traditional data integration systems, our approach executes essential (dynamic) parts of the data-integrating views at the data sources. The other, more static parts of the data are integrated à priori at the central portal, e.g., the market place. The portal serves as an intermediary between clients and data providers which execute their sub-queries referenced via hyperlinks. The hyperlinks are embedded as attribute values within data objects of the intermediarys database. Retrieving such a virtual object will execute the referenced HyperQuery in order to materialize the missing data. We illustrate the flexibility of this distributed query processing architecture in the context of B2B electronic market places with an example derived from the car manufacturing industry.Based on these HyperQueries, we propose a reference architecture for building scalable and dynamic electronic market places. All administrative tasks in such a distributed B2B market place are modeled as Web services and are initiated decentrally by the participants. Thus, sensitive data remains under the full control of the data providers. We describe optimization and implementation issues to obtain an efficient and highly flexible data integration platform for electronic market places. All proposed techniques have been fully implemented in our QueryFlow prototype system which served as the platform for our performance evaluation.     

Distributed robust control of uncertain linear multi‐agent systems

In this paper, the distributed H _∞ robust control problem synthesized with transient performance is investigated for a group of autonomous agents governed by uncertain general linear node dynamics. Based on the relative information between neighboring agents and some information of other agents, distributed state‐feedback and observer‐type output‐feedback control protocols are designed and analyzed, respectively. By using tools from robust control theory, conditions for the existence of controllers for solving such a problem are established. It is shown that the problem of distributed H _∞ robust control synthesized with transient performance can be converted to the H _∞ control problem synthesized with transient performance for decoupled linear systems of the same low dimensions. Finally, simulation examples are provided to illustrate the effectiveness of the design. Copyright © 2014 John Wiley & Sons, Ltd.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define (P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy . HeresQ denotes a scaling ofQ by the factors, andQ,Q are some translates ofQ. This function gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.)For integerk 3, define (k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with (P, Q) (k). Among other results, we prove that 2.118 ... <-(3) 2.25 and (k) = 1 + (k ^–2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes (T, P) among triangles. However, in linear time we can find a trianglet with (t, P)<-2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.Work of all authors was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Rudolf Fleischer and Kurt Mehlhorn acknowledge also DFG (Grant SPP Me 620/6). Chee Yap acknowledges also DFG (Grant Be 142/46-1) and NSF (Grants DCR-84-01898 and CCR-87-03458). This research was performed when Günter Rote and Chee Yap were at the Freie Universität Berlin.     

A Lie-Group Formulation of Kinematics and Dynamics of Constrained MBS and Its Application to Analytical Mechanics

A Lie-group formulation for the kinematics and dynamics ofholonomic constrained mechanical systems (CMS) is presented. The kinematics ofrigid multibody systems (MBS) is described in terms of the screw system of theMBS. Using Lie-algebraic properties of screw algebra, isomorphicto se(3), allows a purely algebraic derivation of the Lagrangian motion equations. As such the Lie-group SE(3) ... SE(3) (n copies) is theambient space of a MBS consisting of n rigid bodies. Any parameterizationof the ambient space corresponds to a chart on the MBS configuration space ⁿ. The key to combine differential geometric and Lie-algebraic approaches is the existence of kinematic basic functions whichare push forward maps from the tangent bundle Tⁿ to the Lie-algebra of the ambient space.MBS with kinematic loops are CMS subject to holonomic constraints, holonomicCMS. Constraint equations are formulated on the ambient space based on achart on ⁿ. Explicitly considering the Lie-algebraicstructure of se(3) as semidirect sum of the algebra oftranslations and rotations enables to reduce the number of holonomicconstraints for cut joints. It is shown that third order Lie-brackets are sufficient to obtain any subalgebra of se(3).Differential geometric aspects of the kinematics of MBS with open and closedkinematic chains are considered. The distribution in any configuration andthe subalgebra generated by the screw system of a mechanism is the key todetect singularities and to analyze the structure of the set of singularpoints.     

Distributed robust control of linear multi-agent systems with parameter uncertainties

This article considers the distributed robust control problems of uncertain linear multi-agent systems with undirected communication topologies. It is assumed that the agents have identical nominal dynamics while subject to different norm-bounded parameter uncertainties, leading to weakly heterogeneous multi-agent systems. Distributed controllers are designed for both continuous- and discrete-time multi-agent systems, based on the relative states of neighbouring agents and a subset of absolute states of the agents. It is shown for both the continuous- and discrete-time cases that the distributed robust control problems under such controllers in the sense of quadratic stability are equivalent to the H _∞ control problems of a set of decoupled linear systems having the same dimensions as a single agent. A two-step algorithm is presented to construct the distributed controller for the continuous-time case, which does not involve any conservatism and meanwhile decouples the feedback gain design from the communication topology. Furthermore, a sufficient existence condition in terms of linear matrix inequalities is derived for the distributed discrete-time controller. Finally, the distributed robust H _∞ control problems of uncertain linear multi-agent systems subject to external disturbances are discussed.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

A Distributed Approach of a Threshold Certificate-Based Encryption Scheme with No Trusted Entities

ABSTRACT

The distributed paradigm as manifested in distributed networks, calls for a different way from the traditional client-server model for providing Trusted third party (TTP) services to strengthen security. Certificate Authorities (CAs) are among the most common such TTP. Generating certified keys and manage certification information (the basic functionality of a CA) in a fully distributed manner is a key challenge in the distributed IT environment. Current approaches are based on the use of trusted entities within the distributed system that constitute single points of failure and follow complex certificate management and revocation mechanisms capable of hindering their adoption in a large scale. The hardware resources cost of each distributed system member committed to realizing and maintaining such certificate authority system can be high. Furthermore, distributed CA approaches lack flexibility when it come to dynamic member behavior such as dynamic member joining or leaving the system, since they employ complex, computational intensive mechanisms for retaining the CA consistency during such activity. In this paper, we propose the combination of a distributed key generation threshold cryptography scheme along with an efficient secure certificate-based encryption scheme to provide a solution that matches the above problems. The outcome of this proposal is a distributed Threshold Certificate-Based Encryption Scheme that has no need for any centralized trusted entity to create, and split secrets or distribute keys-certificates at any point during its operating cycle. The proposed scheme has few requirements concerning certificate management due to its inherited Certificate-based Encryption features which enables the scheme's participants to use their certificates as keys and has an easy participant addition-removal mechanism to support dynamic network environments. Extending the work done in (Fournaris, 2012 Fournaris, A. P. 2012. Distributed threshold certificate based encryption scheme with no trusted dealer. SECRYPT, 2012: 314–320.  [Google Scholar]), in this paper the proposed distributed Certificate Authority and encryption/decryption scheme is described and analyzed, participant addition and removal mechanisms as detailed and the scheme's security and performance is discussed. Performance characterization reveals that our scheme is very efficient in terms of computational intensive and resource constraining operations like Elliptic Curve point multiplication and bi-linear pairing.     

Distributed extended state observer design and output feedback anti-disturbance control for nonlinear interconnected systems: A dynamic memory event-triggered mechanism

This paper investigates a distributed extended state observer design and output feedback anti-disturbance control for nonlinear interconnected systems (ISs) with multiple disturbances. First, a distributed extended state observer with a sparse observer communication network is established to estimate the system states and external disturbances. Then, an output feedback controller with a disturbance compensation (DC) item is designed, where a novel dynamic memory event-triggered mechanism (DMETM) is proposed to save communication resources. Third, under the proposed controller, the closed-loop signals are bounded and the system states and the estimation errors converge to zero. Additionally, the system outputs satisfy $$ performance. Finally, the simulation examples demonstrate the effectiveness of the DMETM in reducing the number of data transmissions compared to the dynamic event-triggered mechanism (ETM).     

Distributed H∞ consensus of second‐order multiagent systems with nonconvex constraints

In this paper, the distributed H_∞ consensus problem for second‐order multiagent systems is studied. We first propose a distributed control algorithm based on local information. In the presence of external disturbances, some sufficient conditions are then derived to guarantee that all agents reach the distributed H_∞ consensus, and meanwhile, the inputs of agents always stay in the nonconvex sets, making the results in this paper more practical. Finally, a numerical simulation is provided to show the effectiveness of the results.     

A Priori Convergence Theory for Reduced-Basis Approximations of Single-Parameter Elliptic Partial Differential Equations

We consider Lagrangian reduced-basis methods for single-parameter symmetric coercive elliptic partial differential equations. We show that, for a logarithmic-(quasi-)uniform distribution of sample points, the reduced–basis approximation converges exponentially to the exact solution uniformly in parameter space. Furthermore, the convergence rate depends only weakly on the continuity-coercivity ratio of the operator: thus very low-dimensional approximations yield accurate solutions even for very wide parametric ranges. Numerical tests (reported elsewhere) corroborate the theoretical predictions.     

Distributed filtering in sensor networks with randomly occurring saturations and successive packet dropouts

This paper is concerned with the distributed filtering problem for a class of nonlinear systems with randomly occurring sensor saturations (ROSS) and successive packet dropouts in sensor networks. The issue of ROSS is brought up to account for the random nature of sensor saturations in a networked environment of sensors, and accordingly, a novel sensor model is proposed to describe both the ROSS and successive packet dropouts within a unified framework. Two sets of Bernoulli distributed white sequences are introduced to govern the random occurrences of the sensor saturations and successive packet dropouts. Through available output measurements from not only the individual sensor but also its neighboring sensors, a sufficient condition is established for the desired distributed filter to ensure that the filtering dynamics is exponentially mean‐square stable and the prescribed performance constraint is satisfied. The solution of the distributed filter gains is characterized by solving an auxiliary convex optimization problem. Finally, a simulation example is provided to show the effectiveness of the proposed filtering scheme. Copyright © 2013 John Wiley & Sons, Ltd.     

Distributed event-triggered output regulation of multi-agent systems

Motivated by the future use of embedded microprocessors with limited resources and limited computational resources, the distributed output regulation with event-driven strategies problem of linear multi-agent systems is considered in this paper. The main task is to design distributed feedback by employing event-triggered technique for multi-agent systems such that all agents can track an active leader, and/or distributed disturbance rejection. Both leader and disturbance are generated by some external system (exosystem). Both distributed static and dynamic feedback with event-triggered strategy are constructed here. Then, the input-to-state stability of the closed-loop multi-agent system is analysed. Finally, a numerical example is given to validate the proposed control.     

Increasing Workplace Independence for People with Cognitive Disabilities by Leveraging Distributed Cognition among Caregivers and Clients

This paper describes a group configuration that is currently employed to support the everyday living and working activities of people with cognitive disabilities. A client receiving face-to-face, often one-to-one, assistance from a dedicated human job coach is characteristic of this traditional configuration. We compare it with other group configurations that are used in cooperative and distributed work practices and propose an alternative configuration titled active distributed support system. In so doing, we highlight requirements that are unique to task support for people with cognitive disabilities. In particular, we assert that the knowledge of how to perform such activities is shared not only among people, but also between people and artifacts. There is a great potential for innovative uses of ubiquitous and mobile technologies to support these activities. A survey of technologies that have been developed to provide these individuals with greater levels of independence is then presented. These endeavors often attempt to replace human job coaches with computational cognitive aids. We discuss some limitations of such approaches and present a model and prototype that extends the computational job coach by incorporating human caregivers in a distributed one-to-many support system.     

Checking Combinational Equivalence of Speed-Independent Circuits

We introduce the notion of combinational equivalence to relate two speed-independent asynchronous (sequential) circuits: a golden hazard-free circuit C ₁ and a target circuit C ₂ that can be derived from C ₁ through only combinational decomposition and extraction. Both circuits are assumed to be networks of single-output basic gates; multiple output gates such as arbiters, toggles, and dual-rail function blocks are not considered. We say that the circuits are combinationally equivalent if the decomposition and extraction preserves the essential functionality of the combinational blocks in the circuit and does not introduce hazards. The paper's focus is the bottleneck of the verification procedure, checking whether C ₂ is hazard-free. We show that C ₂ is hazard-free if and only if all of its signals are monotonic and acknowledged . We then show how cubes that approximate sets of reachable circuit states can be used to give sufficient conditions for monotonicity and acknowledgement. These sufficient conditions are used to develop a verification technique for combinational equivalence that can be exponentially faster than applying traditional, more general verification techniques. This result can be useful for verifying logic synthesis and technology mapping procedures.