Brief announcement: selfishness in transactional memory

ABSTRACT

In order to be efficient with selfish programmers, a multicore transactional memory (TM) system must be designed such that it is compatible with good programming incentives (GPI), i.e., writing efficient code for the overall system coincides with writing code that optimizes an individual program's performance. By implementing a selfish strategy, we show that under most contention managers (CM) proposed in the literature so far, TM systems are not GPI compatible, whereas a simple randomized CM is GPI compatible.

REFERENCES

• 1: Hagit Attiya , Leah Epstein , Hadas Shachnai , Tami Tamir, Transactional contention management as a non-clairvoyant scheduling problem, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146428]
• 2: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073863]
• 3: Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, ACM SIGPLAN Notices, v.41 n.10, October 2006
• 4: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, ACM SIGARCH Computer Architecture News, v.21 n.2, p.289-300, May 1993
• 5: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 6: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling; Threads

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Design, Experimentation, Human Factors, Performance

Keywords:
contention management, game theory, multicore architecture, transactional memory