Indexado en

Licencia y uso

Citaciones

Altmetrics

Análisis de autorías institucional

Compartir

Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures

Publicado en:Computing. 105 (6): 1165-1187 - 2023-01-01 105(6), DOI: 10.1007/s00607-022-01135-9

Autores: Jiménez E; López-Presa JL; Patiño-Martínez M

Afiliaciones

Resumen

Uniform Atomic Broadcast is one of the most important fault-tolerant communication abstractions for distributed systems. It ensures that processes deliver messages in the same order, even when processes may fail by crashing. On the other hand, Uniform Consensus is a fundamental abstraction in fault-tolerant distributed systems. It guarantees that, despite of failures by crashing, the processes decide on the same value among those proposed by all the processes in the system. These two abstractions have been extensively studied in the literature over the years. Traditionally, works on Uniform Atomic Broadcast and Consensus focus on classic systems, that is, systems where the processes have a univocal identity. Due to its advantages in security, among other properties, a different line has emerged to study these two abstractions in anonymous distributed systems where processes are indistinguishable because they do not have identifiers or any other way to tell them apart. So far, in these anonymous systems, Uniform Atomic Broadcast and Consensus have been studied considering the knowledge of two important parameters: f and n. The parameter f represents the maximum number of processes that can fail by crashing in an execution. The other parameter n indicates the total number of processes in the system. It is easy to see that these two parameters are also very important regarding security problems. This knowledge about the total number of processes (n) or the maximum number of processes that can fail (f) may compromise the security of the system. In this paper we study, for the first time in the literature, these two important problems in fully anonymous systems, that is, not only where processes are anonymous, but where the values of f and n are totally unknown. Although it is known in the literature that many agreement problems are impossible to solve in anonymous systems (even if n and f are known), we present in this paper algorithms to solve both abstractions in fully anonymous synchronous systems and we also present algorithms to show that they are also equivalent problems in these fully anonymous synchronous systems, just as they are in classical systems, as is well known in the literature.

Palabras clave