An Almost Tight Lower Bound for Abortable Leader Election

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.