Ensuring Consistency in Transactional Data Stores

Get Complete Project Material File(s) Now! »

Micro-robotics, observation and actuation

The driving forces behind micro-scale experimentation hang on appropriate observation, actuation and control tools which are the centrepiece of micro-robotics. Micro-robotics as a field has been developed since the 1990s, and consists in the application of micro- or macro-scale robotic tools in order to aﬀect micro-scale objects – where micro-scale originally refers to sizes between a micrometre and a millimetre. This extends further into actuation and manipulation down to the nanometre scale, and although the transition is not trivial, the physics here will pertain to both the micro- and nano-world. This section will address the main aspects of physics and robotics which are specific to these scales: physical phenomena, observation tools, actuation systems, and, as pertains to the experiments conducted in this work, their applications under scanning electron microscopes.

Physics of the micro-world

The physical phenomena which form the basis of interaction and sensing at the micro-scale are not those we are normally familiar with. Although the laws of classical (as opposed to quantum) physics still apply at this scale, diﬀerent forces prevail in the micro-world. This diﬀerence is referred to as the scale eﬀect [?].

Scale eﬀect

The prevailing forces at our scale (the human or macro-scale) are « volumetric forces », so called because they scale with the volume of the objects involved: gravity and inertial forces. However, at the micro-scale, the power balance is reversed and « surface forces » take over.
This phenomenon can be illustrated through the « Square-Cube Law »: a cube with edges 10 cm has 100 cm2 sides and a volume of 1000 cm3. A cube with ten times smaller edges would have a side surface of 1 cm2 (e.g. a hundred times smaller) and a volume of 1 cm3 (e.g. a thousand times smaller). Therefore, through this evolution in scale, the eﬀects of forces that apply on surfaces progressively catch up with those of volumetric forces (Fig. ??).
Figure 1.1 – Evolution of the balance of forces when going down in scale [?] : tension forces (Ftens), van der Waals forces (Fvdw), and electrostatic forces (Felec) progressively get to overcome gravity (Fgrav).
Beyond surface and volume forces, the scale eﬀect also aﬀects behaviour as they relate to time (time dilatation) and all physical phenomena of the micro-world, from solid or fluid mechanics to heat transfers. The immediate consequence is the apparition of significant interaction forces between objects: attractive forces if they are very close, adhesion forces if they are in contact, but also attractive or repulsive electrostatic forces which can be completely unpredictable. These behaviours result in both challenges and opportunities for experimentation at the micro-scale.

Surface forces

Surface forces can be attractive or repulsive. Attractive forces notably contribute to adhesion eﬀects, which are omnipresent in micro-robotics. The three main categories of adhesion forces at the micro-scale are : [?]
Van der Waals forces: interaction forces between two permanent or induced dipoles, which cover most intermolecular forces aside from covalent or hydrogen bonds. They are dependent upon the materials of the objects, and become significant at distances around a dozen nanometres.
electrostatic forces, or classical Coulomb forces, which act between all charged objects. They are dependent upon the accumulation of electrostatic charges by the objects. When in the presence of even weak charges, electrostatic interaction of modest magnitude can be detected from over a hundred nanometres, but compared to Van der Waals forces, it only becomes significant in closest proximity [?].
capillary forces, which govern surface tensions and liquid menisci, according to the hu-midity of the medium. They appear at air-liquid interfaces, or on immersed hydrophobic surfaces. They are dependent upon the nature of the liquids, materials and geometry of the system.
In the context of this work, quartz probes will mainly seek to sense attractive or repulsive van der Waals forces, which are reliably short-ranged. Electrostatic forces apply at a greater and potentially more variable range, and may for this reason be an obstacle, especially in the experiments combined with electron microscopy in Chapter 4.

Observing the micro- and nano-world

Various means of observation are available when it comes to obtaining global vision feed-back into the micro-world. Depending on the scale aimed for (Fig. ??), they rely on distinct physical principles of operation, and may interact directly or indirectly with objects to build an image. Alternatives to optical vision therefore come with their advantages as well as additional hindrances; in this regard, the microscopes relevant to this work are the optical, electron and local probe microscopes, the characteristics of which are as follows.

Optical microscopes

Optical microscopy relies on mirrors and lenses to redirect photons and provide the user with an enlarged image. Photons can be reflected, as is the case for human vision, or transmitted (going through a transparent sample). Although it is very commonly used and easy to set up, optical microscopy is limited by:
resolution, which cannot be lower than 0.2 m for classical optical microscopes 1 depth of field, which decreases as resolution increases, and only covers a very thin layer of space, so that topography or movements along the depth axis cannot be observed.

Electron microscopes

Electron microscopy relies on electrons instead of photons. Electrons are emitted by a field electron gun (electromagnetically induced) or a thermoionic field gun (tungsten filament, LaB6 cathode). As with photonic microscopy, these electrons can then be reflected (SEM: Scanning Electron Microscopy) or transmitted (TEM: Transmission Electron Microscopy). The electron beam interacts with matter as it hits its surface, which results in emissions e.g. secondary, Auger, back-scattered electrons, or X-rays. These emissions are intercepted by specific sensors, and treated so as to reconstruct an image of the object’s surface, topography, atomic composition…
A SEM can reach sub-nanometre resolutions, and a TEM ten times finer resolutions yet on thin samples. However, the electron beam also interacts with the environment along the distance that separates it from the samples, including air molecules – an electron microscope therefore requires a vacuum chamber (or at least, in the case of the more recent « environmental » models2,
1The Rayleigh criterion or Rayleigh limit: half the illumination wavelength.
2 These models, based on technology enabling airtight transmission between the gun and sample chambers, are meant to extend their application range to the observation of e.g. hydrated objects around the triple point of water, or objects that would be damaged by low pressure.
1. Micro-robotics, observation and actuation
an environment with controlled pressure and composition). Further, the samples and sample holders must be conductive, lest electric charges accumulate on them and interfere with the behaviour of the microscope. Despite these drawbacks, electron microscopy is the most popular when real-time vision feedback is required at resolutions not reached by optical microscopy.
Figure 1.3 – Images of a 20 30 m membrane by optical (left) and electron (right) microscopy.

Local probe microscopes

These microscopes use end-tools of various natures, sizes and operating principles, which have in common that they probe the observed surfaces with a stiﬀ tip. In each case, the apex of this tip is of a nano- or micrometre scale and is brought very close or even in contact with the zones of interest. Imaging conducted with quartz probes falls into this category.
Atomic Force Microscopes (AFM) [?] : probes are either soft cantilevers deflecting and reflecting a laser, or more recently so-called « self-sensing » probes, such as the quartz resonators used in this work. Measured data are the Z (vertical) position of the probe and the interaction forces applied on the apex of its tip, be they attractive or repulsive. This combined information allows the reconstitution of a topographic profile of the sample’s surface, and/or the measurement of forces at the nano- or pico-Newton scales. The three main AFM modes are contact mode, intermittent contact (or « tapping »), and « non-contact » (or « near-contact ») modes. These modes of operation, as well as the state of the art in AFM, will be further elaborated on in the next section of this chapter. Aside from (or in conjunction with) microscopy, AFM probes can also be used as self-sensing manipulators [?].
Scanning Tunnelling Microscopes (STM) [?] can be used for conductive or semi-conductive samples. As the tip remains within 0.1 to 1 nanometre of the object’s surface, informa-tion is obtained through the electric current flowing between the two. Tunnelling can also be combined with atomic force microscopy on a same probe [?], with the drawback that any deformation caused by one mode of observation is then itself observed by the other with a phase shift [?]. Just as AFM can be used to push objects along with their imaging capabilities, so have STM been used for electrodeposition – for instance to build nanometre-scale batteries [?].
The capabilities of local probe microscopes vary widely across all types – the technology is however the most precise currently in use, and can reach the atomic resolution [?]. The main performance downside of local probe microscopy is the length of time it takes to scan an image: several minutes for micrometre-sized samples, and up to half an hour or more when aiming for higher-resolution images. This is one of the motivations behind seeking higher-frequency quartz resonators in the next two chapters, and the literature on the subject will be examined in Sect. ??. Although quartz local probes will be used as imaging tools in Chapter 3, the sample characterisation experiments that follow in Chapter 4 will require real-time vision: electron microscopy (SEM) will therefore be the observation method of choice. Whether it be for imaging or its applications in force sensing or characterisation, local probe microscopy will equally rely on micro-actuation systems; we now turn towards these sytems and their combined use with SEM.

Micro-robotic systems and SEM-controlled characterisation

Micro-robotic setups involve accurate movements at the micro-scale, carried through actu-ating systems at the end of which eﬀectors are displaced by micrometric or nanometric steps. These systems can be composed of one or more actuators, and assembled into micro-robotic plat-forms with one or several eﬀectors adapted to the environment, sample objects and observation method.

Micro-robotic actuators

Micro-robotic actuators exploit displacement phenomena which are not significant at the macro-scale but oﬀer great accuracy in micro-manipulation. The main actuating principles used in micro-robotics are piezoelectric; electrostatic; thermal; SMA (shape memory alloys) or EAP (electroactive polymers) [?].
To this day, actuators used in micro-robotics have for the most part been based on the piezoelectric eﬀect: deformation occurs when current is applied through piezoelectric ceramics in a quantified and repeatable manner, which is easily controlled in closed loop. This deforma-tion, when exploited directly, oﬀers the ability to apply continuous displacement at extremely high resolutions proportional to the actuator’s size. Hence, the best resolutions and speeds [?] cannot be directly applied on a large range. A common way to remedy this problem is to have a small-range, accurate positioner placed at the end of a rougher, larger-range positioner chain. Another way to exploit the piezoelectric eﬀect for larger-range positioning exists through the stick-slip principle [?] : during the « stick » phase, a progressive displacement is applied by a piezoelectric actuator, during which the eﬀector is carried by its guide through friction; then the electric signal driving this displacement is suddenly inverted, and the subsequent, comparatively much quicker deformation or relaxation of the piezoelectric actuator withdraws the guide but lets the end eﬀector « slip » (Fig. ??). Whereas the actuators used in Chapter 3 are piezo-stacks with a range limited to 50 micrometres, Chapter 4 will make use of stick-slip actuators with a range over a centimetre, which represents an advantage over a combination of distinct coarse-and fine actuators in that the position sensors remain the same throughout both large-range and close-range motion – meaning that the reference position between eﬀector and sample is not lost after large-range relocation, in turn enabling enough flexibility for operations such as the local characterisation of samples on a larger-scale batch to go on uninterrupted.
Other types of positioners are found in the literature, especially in order to satisfy specific requirements with regard to performance or environmental conditions. General-purpose micro-robotic manipulation platforms (such as the SmarPod system used in this work), however, all rely on the piezoelectric eﬀect.

SEM-integrated platforms

In order to use a manipulation system at the nanometric scale, the positions of the tools and eﬀectors relative to the objects with which they interact need to be observed in a fairly precise manner. In the case of Atomic Force Microscopy (AFM), the manipulator itself can be used as a probe to obtain images before or during the manipulation, but more complex or exploratory operations call for more direct visual feedback. Using scanning electron microscopes (SEMs) is advantageous in this regard. This choice is mainly motivated by performances that classical optical microscopy cannot oﬀer: the nanometric imaging resolution, and the depth of field which is instrumental to simultaneously observing tools and samples. Indeed, in a typical setup, tools and samples end up being superimposed vertically during operations, and the field of view needs to be tilted at an angle in order to discern the precise interactions and contact points between the two (Fig. ??). In these conditions, it is often impossible to focus on both using optical microscopy. Without a depth of field such as that oﬀered by a SEM, it is possible for AFM and derived technologies to rely on force-feedback to control the position of the tools relative to substrates and samples; one can also tilt the eﬀectors rather than the whole system, or use angled tool tips [ ?] as is often the case for cantilevers. However, in some cases tools must stay perpendicular to the surface of the sample (see Chapter 2, Sect. ??) and, short of designing specific interface tools, a tilted field of view with a high depth of field may indeed be required for human-operated experimentation.
Figure 1.6 – Illustration of the reduced depth of field in optical microscopy and its impact when the observed surface is tilted – a.: Cantilever tool viewed from above; b.: Focal plane in a tilted setup; the depth of field cannot fully include both the probe and sample.
Dissuasive factors, on the other hand, are the cost and upkeep of a SEM. Besides, the tech-nical challenges related to the use of a SEM are themselves the subject of much work, usually concerning the vacuum chamber which is part of a SEM. When it comes to eﬀectors and tools, these challenges include the potentially limited space of the chamber, the restriction to specific materials (vacuum-compatible, and nonmagnetic so as not to interfere with the electron beam), and the absence of thermal dissipation through convection (which is a limitation to how much heat the sensors and actuators are allowed to generate). For samples, diﬃculties include the fixation, loading and unloading inside the chamber, and specific conditions required for the ob-servation of hydrated or biological samples which otherwise exsiccate. Further, observed objects have to be suﬃciently conductive so as not to be electrically charged (and thus rendered un-observable or even damaged) under the eﬀect of the electron beam – this is often, for normally non-conductive surfaces, done through metallisation.
The overview of SEM-integrated nanomanipulation platforms as described in the literature shows that electron microscopy is a viable and valued tool in micro-robotics. The main char-acteristics for the micro-robotic platforms found in recent papers are summarised in table ??: embedding into a SEM correlates with nanometre-range experiments, and with flexible degrees of freedom; both are exemplified in the specific advantages of self-sensing AFM probes.
The operation of quartz probes in force sensing or mechanical characterisation, just like topographical imaging, finds its roots in Atomic Force Microscopy (AFM). This particular branch of local probe microscopy was developed by Binnig, Quate and Gerber in 1986, following the invention of the Scanning Tunneling Microscope (STM). AFM and STM have since been pre-eminent methods of observation and measurement at the nanoscale and below. Although AFM can be used for manipulation, i.e. the pushing and positioning of small objects, this aspect will not addressed here, the focus being on force sensing and imaging. This section will first summarise the general principles and control modes of AFM, then the use of tuning forks as AFM probes, the medium specificities of ambient and liquid environments, and the evolution towards faster AFM imaging.

READ The art of bowling ball

General principles of AFM

AFM as it was first conceived [?] consists in using a cantilever as a probe: a soft horizontal beam, clamped at one end and with a sharp vertical tip at the other; this initial setup also allowed some degree of observation under an optical microscope. Countless other applications based on AFM were then developed. AFM can be combined together with another observation technique, such as optical microscopy for coarse positioning, an electron microscope for more precise yet relatively large-scale observation, or complementary tools such as fluorescence [?] for biological applications.
Figure 1.7 – AFM setup with a photodiode measuring laser deflection [?].

AFM modes

The term AFM in and of itself only describes the use of nanoscale force sensing, but can refer to very diﬀerent ways of using a probe. There are three main variations of AFM:
contact mode, or static mode: the cantilever’s tip is and remains in contact with the imaged surface, and the beam’s deflection is measured – usually through laser reflection (Fig. ??). During the scan, the cantilever or the substrate are moved along the vertical axis so as to maintain a constant application of force. This mode obviously involves high forces and frictions, and can damage both the tool and the observed surfaces.
« non-contact » or « near-contact » mode: the cantilever is excited by an oscillator and vibrates close to its resonance frequency. When the tip is brought onto the surface of the sample, the interaction forces influence the frequency, amplitude and phase of the oscillation, whence data is extracted to reconstitute an image. The oscillation amplitude must remain small, at a sub-nanometre or even sub-Angström scale, to remain within the range of attractive forces (Fig. ??).
« tapping » mode: this hybrid dynamic mode somewhat combines contact and dynamic modes. The cantilever is also excited, and the tip only briefly touches the surface, near the desired maximum amplitude when the oscillating movement reaches its end. This mode usually uses greater oscillation amplitudes than pure non-contact modes, as it needs to be able to pull free from adhesion forces.

Model

In this section, we define elements in our model such as objects, transactions and histories. Our model is very similar to the models of Adya [3] and Bernstein et al. [24]. We also define formally the concept of a replication system used throughout this thesis.

Objects & transactions

Let Objects be a set of objects, and T be a set of transaction identifiers. Given an object x and a transaction identifier i, xi denotes version i of x written by Ti. A transaction Ti2T is a finite sequence of read and write operations followed by a terminating operation, commit (ci) or abort (ai). Throughout this thesis, a read-only transaction is specified with an alphabetic subscript, and an update transaction with a numeric subscript. We use wi(xi) to denote transaction Ti writing version i of object x, and ri(xj) to mean that T i reads version j of object x. We assume that the initial transaction T0 installs the initial versions of all objects. Without loss of generality, we assume that in a given transaction, every write is preceded by a read to the same object, and every object is read or written at most once. 1 We note ws(Ti) the writeset of Ti, i.e., the set of objects written by transaction Ti. Similarly, rs(T i) denotes the readset of transaction Ti. Two transactions conflict when they access the same object and at least one of them modifies it (i.e., rs(Ti) \ ws(T j) =6 ?); they write-conflict when they both write to the same object (i.e., ws(Ti) \ws(T j) =6 ?).
Ordering transactions globally is expensive, specially in large scale systems because all replicas should be involved in the execution of some agreement protocol that orders messages globally. In addition, protocols based on atomic broadcast cannot fully leverage the benefits of partial repli-cation since all processes are still involved in processing each transaction. Hence, an emerging alternative is to order transactions partially for partial replication protocols [117, 127, 129, 130]. In this approach, transactions are totally ordered within some replica groups (or some partitions), but they are not totally ordered globally.
Atomic Multicast Atomic Multicast sends a message m to ∞ groups of processes using AM-Cast primitive, and atomic-delivers m to all processes in ∞ using AM-Deliver primitive.
Uniform Atomic Multicast ensures the following properties [122]:
(i) Validity: if a correct process atomic-multicasts m, then eventually all correct processes in ∞ atomic-deliver m.
(ii) Uniform Integrity: a process p atomic-delivers message m at most once, and only if m was previously atomic-multicast.
(iii) Uniform Agreement: if a process atomic in ∞ atomic-delivers message m, then eventually all correct processes in ∞ atomic-delivers m.
(iv) Uniform Prefix order: for any two process p and q that are the recipients of m1 and m2, if p atomic-delivers m1 and q atomic-delivers m2, then either p atomic-delivers m2 before m1 or q atomic-delivers m1 before m2.
(v) Uniform Acyclic Order: noting m1 < m2 if and only if m1 is delivered before m2 by a process, the relation < is acyclic.
Note that the uniform prefix order disallows holes in the sequence of messages delivered by processes. For instance, consider that three messages m1, m 2 and m3 are atomic-multicast to a group g containing process p and q. Process p delivers all messages as follows: m1 < m2 < m 3. Without this property, a faulty process q would be allowed to deliver only m1 and m3 in the same order, and to skip the delivery of m2. Uniform prefix order precludes this.
In addition, uniform acyclic order ensures a global partial order of messages without cycles. For instance, consider messages m1 sent to groups gx and gz, message m 2 that is atomic-multicast to groups gx and g y, and finally m3 that targets groups gz and g y. Without the acyclic ordering properties, groups would be able to deliver messages in the following orders: 1. group gx: m1 < m2; 2. group g y: m2 < m3; 3. group gz: m3 < m1.

STRONG CONSISTENCY CRITERIA

All the above reviewed approaches provide the same functionality: they are used to commit or abort a transaction atomically at all replicas. Hence, we use the term atomic commitment to refer to any protocol providing this functionality.

Strong Consistency Criteria

In this section, we first define a consistency criterion, and a strong consistency criterion concepts. Then we review some of the main strong consistency criteria, along with the anomalies that they expose to clients. Finally, we compare the criteria reviewed in terms of their undesirable effects.
A (transactional) consistency criterion is a safety property that constraints how transactions interleave. Roughly speaking, a safety property ensures that nothing bad happens [79]. In the database community, this safety property is named isolation level (I in ACID) because they ensure different levels of non-interference between transactions [3], and the term consistency is used to specify the application-level consistency (C in ACID). In the first part of this thesis, we use the term consistency criterion as Adya [3] to refer to isolation levels (such as serializability).
Definition 2.1 (Consistency Criterion). A consistency criterion C is a prefix-closed subset of H, where H is the set of all histories.
Depending on how transactions are interleaved in each consistency (i.e., deviate from se-quential execution), some undesirable observations called anomalies are observable in each consistency. Some of these anomalies are tractable: they can be precluded easily.
Tractable Anomalies In what follows, we review three tractable anomalies, and briefly ex-plain different ways to preclude them.
Dirty Write happens when a modification to an object is overwritten with the changes made by another unfinished transaction.
Definition 2.2 (Dirty Write). Dirty Write happens in a history h when transaction Ti modifies an object x, and before committing or aborting, another transaction T j also modifies x. If either
T i or T j aborts, then it is not clear what should be the final value of object x.
Berenson et al. [22] consider that any consistency criterion should prevent the dirty write anomaly. In practice, it is easy to prevent this anomaly either by using locks, or by using a multi-version scheme and making changes visible once the transaction commits.
The second tractable anomaly is Dirty Read anomaly. For instance, consider the following history: hdr = r 1(x0).w1(x1).ra(x1).ca.a1. In this history, transaction Ta reads an uncommitted value from T1, and commits; transaction T1 later aborts, and does not install x1.
Definition 2.3 (Dirty Read). Dirty read happens in a history h when a transaction T j reads a value of the object modified by an uncommitted transaction Ti, and Ti may later abort or change again the value of the object.

Table of contents :

1 Introduction
1.1 Contributions
1.1.1 Part I
1.1.2 Part II
1.2 Outline of the thesis
Part I: Ensuring Consistency in Transactional Data Stores
2 Background
2.1 Model
2.1.1 Objects & transactions
2.1.2 Histories
2.1.3 Distributed System
2.1.3.1 Failure Models
2.1.3.2 Synchrony Assumptions
2.1.3.3 Failure Detectors
2.1.4 Replication
2.1.5 Transactional Commitment
2.1.5.1 Atomic Commitment Approach
2.1.5.2 Total Ordering Approach
2.1.5.3 Partial Ordering Approach
2.2 Strong Consistency Criteria
2.2.1 Strict Serializability (SSER)
2.2.2 Full Serializability (SER)
2.2.3 Update Serializability (US)
2.2.4 Snapshot Isolation (SI)
2.2.4.1 Generalized Snapshot Isolation (GSI)
2.2.5 Parallel Snapshot Isolation (PSI)
2.2.6 Causal Serializability (CSER)
2.2.7 Consistency Criteria for Software Transactional Memory
2.2.8 Anomaly Comparison
2.3 Liveness and Progress
3 Catalog of Transactional Protocols Supporting Partial Replication
3.1 Scalability Properties
3.1.1 Wait-Free Queries (WFQ )
3.1.2 Genuine Partial Replication (GPR )
3.1.3 Minimal Commitment Synchronization
3.1.4 Forward Freshness
3.2 Review of Transactional Protocols Supporting Partial Replication
3.2.1 SSER
3.2.2 SER
3.2.3 US
3.2.4 SI
3.2.5 PSI
4 Scalability of Strong Consistency Criteria
4.1 Decomposing SI
4.1.1 Absence of Cascading Aborts (ACA)
4.1.2 Consistent and Strictly Consistent Snapshots (SCONS)
4.1.3 Snapshot Monotonicity (MON)
4.1.4 Write-Conflict Freedom
4.1.5 The Decomposition
4.2 The impossibility of SI with GPR
4.3 Discussion
4.3.1 SSER and Opacity
4.3.2 SER
4.3.3 PSI
4.3.4 Circumventing The Impossibility Result
4.4 Conclusion
5 NMSI : Non-monotonic Snapshot Isolation
5.1 Definition of NMSI
5.2 Jessy: a Protocol for NMSI
5.2.1 Taking Consistent Snapshots
5.2.2 Transaction Lifetime in Jessy
5.2.3 Execution Protocol
5.2.4 Termination Protocol
5.2.5 Sketch of Proof
5.2.5.1 Safety Properties
5.2.5.2 Scalability Properties
5.3 Ensuring Obstruction-Freedom
5.4 Empirical study
5.4.1 Implementation
5.4.2 Setup and Benchmark
5.4.3 Experimental Results
5.5 Conclusion
6 G-DUR: Generic Deferred Update Replication
6.1 Overview
6.2 Execution
6.2.1 Version Tracking
6.2.2 Picking a Version
6.3 Termination
6.3.1 Group Communication
6.3.2 Two-Phase Commit
6.3.3 Fault-Tolerance
6.4 Realizing Protocols
6.4.1 P-Store
6.4.2 S-DUR
6.4.3 GMU
6.4.4 Serrano07
6.4.5 Walter
6.4.6 Jessy2pc
6.5 Implementation
6.6 Case Study
6.6.1 Setup and Benchmark
6.6.2 Comparing Transactional Protocols
6.6.3 Understanding Bottlenecks
6.6.4 Pluggability Capabilities
6.6.5 Dependability
6.6.5.1 Disaster Prone
6.6.5.2 Disaster Tolerant
6.7 Related Work
6.8 Conclusion
Part II: Ensuring Consistency in Non-Transactional Data Stores
7 Tuba: A Self-Configurable Cloud Storage System
7.1 Introduction
7.2 System Overview
7.2.1 Tuba Features from Pileus
7.2.2 Tuba’s New Features
7.3 Configuration Service (CS)
7.3.1 Constraints
7.3.2 Cost Model
7.3.3 Selection
7.3.4 Operations
7.3.4.1 Adjust the Synchronization Period
7.3.4.2 Add/Remove Secondary Replica
7.3.4.3 Change Primary Replica
7.3.4.4 Add Primary Replica
7.3.4.5 Summary
7.4 Client Execution Modes
7.5 Implementation
7.5.1 Communication
7.5.2 Client Operations
7.5.2.1 Read Operation
7.5.2.2 Single-primary Write Operation
7.5.2.3 Multi-primary Write Operation
7.5.3 CS Reconfiguration Operations
7.5.4 Fault-Tolerance
7.6 Evaluation
7.6.1 Setup and Benchmark
7.6.2 Macroscopic View
7.6.3 Microscopic View
7.6.4 Fast Mode vs. Slow Mode
7.6.5 Scalability of the CS
7.7 Related Work
7.8 Conclusion
8 Conclusion
8.1 Future Work
Part III: Appendix
A Proof of SI Decomposition
B Correctness of Jessy
B.1 Safety
B.2 Liveness and Progress
C Résumé de la thèse
C.1 Résumé
C.2 Introduction
C.2.1 Contributions
C.2.1.1 Partie I
C.2.1.2 Partie II
C.3 Passage à l’échelle du Critère de Cohérence Forte
C.3.1 Décomposition SI
C.3.1.1 Annulation en cascade (Absence of Cascading Aborts)
C.3.1.2 Instantanés cohérents et strictement cohérents
C.3.1.3 Instantané monotone
C.3.2 Write-Conflict Freedom
C.3.3 La décomposition
C.3.4 L’impossibilité de SI avec GPR
C.4 Non-monotonic Snapshot Isolation
C.5 Generic Deferred Update Replication
C.6 Un Système de Stockage Cloud Auto-Configurable
Bibliograph