Distributed Consensus on Boolean Information
Estimation and Control of Networked Systems, Volume # 1 | Part# 1
Fagiolini, Adriano; Martini, Simone; Dubbini, Nevio; Bicchi, Antonio
Digital Object Identifier (DOI)
Consensus problems; Decentralized algorithms for computation over sensor networks; Coordinated control and estimation over networks
In this paper we study the convergence towards consensus on information in a distributed system of agents communicating over a network. The particularity of this study is that the information on which the consensus is seeked is not represented by real numbers, rather by logical values or sets. Whereas the problems of allowing a network of agents to reach a consensus on logical functions of input events, and that of agreeing on set--valued information, have been separately addressed in previous work, in this paper we show that these problems can indeed be attacked in a unified way in the framework of Boolean distributed information systems. Based on a notion of contractivity for Boolean dynamical systems, a necessary and sufficient condition ensuring the global convergence toward a unique equilibrium point is presented. This result can be seen as a first step toward the definition of a unified framework to uniformly address all consensus problems on Boolean algebras.
REFERENCES J. Cortęes, S. Martęűnez, T. KarataŁs, and F. Bullo. Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 20(2):243–255, 2004. M. Di Marco, A. Garulli, A. Giannitrapani, and A. Vi- cino. Simultaneous localization and map building for a team of cooperating robots: a set membership approach. IEEE Trans. on Robotics and Automation, 19(2):238– 249, 2003. A. Fagiolini, M. Pellinacci, G. Valenti, G. Dini, and A. Bic- chi. Consensus based Distributed Intrusion Detection for Multi Robot Systems. In IEEE Intl. Conf. on Robotics and Automation, pages 120–127, 2008a. A. Fagiolini, E.M. Visibelli, and A. Bicchi. Logical Consen- sus for Distributed Network Agreement. In IEEE Conf. on Decision and Control, pages 5250–5255, 2008b. A. Fagiolini, S. Martini, and A. Bicchi. Set–valued consen- sus for distributed clock synchronization. IEEE Conf. on Automation Science and Engineering, 2009. J.A. Fax and R.M. Murray. Information Ŗow and cooper- ative control of vehicle formations. IEEE Transactions on Automatic Control, 49(9):1465–1476, Sept. 2004. P. Frasca, R. Carli, F. Fagnani, and S. Zampieri. Average consensus on networks with quantized communication. Intl. Journal of Robust and Nonlinear Control, 2008. L. Greco, M. Gaeta, and B. Piccoli. Deployment of sensors in a network-like environment. In IEEE Conf. on Decision and Control, 2008, pages 4257–4262, 2008. A. Jadbabaie, J. Lin, and A.S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Con- trol, 48(6):988–1001, 2003. K. Marzullo. Maintaining the time in a distributed system: An example of a loosely-coupled distributed service. Dissert. Abstracts Intl. Part B: Science and Engineering, 46(1), 1985. D. Mills. Internet time synchronization: the network time protocol. IEEE Trans. on Comm., 39(10), Oct 1991. R. Olfati-Saber, J.A. Fax, and R.M. Murray. Consensus and cooperation in networked multi-agent systems. Pro- ceedings of the IEEE, 95(1):215, 2007. F. Robert. Thęeor`emes de Perron–Frobenius et Stein– Rosenberg Booleens. Linear Algebra and its Applica- tions, 19:237–250, 1978. F. Robert. Itęerations sur des ensembles řnis convergence d’automates cellulaires contractants. Linear Algebra and its Applications, 29:393–412, 1980. NV Subrahmanyam. Boolean vector spaces. I. Mathema- tische Zeitschrift, 83(5):422–433, 1964.