Baras gives semi-plenary lecture at NTNS2010

Professor John Baras (ECE/ISR) gave an invited semi-plenary lecture on July 8, 2010 at the 19th International Symposium on the Mathematical Theory of Networks and Systems (MTNS2010).

The Symposium was held in Budapest, Hungary and hosted by Eötvös Loránd University (ELTE) and MTA SZTAKI (Computer and Automation Research Institute, Hungarian Academy of Sciences). The MTNS Symposia represent a prestigious prime conference series, held every two years, in the general area of mathematical systems theory. The first MTNS was held at the University of Maryland College Par in 1972. MTNS traditionally covers areas involving a wide range of research directions in mathematical systems, networks and control theory, with emphasis on new challenges and potential applications. A prime objective of the MTNS 2010 Symposium is to explore and present mathematics as a key technology for the 21st century.

Dr. Baras’ lecture was entitled “Dynamic 'Magic' Graphs in Cooperative Networked Systems”. Dr. Baras described emerging models for the ubiquitous networked systems that appear in so many current science and technology areas including infrastructure/communication networks, social/economic networks and biological networks. He first described his recently developed novel framework for modeling and analysis of dynamic networked systems that utilizes several interacting dynamic hypergraphs. The simplest of the new class of models utilizes two hypergraphs: the collaboration one and the communication one. The collaboration hypergraph describes the time varying relation of collaboration between the systems; that is it answers the question: who has to collaborate with whom and when. The communication hypergraph describes the time varying communications that occur between the systems; that is it answers the question: who has to communicate with whom and when. Dr. Baras next presented a new fundamental way for analyzing networked control systems as networks of collaborating agents. The new fundamental view is that agents in such a network are dynamic entities that collaborate because via collaboration they can accomplish objectives and goals much better than working alone, or even accomplish objectives that they cannot achieve alone at all. Yet the benefits derived from such collaboration require some costs (or expenditures), for example due to communications. Or in equivalent terms, the collaboration is subject to constraints such as energy, communication, trust, organizational relations and structures. Understanding and quantifying this tradeoff between the benefits vs. the costs of collaboration, leads to new methods that can be used to analyze, design and control/operate networked control systems. He then described the dynamic constrained coalitional games mathematical framework, he has developed and demonstrated how the metrics of benefit and cost control the dynamics, their convergence or divergence, and the structure of the resulting equilibria (i.e. generated networks).

He then proceeded to describe the effects of the communication topology on the performance, and in particular the speed of convergence, of various distributed tasks in networked systems and demonstrated how small world graphs, and expander graphs emerge as efficient graphs for supporting distributed task execution. Expander graphs are graphs that have locally rich neighborhood connectivity but are globally sparse. He linked these results to practical applications such as energy efficiency, reputations in social networks and trust-aware networked systems. He described his results as the first results towards establishing a taxonomy of architecture vs. behavior in networked systems and described various inspirational paradigms from biology ranging from collaborating insects, to cell networks to the architecture of neural networks in mammalian brains. The “magic” graphs of his title are precisely these expander graphs that have a rich set of properties beneficial to collaborative systems and which were first discovered and analyzed in coding theory by Pinsker circa 1973, and have played an important role in coding theory including recent proofs of results on the famous Low Density Parity Codes studied by Gallager circa 1963. He reviewed the relation of expander graphs to minimal complexity electronic circuit design, design of good error correcting nodes, and deterministic error amplification in minimally randomized algorithms. He then described various methods to construct expander graphs, including optimization, perturbation and ZigZag product algorithms. Dr. Baras concluded by describing a rich set of theoretical and application problems emerging by applying expander graphs to networked systems.

Published July 10, 2010