The notion of veto number for distributed agreement problems

被引：0

作者：

Friedman, R ^{[1
]}

Mostefaoui, A

Raynal, M

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] IRISA, F-35042 Rennes, France

来源：

DISTRIBUTED COMPUTING - IWDC 2004, PROCEEDINGS | 2004年 / 3326卷

关键词：

agreement problem; asynchronous system; consensus; distributed algorithm; one shot problem; process crash; failure detector;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper introduces the notion of veto number that can be associated with agreement problems. An agreement problem has veto number l when l is the minimal number of processes that control the allowed decision values, i.e., if each of them changes its mind on the value it proposes, then it forces deciding on a different value. The paper presents and investigates this concept.

引用

页码：315 / 325

页数：11

共 10 条

[1] Unreliable failure detectors for reliable distributed systems [J].

Chandra, TD ;

Toueg, S .

JOURNAL OF THE ACM, 1996, 43 (02) :225-267

[2]

Delporte-Gallet C, 2002, LECT NOTES COMPUT SC, V2508, P237

[3] IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS [J].

FISCHER, MJ ;

LYNCH, NA ;

PATERSON, MS .

JOURNAL OF THE ACM, 1985, 32 (02) :374-382

[4] A weakest failure detector-based asynchronous consensus protocol for f < n [J].

Friedman, R ;

Mostefaoui, A ;

Raynal, M .

INFORMATION PROCESSING LETTERS, 2004, 90 (01) :39-46

[5]

FRIEDMAN R, 2004, LNCS

[6] Non-blocking atomic commit in asynchronous distributed systems with failure detectors [J].

Guerraoui, R .

DISTRIBUTED COMPUTING, 2002, 15 (01) :17-25

[7] Computing global functions in asynchronous distributed systems with perfect failure detectors [J].

Hélary, JM ;

Hurfin, M ;

Mostefaoui, A ;

Raynal, M ;

Tronel, F .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2000, 11 (09) :897-909

[8] WAIT-FREE SYNCHRONIZATION [J].

HERLIHY, M .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1991, 13 (01) :124-149

[9] LINEARIZABILITY - A CORRECTNESS CONDITION FOR CONCURRENT OBJECTS [J].

HERLIHY, MP ;

WING, JM .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1990, 12 (03) :463-492

[10] Conditions on input vectors for consensus solvability in asynchronous distributed systems [J].

Mostefaoui, A ;

Rajsbaum, S ;

Raynal, M .

JOURNAL OF THE ACM, 2003, 50 (06) :922-954

← 1 →