Browsing by Author "Eghbali, Aryaz"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemOpen AccessAn Almost Tight Lower Bound for Abortable Leader Election(2018-07-11) Eghbali, Aryaz; Woelfel, Philipp; Woelfel, Philipp; Cockett, J. Robin B.; Hadzilacos, VassosThis 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.