An Almost Tight Lower Bound for Abortable Leader Election

Simple item page
dc.contributor.advisorWoelfel, Philipp
dc.contributor.authorEghbali, Aryaz
dc.contributor.committeememberWoelfel, Philipp
dc.contributor.committeememberCockett, J. Robin B.
dc.contributor.committeememberHadzilacos, Vassos
dc.date2018-11
dc.date.accessioned2018-07-17T15:16:24Z
dc.date.available2018-07-17T15:16:24Z
dc.date.issued2018-07-11
dc.description.abstractThis 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.en_US
dc.identifier.citationEghbali, 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
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/32406
dc.identifier.urihttp://hdl.handle.net/1880/107195
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.facultyScience
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subjectRemote Memory Reference
dc.subjectDistributed Algorithms
dc.subjectShared Memory
dc.subject.classificationComputer Scienceen_US
dc.titleAn Almost Tight Lower Bound for Abortable Leader Election
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2018_eghbali_aryaz.pdf
Size:
474.09 KB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.74 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Open Theses and Dissertations

Powered by

Libraries & Cultural Resources

Start Something.

University of Calgary
2500 University Drive NW
Calgary Alberta T2N 1N4
CANADA

Copyright © 2023

The University of Calgary, located in the heart of Southern Alberta, both acknowledges and pays tribute to the traditional territories of the peoples of Treaty 7, which include the Blackfoot Confederacy (comprised of the Siksika, the Piikani, and the Kainai First Nations), the Tsuut’ina First Nation, and the Stoney Nakoda (including Chiniki, Bearspaw, and Goodstoney First Nations). The City of Calgary is also home to the Métis Nation of Alberta (Districts 5 and 6).

The University of Calgary is situated on land Northwest of where the Bow River meets the Elbow River, a site traditionally known as Moh’kins’tsis to the Blackfoot, Wîchîspa to the Stoney Nakoda, and Guts’ists’i to the Tsuut’ina. On this land and in this place we strive to learn together, walk together, and grow together “in a good way.”