2013 Poster Sessions : Time, Energy and Resilience: Fundamental Limitations of Distributed Decision-Making on Hybrid Networks?

Student Name : Federico Rossi
Advisor : Marco Pavone
Research Areas: Information Systems
Distributed consensus on cyber-physical networks is a ubiquitous problem, with applications as diverse as state estimation, formation control of robotic vehicles and cooperative task allocation. Yet most recent efforts have concentrated either on proposing and analyzing specific algorithms or on studying the properties and fundamental limitations of average-based algorithms, a subclass of consensus algorithms in which nodes average their physical state with their neighbors' at each time instant.

In our contribution, we analyze fundamental limitations in terms of time and communication complexity for all distributed consensus algorithms on cyber-physical networks.

We show that, if the network topology does not vary in time, convex consensus is at least as hard as leader election in terms of time and communication complexity.

On time-varying Markov networks, we prove an analytical upper bound on the time complexity and a lower bound on the communication complexity of flooding algorithms on a class of structured Markov networks; we then use this result to relate time and communication complexity on generic Markov networks and we explore tightness of these bounds via numerical simulations.

We also explore complex decision-making via Linear Temporal Logic on cyber-physical networks, showing how LTL can be used to reach agreement on complex predicates in hybrid networks.

Federico Rossi is a Visiting Student Researcher at professor Pavone's Autonomous Systems Lab at Stanford University's Department of Aeronautics and Astronautics. His current research focuses on identifying fundamental limitations of distributed control for aerospace applications. He is completing his M.Sc. in Space Engineering at Politecnico di Milano, Italy, where he received his B.Sc. in Aerospace Engineering in 2010. His research interests include distributed control systems, optimization and robotics.