Show simple item record

dc.contributor.author
Khanchandani, Pankaj
dc.contributor.supervisor
Wattenhofer, Roger
dc.contributor.supervisor
Gafni, Eli
dc.contributor.supervisor
Guerraoui, Rachid
dc.date.accessioned
2021-03-26T13:04:15Z
dc.date.available
2021-03-26T10:57:55Z
dc.date.available
2021-03-26T13:04:15Z
dc.date.issued
2020
dc.identifier.isbn
9798726545141
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/476540
dc.identifier.doi
10.3929/ethz-b-000476540
dc.description.abstract
Any set of computing processes or participants interacting to achieve a common objective can be considered as a Distributed System. Arguably, the most important algorithms for designing such a system are related to ordering the system events identically for all the processes. This is also the problem that many blockchain systems seek to address. Ideally, we want the algorithms to use minimal resources and scale well to a large number of processes or participants. We also want them to be robust against a multitude of failures such as unpredictable message delays and participants behaving maliciously. In this thesis, we discuss several fundamental distributed ordering problems and give algorithms with better scalability and robustness. For a multiprocessor system, we design an improved shared counter and also a concurrent queue. Our design works with concurrent unreliable processes that can crash at any time. We also propose a pair of new atomic instructions for a multiprocessor that have better scalability properties than the compare-and-swap instruction, which is widely supported by modern hardware. For a network of computers, we give a family of algorithms for distributed synchronization, which order concurrent requests to an exclusive resource that is shared over the network. These algorithms are not only simple but also efficient and only use a constant space per node. We also consider networks where potentially malicious or Byzantine participants can join the network and honest participants can leave over time. Such a dynamic setting is true for many blockchain systems that are used in practice. We give simple agreement protocols in such networks to totally order the events in the network.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Distributed algorithms
en_US
dc.subject
Consensus
en_US
dc.subject
concurrent data structures
en_US
dc.subject
Byzantine Agreement
en_US
dc.subject
Multiprocessor synchronization
en_US
dc.subject
Synchronization
en_US
dc.title
Robust and Scalable Distributed Ordering: Counting, Queueing and Agreement
en_US
dc.type
Doctoral Thesis
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2021-03-26
ethz.size
134 p.
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.identifier.diss
26743
en_US
ethz.publication.place
Zurich
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
en_US
ethz.date.deposited
2021-03-26T10:58:03Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-03-26T13:04:24Z
ethz.rosetta.lastUpdated
2022-03-29T06:04:15Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Robust%20and%20Scalable%20Distributed%20Ordering:%20Counting,%20Queueing%20and%20Agreement&rft.date=2020&rft.au=Khanchandani,%20Pankaj&rft.isbn=9798726545141&rft.genre=unknown&rft.btitle=Robust%20and%20Scalable%20Distributed%20Ordering:%20Counting,%20Queueing%20and%20Agreement
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record