Validity conditions in agreement problems and time complexity

Bernadette Charron-Bost; Fabrice Le Fessant

Validity conditions in agreement problems and time complexity

Bernadette Charron-Bost
, Fabrice Le Fessant

École Polytechnique

Microsoft Research

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

4 Citations (Scopus)

Résumé

We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.

langue originale	Anglais
Pages (de - à)	196-207
Nombre de pages	12
journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2932
état	Publié - 1 déc. 2003

Contient cette citation

@article{9c3b906b42814871a62b330e1796ba3d,

title = "Validity conditions in agreement problems and time complexity",

abstract = "We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.",

keywords = "Complexity, Distributed Algorithms",

author = "Bernadette Charron-Bost and \{Le Fessant\}, Fabrice",

year = "2003",

month = dec,

day = "1",

language = "English",

volume = "2932",

pages = "196--207",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

Validity conditions in agreement problems and time complexity. / Charron-Bost, Bernadette; Le Fessant, Fabrice.
Dans: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol 2932, 01.12.2003, p. 196-207.

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

TY - JOUR

T1 - Validity conditions in agreement problems and time complexity

AU - Charron-Bost, Bernadette

AU - Le Fessant, Fabrice

PY - 2003/12/1

Y1 - 2003/12/1

N2 - We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.

AB - We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.

KW - Complexity

KW - Distributed Algorithms

M3 - Article

AN - SCOPUS:35048851524

SN - 0302-9743

VL - 2932

SP - 196

EP - 207

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Validity conditions in agreement problems and time complexity

Résumé

Empreinte digitale

Contient cette citation