Fault-Tolerant Computing with Unreliable Channels

This thesis studies the foundations of fault-tolerant distributed computing under unreliable communication. Motivated by the practical challenges of message loss in modern networks, we consider a general model where both processes and communication channels may fail. Unlike classical models, we allow channels to be flaky, meaning they can lose an arbitrary number of messages without fairness or eventual delivery guarantees. This setting reflects a wide range of real-world failures observed in modern distributed applications. Our first contribution is a general characterization of solvability under arbitrary combinations of process and channel failures. We introduce a framework called a generalized quorum system (GQS), which precisely captures the minimal connectivity needed to implement classical shared-memory abstractions such as atomic registers, atomic snapshots, lattice agreement, and consensus. We prove that a GQS is both necessary and sufficient for solving these problems, even under extremely weak connectivity conditions. In particular, we show that these abstractions can be implemented even when read quorums are not strongly connected, as long as some strongly connected write quorum is reachable from them. To match this lower bound, we develop algorithms for each of the four problems in an adversarial model where correct channels are only eventually reliable and faulty channels are flaky. A key technical challenge is implementing registers under these assumptions. To address this, we develop two new building blocks: quorum access functions and custom logical clocks, which enable indirect coordination between weakly connected quorums. We then shift our attention to a practically motivated class of fail-prone systems in which at most a minority of processes may crash. This assumption, although restrictive, allows stronger guarantees and more efficient algorithms. In this setting, we show that consensus becomes the most difficult abstraction to implement efficiently. Classical mechanisms like leader election or failure detectors are not effective under flaky communication. To overcome this, we adapt a recently proposed abstraction of a view synchronizer, which enables groups of correct processes to coordinate in a common view with a correct leader. Using this abstraction, we design a modular consensus protocol that guarantees wait-freedom within a connected core of the system, using bounded memory and without assuming transitive connectivity. Finally, we demonstrate how our bounds can be used to analyze consensus solvability in existing models of weak connectivity. In particular, we show that some models strong enough to implement a leader detector are still too weak to solve consensus. Overall, this thesis contributes new theoretical foundations, abstractions, and algorithms for reliable distributed computing under weak connectivity. It provides a unified framework for reasoning about solvability and complexity in settings that better reflect the behavior of modern networks. RESUMEN Esta tesis estudia los fundamentos de la computación distribuida tolerante a fallos en presencia de comunicación no confiable. Motivados por los desafíos prácticos que impone la pérdida de mensajes en redes modernas, consideramos un modelo general donde tanto los procesos como los canales de comunicación pueden fallar. A diferencia de los modelos clásicos, permitimos canales flaky, que pueden perder una cantidad arbitraria de mensajes sin garantías de equidad ni entrega eventual. Este escenario refleja una amplia gama de fallos reales observados en aplicaciones distribuidas actuales. Nuestra primera contribución es una caracterización general de la posibilidad de implementación bajo combinaciones arbitrarias de fallos de procesos y canales. Introducimos una nueva herramienta, el sistema de quórums generalizado (GQS, por sus siglas en inglés), que captura de forma precisa la conectividad mínima necesaria para implementar abstracciones clásicas de memoria compartida, como registros atómicos, instantáneas atómicas, acuerdo sobre retículos y consenso. Demostramos que un GQS es una condición necesaria y suficiente para resolver estos problemas, incluso bajo supuestos de conectividad extremadamente débiles. En particular, mostramos que estas abstracciones pueden implementarse incluso si los quórums de lectura no son fuertemente conexos, siempre que exista un quórum de escritura fuertemente conexo alcanzable desde ellos. Para igualar esta cota inferior, desarrollamos algoritmos para cada uno de los cuatro problemas bajo un modelo adversario donde los canales correctos son solo eventualmente fiables y los canales defectuosos son flaky. Un desafío clave es la implementación de registros en este contexto. Para resolverlo, desarrollamos dos mecanismos: funciones de acceso a quórum y relojes lógicos personalizados, que permiten la coordinación indirecta entre quórums débilmente conectados. Luego analizamos una clase de sistemas motivada por la práctica, en los que como mucho puede fallar una minoría de procesos. Aunque esta suposición restringe el conjunto de fallos posibles, permite ofrecer garantías más fuertes y algoritmos más eficientes. En este caso, demostramos que consenso se vuelve la abstracción más difícil de implementar de manera eficiente. Mecanismos clásicos como detectores de fallos o detectores de líder no son eficaces bajo canales flaky. Para superar esta dificultad, adaptamos una abstracción propuesta recientemente llamada sincronizador de vistas, que permite a grupos de procesos correctos coordinarse en una vista común con un líder correcto. Con esta abstracción, diseñamos un protocolo modular de consenso que garantiza progreso en el núcleo conectado del sistema, utiliza memoria acotada y no asume conectividad transitiva. Finalmente, mostramos cómo nuestras cotas pueden aplicarse al análisis de modelos existentes con conectividad débil. En particular, demostramos que algunos modelos suficientemente fuertes para implementar detectores de líder no alcanzan para resolver consenso. En conjunto, esta tesis ofrece nuevas bases teóricas, abstracciones y algoritmos para la computación distribuida confiable bajo conectividad parcial. Proporciona un marco unificado para razonar sobre posibilidad de implementación y complejidad en entornos que reflejan mejor el comportamiento de las redes modernas.