OPODIS2025

Computing with Content-Oblivious Messages

One of the core aspects of distributed computing is the design of algorithms that tolerate failures. Failures may involve processes (such as crash-stop, memory corruption, or Byzantine failures) or the communication among processes. When processes communicate through message passing, failures may include message loss, message addition (either duplication or fabrication), and message corruption. Tight bounds are known for agreement in the synchronous setting under these types of failures, and numerous works have investigated message loss in both synchronous and asynchronous systems.
In this talk, we focus on what can be computed when the system is asynchronous and messages may be corrupted; that is, a sent message can be arbitrarily modified by an adversary, but it cannot be deleted or duplicated. We specifically consider the bleak scenario in which all messages sent by processes are corrupted. Alternatively, one can view this as a setting where all messages have zero size, consisting only of simple pulses. This content-oblivious model is reminiscent of the beeping model, but in the beeping model, synchrony allows silence to be used as a means of communication.
Surprisingly, contrary to what one might expect at first glance, (Censor-Hillel, Cohen, Gelles, and Sela; 2023) have shown that, in the content-oblivious setting, when a predetermined leader is present and the network topology is 2-connected, it is possible to simulate an environment that is completely fault-free. While their work showed that 2-connectivity is necessary, they also conjectured that the presence of a leader was a required assumption. (Frei, Gelles, Ghazy, and Nolin; 2024) disproved this conjecture for the special case of oriented ring graphs by presenting a composable leader election algorithm. This result was later extended by (Chalopin, Chang, Chen, Di Luna, and Zhou; 2025) to the case of unoriented graphs and, under the mild assumption of an upper bound on the network size, for any 2-edge-connected network. Thus, for the special case of ring topologies, we have a computational equivalence between content-oblivious and classic asynchronous message passing. Finally, (Chalopin, Chang, Chen, Di Luna, and Zhou; 2025) also presented a non-uniform leader election algorithm with an optimal dependency on process identifiers for oriented rings.
The talk discusses these results, focusing on open problems and the current state of computation in systems where messages carry no content.

 

About the speaker

Giuseppe Antonio Di Luna received his Ph.D. from Sapienza University of Rome in 2015, with a dissertation on counting in anonymous dynamic networks. Following his Ph.D., he joined the University of Ottawa as a postdoctoral researcher, focusing on fault-tolerant distributed algorithms, distributed robotics, and algorithmic design for programmable particles. In 2018, he moved to Aix-Marseille University for a postdoctoral position, where he worked on dynamic graphs. He later returned to Sapienza University of Rome, where he is currently an Associate Professor. He has served on the program committees of several international conferences in distributed computing and systems and was the General Co-Chair of EuroSys 2023.