Efficient Bounded Timestamping from Standard Synchronization Primitives
| dc.contributor.advisor | Woelfel, Philipp | |
| dc.contributor.author | Jamadi, Ali | |
| dc.contributor.committeemember | Woelfel, Philipp | |
| dc.contributor.committeemember | Jayanti, Prasad | |
| dc.contributor.committeemember | Cockett, Robin | |
| dc.contributor.committeemember | Denzinger, Jorg | |
| dc.date | 2024-05 | |
| dc.date.accessioned | 2024-04-30T16:15:48Z | |
| dc.date.available | 2024-04-30T16:15:48Z | |
| dc.date.issued | 2024-04-25 | |
| dc.description.abstract | Timestamping systems are at the core of many solutions to fundamental problems in distributed algorithms [2, 4, 11, 13, 15, 22, 25, 27], and are well-studied. These systems allow processes to determine the temporal ordering of events by assigning a timestamp to each event and defining an ordering on the timestamps that corresponds to the temporal order of events. Israeli and Li [19] were the first to formalize a variation of these systems, called bounded timestamping systems (BTS), wherein the domain of timestamps is finite. They established a crucial lower bound that implies any BTS implementation, where the values of the timestamps assigned to events are sufficient to determine the temporal order of events, requires ฮฉ(๐) bits to represent a timestamp. Existing BTS implementations [3, 6โ8, 12, 20] have ฮฉ(๐) step complexity and use registers of size ฮฉ(๐) bits. This thesis introduces a novel specification for a bounded times- tamping system called marker based timestamping (MBT), which has a more efficient implementation than all prior BTS implementations and is still practical. An MBT object keeps track of ๐ markers where each marker belongs to a process and each process has at least one marker. It provides two functionalities: mark(๐) operation to mark the current point in time with marker ๐, and isEarlier(๐, ๐) to determine the temporal order of the events marked by markers ๐ and ๐. Note that the lower bound of Israeli and Li does not apply to an MBT object. We present a linearizable, wait-free MBT implementation with constant step complexity from ๐(๐ ยท ๐) Compare-And-Swap (CAS) objects and a single bounded Fetch-And-Add (FAA) object, where each base object stores only ๐(log ๐) bits. | |
| dc.identifier.citation | Jamadi, A. (2024). Efficient bounded timestamping from standard synchronization primitives (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. | |
| dc.identifier.uri | https://hdl.handle.net/1880/118551 | |
| dc.language.iso | en | |
| dc.publisher.faculty | Graduate Studies | |
| dc.publisher.institution | University of Calgary | |
| dc.rights | University 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.subject | Theory of computation | |
| dc.subject | Shared memory algorithms | |
| dc.subject | Bounded Timestamping | |
| dc.subject.classification | Computer Science | |
| dc.title | Efficient Bounded Timestamping from Standard Synchronization Primitives | |
| dc.type | master thesis | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of Calgary | |
| thesis.degree.name | Master of Science (MSc) | |
| ucalgary.thesis.accesssetbystudent | I do not require a thesis withhold โ my thesis will have open access and can be viewed and downloaded publicly as soon as possible. |