Computing with Content-Oblivious Messages

Abstract

One of the core aspects of distributed computing is the design of algorithms that tolerate failures [1, 8]. Failures may involve processes (in which case we may encounter 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 [9]. Tight bounds are known for agreement in the synchronous setting under these types of failures [9], and numerous works have investigated message loss in the synchronous setting and asynchronous setting for many other problems [7, 8, 10, 11].

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 [2], 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, [3] has recently 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 [3] has shown that $2$-connectivity is necessary, it also conjectured that the presence of a leader was a required assumption. [6] disproved this conjecture for the special case of oriented ring graphs by presenting a composable leader election algorithm. This result was later extended in [5] 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.

Always in oriented in rings [4] has shown a non-uniform leader election algorithm with an optimal dependency on process IDs.

The talk will discuss these results, focusing on the open problems and the current state of computation in systems where messages carry no content.