Agreement Abstractions in Anonymous and Homonymous Distributed Systems Prone to Failures

Tang, Jian (2015). Agreement Abstractions in Anonymous and Homonymous Distributed Systems Prone to Failures. Tesis (Doctoral), E.T.S.I. de Sistemas Informáticos (UPM).


Título: Agreement Abstractions in Anonymous and Homonymous Distributed Systems Prone to Failures
  • Tang, Jian
  • Jiménez Merino, Ernesto
  • Arévalo Viñuales, Sergio
Tipo de Documento: Tesis (Doctoral)
Fecha: 2015
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial



Hay una versión más reciente de este eprint. Pulse aquí para verla.

Texto completo

Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (909kB) | Vista Previa


The distributed computing models typically assume every process in the system has a distinct identifier (ID) or each process is programmed differently, which is named as eponymous system. In such kind of distributed systems, the unique ID is helpful to solve problems: it can be incorporated into messages to make them trackable (i.e., to or from which process they are sent) to facilitate the message transmission; several problems (leader election, consensus, etc.) can be solved without the information of network property in priori if processes have unique IDs; messages in the register of one process will not be overwritten by others process if this process announces; it is useful to break the symmetry. Hence, eponymous systems have influenced the distributed computing community significantly either in theory or in practice. However, every thing in the world has its own two sides. The unique ID also has disadvantages: it can leak information of the network(size); processes in the system have no privacy; assign unique ID is costly in bulk-production(e.g, sensors). Hence, homonymous system is appeared. If some processes share the same ID and programmed identically is called homonymous system. Furthermore, if all processes shared the same ID or have no ID is named as anonymous system. In homonymous or anonymous distributed systems, the symmetry problem (i.e., how to distinguish messages sent from which process) is the main obstacle in the design of algorithms. This thesis is aimed to propose different symmetry break methods (e.g., random function, counting technique, etc.) to solve agreement problem. Agreement is a fundamental problem in distributed computing including a family of abstractions. In this thesis, we mainly focus on the design of consensus, set agreement, broadcast algorithms in anonymous and homonymous distributed systems. Firstly, the fault-tolerant broadcast abstraction is studied in anonymous systems with reliable or fair lossy communication channels separately. Two classes of anonymous failure detectors AΘ and AP∗ are proposed, and both of them together with a already proposed failure detector ψ are implemented and used to enrich the system model to implement broadcast abstraction. Then, in the study of the consensus abstraction, it is proved the AΩ′ failure detector class is strictly weaker than AΩ and AΩ′ is implementable. The first implementation of consensus in anonymous asynchronous distributed systems augmented with AΩ′ and where a majority of processes does not crash. Finally, a general consensus problem– k-set agreement is researched and the weakest failure detector L used to solve it, in asynchronous message passing systems where processes may crash and recover, with homonyms (i.e., processes may have equal identities), and without a complete initial knowledge of the membership.

Más información

ID de Registro: 38766
Identificador DC:
Identificador OAI:
Depositado por: Archivo Digital UPM 2
Depositado el: 22 Dic 2015 09:01
Ultima Modificación: 14 Jun 2016 22:30
  • InvestigaM
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM