@inproceedings{e8266625ef344bf89478f1968afc34d5,
title = "Stable Scheduling in Transactional Memory",
abstract = "We study computer systems with transactions executed on a set of shared objR framed as an adversarial model and impose limits on the average rate of transaction generation and the number of objects that transactions use. We show that no deterministic distributed scheduler in the queue-free model of transaction autonomy can provide stability for any positive rate of transaction generation. Let a system consist of m shared objects and an adversary be constrained such that each transaction may access at most k shared objects. We prove that no scheduler can be stable if a generation rate is greater than We develop a centralized scheduler that is stable if a transaction generation rate is at most We design a distributed scheduler in the queue-based model of transaction autonomy, in which a transaction is assigned to an individual processor, that guarantees stability if the rate of transaction generation is less than For each of the schedulers we give upper bounds on the queue size and transaction latency in the range of rates of transaction generation for which the scheduler is stable.",
keywords = "Transactional memory, adversarial model, dynamic transaction generation, latency, shared object, stability",
author = "Costas Busch and Chlebus, {Bogdan S.} and Kowalski, {Dariusz R.} and Pavan Poudel",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 13th International Symposium on Algorithms and Complexity, CIAC 2023 ; Conference date: 13-06-2023 Through 16-06-2023",
year = "2023",
doi = "10.1007/978-3-031-30448-4_13",
language = "English (US)",
isbn = "9783031304477",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "172--186",
editor = "Marios Mavronicolas",
booktitle = "Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings",
address = "Germany",
}