Referenz
Schneider, J., & Wattenhofer, R. (2009). Bounds On Contention Management Algorithms. Paper presented at the Symposium on Algorithms and Computation (ISAAC).
Publikationsart
Beitrag in Konferenztagungsband
Abstract
We present two new algorithms for contention management in transactional memory, the deterministic algorithm CommitRounds and the randomized algo- rithm RandomizedRounds. Our randomized algorithm is e?cient: in some noto- rious problem instances (e.g., dining philosophers) it is exponentially faster than prior work from a worst case perspective. Both algorithms are (i) local and (ii) starvation-free. Our algorithms are local because they do not use global synchro- nization data structures (e.g., a shared counter), hence they do not introduce additional resource con?icts which eventually might limit scalability. Our algo- rithms are starvation-free because each transaction is guaranteed to complete. Prior work sometimes features either (i) or (ii), but not both. To analyze our algorithms (from a worst case perspective) we introduce a new measure of com- plexity that depends on the number of actual con?icts only. In addition, we show that even a non-constant approximation of the length of an optimal (shortest) schedule of a set of transactions is NP-hard – even if all transactions are known in advance and do not alter their resource requirements.
Mitarbeiter
Einrichtungen
- Institut für Wirtschaftsinformatik
- Hilti Lehrstuhl für Business Process Management