Show simple item record

dc.contributor.author
Melnyk, Darya
dc.contributor.author
Wattenhofer, Roger
dc.date.accessioned
2020-08-03T08:04:58Z
dc.date.available
2020-08-03T02:47:41Z
dc.date.available
2020-08-03T08:04:58Z
dc.date.issued
2020-07
dc.identifier.isbn
978-1-4503-6935-0
en_US
dc.identifier.other
10.1145/3350755.3400272
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/429603
dc.description.abstract
This paper presents a novel shared memory model that simplifies the analysis of consensus on a Chain and a DAG. In this new model, referred to as the append memory model, nodes are allowed to write new values to the unordered memory, but not to overwrite already existing values. We show that although this model differs from the standard shared memory model with n shared read-write registers, many known results from the shared memory model still hold in the append memory model: It is, for example, impossible to establish consensus on n nodes with one crash failure if the nodes in the system are asynchronous. We also consider the append memory model in a synchronous setting with Byzantine failures. For this case, we show that Byzantine agreement cannot be solved in less than t+1 rounds, where t is the number of Byzantine nodes in the system. Assuming a probabilistic access restriction to the append memory, we compare the Byzantine agreement protocols on the Chain and the DAG. We show that the DAG structure achieves an almost optimal resilience (close to t<n/2) in contrast to the Chain structure that can tolerate less than t<n/(1+l∗(n-t)) Byzantine nodes, where l is the rate at which the nodes access the memory. © 2020 ACM.
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computing Machinery
en_US
dc.subject
Chain
en_US
dc.subject
DAG
en_US
dc.subject
Shared memory
en_US
dc.subject
Byzantine agreement
en_US
dc.title
The Append Memory Model: Why BlockDAGs Excel Blockchains
en_US
dc.type
Conference Paper
ethz.book.title
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
en_US
ethz.pages.start
383
en_US
ethz.pages.end
393
en_US
ethz.event
32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020) (virtual)
en_US
ethz.event.location
Philadelphia, PA, USA
en_US
ethz.event.date
July 14-16, 2020
en_US
ethz.notes
Due to the Corona virus (COVID-19) the conference was conducted virtually.
en_US
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.date.deposited
2020-08-03T02:48:03Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-08-03T08:05:12Z
ethz.rosetta.lastUpdated
2021-02-15T15:47:40Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=The%20Append%20Memory%20Model:%20Why%20BlockDAGs%20Excel%20Blockchains&amp;rft.date=2020-07&amp;rft.spage=383&amp;rft.epage=393&amp;rft.au=Melnyk,%20Darya&amp;Wattenhofer,%20Roger&amp;rft.isbn=978-1-4503-6935-0&amp;rft.genre=proceeding&amp;rft_id=info:doi/10.1145/3350755.3400272&amp;rft.btitle=Proceedings%20of%20the%2032nd%20ACM%20Symposium%20on%20Parallelism%20in%20Algorithms%20and%20Architectures
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record