On the Inherent Sequentiality of Concurrent Objects
We present Ω(n) lower bounds on the worst case time to perform a single instance of an operation in any nonblocking implementation of a large class of concurrent data structures shared by n processes. Time is measured by the number of stalls a process incurs as a result of contention with other proc...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/75034 https://orcid.org/0000-0002-4552-2414 |
| _version_ | 1826198353919082496 |
|---|---|
| author | Ellen, Faith Hendler, Danny Shavit, Nir N. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ellen, Faith Hendler, Danny Shavit, Nir N. |
| author_sort | Ellen, Faith |
| collection | MIT |
| description | We present Ω(n) lower bounds on the worst case time to perform a single instance of an operation in any nonblocking implementation of a large class of concurrent data structures shared by n processes. Time is measured by the number of stalls a process incurs as a result of contention with other processes. For standard data structures such as counters, stacks, and queues, our bounds are tight. The implementations considered may apply any primitives to a base object. No upper bounds are assumed on either the number of base objects or their size. |
| first_indexed | 2024-09-23T11:03:31Z |
| format | Article |
| id | mit-1721.1/75034 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:03:31Z |
| publishDate | 2012 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/750342022-10-01T00:51:23Z On the Inherent Sequentiality of Concurrent Objects Ellen, Faith Hendler, Danny Shavit, Nir N. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shavit, Nir N. We present Ω(n) lower bounds on the worst case time to perform a single instance of an operation in any nonblocking implementation of a large class of concurrent data structures shared by n processes. Time is measured by the number of stalls a process incurs as a result of contention with other processes. For standard data structures such as counters, stacks, and queues, our bounds are tight. The implementations considered may apply any primitives to a base object. No upper bounds are assumed on either the number of base objects or their size. 2012-11-27T17:52:49Z 2012-11-27T17:52:49Z 2012-05 2008-06 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/75034 Ellen, Faith, Danny Hendler, and Nir Shavit. “On the Inherent Sequentiality of Concurrent Objects.” SIAM Journal on Computing 41.3 (2012): 519–536. © 2012 Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-4552-2414 en_US http://dx.doi.org/10.1137/08072646x SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Ellen, Faith Hendler, Danny Shavit, Nir N. On the Inherent Sequentiality of Concurrent Objects |
| title | On the Inherent Sequentiality of Concurrent Objects |
| title_full | On the Inherent Sequentiality of Concurrent Objects |
| title_fullStr | On the Inherent Sequentiality of Concurrent Objects |
| title_full_unstemmed | On the Inherent Sequentiality of Concurrent Objects |
| title_short | On the Inherent Sequentiality of Concurrent Objects |
| title_sort | on the inherent sequentiality of concurrent objects |
| url | http://hdl.handle.net/1721.1/75034 https://orcid.org/0000-0002-4552-2414 |
| work_keys_str_mv | AT ellenfaith ontheinherentsequentialityofconcurrentobjects AT hendlerdanny ontheinherentsequentialityofconcurrentobjects AT shavitnirn ontheinherentsequentialityofconcurrentobjects |