References

1. Balakrishnan, M., Malkhi, D., Davis, J. P., Prabhakaran, V., Wei, M., Wobber, T. CORFU: a distributed shared log. ACM Trans. Comp. Syst. 31, 4 (Dec. 2013).

2. Calciu, I., Gottschlich, J.E., Herlihy, M. Using delegation and elimination to implement a scalable NUMA-friendly stack. In USENIX Workshop on Hot Topics in Parallelism (June 2013).

3. Calciu, I., Sen, S., Balakrishnan, M., Aguilera, M.K. Black-box concurrent data structures for NUMA architectures. In International Conference on Architectural Support for Programming Languages and Operating Systems (Apr. 2017), 207–221.

4. Fraser, K. Practical lock-freedom.

Technical Report UCAM-CL-
TR-579, University of Cambridge,
Computer Laboratory
(Feb. 2004).

5. Hendler, D., Incze, I., Shavit, N., Tzafrir, M. Flat combining and the synchronization-parallelism tradeoff. In ACM Symposium on Parallelism in Algorithms and Architectures (June 2010),

355–364.

6. Herlihy, M. Wait-free synchronization. ACM Trans.

Program. Lang. Syst. 11, 1 (Jan.

1991), 124–149.

7. Herlihy, M., Shavit, N. The Art of Multiprocessor Programming.

Morgan Kaufmann Publishers Inc., San Francisco, CA, USA,

2008.

8. Herlihy, M. P., Wing, J. M.

Linearizability: a correctness condition for concurrent objects.

ACM Trans. Program. Lang. Syst.

12, 3 (July 1990), 463–492.

9. Lameter, C. NUMA (non-uniform memory access): an overview. ACM

Copyright held by authors/owners.

Publication rights licensed to ACM. $15.00.

Queue 11, 7 (July 2013).

10. Lim, H., Han, D., Andersen, D. G., Kaminsky, M. MICA: a holistic approach to fast in-memory key-value storage. In Symposium on Networked Systems Design and Implementation (Apr. 2014),

429–444.

11. Mao, Y., Kohler, E., Morris, R. T. Cache craftiness for fast multicore key-value storage. In European Conference on Computer Systems (Apr. 2012),

183–196.

12. Metreveli, Z., Zeldovich, N., Kaashoek, M.F. CPHash: a cache-partitioned hash table. In ACM Symposium on Principles and Practice of Parallel Programming (Feb. 2012), 319–320.

13. Michael, M.M. Hazard pointers: safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst. 15, 6 (June 2004), 491–504.

14. Porobic, D., Liarou, E., Tözün, P., Ailamaki, A. ATraPos: adaptive transaction processing on hardware islands. In International Conference on Data Engineering (Mar. 2014), 688–699.

15. Pugh, W. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (June 1990), 668–676.

16. Shalev, O., Shavit, N. Predictive log-synchronization. In European Conference on Computer Systems (Apr. 2006), 305–316.

Irina Calciu and Marcos K. Aguilera, VMware Research Group, Palo Alto, CA, USA.

Siddhartha Sen, Microsoft Research, New York, NY, USA.

Mahesh Balakrishnan, Yale University , New Haven, CT, USA.

realized, it can be used to provide all data structures with no extra work. With such a black-box method, we design for the architecture (in this case, NUMA) rather than for a data structure. We believe the community should investigate this black-box approach for future new architectures.