Reorder and add a hard problem

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
index 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}