Efficient Bounded Timestamping from Standard Synchronization Primitives
| dc.contributor.author | Bashari, Benyamin | |
| dc.contributor.author | Jamadi, Ali | |
| dc.contributor.author | Woelfel, Philipp | |
| dc.date.accessioned | 2023-05-23T15:53:25Z | |
| dc.date.available | 2023-05-23T15:53:25Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | Bounded timestamps [9, 19 ] allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well studied building block used in many shared memory algorithms. A concurrent timestamp system keeps track of 𝑚 timestamps, which is usually greater or equal to the number of processes in the system, 𝑛. A process may, at any point, obtain a new timestamp, and later determine a total order of all process’s most recent timestamps. Known timestamp algorithms do not scale well in the number of processes. Getting a new timestamp takes at least a linear number of steps, and a lower bound by Israeli and Li [ 19 ] implies that each timestamp needs to be represented by at least Ω(𝑚) bits. We introduce a slightly different semantics for timestamping, where there is no fixed timestamp value associated with an event. A process can execute operation updateTS() to update its latest timestamp, associating it with the (linearization) point of that operation, and is Earlier (𝑝,𝑞) to determine the temporal order of the latest updateTS() operations executed by processes 𝑝 and 𝑞. Since no static timestamp value is returned by update TS(), the lower bound of Israeli and Li does not apply. We present efficient linearizable and wait-free implementations of these methods using a single bounded fetch-and-add object and 𝑂 (𝑛²) bounded compare-and-swap objects, which are available on standard hardware. The step complexity of each method call is constant, and base objects need only store 𝑂 (log 𝑛) bits. | |
| dc.description.grantingagency | Natural Sciences and Engineering Research Council (NSERC) | |
| dc.identifier.citation | Bashari, B., Jamadi, A., & Woelfel, P. (2023). Efficient Bounded Timestamping from Standard Synchronization Primitives [Report]. University of Calgary, Calgary, AB. | |
| dc.identifier.grantnumber | RGPIN-2019-04852 | |
| dc.identifier.uri | https://hdl.handle.net/1880/116565 | |
| dc.identifier.uri | https://dx.doi.org/10.11575/PRISM/dspace/41408 | |
| dc.language.iso | en | en |
| dc.publisher.faculty | Science | en |
| dc.publisher.institution | University of Calgary | en |
| dc.rights | Unless otherwise indicated, this material is protected by copyright and has been made available with authorization from the copyright owner. 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. | en |
| dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | en |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Theory of computation | |
| dc.subject | Shared memory algorithms | |
| dc.title | Efficient Bounded Timestamping from Standard Synchronization Primitives | |
| dc.type | Conference presentation |