In his professional and personal life, Sergio Rajsbaum is an eternally curious person. He is interested in a variety of topics related to computer science and mathematics, but he also plays classical guitar, likes racquet sports and is passionate about arts. He admits not being an expert in any of his hobbies, rather, he has learned over time to admire people who excel in a discipline. Meeting with Sergio Rajsbaum, visiting IRIF for a year.

“I try to understand the possibilities of what can be done, and the limits of how fast and how reliably it can be done, by a set of processes collaborating with each other, forming a distributed systems. We have been discovering more recently that the foundation to this field provided by algebraic topology exposes connections with other areas.” Sergio Rajsbaum, one-year visitor at IRIF | Pole Algorithms and discrete structures - Team Distributed computing

I have always been interested in algorithms and computer systems composed of processes that interact with each other. In UNAM Mexico, where I did my undergrad in 1985, I studied computer engineering and chose for thesis subject “Parallel Computing With Microprocessors”. That was my first experience of getting into the topic. I did my PhD in computer science in the Israel Institute of Technology- Technion. My PhD advisor proposed me three different topics: Graph Algorithms, Cryptography and Distributed Computing. I ended up selecting Distributed Computing but I have always been exposed to the other two topics in my academic career. I did a postdoc in the Computer Science department of MIT with Nancy Lynch. My research first focused on clock synchronization for computer networks. I tried to understand how good clocks can be synchronized. For many tasks, it is very useful to have a common notion of time. For example, when a process has entered by error into a loop, how do we know when to stop it? There is a protocol in the internet for clock synchronization, the Network Time Protocol (NTP). The protocol is used to distribute the time of extremely precise atomic clocks all over the network. I wrote at STOC 1994 with Boaz Patt-Shamir providing a precise characterization of how well clocks can be synchronized, as a function of given upper and lower bounds of link delays and local clock drifts.
During the second part of my postdoc at MIT, I had the good luck of meeting Maurice Herlihy, who had just announced in the ACM STOC 1993 conference, together with Nir Shavit, a remarkable connection between distributed computing and algebra topology, that merited the Godel Prize. They showed that computation by an asynchrnous concurrent system where processes communicate by reading and writing shared registers is in fact a continuous deformation of its inputs as represented by a simplicial complex, with the sole effect of subdividing it. We published a paper in ACM PODC 1994 showing that the connection with algebraic topology was even deeper: the effect of having in the system objects more powerful than read/write registers is that the deformation of the input complex is no longer perfect, in the sense that higher dimensional holes can appear in the subdivision. This was the first result of a long collaboration, including mutual visits to Mexico and Brown University, that has continued until today, developing a scientific foundation for distributed computing of a topological nature, spanning shared memory, message passing systems, both synchronous and asynchronous, with both crash failures and a Byzantine failures, including even robot systems. Although I have worked on many other problems, the topological approach has shaped my way of thinking about a wide variety of multi-agent interaction situations, including a recent work on Arrow’s impossibility theorem. It is one of the reasons I have been collaborating with IRIF over the years, and it led to the current ANR project Distributed Network Computing through the Lens of Combinatorial Topology- DUCAT with members in LIS Marseille, Telecom Paris and LIP6.

I try to understand the possibilities of what can be done, and the limits of how fast and how reliably it can be done, by a set of processes collaborating with each other, forming a distributed systems. We have been discovering more recently that the foundation to this field provided by algebraic topology exposes connections with other areas. In a paper in ACM PODC 2022 Armajac Raventos and I showed that one of the central results of social choice theory, Arrow’s impossibility result, is in fact of a topological nature. This was first discovered by Baryshnikov in 1993, but this result remained undeveloped, until now that we simplified it and explained, and used it to obtain the first restricted domain characterizations. Arrow proved his result in 1950, showing the impossibility of designing a voting system satisfying some seemingly minimal natural axioms, gave birth to the modern field of social choice. We discovered another connection with a different area with Eric Goubault of Ecole Polytechnique: multi-agent epistemic logic. We have published several papers, with the first results announced in GANDALF 2018 (and its journal version), where we showed that Kripke models have implicit topological information. This led to a series of workshops together with researchers interested in topological methods in logic starting with one in IACAP 2019, then a recent one CELT 2022 associated to LICS, and a forthcoming one in Dagstuhl 2023.
Yet another series of workshops and interdisciplinary collaborations was started with my work with Pierre Fraigniaud IRIF and Corentin Travers LABRI, using topological methods for runtime verification, with the results announced in RV 2014. A forthcoming workshop in this series will take place soon in Dagstuhl 2022, exploring connections between distributed algorithms and formal methods, following others in Bertinoro 2016 and Dagstuhl 2018.

During my one-year visit at IRIF, my main goal is to collaborate with Pierre Fraigniaud, Hugues Fauconnier and Carole Delporte, on developing further a scientific theory of distributed computing. We have recent results illustrating interesting relations with synchronous network algorithms, an area in which Fraigniaud is an expert, the latest published in ACM PODC 2022. With Hugues Fauconnier and Carole Delporte we have explored the topic of communication complexity of distributed algorithms in SIROCCO 2020, and we hope to develop this research project further. I would be interested in exploring uses of topology in other fields, especially those with world wide experts in IRIF, such as distributed systems composed of animals with Amos Korman or cryptography, with Adi Rosen. I plan also to continue developing the topological theory of multi-agent epistemic logic with Eric Goubault and other collaborators.
Recently, I have been selected to collaborate in the international project MEGA-ACE of AlgoRand Foundation, based on a new blockchain idea by Silvio Micali. The purpose of this project is to promote research on blockchains, especially showing that it is possible to having negligible energy consumption per transaction. Members of our project include Ecole Polytechnique.

In my undergrad, I was very much interested in mathematics and especially graph theory. When I first learned to program, in the first semester of my Engineering studies, I fell in love, and immediately switched from Electronic Engineering to Computer Engineering. The combination of my interest for programming and graph theory led me to the study of Theoretical Computer Science, motivated by the strong group at the Technion in Israel.

I have been collaborating very successfully with Pierre Fraigniaud, Hugues Fauconnier and Carole Delporte, and other French colleagues for many years now, especially with Michel Raynal, since our first paper in STOC 2001 (journal version), with yearly mutual visits to Mexico and France, funded research projects, and over 50 publications. I hope to take advantage of this unique opportunity to stay longer in France and I am very excited to pursue a deeper collaboration.

In Israel, my PhD advisor was Shimon Even, a famous professor and one of the fathers of computer science in Israel. He had an imposing presence and people were a bit afraid of talking to him, thinking that only the brightest students would have a chance of working with him. As a new student, I didn’t know all that, I was not an especially good student, and I didn’t even know Hebrew very well! But innocently, I went to him and asked if he would accept to be my advisor. He was very friendly and soon accepted me as his student. People around me were amazed and kept asking how did I do this. Retrospectively, if I have known that about him my life would have been completely different because I would have never gone to his office. But instead, he was my academic father, greatly shaping my way of thinking, and we became good friends until his premature death in 2004.

2021: Visiting IRIF / Full Professor at the National University of Mexico
1995: Postdoc at MIT
1991: PhD at the Israel Institute of Technology
1985: Computer Engineering in Mexico