Non-Interleaving Operational Semantics for Geographically Replicated Databases
For scalable distributed database systems, weak consistency models are essential. Distributed databases, such as Google Spanner, scale to millions of nodes that replicate data across datacentres possibly located on different continents. At this scale, it is infeasible to maintain serialisability, wh...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2015
|
| Online Access: | https://hdl.handle.net/10356/81027 http://hdl.handle.net/10220/39011 |
| _version_ | 1811685677122715648 |
|---|---|
| author | Ciobanu, Gabriel Horne, Ross |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Ciobanu, Gabriel Horne, Ross |
| author_sort | Ciobanu, Gabriel |
| collection | NTU |
| description | For scalable distributed database systems, weak consistency models are essential. Distributed databases, such as Google Spanner, scale to millions of nodes that replicate data across datacentres possibly located on different continents. At this scale, it is infeasible to maintain serialisability, which assumes that a global total order over committed transactions can be established. Instead, weaker consistency models, such as eventual consistency, causal consistency, sequential consistency and external consistency, are assumed. The problem is that operational models, such as labelled transition systems, tend to assume an interleaving semantics, which serialises transactions. To address this limitation, we provide an operational model that allows a weaker notion of consistency for a geographically distributed database inspired by Spanner. We reduce the timing guarantees provided by Spanner's TrueTime protocol to causal dependencies that are specified in a formal calculus. |
| first_indexed | 2024-10-01T04:48:19Z |
| format | Conference Paper |
| id | ntu-10356/81027 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:48:19Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/810272020-05-28T07:18:19Z Non-Interleaving Operational Semantics for Geographically Replicated Databases Ciobanu, Gabriel Horne, Ross School of Computer Engineering International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) (15th:2013:Timisoara) For scalable distributed database systems, weak consistency models are essential. Distributed databases, such as Google Spanner, scale to millions of nodes that replicate data across datacentres possibly located on different continents. At this scale, it is infeasible to maintain serialisability, which assumes that a global total order over committed transactions can be established. Instead, weaker consistency models, such as eventual consistency, causal consistency, sequential consistency and external consistency, are assumed. The problem is that operational models, such as labelled transition systems, tend to assume an interleaving semantics, which serialises transactions. To address this limitation, we provide an operational model that allows a weaker notion of consistency for a geographically distributed database inspired by Spanner. We reduce the timing guarantees provided by Spanner's TrueTime protocol to causal dependencies that are specified in a formal calculus. Accepted version 2015-12-09T04:25:11Z 2019-12-06T14:19:51Z 2015-12-09T04:25:11Z 2019-12-06T14:19:51Z 2013 Conference Paper Ciobanu, G., & Horne, R. (2014). Non-Interleaving Operational Semantics for Geographically Replicated Databases. 2013 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 440-447. https://hdl.handle.net/10356/81027 http://hdl.handle.net/10220/39011 10.1109/SYNASC.2013.64 en © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/SYNASC.2013.64]. application/pdf |
| spellingShingle | Ciobanu, Gabriel Horne, Ross Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title | Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title_full | Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title_fullStr | Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title_full_unstemmed | Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title_short | Non-Interleaving Operational Semantics for Geographically Replicated Databases |
| title_sort | non interleaving operational semantics for geographically replicated databases |
| url | https://hdl.handle.net/10356/81027 http://hdl.handle.net/10220/39011 |
| work_keys_str_mv | AT ciobanugabriel noninterleavingoperationalsemanticsforgeographicallyreplicateddatabases AT horneross noninterleavingoperationalsemanticsforgeographicallyreplicateddatabases |