Uniform Consensus with Homonyms and Omission Failures

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 1, 2 Hung Tran-The 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : n synchronous message passing models in which some processes may be homonyms, i.e. may share the same id, we consider the consensus problem. Many results have already been proved concerning Byzantine failures in models with homonyms [10], we complete here the picture with crash and omission failures. Let n be the number of processes, t the number of processes that may be faulty (t < n) and l (1 ≤ l ≤ n) the number of identifiers. We prove that for crash failures and send-omission failures, uniform consensus is solvable even if l = 1, that is with fully anonymous processes for any number of faulty processes. Concerning omission failures, when the processes are numerate, i.e. are able to count the number of copies of identical messages they received in each round, uniform consensus is solvable even for fully anonymous processes for n > 2t. If processes are not numerate, uniform consensus is solvable if and only if l > 2t. All the proposed protocols are optimal both in the number of communication steps needed, and in the number of processes that can be faulty. All these results show, (1) that identifiers are not useful for crash and send-omission failures or when processes are numerate, (2) for general omission or for Byzantine failures the number of different ids becomes significant.
Type de document :
Communication dans un congrès
Davide Frey and Michel Raynal and Saswati Sarkar and Rudrapatna K. Shyamasundar and Prasun Sinha. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbai, India. Springer, 7730, pp.161-175, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_12〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922428
Contributeur : Carole Delporte-Gallet <>
Soumis le : jeudi 26 décembre 2013 - 16:05:20
Dernière modification le : mardi 17 avril 2018 - 11:29:36

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The. Uniform Consensus with Homonyms and Omission Failures. Davide Frey and Michel Raynal and Saswati Sarkar and Rudrapatna K. Shyamasundar and Prasun Sinha. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbai, India. Springer, 7730, pp.161-175, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_12〉. 〈hal-00922428〉

Partager

Métriques

Consultations de la notice

127