25
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Quantifiability: Concurrent Correctness from First Principles

      Preprint

      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Architectural imperatives due to the slowing of Moore's Law, the broad acceptance of relaxed semantics and the O(n!) worst case verification complexity of generating sequential histories motivate a new approach to concurrent correctness. Desiderata for a new correctness condition are that it be independent of sequential histories, composable over objects, flexible as to timing, modular as to semantics and free of inherent locking or waiting. We propose Quantifiability, a novel correctness condition based on intuitive first principles. Quantifiability models a system in vector space to launch a new mathematical analysis of concurrency. The vector space model is suitable for a wide range of concurrent systems and their associated data structures. This paper formally defines quantifiablity with its system model and demonstrates useful properties such as compositionality. Analysis is facilitated with linear algebra, better supported and of much more efficient time complexity than traditional combinatorial methods. We present results showing that quantifiable data structures are highly scalable due to the usage of relaxed semantics, an explicit implementation trade-off that is permitted by quantifiability.

          Related collections

          Most cited references 27

          • Record: found
          • Abstract: not found
          • Article: not found

          Linearizability: a correctness condition for concurrent objects

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Wait-free synchronization

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Amortized Computational Complexity

               Robert Tarjan (1985)
                Bookmark

                Author and article information

                Journal
                15 May 2019
                Article
                1905.06421

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                19 pages
                cs.DC

                Networking & Internet architecture

                Comments

                Comment on this article