DARE 2022: 2nd Workshop on Distributed Algorithms on Realistic Network Models

The PODC community focuses on theoretical models and tools to understand distributed computing. A challenge is to develop novel and powerful mathematical frameworks that also have impact outside theoretical computer science. The goal of this workshop is to tackle this challenge in the area of distributed computing on networks of different origin.

In the last decades, this area has been flourishing on the theoretical side, and it is meaningful to evaluate the relevance of these results on the practical side, and to give new directions for future research originating from practice.

Marthe Bonamy

Distributed discharging: global guarantees of local behaviors

Distributed discharging: global guarantees of local behaviors

Abstract tbd

Marthe Bonamy received her PhD in 2015 from University of Montpellier, and since then she has been a CNRS researcher in Bordeaux. She studies combinatorics, and is a specialist of both structural and algorithmic graph theory. She recently successfully brought graph theory techniques to distributed graph algorithms, in particular for structured networks, such as planar graphs.

Marián Boguñá Espinal

A brief introduction to Network Geometry

A brief introduction to Network Geometry

The main hypothesis of network geometry states that the architecture of real complex networks has a geometric origin. The nodes of the complex network can be characterized by their positions in an underlying metric space so that the observable network topology—abstracting their patterns of interactions—is then a reflection of distances in this space. This simple idea led to the development of a very general framework able to explain the most ubiquitous topological properties of real networks, namely, degree heterogeneity, the small-world property, and high levels of clustering. Network geometry is also able to explain in a very natural way other non-trivial properties, like self-similarity and community structure, their navigability properties, and is the basis for the definition of a renormalization group in complex networks. In this talk, I will give a brief introduction to this exciting topic and I will highlight some of its most interesting applications.

M. Boguñá is a full professor at the Departament of Condensed Matter Physics of the University of Barcelona. He obtained his PhD in Physics in 1998. In 1999, he moved to the USA to do a postdoctoral stay at the National Institutes of Health, Washington DC. After this period, he moved back to Barcelona where, in 2003, he was awarded a Ramón y Cajal fellowship. He got the tenure position at the end of 2008. During this period, he has also spent several months in the USA as invited guest scientist at Indiana University. M. Boguñá has written over 90 publications in major peer reviewed international scientific journals, book chapters, and conference proceedings. In January 2008, he obtained the Outstanding Referee award of the American Physical Society. He was awarded as ICREA Academia researcher in 2010, 2015 and 2020. Since January 2013, he serves as an editorial board member for Scientific Reports. His research interests are focused on the study of complex systems. In particular, those systems made up of a large number of units that interact through complex topologies and, therefore, are suitable to be studied using statistical physics tools. Such systems are ubiquitous and can be found in very diverse fields: societies at the large scale, cellular networks, or communication networks like the Internet, to name just a few. One of the major challenges in this field is the understanding of the coupling between the complex topologies shown by these type of systems and the functions they perform. M. Boguñá is one of the major proponents of the new field of Network Geometry, a theory aiming at finding the geometric origin of the discrete structures underlying complex systems.

Silvio Lattanzi

Large Scale Algorithms, Clustering and the MPC model

Large Scale Algorithms, Clustering and the MPC model

In modern computational tasks, we often need to cope with very large datasets. Thus, it becomes increasingly more important to design efficient parallel algorithms. Obtaining such algorithms is often challenging because many classic algorithms are inherently sequential, e.g., their structure is defined iteratively and in an adaptive manner. In this talk, we discuss the classic massively parallel computation (MPC) model and some techniques to obtain efficient algorithms for it with a focus on clustering problems on graphs and metric spaces.

Silvio Lattanzi is a Research Scientist at Google since January 2011. He is part of the Algorithm & Optimization group. He was based in Google New York(2011-2017), in Google Zurich(2017-2021), and is currently based in Barcelona. He received his PhD from Sapienza University of Rome under the supervision of Alessandro Panconesi. His main research interests are in the areas of algorithms, machine learning and information retrieval.

Yvonne-Anne Pignolet

Catching up on the Internet Computer

Catching up on the Internet Computer

In May 2021 the internet computer, a web-speed smart contract and app platform, went live. After a bit more a year, the internet computer hosts more than 60'000 smart contract apps and serves more than 1 million users, providing a plethora of services, ranging from social media and chat applications to DeFi and NFTs. Thanks to its governance system and support for new service and business models, the internet computer has the potential to revolutionize how we develop, host and use apps. Naturally, such a system accrues a vast amount of data as well. In order to provide a reliable service despite some of the machines failing or misbehaving, it is hence crucial to provide efficient mechanisms for machines to (re)-join the system. In this talk I discuss the problems and challenges the Internet Computer faces to enable machines to catch up quickly and present our approach to tackle them.

Yvonne-Anne Pignolet's work is centered around distributed systems, ranging from the design and analysis of algorithms for reliable and efficient distributed systems despite failures and malicious behaviour to complex network analysis. After her PhD at ETH Zurich in 2009 she was a postdoc at IBM Research Zurich and Ben Gurion University, Be'er Sheva. She worked for 8 years at ABB Corporate Research, Switzerland mostly devoted to research on communication systems for industrial and power systems, as a Principal Scientist in her final role. In 2019, she joined DFINITY, where she leads teams of researchers and engineers building and improving the Internet Computer.

Start | Length | Speaker |
---|---|---|

9:00 | 0:10 | Welcome |

9:10 | 0:50 | Marián Boguñá Espinal |

10:00 | 0:30 | Coffee Break |

10:30 | 0:50 | Yvonne-Anne Pignolet |

11:20 | 0:40 | Discussion |

12:00 | 1:30 | Lunch Break |

13:30 | 0:50 | Marthe Bonamy |

14:20 | 0:50 | Silvio Lattanzi |

15:10 | 0:10 | Goodbye |

Send us an email!

Thank to flyingfisch and their pen.