Verifying a quantitative relaxation of linearizability via refinement | International Journal on Software Tools for Technology Transfer Skip to main content
Springer Nature Link
Log in

Verifying a quantitative relaxation of linearizability via refinement

  • SPIN 2013
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

Abstract

The recent years have seen increasingly widespread use of highly concurrent data structures in both multi-core and distributed computing environments, thereby escalating the priority for verifying their correctness. Quasi linearizability is a quantitative variation of the standard linearizability correctness condition to allow more implementation freedom for performance optimization. However, ensuring that the implementation satisfies the quantitative aspect of this new correctness condition is often an arduous task. In this paper, we propose the first automated method for formally verifying quasi linearizability of the implementation model of a concurrent data structure with respect to its sequential specification. The method is based on checking a relaxed version of the refinement relation between the implementation model and the specification model through explicit state model checking. Our method can directly handle concurrent systems where each thread or process makes infinitely many method calls. Furthermore, unlike many existing verification methods, it does not require the user to supply annotations of the linearization points. We have implemented the new method in the PAT verification framework. Our experimental evaluation shows that the method is effective in verifying the new quasi linearizability requirement and detecting violations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Afek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: relaxed consistency for improved concurrency. In: International Conference on Principles of Distributed Systems, pp. 395–410 (2010)

  2. Aspnes, J., Herlihy, M., Shavit, N.: Counting networks. J. ACM. 41(5), 1020–1048 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  3. Attiya, H., Welch, J.: Distributed computing: fundamentals, simulations, and advanced topics, 2nd edn. John Wiley and Sons Inc., Publication, New Jersey (2004)

    Book  MATH  Google Scholar 

  4. Burckhardt, S., Dern, C., Musuvathi, M., Tan, R.: Line-up: a complete and automatic linearizability checker. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 330–340 (2010)

  5. Cerný, P., Radhakrishna, A., Zufferey, D., Chaudhuri, S., Alur, R.: Model checking of linearizability of concurrent list implementations. In: International Conference on Computer Aided Verification, pp. 465–479 (2010)

  6. Farzan, A., Madhusudan, P.: Monitoring atomicity in concurrent programs. In: International Conference on Computer Aided Verification, pp. 52–65 (2008)

  7. Flanagan, C., Qadeer, S.: A type and effect system for atomicity. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 338–349 (2003)

  8. Ganai, M.K., Arora, N., Wang, C., Gupta, A., Balakrishnan, G.: BEST: A symbolic testing tool for predicting multi-threaded program failures. In: IEEE/ACM International Conference on Automated Software Engineering, (2011)

  9. Haas, A., Lippautz, M., Henzinger, T.A., Payer, H., Sokolova, A., Kirsch, C.M., Sezgin, A.: Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation. In: Conference Computing Frontiers, p. 17 (2013)

  10. Henzinger, T.A., Sezgin, A., Kirsch, C.M., Payer, H., Sokolova, A.:. Quantitative relaxation of concurrent data structures. In: ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 317–328 (2013)

  11. Herlihy, M., Shavit, N.: The art of multiprocessor programming. Morgan Kaufmann, USA (2008)

    Google Scholar 

  12. Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM. Trans. Program. Lang. Syst. 12(3), 463–492 (1990)

    Article  Google Scholar 

  13. Hoare, C.A.R.: Communicating sequential processes. Prentice Hall, Englewood Cliffs (1985)

    MATH  Google Scholar 

  14. Kirsch, C.M. Payer, H.: Incorrect systems: it’s not the problem, it’s the solution. In: Proceedings of the Design Automation Conference, pp. 913–917 (2012)

  15. Kirsch, C.M., Payer, H., Röck, H., Sokolova, A.: Performance, scalability, and semantics of concurrent fifo queues. In: ICA3PP, pp. 273–287 (2012)

  16. Lamport, L.: How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE. Trans. Comput. 28(9), 690–691 (1979)

    Article  MATH  Google Scholar 

  17. Liu, Y., Chen, W., Liu, Y., Zhang, S., Sun, J., Dong, J.S.: Verifying linearizability via optimized refinement checking. IEEE. Trans. Softw. Eng. (2013)

  18. Liu, Y., Chen, W., Liu, Y.A., Sun, J.: Model checking linearizability via refinement. In: International Symposium on Formal Methods, pp. 321–337 (2009)

  19. Lynch, N.: Distributed algorithms. Morgan Kaufmann, USA (1997)

    Google Scholar 

  20. Michael, M.M., Vechev, M.T., Saraswat, V.A.: Idempotent work stealing. In: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Raleigh, pp. 45–54 (2009)

  21. Payer, H., Röck, H., Kirsch, C.M., Sokolova, A.: Scalability versus semantics of concurrent fifo queues. In: ACM Symposium on Principles of Distributed Computing, pp. 331–332 (2011)

  22. Said, M., Wang, C., Yang, Z., Sakallah, K.: Generating data race witnesses by an SMT-based analysis. In: NASA Formal Methods, pp. 313–327 (2011)

  23. Sinha, A., Malik, S., Wang, C., Gupta, A.: Predicting serializability violations: SMT-based search vs. DPOR-based search. In: Haifa Verification Conference, pp. 95–114 (2011)

  24. Sinha, A., Malik, S., Wang, C., Gupta, A.: Predictive analysis for detecting serializability violations through trace segmentation. In: Formal Methods and Models for Codesign, pp. 99–108 (2011)

  25. Sinha, N., Wang, C.: Staged concurrent program analysis. In: ACM SIGSOFT Symposium on Foundations of Software Engineering, pp. 47–56 (2010)

  26. Sun, J., Liu, Y., Dong, J.S., Chen, C.: Integrating specification and programs for system modeling and verification. In: International Symposium on Theoretical Aspects of Software Engineering, pp. 127–135 (2009)

  27. Sun, J., Liu, Y., Dong, J.S., Pang, J.: PAT: Towards Flexible Verification under Fairness. In: International Conference on Computer Aided Verification, pp. 709–714 (2009)

  28. Treiber, R.K.: Systems programming: coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center (1986)

  29. Vafeiadis, V.: Shape-value abstraction for verifying linearizability. In: International Conference on Verification, Model Checking, and Abstract Interpretation, pp. 335–348 (2009)

  30. Vafeiadis, V., Herlihy, M., Hoare, T., Shapiro, M.: Proving correctness of highly-concurrent linearisable objects. In: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 129–136 (2006)

  31. Vechev, M.T., Yahav, E., Yorsh, G.: Experience with model checking linearizability. In: International SPIN Workshop on Model Checking Software, pp. 261–278 (2009)

  32. Vogels, W.: Eventually consistent. Commun. ACM. 52(1), 40–44 (2009)

    Article  Google Scholar 

  33. Wang, C., Ganai, M.: Predicting concurrency failures in generalized traces of x86 executables. In: International Conference on Runtime Verification (2011)

  34. Wang, C., Hoang, K.: Precisely deciding control state reachability in concurrent traces with limited observability. In: International Conference on Verification, Model Checking, and Abstract Interpretation, pp. 376–394 (2014)

  35. Wang, C., Kundu, S., Ganai, M., Gupta, A.: Symbolic predictive analysis for concurrent programs. In: International Symposium on Formal Methods, pp. 256–272 (2009)

  36. Wang, C., Limaye, R., Ganai, M., Gupta, A.: Trace-based symbolic analysis for atomicity violations. In: International Conference on Tools and Algorithms for Construction and Analysis of Systems, pp. 328–342 (2010)

  37. Wang, C., Yang, Y., Gupta, A., Gopalakrishnan, G.: Dynamic model checking with property driven pruning to detect race conditions. In: International Symposium on Automated Technology for Verification and Analysis, pp. 126–140 (2008)

  38. Wang, L., Stoller, S.D.: Runtime analysis of atomicity for multithreaded programs. IEEE. Trans. Softw. Eng. 32(2), 93–110 (2006)

    Article  Google Scholar 

  39. Zhang, L., Chattopadhyay, A., Wang, C.: Round-Up: Runtime checking quasi linearizability of concurrent data structures. In: IEEE/ACM International Conference on Automated Software Engineering, pp. 4–14 (2013)

  40. Zhang, L., Wang, C.: Runtime prevention of concurrency related type-state violations in multithreaded applications. In: International Symposium on Software Testing and Analysis, pp. 1–12 (2014)

Download references

Acknowledgments

This research was supported by the U.S. National Science Foundation under Grant Number CCF-1149454. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Author information

Authors and Affiliations

  1. Virginia Tech, Blacksburg, Virginia, USA

    Kiran Adhikari, James Street & Chao Wang

  2. Nanyang Technological University, Singapore, Singapore

    Yang Liu

  3. Singapore University of Technology and Design, Singapore, Singapore

    Shaojie Zhang

Authors
  1. Kiran Adhikari
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. James Street
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Chao Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Yang Liu
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Shaojie Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Chao Wang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Adhikari, K., Street, J., Wang, C. et al. Verifying a quantitative relaxation of linearizability via refinement. Int J Softw Tools Technol Transfer 18, 393–407 (2016). https://doi.org/10.1007/s10009-015-0373-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-015-0373-2

Keywords