Distributed FIFO Allocation of Identical Resources Using Small Shared Space
We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as...
| Huvudupphovsmän: | , , , |
|---|---|
| Publicerad: |
2023
|
| Länkar: | https://hdl.handle.net/1721.1/149099 |
| _version_ | 1826195267958865920 |
|---|---|
| author | Fischer, Michael J. Lynch, Nancy A. Burns, James Borodin, Allan |
| author_facet | Fischer, Michael J. Lynch, Nancy A. Burns, James Borodin, Allan |
| author_sort | Fischer, Michael J. |
| collection | MIT |
| description | We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against processes failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show the algorithm is optimal (to within a constant factor) with respect to shared space complexity. |
| first_indexed | 2024-09-23T10:10:01Z |
| id | mit-1721.1/149099 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:10:01Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490992023-03-30T04:04:27Z Distributed FIFO Allocation of Identical Resources Using Small Shared Space Fischer, Michael J. Lynch, Nancy A. Burns, James Borodin, Allan We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against processes failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show the algorithm is optimal (to within a constant factor) with respect to shared space complexity. 2023-03-29T14:27:07Z 2023-03-29T14:27:07Z 1985-10 https://hdl.handle.net/1721.1/149099 MIT-LCS-TM-290 application/pdf |
| spellingShingle | Fischer, Michael J. Lynch, Nancy A. Burns, James Borodin, Allan Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title | Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title_full | Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title_fullStr | Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title_full_unstemmed | Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title_short | Distributed FIFO Allocation of Identical Resources Using Small Shared Space |
| title_sort | distributed fifo allocation of identical resources using small shared space |
| url | https://hdl.handle.net/1721.1/149099 |
| work_keys_str_mv | AT fischermichaelj distributedfifoallocationofidenticalresourcesusingsmallsharedspace AT lynchnancya distributedfifoallocationofidenticalresourcesusingsmallsharedspace AT burnsjames distributedfifoallocationofidenticalresourcesusingsmallsharedspace AT borodinallan distributedfifoallocationofidenticalresourcesusingsmallsharedspace |