🪄 Workshop on Analysis of Network Dynamics 🪄

Lélia Blin (Université Paris Cité)

TBA.

Yuval Emek  (Technion)

Uniform Distributed Graph Algorithms
The term "uniform computational model" typically refers to an algorithm designer who is oblivious to the parameters (e.g., size) of the input instances on which the algorithm is to be invoked. This is a desired feature since it facilitates the deployment of algorithms in a one-size-fits-all manner. In distributed graph algorithms, uniformity has an additional angle: more often than not, the global parameters of the input graphs are not readily revealed to the individual decision-making units (the nodes) even after the algorithm is invoked. Therefore, the design of uniform distributed algorithms raises certain algorithmic challenges which are less common in other domains. In this talk, we will discuss those challenges as well as some recent advances in the design of uniform algorithms for fundamental distributed tasks.
The talk will be self-contained.

Bio: Yuval Emek is a professor at the Faculty of Data and Decision Sciences in the Technion – Israel Institute of Technology, where he conducts his research on algorithmic aspects of coping with uncertainty. He graduated (summa cum laude) from the Technion with a bachelor degree in computer science (2000) and completed his master studies (2003) and PhD (2008) in computer science and applied mathematics at the Weizmann Institute of Science under the supervision of David Peleg. Following that, he held post-doc positions at Tel Aviv University (2008-2009), Microsoft (2009-2010), and ETH Zurich (2010-2013), before joining the Technion as a faculty member in 2013. Between 2021-2022, Yuval was a visiting Assoc. Prof. at the Department of Computer Science in the University of British Columbia. 

Yuval is the author of more than 30 journal papers that were published in prestigious venues such as JACM, SICOMP, TALG, and Distributed Computing; and more than 65 conference papers that appeared in the proceedings of competitive conferences such as STOC, SODA, PODC, and ICALP. He has served on the program and steering committees of dozens of conferences and workshops, including PODC, DISC, ICALP, and SODA, and he is currently an editorial board member of Information and Computation.
In his research, Yuval focuses on combinatorial optimization problems with a special interest in network algorithms, particularly when the data is provided in an online fashion or when it is distributed across the network and requires decentralized decision making. Yuval's theoretical research is motivated by applications in diverse domains ranging from large scale telecommunication systems and transportation networks to nano-computing and distributed biological processes.

Andrea Richa (Arizona State University)

Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots

Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute distributed, local algorithms to self-organize and solve system-wide problems, such as movement, reconfiguration, and coordination. Self-organizing particle systems (SOPS) have many interesting potential applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. We describe some of our work on the algorithmic foundations of programmable matter, investigating how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles: We utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into distributed, local algorithms for SOPS that drive the desired emergent collective behavior for the problems of compression, separation, and foraging, among others. We further establish the notion of algorithmic matter, where we leverage standard binary computation, as well as physical characteristics of the robots and interactions with the environment in order to implement our micro-level algorithms in actual testbeds composed of robots that are not capable of any standard computation. We conclude by addressing full concurrency and asynchrony in SOPS.

Bio: Andrea W. Richa was inducted as 2022 President's Professor at Arizona State University (ASU), one of the most prestigious faculty honors bestowed by the university.  She is a Professor of Computer Science and Engineering at the School for Computing and Augmented Intelligence (SCAI) and an associate faculty at the Center for Bio-computing, Security and Society at the Biodesign Institute at ASU. She recently 

served as SCAI's Interim Associate Director. Her main areas of expertise are in distributed and network algorithms and computing in general. More recently, she has focused on developing the algorithmic foundations on what has been coined as programmable matter, through her work on self-organizing particle systems (SOPS). Her work has been widely cited, and includes, besides SOPS, work on bio-inspired distributed algorithms, distributed load balancing, packet routing, wireless network modeling and topology control, wireless jamming, data mule networks, underwater optical networking, and distributed hash tables (DHTs). She received the 2024 ASU Fulton Undergraduate Research Initiative Outstanding Faculty Mentor Award, the 2021 ASU Faculty Women Association Outstanding Mentor Award and the 2017 SCAI Best Senior Researcher award. She is currently the recipient of a DoD MURI award and was the recipient of an NSF CAREER Award, among others; she was also the keynote speaker and program and general chair of several prestigious conferences. For more on her work and that of her students, please check http://sops.engineering.asu.edu .