Space-efficient asynchronous consensus without shared memory initialization

Michael J. Fischer; Shlomo Moran; Gadi Taubenfeld

doi:10.1016/0020-0190(93)90223-V

Space-efficient asynchronous consensus without shared memory initialization

Michael J. Fischer, Shlomo Moran, Gadi Taubenfeld

نتاج البحث: نشر في مجلة › مقالة › مراجعة النظراء

ملخص

We study the consensus problem in a shared memory model where all processes are programmed alike, there is no global synchronization, it is not possible to simultaneously reset all parts of the system to a known initial state, and processes may be faulty. We present a consensus protocol for n processes which can tolerate up to ⌈n/2⌉ - 1 failures and which uses a single (2⌈1.5n-1⌉)-valued shared register.

اللغة الأصلية	الإنجليزيّة
الصفحات (من إلى)	101-105
عدد الصفحات	5
دورية	Information Processing Letters
مستوى الصوت	45
رقم الإصدار	2
المعرِّفات الرقمية للأشياء	https://doi.org/10.1016/0020-0190(93)90223-V
حالة النشر	نُشِر - 26 فبراير 1993
منشور خارجيًا	نعم

ملاحظة ببليوغرافية

Funding Information:
Correspondence to: G. Taubenfeld, AT&T Bell Laboratories, 28-408, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. * This work was supported in part by ONR contract NOO014-89-J-1980, by the National Science Foundation under grants CCR-8405478 and IRI-9015570, by the Hebrew Technical Institute scholarship, by the Technion V.P.R. Funds - Wellner Research Fund, and by the Foundation for Re-search in Electronics, Computers and Communications, administered by the Israel Academy of Sciences and Hu-manities.

الوصول إلى المستند

10.1016/0020-0190(93)90223-V

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{aadec4755fc84015ae5da2f1fd2b5071,

title = "Space-efficient asynchronous consensus without shared memory initialization",

abstract = "We study the consensus problem in a shared memory model where all processes are programmed alike, there is no global synchronization, it is not possible to simultaneously reset all parts of the system to a known initial state, and processes may be faulty. We present a consensus protocol for n processes which can tolerate up to ⌈n/2⌉ - 1 failures and which uses a single (2⌈1.5n-1⌉)-valued shared register.",

keywords = "Fault tolerance, crash failures, initialization failures, shared memory",

author = "Fischer, {Michael J.} and Shlomo Moran and Gadi Taubenfeld",

note = "Funding Information: Correspondence to: G. Taubenfeld, AT&T Bell Laboratories, 28-408, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. * This work was supported in part by ONR contract NOO014-89-J-1980, by the National Science Foundation under grants CCR-8405478 and IRI-9015570, by the Hebrew Technical Institute scholarship, by the Technion V.P.R. Funds - Wellner Research Fund, and by the Foundation for Re-search in Electronics, Computers and Communications, administered by the Israel Academy of Sciences and Hu-manities.",

year = "1993",

month = feb,

day = "26",

doi = "10.1016/0020-0190(93)90223-V",

language = "אנגלית",

volume = "45",

pages = "101--105",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Space-efficient asynchronous consensus without shared memory initialization

AU - Fischer, Michael J.

AU - Moran, Shlomo

AU - Taubenfeld, Gadi

N1 - Funding Information: Correspondence to: G. Taubenfeld, AT&T Bell Laboratories, 28-408, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. * This work was supported in part by ONR contract NOO014-89-J-1980, by the National Science Foundation under grants CCR-8405478 and IRI-9015570, by the Hebrew Technical Institute scholarship, by the Technion V.P.R. Funds - Wellner Research Fund, and by the Foundation for Re-search in Electronics, Computers and Communications, administered by the Israel Academy of Sciences and Hu-manities.

PY - 1993/2/26

Y1 - 1993/2/26

N2 - We study the consensus problem in a shared memory model where all processes are programmed alike, there is no global synchronization, it is not possible to simultaneously reset all parts of the system to a known initial state, and processes may be faulty. We present a consensus protocol for n processes which can tolerate up to ⌈n/2⌉ - 1 failures and which uses a single (2⌈1.5n-1⌉)-valued shared register.

AB - We study the consensus problem in a shared memory model where all processes are programmed alike, there is no global synchronization, it is not possible to simultaneously reset all parts of the system to a known initial state, and processes may be faulty. We present a consensus protocol for n processes which can tolerate up to ⌈n/2⌉ - 1 failures and which uses a single (2⌈1.5n-1⌉)-valued shared register.

KW - Fault tolerance

KW - crash failures

KW - initialization failures

KW - shared memory

UR - http://www.scopus.com/inward/record.url?scp=0027543649&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(93)90223-V

DO - 10.1016/0020-0190(93)90223-V

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:0027543649

SN - 0020-0190

VL - 45

SP - 101

EP - 105

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Space-efficient asynchronous consensus without shared memory initialization

ملخص

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا