An Almost Tight Lower Bound for Abortable Leader Election
Date
2018-07-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis introduces a general definition of abortability for object types with concurrent specifications. The main result discussed here is a lower bound of Ω(log n/ log log n) remote memory references (RMR) of abortable leader election in both cache coherent (CC) and distributed shared memory (DSM) models. Hence, showing a gap in the RMR complexity of abortable and non-abortable leader election, as leader election has O(1) RMR complexity [30]. Further, a small modification to the implementation of name-consensus and compare-and-swap [33] provides abortable name-consensus and abortable compare-and-swap in the CC model, given an abortable or atomic test-and-set object.
Description
Keywords
Remote Memory Reference, Distributed Algorithms, Shared Memory
Citation
Eghbali, A. (2018). An Almost Tight Lower Bound for Abortable Leader Election (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/32406