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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00922428
Contributor : Carole Delporte-Gallet <>
Submitted on : Thursday, December 26, 2013 - 4:05:20 PM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM

Links full text

Identifiers

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The. Uniform Consensus with Homonyms and Omission Failures. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbai, India. pp.161-175, ⟨10.1007/978-3-642-35668-1_12⟩. ⟨hal-00922428⟩

Share

Metrics

Record views

190