A gap theorem for consensus types

Gary L. Peterson; Rida A. Bazzi; Gil Neiger

doi:10.1145/197917.198123

A gap theorem for consensus types

Gary L. Peterson, Rida A. Bazzi, Gil Neiger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 Scopus citations

Abstract

This paper presents a strong characterization that precisely determines the ability of n-process deterministic types to solve n-process wait-free consensus. This characterization, called the High Gap Theorem, has several important corollaries including a proof that Jayanti's hierarchy that allows multiple copies and read/write shared memory is robust for deterministic types.

Original language	English (US)
Title of host publication	Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994
Publisher	Association for Computing Machinery
Pages	344-353
Number of pages	10
ISBN (Electronic)	0897916549
DOIs	https://doi.org/10.1145/197917.198123
State	Published - Aug 14 1994
Externally published	Yes
Event	13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994 - Los Angeles, United States Duration: Aug 14 1994 → Aug 17 1994

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume	Part F129432

Other

Other	13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994
Country/Territory	United States
City	Los Angeles
Period	8/14/94 → 8/17/94

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/197917.198123

Cite this

Peterson, G. L., Bazzi, R. A., & Neiger, G. (1994). A gap theorem for consensus types. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994 (pp. 344-353). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. Part F129432). Association for Computing Machinery. https://doi.org/10.1145/197917.198123

A gap theorem for consensus types. / Peterson, Gary L.; Bazzi, Rida A.; Neiger, Gil.
Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994. Association for Computing Machinery, 1994. p. 344-353 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. Part F129432).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Peterson, GL, Bazzi, RA & Neiger, G 1994, A gap theorem for consensus types. in Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, vol. Part F129432, Association for Computing Machinery, pp. 344-353, 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994, Los Angeles, United States, 8/14/94. https://doi.org/10.1145/197917.198123

@inproceedings{7b921dcab0b249eb8f30ccb784e9a5d5,

title = "A gap theorem for consensus types",

abstract = "This paper presents a strong characterization that precisely determines the ability of n-process deterministic types to solve n-process wait-free consensus. This characterization, called the High Gap Theorem, has several important corollaries including a proof that Jayanti's hierarchy that allows multiple copies and read/write shared memory is robust for deterministic types.",

author = "Peterson, {Gary L.} and Bazzi, {Rida A.} and Gil Neiger",

year = "1994",

month = aug,

day = "14",

doi = "10.1145/197917.198123",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "344--353",

booktitle = "Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994",

note = "13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994 ; Conference date: 14-08-1994 Through 17-08-1994",

}

TY - GEN

T1 - A gap theorem for consensus types

AU - Peterson, Gary L.

AU - Bazzi, Rida A.

AU - Neiger, Gil

PY - 1994/8/14

Y1 - 1994/8/14

N2 - This paper presents a strong characterization that precisely determines the ability of n-process deterministic types to solve n-process wait-free consensus. This characterization, called the High Gap Theorem, has several important corollaries including a proof that Jayanti's hierarchy that allows multiple copies and read/write shared memory is robust for deterministic types.

AB - This paper presents a strong characterization that precisely determines the ability of n-process deterministic types to solve n-process wait-free consensus. This characterization, called the High Gap Theorem, has several important corollaries including a proof that Jayanti's hierarchy that allows multiple copies and read/write shared memory is robust for deterministic types.

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

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

U2 - 10.1145/197917.198123

DO - 10.1145/197917.198123

M3 - Conference contribution

AN - SCOPUS:0000342239

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 344

EP - 353

BT - Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994

PB - Association for Computing Machinery

T2 - 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994

Y2 - 14 August 1994 through 17 August 1994

ER -

A gap theorem for consensus types

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this