Rambo: a robust, reconfigurable atomic memory service for dynamic networks
n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants join, leave, and fail. In fact, the entire set of participants may change dur...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62143 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1811083824547758080 |
|---|---|
| author | Gilbert, Seth Lynch, Nancy Ann Shvartsman, Alexander A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gilbert, Seth Lynch, Nancy Ann Shvartsman, Alexander A. |
| author_sort | Gilbert, Seth |
| collection | MIT |
| description | n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants join, leave, and fail. In fact, the entire set of participants may change during an execution, as the initial devices depart and are replaced by a new set of devices. Even so, Rambo ensures that data stored in the distributed shared memory remains available and consistent. There are two basic techniques used by Rambo to tolerate dynamic changes. Over short intervals of time, replication suffices to provide fault-tolerance. While some devices may fail and leave, the data remains available at other replicas. Over longer intervals of time, Rambo copes with changing participants via reconfiguration, which incorporates newly joined devices while excluding devices that have departed or failed. The main novelty of Rambo lies in the combination of an efficient reconfiguration mechanism with a quorum-based replication strategy for read/write shared memory. The Rambo algorithm can tolerate a wide variety of aberrant behavior, including lost and delayed messages, participants with unsynchronized clocks, and, more generally, arbitrary asynchrony. Despite such behavior, Rambo guarantees that its data is stored consistency. We analyze the performance of Rambo during periods when the system is relatively well-behaved: messages are delivered in a timely fashion, reconfiguration is not too frequent, etc. We show that in these circumstances, read and write operations are efficient, completing in at most eight message delays. |
| first_indexed | 2024-09-23T12:39:56Z |
| format | Article |
| id | mit-1721.1/62143 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:39:56Z |
| publishDate | 2011 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/621432022-10-01T10:23:21Z Rambo: a robust, reconfigurable atomic memory service for dynamic networks Gilbert, Seth Lynch, Nancy Ann Shvartsman, Alexander A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lynch, Nancy Ann Lynch, Nancy Ann n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants join, leave, and fail. In fact, the entire set of participants may change during an execution, as the initial devices depart and are replaced by a new set of devices. Even so, Rambo ensures that data stored in the distributed shared memory remains available and consistent. There are two basic techniques used by Rambo to tolerate dynamic changes. Over short intervals of time, replication suffices to provide fault-tolerance. While some devices may fail and leave, the data remains available at other replicas. Over longer intervals of time, Rambo copes with changing participants via reconfiguration, which incorporates newly joined devices while excluding devices that have departed or failed. The main novelty of Rambo lies in the combination of an efficient reconfiguration mechanism with a quorum-based replication strategy for read/write shared memory. The Rambo algorithm can tolerate a wide variety of aberrant behavior, including lost and delayed messages, participants with unsynchronized clocks, and, more generally, arbitrary asynchrony. Despite such behavior, Rambo guarantees that its data is stored consistency. We analyze the performance of Rambo during periods when the system is relatively well-behaved: messages are delivered in a timely fashion, reconfiguration is not too frequent, etc. We show that in these circumstances, read and write operations are efficient, completing in at most eight message delays. National Science Foundation (U.S.) (ITR Grant CCR-0121277) National Science Foundation (U.S.) (9804665) National Science Foundation (U.S.) (9984778) National Science Foundation (U.S.) (9988304) National Science Foundation (U.S.) (0311368) 2011-04-06T13:22:26Z 2011-04-06T13:22:26Z 2010-09 2008-03 Article http://purl.org/eprint/type/JournalArticle 0178-2770 1432-0452 http://hdl.handle.net/1721.1/62143 Gilbert, Seth, Nancy Lynch, and Alexander Shvartsman. “Rambo: a robust, reconfigurable atomic memory service for dynamic networks.” Distributed Computing 23.4 (2010): 225-272-272. https://orcid.org/0000-0003-3045-265X en_US http://dx.doi.org/10.1007/s00446-010-0117-1 Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Gilbert, Seth Lynch, Nancy Ann Shvartsman, Alexander A. Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title | Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title_full | Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title_fullStr | Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title_full_unstemmed | Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title_short | Rambo: a robust, reconfigurable atomic memory service for dynamic networks |
| title_sort | rambo a robust reconfigurable atomic memory service for dynamic networks |
| url | http://hdl.handle.net/1721.1/62143 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT gilbertseth ramboarobustreconfigurableatomicmemoryservicefordynamicnetworks AT lynchnancyann ramboarobustreconfigurableatomicmemoryservicefordynamicnetworks AT shvartsmanalexandera ramboarobustreconfigurableatomicmemoryservicefordynamicnetworks |