{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:05:43Z","timestamp":1787385943779,"version":"build-2736575974"},"reference-count":63,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Hybrid consistency, a consistency condition for shared memory multiprocessors, attempts to capture the guarantees provided by contemporary high-performance architectures. It combines the expressiveness of strong consistency conditions (e.g., sequential consistency, linearizability) and the efficiency of weak consistency conditions (e.g., pipelined RAM, causal memory). Memory access operations are classified as either strong or weak. A global ordering of strong operations at different processes is guaranteed, but there is very little guarantee on the ordering of weak operations at different processes, except for what is implied by their interleaving with the strong operations. A formal and precise definition of this condition is given and an algorithm for providing hybrid consistency on distributed memory machines is presented. The response time of the algorithm is proved to be within a constant multiplicative factor of the (theoretical) optimal time bounds.<\/jats:p>","DOI":"10.1137\/s0097539795289215","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1637-1670","source":"Crossref","is-referenced-by-count":12,"title":["A Correctness Condition for High-Performance Multiprocessors"],"prefix":"10.1137","volume":"27","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roy","family":"Friedman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"S. Adve and M. Hill,\n                      Weak ordering\u2014A new definition\n                      , in Proc. 17th ACM\/IEEE International Symp. on Computer Architecture, 1990, pp. 2\u201314."},{"key":"R2","unstructured":"S. Adve and M. Hill,\n                      A Unified Formalization of Four Shared\u2010Memory Models\n                      , Technical Report 1051, Computer Science Department, University of Wisconsin, Madison, 1991."},{"key":"R3","unstructured":"S. Adve and M. Hill,\n                      Sufficient Conditions for Implementing the Data\u2010Race\u2010Free\u20101 Memory Model\n                      , Technical Report 1107, Computer Science Department, University of Wisconsin, Madison, 1992."},{"key":"R4","unstructured":"M. Ahamad, P. Hutto, and R. John,\n                      Implementing and Programming Causal Distributed Shared Memory\n                      , Technical Report TR GIT\u2010CC\u201090\u201049, Georgia Institute of Technology, Atlanta, 1990."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"R6","unstructured":"G. Alvarez, F. Cristian, and S. Mishra,\n                      On\u2010Demand Asynchronous Atomic Broadcast\n                      , Technical Report CS95\u2010416, Dept. of Computer Science, University of California, San Diego, 1995."},{"key":"R7","unstructured":"Y. Amir, D. Dolev, S. Kramer, and D. Malki,\n                      Total Ordering of Messages in Broadcast Domains\n                      , Technical Report CS92\u20109, Dept. of Computer Science, The Hebrew University of Jerusalem, 1992."},{"key":"R8","unstructured":"Y. Amir, L. E. Moser, P. M. Melliar\u2010Smith, D. A. Agarwal, and P. Ciarfella,\n                      Fast message ordering and membership using a logical token\u2010passing ring\n                      , in Proc. 13th IEEE International Conf. on Distributed Computing Systems, 1993, pp. 551\u2013560."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794278396"},{"key":"R10","unstructured":"H. Attiya and R. Friedman,\n                      A Correctness Condition for High\u2010Performance Multiprocessors\n                      . Technical Report #767, Department of Computer Science, Technion, Haifa, Israel, 1993."},{"key":"R11","unstructured":"H. Attiya and R. Friedman,\n                      Programming DEC\u2010alpha based multiprocessors the easy way\n                      , in Proc. 6th ACM Symp. on Parallel Algorithms and Architectures, ACM, New York, 1994, pp. 157\u2013166; also, Technical Report LPCR #9411, Department of Computer Science, Technion, Haifa, Israel."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/176575.176576"},{"key":"R13","unstructured":"A. Bar\u2010Noy and S. Kipnis,\n                      Designing broadcasting algorithms in the postal model for message\u2010passing systems\n                      , in Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, ACM, New York, 1992, pp. 11\u201322."},{"key":"R14","unstructured":"J. Bennett, J. Carter, and W. Zwaenepoel,\n                      Munin: Distributed shared memory based on type\u2010specific memory coherence\n                      , in Proc. 2nd ACM Symp. on Principles and Practice of Parallel Processing, ACM, New York, 1990, pp. 168\u2013176."},{"key":"R15","unstructured":"P. Bernstein, V. Hadzilacos, and H. Goodman,\n                      Concurrency Control and Recovery in Database Systems\n                      . Addison\u2010Wesley, Reading, MA, 1987."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/163298.163303"},{"key":"R17","unstructured":"K. Birman and T. Joseph,\n                      Exploiting virtual synchrony in distributed systems\n                      , in Proc. 11th ACM Symp. on Operating Systems Principles, ACM, New York, 1987, pp. 123\u2013138."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/7351.7478"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/128738.128742"},{"key":"R20","unstructured":"R. Bisiani, A. Nowatzyk, and M. Ravishankar,\n                      Coherent Shared Memory on a Distributed Memory Machine\n                      , in Proc. International Conf. on Parallel Processing, Pennsylvania State University, University Park, PA, 1989, pp. I\u2013133\u2013141."},{"key":"R21","unstructured":"W. Brantley, K. McAuliffe, and J. Weiss,\n                      RP3 processor\u2010memory element\n                      , in Proc. International Conf. on Parallel Processing, Pennsylvania State University, University Park, PA, 1985, pp. 782\u2013789."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675013"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/989.357400"},{"key":"R24","unstructured":"W. W. Collier,\n                      Architectures for Systems of Parallel Processes\n                      , Technical Report IBM TR 00.3253, IBM, Poughkeepsie, NY, 1984."},{"key":"R25","first-page":"115","volume":"33","author":"Cristian F.","year":"1991","journal-title":"IBM Technical Disclosure Bulletin"},{"key":"R25","unstructured":"also, 1st IEEE Workshop on Management of Replicated Data, Houston, TX, IEEE, Piscataway, NJ, 1990."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1088\/0967-1846\/1\/4\/001"},{"key":"R27","unstructured":"F. Cristian and S. Mishra,\n                      The pinwheel asynchronous atomic broadcast protocols\n                      , in Proc. 2nd International Symp. on Autonomous Decentralized Systems, Phoenix, AZ, 1995;"},{"key":"R27","unstructured":"also, Technical Report CSE93\u2010331, Department of Computer Science & Engineering, University of California, San Diego."},{"key":"R28","unstructured":"D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eiken,\n                      LogP: Towards a realistic model of parallel computation\n                      , in ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM, New York, 1993."},{"key":"R28","unstructured":"Also: Technical Report UCB\/CS\/92 713, University of California, Berkeley."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/32.55094"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/2.15"},{"key":"R31","unstructured":"P. Ezhilchelvan, R. Macedo, and S. Shrivastava,\n                      Newtop: A Fault\u2010Tolerant Group Communication Protocol\n                      , Technical Report, Computer Science Department, University of Newcastle, Newcastle upon Tyne, UK, 1994."},{"key":"R32","unstructured":"R. Friedman,\n                      Consistency Conditions for Distributed Shared Memories\n                      . Ph.D. Thesis, Department of Computer Science, Technion, Haifa, Israel, 1994."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050014"},{"key":"R34","unstructured":"K. Gharachorloo, A. Gupta, and J. Hennessy,\n                      Performance evaluation of memory consistency models for shared\u2010memory multiprocessors\n                      , in Proc. 4th ACM International Conf. on Architectural Support for Programming Languages and Operating Systems, ACM, New York, 1991, pp. 245\u2013257."},{"key":"R35","unstructured":"K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. Hennessy,\n                      Memory consistency and event ordering in scalable shared\u2010memory multiprocessors\n                      , in Proc. 17th ACM\/IEEE International Symp. on Computer Architecture, 1990, pp. 15\u201326."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"R37","unstructured":"P. Gibbons and M. Merritt,\n                      Specifying non\u2010blocking shared memories\n                      , in Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, ACM, New York, 1992, pp. 306\u2013315."},{"key":"R38","unstructured":"P. Gibbons, M. Merritt, and K. Gharachorloo,\n                      Proving sequential consistency of high\u2010performance shared memories\n                      , in Proc. 3rd ACM Symp. on Parallel Algorithms and Architectures, ACM, New York, 1991, pp. 292\u2013303."},{"key":"R39","unstructured":"R. J. Goodman,\n                      Cache Consistency and Sequential Consistency\n                      , Technical Report 1006, Computer Science Department, University of Wisconsin, Madison, 1991."},{"key":"R40","unstructured":"A. Gupta, J. Hennessy, K. Gharachorloo, T. Mowry, and W. Weber,\n                      Comparative evaluation of latency reducing and tolerating techniques\n                      , in Proc. 18th ACM\/IEEE International Symp. on Computer Architecture, May 1991, pp. 254\u2013263."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"R42","unstructured":"J. James and A. Singh,\n                      Complete implementations for shared memory consistency conditions\n                      , in Proc. 14th ACM Symp. on Principles of Distributed Computing, ACM, New York, 1995, p. 273."},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1145\/70730.70732"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675439"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1145\/75104.75105"},{"key":"R46","unstructured":"R. Lipton and J. Sandberg,\n                      PRAM: A Scalable Shared Memory\n                      , Technical Report CS\u2010TR\u2010180\u201088, Computer Science Department, Princeton University, Princeton, NJ, 1988."},{"key":"R47","first-page":"42","volume":"24","author":"Marzullo K.","year":"1991","journal-title":"IEEE Trans. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9340","issn-type":"print"},{"key":"R48","unstructured":"S. Min and J. Baer,\n                      A timestamp\u2010based cache coherence scheme\n                      , in Proc. International Conf. on Parallel Processing, Pennsylvania State University, University Park, PA, 1989, pp. I\u201323\u201332."},{"key":"R49","unstructured":"C. Papadimitriou,\n                      The Theory of Concurrency Control\n                      , Computer Science Press, Rockville, MD, 1986."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90106-X"},{"key":"R51","unstructured":"U. Ramachandran, M. Ahamad, and M. Y. Khalidi,\n                      Coherence of distributed shared memory: Unifying synchronization and data transfer\n                      , in Proc. International Conf. on Parallel Processing, Pennsylvania State University, University Park, PA 1989, pp. II\u2013160\u2013169."},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1145\/358527.358537"},{"key":"R53","unstructured":"P. Reynolds, C. Williams, and R. Wagner,\n                      Empirical Analysis of Isotach Networks\n                      , Technical Report 92\u201019, Dept. of Computer Science, University of Virginia, Richmond, 1992."},{"key":"R54","unstructured":"C. Scheurich and M. Dubois,\n                      Correct memory operation of cache\u2010based multiprocessors\n                      , in Proc. 14th ACM\/IEEE International Symp. on Computer Architecture, 1987, pp. 234\u2013243."},{"key":"R55","unstructured":"A. Setubal and G. Gerber,\n                      Fault\u2010tolerant distributed database for supervisory control system\n                      , in Proc. Workshop Verteilte Datenbaksysteme, Karlsruhe University, Karlsruhe, Germany, 1991."},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1145\/42190.42277"},{"key":"R57","unstructured":"A. Siegel, K. Birman, and K. Marzullo,\n                      Deceit: A Flexible Distributed File System\n                      , Technical Report TR 89\u20101042, Department of Computer Science, Cornell University, Ithaca, NY, 1989."},{"key":"R58","unstructured":"R. van Renesse, K. Birman, R. Friedman, M. Hayden, and D. Karr,\n                      A framework for protocol composition in horus\n                      , in Proc. 14th ACM Symposium on Principles of Distributed Computing, ACM, New York, 1995, pp. 80\u201389."},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1145\/227210.227229"},{"key":"R60","unstructured":"R. N. Zucker and J.\u2010L. Baer,\n                      A Performance Study of Memory Consistency Models\n                      , in Proc. 19th ACM\/IEEE International Symp. on Computer Architecture, 1992, pp. 2\u201312."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795289215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:17Z","timestamp":1787336057000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795289215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":63,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795289215"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795289215","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}