Transactional contention management as a Non-clairvoyant scheduling problem.

*(English)*Zbl 1184.68118Summary: The transactional approach to contention management guarantees consistency by making sure that whenever two transactions have a conflict on a resource, only one of them proceeds. A major challenge in implementing this approach lies in guaranteeing progress, since transactions are often restarted.

Inspired by the paradigm of non-clairvoyant job scheduling, we analyze the performance of a contention manager by comparison with an optimal, clairvoyant contention manager that knows the list of resource accesses that will be performed by each transaction, as well as its release time and duration. The realistic, non-clairvoyant contention manager is evaluated by the competitive ratio between the last completion time (makespan) it provides and the makespan provided by an optimal contention manager.

Assuming that the amount of exclusive accesses to the resources is non-negligible, we present a simple proof that every work conserving contention manager guaranteeing the pending commit property achieves an \(O(s)\) competitive ratio, where \(s\) is the number of resources. This bound holds for the Greedy contention manager studied by R. Guerraoui et al. [in: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), 258–264 (2005)] and is a significant improvement over the \(O(s^2)\) bound they prove for the competitive ratio of Greedy. We show that this bound is tight for any deterministic contention manager, and under certain assumptions about the transactions, also for randomized contention managers.

When transactions may fail, we show that a simple adaptation of Greedy has a competitive ratio of at most \(O(ks)\), assuming that a transaction may fail at most \(k\) times. If a transaction can modify its resource requirements when re-invoked, then any deterministic algorithm has a competitive ratio \(\Omega(ks)\). For the case of unit length jobs, we give (almost) matching lower and upper bounds.

Inspired by the paradigm of non-clairvoyant job scheduling, we analyze the performance of a contention manager by comparison with an optimal, clairvoyant contention manager that knows the list of resource accesses that will be performed by each transaction, as well as its release time and duration. The realistic, non-clairvoyant contention manager is evaluated by the competitive ratio between the last completion time (makespan) it provides and the makespan provided by an optimal contention manager.

Assuming that the amount of exclusive accesses to the resources is non-negligible, we present a simple proof that every work conserving contention manager guaranteeing the pending commit property achieves an \(O(s)\) competitive ratio, where \(s\) is the number of resources. This bound holds for the Greedy contention manager studied by R. Guerraoui et al. [in: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), 258–264 (2005)] and is a significant improvement over the \(O(s^2)\) bound they prove for the competitive ratio of Greedy. We show that this bound is tight for any deterministic contention manager, and under certain assumptions about the transactions, also for randomized contention managers.

When transactions may fail, we show that a simple adaptation of Greedy has a competitive ratio of at most \(O(ks)\), assuming that a transaction may fail at most \(k\) times. If a transaction can modify its resource requirements when re-invoked, then any deterministic algorithm has a competitive ratio \(\Omega(ks)\). For the case of unit length jobs, we give (almost) matching lower and upper bounds.

##### MSC:

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

##### Keywords:

Scheduling; Transactions; Software transactional memory; Concurrency control; Contention management
PDF
BibTeX
XML
Cite

\textit{H. Attiya} et al., Algorithmica 57, No. 1, 44--61 (2010; Zbl 1184.68118)

Full Text:
DOI

##### References:

[1] | Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998) · Zbl 0931.68015 |

[2] | Edmonds, J., Chinn, D.D., Brecht, T., Deng, X.: Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. J. Sched. 6(3), 231–250 (2003) · Zbl 1154.90444 |

[3] | Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention management. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 258–264 (2005) · Zbl 1314.68088 |

[4] | Guerraoui, R., Herlihy, M., Kapałka, M., Pochon, B.: Robust contention management in software transactional memory. In: Synchronization and Concurrency in Object-Oriented Languages (SCOOL). Workshop, in Conjunction with OOPSLA (2005). http://urresearch.rochester.edu/handle/1802/2103 |

[5] | Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 92–101 (2003) |

[6] | Irani, S., Leung, V.: Scheduling with conflicts, and applications to traffic signal control. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 85–94 (1996) · Zbl 0845.90072 |

[7] | Kalyanasundaram, B., Pruhs, K.R.: Fault-tolerant scheduling. SIAM J. Comput. 34(3), 697–719 (2005) · Zbl 1075.68004 |

[8] | Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994) · Zbl 0820.90056 |

[9] | Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: System level concurrency control for distributed database systems. ACM Trans. Database Syst. 3(2), 178–198 (1978) |

[10] | Scherer III, W.N., Scott, M.: Contention management in dynamic software transactional memory. In: PODC Workshop on Concurrency and Synchronization in Java Programs, pp. 70–79 (2004) |

[11] | Scherer III, W.N., Scott, M.: Advanced contention management for dynamic software transactional memory. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 240–248 (2005) |

[12] | Silberschatz, A., Galvin, P.: Operating Systems Concepts, 5th edn. Wiley, New York (1999) · Zbl 0803.68019 |

[13] | Vossen, G., Weikum, G.: Transactional Information Systems. Morgan Kaufmann, San Mateo (2001) |

[14] | Yao, A.C.C.: Probabilistic computations: towards a unified measure of complexity. In: Proc. 18th Symp. Foundations of Computer Science (FOCS), pp. 222–227. IEEE (1977) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.