diff options
| -rw-r--r-- | doc/talks/2023-01-18-tocatta/talk.pdf | bin | 2488793 -> 2490671 bytes | |||
| -rw-r--r-- | doc/talks/2023-01-18-tocatta/talk.tex | 61 |
2 files changed, 37 insertions, 24 deletions
diff --git a/doc/talks/2023-01-18-tocatta/talk.pdf b/doc/talks/2023-01-18-tocatta/talk.pdf Binary files differindex 6a70fcd7..3d0c8830 100644 --- a/doc/talks/2023-01-18-tocatta/talk.pdf +++ b/doc/talks/2023-01-18-tocatta/talk.pdf diff --git a/doc/talks/2023-01-18-tocatta/talk.tex b/doc/talks/2023-01-18-tocatta/talk.tex index 4c3e4eeb..09250cf1 100644 --- a/doc/talks/2023-01-18-tocatta/talk.tex +++ b/doc/talks/2023-01-18-tocatta/talk.tex @@ -509,7 +509,8 @@ \begin{frame} \frametitle{Consensus vs weak consistency} \begin{center} - \textbf{The same objects cannot be implemented in both models.} + \textbf{From a theoretical point of view:}\\ + \end{center} \vspace{2em} @@ -519,11 +520,8 @@ \vspace{1em} - \textbf{Any sequential specification}\\~ - - \vspace{1em} - \textbf{Easier to program for}: just write your program as if it were sequential on a single machine - + Require \textbf{additionnal assumptions} such as a fault detector or a strong RNG\\ + (FLP impossibility theorem) \end{minipage} \hfill \begin{minipage}{6.5cm} @@ -531,19 +529,20 @@ \vspace{1em} - \textbf{Limited objects such as CRDTs}\\(conflict-free replicated data types) - - \vspace{1em} - Part of the complexity is \textbf{reported to the consumer of the API}\\~ + Can be implemented in \textbf{any\\asynchronous message passing\\distributed system} with node crashes \end{minipage} \hspace{1em} + + \vspace{3em} + \begin{center} + They represent \textbf{different classes of computational capability}\\ + \end{center} \end{frame} \begin{frame} \frametitle{Consensus vs weak consistency} \begin{center} - \textbf{From a theoretical point of view:}\\ - + \textbf{The same objects cannot be implemented in both models.} \end{center} \vspace{2em} @@ -553,7 +552,11 @@ \vspace{1em} - Require \textbf{additionnal assumptions} such as a fault detector or a strong RNG\\~ + \textbf{Any sequential specification}\\~ + + \vspace{1em} + \textbf{Easier to program for}: just write your program as if it were sequential on a single machine + \end{minipage} \hfill \begin{minipage}{6.5cm} @@ -561,14 +564,12 @@ \vspace{1em} - Can be implemented in \textbf{any asynchronous message passing distributed system} + \textbf{Only CRDTs}\\(conflict-free replicated data types) + + \vspace{1em} + Part of the complexity is \textbf{reported to the consumer of the API}\\~ \end{minipage} \hspace{1em} - - \vspace{3em} - \begin{center} - They represent \textbf{different classes of computational capability} - \end{center} \end{frame} \begin{frame} @@ -608,7 +609,7 @@ $\to$ the API cannot be implemented in a weakly consistent system \vspace{2em} \item \textbf{This API can be implemented using only weak primitives}\\ - (e.g. a bunch of atomic registers)\\ + (e.g. in the asynchronous message passing model with no further assumption)\\ $\to$ the API is strictly weaker than consensus\\ $\to$ we can implement it in Garage! \end{itemize} @@ -625,7 +626,10 @@ \item \textbf{Performance issues:} \vspace{1em} \begin{itemize} - \item The leader is a \textbf{bottleneck} for all requests + \item Theoretical requirements (RNG, failure detector) translate into \textbf{practical costs} + \vspace{1em} + \item The leader is a \textbf{bottleneck} for all requests;\\ + even in leaderless approaches, \textbf{all nodes must process all operations in order} \vspace{1em} \item Particularly \textbf{sensitive to higher latency} between nodes \end{itemize} @@ -746,10 +750,19 @@ \end{frame} \begin{frame} - \frametitle{The hard parts we don't address (yet!)} + \frametitle{A hard problem: layout changes} \begin{itemize} - \item Maintain consistency changes when nodes assigned to a partition change:\\ - \item TODO + \item We rely on quorums $k > n/2$ within each partition:\\ + $$n=3,~~~~~~~k\ge 2$$ + \item When rebalancing, the set of nodes responsible for a partition can change:\\ + $$\{n_A, n_B, n_C\} \to \{n_A, n_D, n_E\}$$ + \vspace{.01em} + \item During the rebalancing, $D$ and $E$ don't yet have the data,\\ + ~~~~~~~~~~~~~~~~~~~and $B$ and $C$ want to get rid of the data to free up space\\ + \vspace{.2em} + $\to$ quorums only within the new set of nodes don't work\\ + $\to$ how to coordinate? \textbf{currently, we don't...} + \end{itemize} \end{frame} |