text:
\chapter{Introduction}

\section{Using genetics to understand complex traits and diseases}

The overarching goal of human genetics is to understand how genetic variation influences phenotypes-- including complex traits and diseases-- within our species.  One approach to connect genotypic to phenotypic variation is to compare humans with non-human primates \cite{RN1343}. This approach is particularly compelling given that human share over 99\% of their DNA sequence with chimpanzees \cite{RN1929, RN2115}. Efforts have been made to understand the 1\%, that is to say the impact of these approximately 30 million single nucleotide polymorphisms (SNPs) differences \cite{RN3426, RN1929, RN2115, RN1342}. Importantly, the majority of these SNPs are in the non-protein coding regions of the genome \cite{RN1343}.
Overall this high degree of sequence similarity led Mary Claire King and Greg Wilson to hypothesize that it is the way these DNA sequences are regulated that leads to phenotypic differences \cite{RN1343}. Consequently, comparisons between humans and non-human primates can help to determine how these DNA sequences function and to reveal the underlying mechanisms that act on or as a result of sequence variation. This desire for for mechanistic understanding has inspired a number of studies to compare gene regulation levels, epigenetic marks, protein levels, and various other molecular phenotypes \cite{RN3251, RN2106, RN1, RN1931, RN1929, RN3285, RN2110, RN2111, RN2113, RN2091, RN3288, RN1966, RN3286, RN3284}.
These efforts have resulted in large comparative genomic catalogs of similarities and differences in gene regulation between humans and other primates. These catalogs have great potential to help us better understand the evolutionary processes that led to adaptations in humans \cite{RN3426, RN1339, RN2106, RN3419, RN519, RN1931, RN3425, RN3422, RN1929, RN3421, RN3435, RN3424, RN1798, RN2091, RN3427}, establish informed models of the relative importance of changes in different molecular mechanisms to regulatory evolution \cite{RN3423, RN3429}, and identify molecular pathways that may be functionally important in the context of complex diseases \cite{RN1339, RN2106}. However, the genetic variants that drive phenotypic diversity often have indirect effects on gene expression or protein levels \cite{RN1343}. It is therefore essential to design comparative studies that allow us to isolate the variables of interest while minimizing the effects of unwanted biological and technical differences. Yet, all too often, various aspects of study design are overlooked, to the detriment of the field. In extreme cases, poor study design leads to erroneous inference and incorrect interpretations \cite{RN3432, RN1402}. The majority of the time, a poor study design limits the accuracy of the study and by extension, the biological insight that can be drawn from it \cite{RN1339, RN3285, RN3434}. Compounding the issue is that study design considerations are usually not explicitly discussed in comparative genomic papers.

The majority of my work has focused on primate comparative genomics - an area which presents many opportunities to discuss how an effective study design can affect the results of a study and aid in its interpretation. In this Introduction, I focus on two principles critical to identifying robust biological differences between species: minimizing confounders and careful sample collection. However, the principles of study design that I will discuss extend beyond primate comparative genomics to any study that makes comparisons between groups, including case-control studies in humans.

\section{Study design challenges in comparative primate genomics}

\textit{Confounders and other potential biases.} As the technology used in genomic studies has progressed, so too has our understanding of the widespread nature and impact of confounders and other potential biases. Furthermore, using multiple species in functional genomic studies has increased the difficulty of minimizing these confounders. For example, early comparative studies using gene expression and DNA methylation microarrays often did not account for the attenuation of hybridization caused by sequence mismatches, which differ between species \cite{RN3419, RN1931, RN3430, RN3421}. More recently, common confounders of sequence-based comparative studies include individual sampling schemes that are unbalanced across species, and sample processing steps that are segregated by species \cite{RN1339, RN1, RN3285, RN3281, RN3432, RN3431}. Systemic differences inherent to the samples, such as differences in material quality between species \cite{RN1, RN3434}, also remain a concern. Similarly, a primate comparative framework brings forth analytical challenges. For example, analyses that do not use orthologous sequences or effective normalization procedures can result in bias \cite{RN1339, RN3285, RN3434}. Yet, most comparative genomic studies of humans and non-human primates that we are aware of, including previous studies from our own group \cite{RN1339, RN3285, RN3434}, suffer from one or more of these weaknesses and caveats.
Very few people would disagree that it is important to use good study design. However, the number of potential confounders are vast, including sex, date of death, age, RNA concentration, RIN score, RNA extraction date, library concentration, index sequence, sequencing pool, sequencing location, sequencing lane, total sequencing reads. Therefore, it can be difficult to detect confounding factors and bias introduced during sample processing or data analysis. Unfortunately, these factors are often neither accounted for nor discussed. Sometimes, this can lead to erroneous conclusions, which could have major implications for biological research. For example, a recent paper claimed that global gene expression levels were driven by species rather than tissue type \cite{RN3432}. Upon re-analysis, it was uncovered that the human and mouse samples used in the study were sequenced in different batches \cite{RN1402}.With this study design, the biological variable of interest (species) is confounded with the technical variable of sequence batch. Therefore, it is unknown to what extent the technical variable drove the biological results reported in the original paper.
Sorting out which results were driven by biological, rather than technical differences, is often led to the reader. Such a task can be quite challenging, as the comparative genomics field, and indeed, the larger genomics community, lacks consensus regarding meta-data collection and study documentation, particularly around sample and study design reporting.

\textit{Opportunistic study collection.} Sample type, size, and collection techniques are critical study design considerations in comparative studies of primates. Until recently, flash frozen tissues were one of the only options for comparing primate biological material \cite{RN1396}. Because of the difficulty of obtaining samples (both for logistic and ethical reasons), we could typically sample only a small number of individuals from each species. Consequently, some primate comparative studies only have only a handful of individuals per species \cite{RN2106, RN2111, RN2091}. Particularly problematic is when there is only 1 individual per species, as individual and tissue are confounded.
Even when there are 3 or more individuals per species, tissues are often subject to high environmental variances because the donors are in an uncontrolled environment, and also flash frozen and shipped post mortem \cite{RN1342}. The necessity of collecting samples opportunistically, together with small sample sizes, can lead to incomplete power to detect regulatory differences between species in any given study, and hence to relatively large apparent differences between studies.
 Furthermore, it was nearly impossible to obtain multiple tissue samples from the same individual. For example, to date, there have been no published comparative studies in primates that have analyzed multiple tissues sampled from the same individuals across multiple species in a balanced design \cite{RN1342}. Consequently, regulatory differences between tissues are always confounded with regulatory differences between individuals \cite{RN2091}. In turn, relative measures of tissue-specific regulatory differences between species are confounded with inter-tissue differences in regulatory variation within species.

\section{Study design challenges in psychiatric genetics}
Unfortunately, these study design challenges are not limited to the field of primate comparative genomics. For example, these are issues in psychiatric genetics and are highly prevalent in the nascent field of eating disorders genomics. \\
\textit{Confounders and other potential biases.} When performing eating disorder studies, complications with the phenotype lend itself to confounders and other potential biases. Like other psychiatric disorders, the way that eating disorders are diagnosed is inherently subjective, even if clinicians use the same criteria \cite{RN2643, RN2461}. For example, AN diagnoses comprise of qualitative criteria, such as over-concern with shape and weight and fear of becoming overweight \cite{RN2668}. While there are attempts to measure these aspects, it is not difficult. Consequently, there was an emphasis on introducing more quantitative measures, such as body mass index (BMI) to the diagnosis \cite{RN4372}. However, these types of quantitative measures are also inherently tricky for psychiatric disorders. For example, in AN, it is unknown whether BMI is only a consequence of AN or plays a role in furthering the disorder \cite{RN4372}. In case-control studies of individuals with anorexia nervosa (AN), disease state is confounded with BMI \cite{RN1166, RN4568}. This confounding complicates analysis and interpretation of results. For example, when a SNP is associated with AN cases, is the SNP associated with a specific AN behavior (and if so, which one) or with BMI?
Even within cases, clinical variables can be confounded, including medication types, age of diagnosis, and number of rehospitalizations \cite{RN1411}. In addition to the large number of biological variables, there are also technical considerations, such as RIN score and batch. As discussed earlier, the larger genomics community lacks consensus regarding meta-data collection and study documentation. This area has also been discussed in the eating disorder field but have not been widely acted upon \cite{RN4569}.
\\
\textit{Opportunistic study collection.} Similar to primates, tissues from humans are collected opportunistically. For many complex psychiatric trait, it is difficult to link genetic variation or gene regulatory differences, to phenotypes. While gene regulation in the brain is a logical place to start, it is difficult to access brains from living patients and a brain bank for eating disorders has only recently been established \cite{RN4533}. Moreover, the brain is extremely heterogeneous. Consequently, it is difficult to identify which brain regions are the most relevant to study \cite{RN3415}. Moreover, while recent research suggests tissues besides the brain may be relevant to disease state in AN \cite{RN10, RN4567, RN4568}, it is hard to decide which tissue to study. Blood is relatively easy to collect from individuals with eating disorders, but the clinical utility of whole blood is unknown \cite{RN1411}.
Since individuals are collected opportunistically, collecting large sample sizes, particularly in longitudinal studies are difficult. Furthermore, individuals are almost always recruited during a state of illness, so it can be difficult to predict patient trajectory and therefore the outcomes represented in the cohort \cite{RN4514}. This issue is compounded by the fact that many eating-disorder phenotypes, including treatment outcomes, are nebulous \cite{RN4543}.Indeed, although the field of eating disorder genomics faces many of the same obstacles as primate comparative genomics and psychiatric genomics more generally, it also presents a unique set of challenges.

\section{Conclusion}
Much of my thesis work has been devoted to addressing these challenges of potential biases and opportunistic study collection. In Chapters 2 and 3, I present examples of how to approach these challenges in gene regulatory studies across primates. Furthermore, I demonstrate that adherence to these key study design principles helps elucidate biological insight. In Chapter 4, I apply these lessons learned in a new context: comparing individuals with eating disorders at high risk of rehospitalization versus those with lower risk. In the final chapter, I discuss opportunities and challenges when using functional genomics to study eating disorders.


text:
%----------------------------------------------------------------------------------------
% Professional experience
%----------------------------------------------------------------------------------------
{{--
@isset ($data['professional experience'])
\section{ {{$data['professional experience']['title']}} }
\centering
\begin{tabuler}{r|p{15cm}}
@foreach ($data['professional experience']['sections'] as $i => $experience)
    \textsc{ {{ $experience['period'] }} } &  \textsc{ {{ $experience['title'] }} } \\
    \{{ $experience['link']['font awesome icon'] }}  \hspace{1mm}\href{ {{ $experience['link']['url'] }}  }{ {{ $experience['link']['title'] }}  } & \textit{Undergraduate experience at IIT Kanpur}\\
    \{{ $experience['link']['font awesome icon'] }}  \hspace{1mm}\href{ {{ $experience['link']['url'] }}  }{ {{ $experience['link']['title'] }}  } & \textit{Supervisor}: \textsc{Dr. Piyush Rai}
        @isset($experience['bullet points'])
            \begin{itemize}
                @foreach ( $experience['bullet points'] as $j=>$point)
                \item {{ $point }}
                @endforeach
            \vspace*{-\baselineskip}
            \end{itemize}\\
        @endisset
    \multicolumn{2}{c}{}\\
@endforeach
\end{tabuler}
@endisset

 --}}

@if (isset($data['professional experience']) && count($data['professional experience']['sections']) > 0)
    \section{ {{ $data['professional experience']['title'] }} } \vspace{1mm}
    \begin{tabular}{r|p{15cm}}

    @foreach ($data['professional experience']['sections'] as $i => $experience)

        {{ $experience['period'] }} & {{ $experience['title'] }} \\

        @isset($experience['bullet points'] )
        @foreach ($experience['bullet points'] as $subsection)
        \{{ $experience['link']['font awesome icon'] }} \hspace{1mm}
        \href{ {{ $experience['link']['url'] }} } { {{ $experience['link']['title'] }} }
        &
        {{ $subsection }} \\
        @endforeach

@endisset
        \multicolumn{2}{c}{} \\
    @endforeach
    \end{tabular}
@endif

ext: tex

max_stars_repo_name: akramaznakour/blade-your-latex

max_issues_repo_name: akramaznakour/blade-your-latex

max_forks_repo_name: akramaznakour/blade-your-latex


text:
% Lecture for ph2a Caltech 2017: Vibrations and Waves
\documentclass[pdf, handout, hideothersubsections]{beamer}
\usepackage{beamerthemeshadow}
\mode<presentation>
  {
    \usefonttheme{structuresmallcapsserif}
    \usetheme{Darmstadt}
    \usecolortheme{whale}
    %\useinnertheme{circles}
%    \useoutertheme{tree}
  }

\usepackage{svg}
\usepackage{multimedia}
\usepackage{xmpmulti}
\usepackage{mathtools}
%\usepackage{enumitem}
\usepackage{hyperref}
\hypersetup{
    pdffitwindow=true,     % window fit to page when opened
    colorlinks=true,       % false: boxed links; true: colored links
    linkcolor=orange,      % color of internal links
    citecolor=green,       % color of links to bibliography
    filecolor=magenta,     % color of file links
    urlcolor=blue,         % color of external links
    pdfstartview={Fit}
}

% Fonts/encoding
\renewcommand{\UrlFont}{\tiny}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[sc,medium,raggedright]{titlesec}
\usepackage{newtxmath}
%\usepackage{libertine}
\usepackage[osf]{ebgaramond}

\graphicspath{{Figures/}}

\begin{document}
\title{Traveling Waves}
\author{Caltech: ph2a}
\date{24 - Oct - 2017}

\frame{\titlepage}

\frame{\frametitle{Table of Contents}\tableofcontents}

\setbeamerfont{footnote}{size=\tiny}

\section{Summary}
\begin{frame}
\frametitle{Waves:}
\begin{enumerate}
  \pause
\item Restoring 'forces' lead to Partial Diff. Eq.
  \pause
\item Separable solutions yield ODE.
  \pause
\item This gives the wave equation:
  $\ddot{y} = \frac{1}{v^2} \frac{\partial^2 y}{\partial t^2}$
  \pause
\item Second order diff. eq. results in oscillatory solutions.
\pause
\item Fourier series decomposition of solutions.
\pause
\item Including the time dependence can give us \emph{traveling}
  waves.
\pause
\item Examples: light, sound, radio, water, cell phone transmissions,
  gravitational waves, and gravity waves.

\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Overview}
\begin{enumerate}
\pause
\item Standing wave solutions are super-position of forward and
  backward traveling wave solutions.
\pause
\item Propagation of a pulse is governed by the \emph{wave equation}
\pause
\item Relationship between space and time arguments determines
  direction of propagation of the wave.

\end{enumerate}
\end{frame}

\section{Standing Waves}
\begin{frame}
\frametitle{The Wave Equation}
\begin{block}{The Wave Equation}
\centering
$ \frac{\partial^2 y}{\partial t^2} = \frac{T}{\mu} \frac{\partial^2 y}{\partial x^2}$
\end{block}
\pause
\begin{alignat}{2}
\frac{d^2 g}{dt^2} &= \omega^2 g  &\quad g(t) &= C_1 cos(\omega t) \\
\frac{d^2 f}{dx^2} &= -k^2 f &\quad f(x) &= A cos(k x) + B
sin(k x)
\end{alignat}
\pause
where the velocity of the wave, $v \equiv \sqrt{\frac{T}{\mu}}$,
$\frac{\omega}{2 \pi}$ is the frequency, and $k \equiv \omega / v$ is
called the 'wave number'. For the wavelength of the wave, we use the
symbol $\lambda \equiv \frac{2 \pi}{k}$.
\end{frame}

\begin{frame}
\frametitle{Impose the Boundary Conditions}
\begin{centering}
\includegraphics[width=0.7\textwidth]{../../Simulations/modes_of_string.pdf}
\end{centering}
    \begin{enumerate}
    \item $f(x) = 0$ for $x \in \{0, L\} \implies$
      \pause
    \item $sin(k L) = 0$ for any and all t, and $A = 0$
      \pause
    \item so $k_n L = n \pi$ or $k_n = n \frac{\pi}{L}$
      \pause
    \item and $y(x, t) = A_n cos(\omega_n t) sin(k_n x)$
    \end{enumerate}
-- \href{http://www.baudline.com/}{Baudline} spectral analysis of
guitar, java string:
\end{frame}

\section{Traveling Waves}
\begin{frame}
\frametitle{Traveling (Progressive) Waves}
\pause
We can now use the trigonometric identity:
\begin{equation}
sin(\theta + \phi) + sin(\theta - \phi) = 2 sin(\theta) cos(\phi)
\end{equation} \pause
to rewrite our general solution as:
\begin{align}
y(x, t) &= A_n cos(\omega_n t) sin(n \frac{\pi}{L} x) \\
        &= \frac{A_n}{2} \bigg[sin(k_n x - \omega_n t)  + sin(k_n x + \omega_n t)\bigg]
\label{eq:genstand}
\end{align}
\pause
with $k_n = n \pi/L$, $v = \frac{T}{\mu}$, and $\omega_n = n v \pi/L$,
\pause
where each term is a \emph{traveling} wave. \\

\end{frame}

\begin{frame}
\frametitle{Traveling Wave: Animation}
\begin{columns}
  \begin{column}{0.4\textwidth}
    \centering
    \includegraphics[height=5cm]{travwaves.pdf}
    % \movie[externalviewer, showcontrols=true, poster,
    % width=4cm]{}{../../Simulations/travelling_wave.mp4}
  \end{column}
\begin{column}{0.6\textwidth}
Questions:
\begin{enumerate}
\item The wave travels with a velocity $v$ in x-direction. What is the
  velocity of the individual points?
\item Do the points exhibit simple harmonic motion?
\item Do all of the points move with the same frequency?
\item Do all of the points move with the same amplitude?
\end{enumerate}
\end{column}
\end{columns}

\end{frame}

\begin{frame}
\frametitle{Traveling Waves: Details}
Let's examine Eq.~\ref{eq:genstand} in more detail:
\pause
\includegraphics[width=\textwidth]{../../Simulations/detail-trav.pdf}
\pause
similarly, $sin(k_n x + \omega_n t)$ represents a wave traveling to
the left.

\end{frame}

\begin{frame}
\frametitle{Properties of Traveling Waves}
\begin{enumerate}
\item Any value of $k = 2 \pi / \lambda$ and $\omega = k v$ are allowed.
\pause
\item Infinite extent in space and time. No boundaries (in principle).
\pause
\item Principle of Superposition still applies: sum of traveling waves
  satisfies the wave equation.
\pause
\item Standing waves can be decomposed into a sum of traveling waves.
\pause
\item Traveling waves carry momentum and energy? How do we
  measure/calculate this?
\end{enumerate}
\end{frame}

\section{Summary}
\begin{frame}
\frametitle{Summary}
\begin{enumerate}
\pause
\item Standing wave solutions are super-position of forward and
  backward traveling wave solutions.

\item Propagation of a pulse is governed by the \emph{wave equation}

\item Relationship between space and time arguments determines
  direction of propagation of the wave.

\item Next: examine properties of air to examine sound waves and
  musical instruments (boundary conditions).

\end{enumerate}

\end{frame}

\end{document}


text:
\documentclass{article}[18pt]
\input{../format}
\lhead{AZ900}

\setlist{nolistsep}
\begin{document}
\begin{center}
\underline{\huge Principles of cloud computing}
\end{center}

\section{What is cloud computing}

Services typically offered

\begin{itemize}
	\tightlist
	\item
	Compute power
	\item
	Storage
	\item
	Networking
	\item
	Analytics
\end{itemize}

Containers - Provide a consistent, isolated execution environment for
applications.

\begin{itemize}
	\tightlist
	\item
	Standard runtime environment used to execute the app
	\item
	Leading platform is docker
\end{itemize}

Serverless computing - Run application code without creating,
configuring or maintaining a server

\begin{itemize}
	\tightlist
	\item
	Application is broken into separate functions that run when triggered
	by some action
	\item
	Only pay for the processing time used by each function as it executes
\end{itemize}

\hypertarget{benefits-of-cloud-computing}{%
	\section{Benefits of cloud
		computing}\label{benefits-of-cloud-computing}}

Cost effective

\begin{itemize}
	\tightlist
	\item
	No upfront infrastructure costs
	\item
	Not buying infrastructure that isn't fully utilised
	\item
	Can scale up and down with demand
\end{itemize}

Scalability

\begin{itemize}
	\item
	Vertical scaling (scaling up)
	\begin{itemize}

		\item
		Adding more resources to a server
	\end{itemize}
	\item
	Horizontal scaling (scaling out)
	\begin{itemize}

		\item
		Adding more servers
	\end{itemize}
\end{itemize}

Elasticity

\begin{itemize}
	\tightlist
	\item
	Automatically adding more resources to handle traffic
\end{itemize}

Current

\begin{itemize}
	\tightlist
	\item
	Don't have to think about having current hardware and patches
\end{itemize}

Reliability (Microsoft responsibility)

\begin{itemize}
	\tightlist
	\item
	Provided backup, recovery replication etc
	\item
	Fault tolerance
\end{itemize}

Global

\begin{itemize}
	\tightlist
	\item
	Fully redundant datacenters
	\item
	High availability (shared responsibility)
	\item Lower customer latency
\end{itemize}

Security (shared responsibility)

\begin{itemize}
	\tightlist
	\item
	Both physical and digital
\end{itemize}
Agility (speed to set up)

\hypertarget{compliance-terms-and-requirements}{%
	\section{Compliance terms and
		requirements}\label{compliance-terms-and-requirements}}

Questions include

\begin{itemize}
	\tightlist
	\item
	How compliant is the cloud provider when it comes to handling
	sensitive data
	\item
	How compliant are the services offered by the cloud provider
	\item
	How can I deploy my own cloud-based solutions to scenarios that have
	accreditation or compliance requirements?
	\item
	What terms are part of the privacy statement for the provider?
\end{itemize}

\hypertarget{economies-of-scale}{%
	\section{Economies of scale}\label{economies-of-scale}}

\begin{itemize}
	\tightlist
	\item
	Less expensive
	\item
	More efficient
	\item
	Pass benefits on
\end{itemize}

\hypertarget{capex-vs-opex}{%
	\section{CapEx vs OpEx}\label{capex-vs-opex}}

\subsection{CapEx (Capital expenditure)}

\begin{itemize}
	\tightlist
	\item
	Spend on physical infrastructure
	\item
	Storage
	\item
	Network
	\item
	Backup and archive
	\item
	Organisation continuity and disaster recovery
	\item
	Datacentre infrastructure
	\item
	Technical personnel
\end{itemize}
\subsection{Benefits}
Fixed costs make prediction easier

\subsection{OpEx (operational expenditure)}

\begin{itemize}
	\tightlist
	\item
	Monthly bill
	\item
	Pay as you go
	\item
	Get set up immediately
	\item
	No upfront costs
	\item
	Leasing software and customised features
	\item
	Scaling charges based on usage/demand
	\item
	Billing at the user or organisation level
\end{itemize}

Azure follows a consumption based model, which just has operational
expenditure
\subsection{Benefits}
Easier to respond to change

\hypertarget{types-of-cloud-models}{%
	\section{Types of cloud models}\label{types-of-cloud-models}}
{\renewcommand{\arraystretch}{2}
	\begin{tabularx}{\textwidth}{|s|s|b|b|}
\hline
Name& Description & Advantages & Disadvantages\\
\hline
Private cloud & Cloud set up in own datacenter&
 \begin{itemize}
	\tightlist
	\item Ensure the configuration is as needed
	\item Control over security and compliance
\end{itemize}&
\begin{itemize}
	\tightlist
	\item Some initial capEx Costs
	\item Limited agility
	\item Require IT skills
\end{itemize}\\
\hline
Public cloud& No local hardware, all running on cloud providers hardware&
\begin{itemize}
	\tightlist
	\item High scalability/agility
	\item Pay as you go pricing
	\item Not responsible for maintenance or updates of the hardware
	\item Minimal technical knowledge required
\end{itemize}&
\begin{itemize}
	\tightlist
	\item May be security requirements that can't be met
	\item May be government policies, industry standards or legal requirements that can't be met
	\item Can't manage hardware in way you want to
	\item May not work with legacy applications
\end{itemize}\\
\hline
Hybrid cloud& Combining public and private clouds&
\begin{itemize}
	\tightlist
	\item Keep any legacy systems running
	\item Flexibility to choose where things run
	\item Get economies of scale from public cloud when available
	\item Meet more compliance
	\item Run things where it is most appropriate
\end{itemize}&
\begin{itemize}
	\tightlist
	\item Increased cost
	\item Increased complexity
\end{itemize}\\
\hline
\end{tabularx}
}

\hypertarget{types-of-cloud-services}{%
	\section{Types of cloud services}\label{types-of-cloud-services}}

\hypertarget{iaas}{%
	\subsection{IaaS}\label{iaas}}
Most flexible category, gives control over hardware.\\
Commonly used for:
\begin{itemize}
	\item Migrating workflows
	\item Test and development
	\item Storage, backup and recovery
\end{itemize}

\textbf{Shared responsibility model} - Cloud provider ensures infrastructure is working correctly, customer makes sure the service they are using is configured correctly, is up to date and is available to users.

\hypertarget{paas}{%
	\subsection{PaaS}\label{paas}}
Provides an environment for building, testing and deploying software applications. Don't have to manage infrastructure\\
Commonly used for:
\begin{itemize}
	\item Development framework
	\item Analytics or business intelligence
\end{itemize}

\hypertarget{saas}{%
	\subsection{SaaS}\label{saas}}

Only responsible for data+access

Access in Azure via marketplace

Pay as you go pricing

Users pay for software they use on a subscription model

\subsection{Cost and Ownership}

{\renewcommand{\arraystretch}{2}
	\begin{tabularx}{\textwidth}{|s|s|b|b|}
		\hline
		& IaaS & PaaS & SaaS\\
		\hline
		Upfront costs& None, pay for consumption,& None, pay for consumption & None, pay subscription\\
		\hline
		User ownership& User responsible for software, OS, middleware and applications& User responsible fort development of applications& Users just use software\\
		\hline
		Cloud provider ownership& Infrastructure is available to user& OS, Network and service& Provision, management and maintenance of application software.\\
		\hline

	\end{tabularx}
}

\begin{center}
	\includegraphics[width=15cm]{5-layer-diagram}
\end{center}

\end{document}

max_stars_repo_path: Module 1 - Principles of cloud computing/Module_1.tex


text:
\documentclass[letterpaper, 12pt]{article}

\input{report/preamble}

\begin{document}

\begin{center}
  {\huge Schuster Lab - GRAPE 2.0 Proposal} \\[0.5em]
  {\large Thomas Propson $\vert$ \href{mailto:tcpropson@uchicago.edu}
    {tcpropson@uchicago.edu} \\[0.5em] \today}
\end{center}

\section{Motivation}
%% "Don't call it a comeback; I've been here for years" LL Cool J.

There are tasks we would like to perform that GRAPE 1.0 \cite{leung2017speedup} does not support. Additionally, there are performance improvements that can be made. We list them here:
\begin{enumerate}
\item GRAPE 1.0 uses Tensorflow to perform automatic differentiation. Tensorflow is a heavy-handed choice for the task at hand. It still does not support automatic differentiation with complex inputs. Therefore, it requires us to perform complex to real, and vice-a-versa, transformations in our code. It stores intermediate propagators and state vectors in its computation graph, using memory uneccessarily. Both storing the computation graph and waiting for a Tensorflow session to perform tensor operations incorporates unecessary boilerplate that can be shed.

\item GRAPE 1.0 does not support arbitrary relationships between control amplitudes and control operations. GRAPE 1.0 does not allow relationships between one control amplitude and more than one control hamiltonian (e.g. it does not allow $H = \epsilon(t)H_{control, 1} + \epsilon(t)^{*}H_{control, 2}$). Furthermore, GRAPE 1.0 restricts the relationship between control amplitudes and control hamiltonians to be linear (e.g. it does not allow $H = \epsilon(t)^{2}H_{control}$). Both of these examples occur in the Piccolo Hamiltonian:
\begin{align*}
  H &= \omega_{f}\ket{f}\bra{f} \\
  &+ \omega_{e}\ket{e}\bra{e}\\
  &+ \epsilon_{ge}e^{i\omega_{d}t}\ket{g}\bra{e} + \epsilon_{ge}^{*}e^{-i\omega_{d}t}\ket{e}\bra{g}\\
  &+ \epsilon_{ef}e^{i\omega_{d}t}\ket{e}\bra{f} + \epsilon_{ef}^{*}e^{-i\omega_{d}t}\ket{f}\bra{e}\\
  &+ \omega_{c}a^{\dagger}a\\
  &+ \chi_{e}\ket{e}\bra{e}a^{\dagger}a + \chi_{f}\ket{f}\bra{f}a^{\dagger}a\\
  &+ \epsilon_{sb}e^{i\omega_{d}t}\ket{f}\bra{g}a + \epsilon_{sb}^{*}e^{-i\omega_{d}t}\ket{g}\bra{f}a^{\dagger}\\
  &+ \epsilon_{sb}^{2}(\eta_{e}\ket{e}\bra{e} + \eta_{f}\ket{f}\bra{f})\\
\end{align*}
  Additionally, GRAPE 1.0 does not allow for time-dependent drift hamiltonians. For example, the qubit frequency in flux-tunable qubits is a function of flux through its junction, which is time-dependent.

\item In GRAPE 1.0, it is difficult to have complete control over the cost functions used in optimization and control their weights. For example, the fidelity cost function is always implicitly used but the user has no frame of reference to choose values for the regularization coefficients specified for other cost functions.

\item Better numerical approximation techniques can be used (e.g. matrix exponentiation, numerical integration, etc.).

\item There are opaque naming conventions and code formatting used in GRAPE 1.0. GRAPE 1.0 is hard to extend.
\end{enumerate}

\section{Automatic Differentiation}
We will use \href{https://github.com/HIPS/autograd}{Autograd} \cite{maclaurin2016modeling} for short operations in GRAPE 2.0. It supports gradients of functions that take complex inputs and return real outputs. This covers all cost functions that we care about and those we will care about: gradient-based optimization techniques require real, scalar output, cost functions. The package accepts functions performing python, numpy, and scipy operations and generates the corresponding gradient function.

For computations with small computation graphs, autograd performs comparably to hand derivatives (see Table 1 and 2, Figures 5 and 6). For the main integration of the GRAPE program, we can achieve constant memory usage where autograd requires exponential memory usage (see Table 3 and 4, Figures 7 and 8). Therefore, we will use hand derivatives for the core functionality of GRAPE 2.0, but outsource tasks which require variable differentiation to autograd. For example, we can use autograd to easily differntiate user defined functions such as cost functions and the hamiltonian specification at each time step.

\begin{table}
  \begin{center}
    \begin{tabular}{c | c | c | c}
      Matrix Size & Autograd + Numpy & Tensorflow & Hand Derivative + Numpy\\
                  & (s)              & (s)        & (s)\\
      \hline
      $2^{1}$  & 0.002646            & 0.533922 & 0.000249\\
      $2^{2}$  & 0.002308            & 0.535869 & 0.000431\\
      $2^{3}$  & 0.002335            & 0.541697 & 0.000496\\
      $2^{4}$  & 0.002350            & 0.550464 & 0.000554\\
      $2^{5}$  & 0.002920            & 0.558944 & 0.000963\\
      $2^{6}$  & 0.005398            & 0.623348 & 0.002803\\
      $2^{7}$  & 0.019332            & 0.961099 & 0.015257\\
      $2^{8}$  & 0.155580            & 2.740084 & 0.131249\\
      $2^{9}$  & 1.227607            & 15.46711 & 1.032369\\
      $2^{10}$ & 9.451809            & 132.5673 & 8.570398\\
    \end{tabular}
  \end{center}
  \caption{Backpropagation times in seconds for a single infidelity computation. A random initial state, target state, drift hamiltonian, control hamiltonians, and control amplitudes were generated. The control amplitudes were dotted with the control hamiltonians, which were added to the drift hamiltonian and exponentiated to get a unitary transformation. The unitary transformation was then applied to the initial state to get a final state. The infedlity (1 - $|<>|$) of the target state and final state was computed. The backward derivative of the infidelity with respect to the control amplitudes was calculated. The Tensorflow implementation required mapping of complex scalars, vectors, and matrices to augmented real forms using the isomorphism in Nelson's GRAPE implementation. Results reported are the mean over 10 trials. Computations were run on Fermium with 1 CPU. Fermium has an Intel i7-6700k @ 4.00GHz chip.}
\end{table}

\begin{table}
  \begin{center}
    \begin{tabular}{c | c | c | c}
      Matrix Size & Autograd + Numpy & Tensorflow & Hand Derivative + Numpy\\
                  & (MB)             & (MB)       & (MB)\\
      \hline
      $2^{1}$  &  166.16             &  565.42  &  165.49\\
      $2^{2}$  &  167.41             &  565.91  &  166.66\\
      $2^{3}$  &  167.30             &  567.42  &  166.82\\
      $2^{4}$  &  167.61             &  574.26  &  165.56\\
      $2^{5}$  &  167.53             &  596.09  &  165.84\\
      $2^{6}$  &  171.85             &  680.20  &  171.85\\
      $2^{7}$  &  178.93             &  915.97  &  172.33\\
      $2^{8}$  &  353.53             & 1976.30  &  299.00\\
      $2^{9}$  &  588.91             & 6776.11  &  646.94\\
      $2^{10}$ &  959.42             & 24335.64 & 1041.47\\
    \end{tabular}
  \end{center}
  \caption{Backpropagation median memory usage over program lifetime in megabytes for the infidelity computations (see Table 1). Memory usage was sampled every 0.1s. The trials here and in Table 1 were performed seperately. Results reported are the median memory usage for a program running 10 trials. Computations were run on Fermium with 1 CPU. Fermium has an Intel i7-6700k @ 4.00GHz chip.}
\end{table}

\begin{figure}
  %% \includegraphics[width=\linewidth]{data/run_time_test.png}
  \caption{Plots corresponding to the data in Table 1.}
\end{figure}

\begin{figure}
  %% \includegraphics[width=\linewidth]{data/memory_usage_test.png}
  \caption{Plots corresponding to the data in Table 2.}
\end{figure}

\begin{table}
  \begin{center}
    \begin{tabular}{c | c | c | c}
      Time Step Count & Autograd + Numpy & Hand Derivative + Numpy\\
                      & (s)              & (s)\\
      \hline
      $10^{0}$        &  0.00669          &  0.00965\\
      $10^{1}$        &  0.06077          &  0.05672\\
      $10^{2}$        &  0.56588          &  0.44039\\
      $10^{3}$        &  5.33935          &  4.25835\\
      $10^{4}$        & 55.45920          & 43.60220\\
    \end{tabular}
  \end{center}
  \caption{Backpropagation times in seconds for the infidelity program with multiple time steps. A random initial state, target state, drift hamiltonian, control hamiltonians, and control amplitudes were generated. The control amplitudes were dotted with the control hamiltonians, which were added to the drift hamiltonian and exponentiated to get a unitary transformation. The unitary transformation was then applied to the initial state to get a final state. The infedlity (1 - $|<>|$) of the target state and final state was computed. The backward derivative of the infidelity with respect to the control amplitudes was calculated. The hand derivative method took advantage of the fact that the state was propagated by unitary transformations. The size of the hilbert space was chosen to be $2^{6}$ based on the results in Table 1 and Table 2 to garauntee fixed overhead was avoided. 10 control hamiltonians and amplitudes were used at each time step. Results reported are the mean over 10 trials. Computations were run on Fermium with 1 CPU. Fermium has an Intel i7-6700k @ 4.00GHz chip.}
\end{table}

\begin{table}
  \begin{center}
    \begin{tabular}{c | c | c | c}
      Time Step Count & Autograd + Numpy & Hand Derivative + Numpy\\
                      & (MB)             & (MB)\\
      \hline
      $10^{0}$        & 165.40039        & 162.91992\\
      $10^{1}$        & 203.94922        & 188.88867\\
      $10^{2}$        & 284.78906        & 267.52734\\
      $10^{3}$        & 515.20703        & 267.42188\\
      $10^{4}$        & 2759.4727        & 271.37109\\
    \end{tabular}
  \end{center}
  \caption{Backpropagation median memory usage over program lifetime in megabytes for the infidelity computations with multiple time steps (see Table 3). Memory usage was sampled every 0.1s. The trials here and in Table 3 were performed seperately. Results reported are the median memory usage for a program running 10 trials. Computations were run on Fermium with 1 CPU. Fermium has an Intel i7-6700k @ 4.00GHz chip.}
\end{table}

\begin{figure}
  %% \includegraphics[width=\linewidth]{data/bpt2_run_time_plot.png}
  \caption{Plots corresponding to the data in Table 3.}
\end{figure}

\begin{figure}
  %% \includegraphics[width=\linewidth]{data/bpt2_memory_plot.png}
  \caption{Plots corresponding to the data in Table 4.}
\end{figure}

\section{Hamiltonian Specification}
The total hamiltonian (drift hamiltonian plus control hamiltonians) at each time step will be specified by providing a function to GRAPE that returns a hamiltonian $H_{j}$given the control operators for a time step $\{u_{j}\}$ and an integer $current\_step \in \{0, ..., steps - 1\}$. This will allow the user to perform arbitrary operations between $\{u_{j}\}$ and the control hamiltonians. This will allow the user to use time-dependent drift and control hamiltonians. The user could draw hamiltonians from a list indexed by the optimization step $current\_step$. This requires storing $steps$ number of matrices in memory and is not advised. Additionally, the user could get the wall time of the optimization by computing $t = current\_step * step\_count / pulse\_time$ to use accordingly. Autograd will allow us to get the gradient of this user-specified function with respect to $\{u_{j}\}$ for each time step.

All problems in GRAPE 2.0 will be framed as state (column vector) transfer problems. A set of initial states, and final states they map to, will be specified. Transferring an entire unitary is equivalent to transferring all basis states of the hilbert space.

\section{Cost Functions}
Cost functions will subclass a super cost function class. Each function will be instantiated with a corresponding weight and constants it requires. For example, the forbidden state cost function would be instantiated with a list of states that it is forbidding. The class will implement a method that computes a cost. The output of all cost functions should be normalized to 1. This will make it easier to choose cost function weights.

The inputs to the cost functions will be parameters of the optimization. Obviously, we must compute $\{u_{k, j}\}$ and expose them to the cost functions. Whether we provide intermediate states $\{\Psi_{j}\}$, intermediate propagators $\{U_{j}\}$, and/or total propagators $\{K_{j}\}$ is a question of memory. Suppose we have an optimization running on a hilbert space of size $2^{16}$, i.e. 16 qubits, and use 1000 optimization steps. If we use 128-bit percision complex numbers, storing $\{K_{j}\}$, $\{U_{j}\}$, and $\{\Psi_{j}\}$ together would require $128 * (2 * (2 ^{16})^{2} + 2^{16}) * 1000$bits $= 137.4$ terabytes.

Conversely, we could compute each $U_{j}$, use it to propagate the most recent $K_{j-1}, \Psi_{j-1} \rightarrow K_{j}, \Psi{j}$ and then discard $U_{j}$. We could then give $K_{j}$ and $\Psi_{j}$ to the cost function at each iteration, compute the cost and gradients for that time step and store them. This would only be required for cost functions that need to be computed for each time step, e.g. forbidden states. Functions such as target fidelity need only be evaluated at the end of optimization. The cost of a function call at each time step will add computational latency. However, only keeping, at most, $U_{j}, K_{j}, \Psi_{j}$ in memory at the same time would result in massive savings for large step sizes at large hilbert space dimensions. This would reduce memory usage in the above example from 137.4 terabytes to .1374 terabytes--a reduction that scales with the number of steps $10^{3}$.

Furthermore, we could discard propagating $K_{j}$ for state transfer problems and $\Psi_{j}$ for gate problems. In light of this analysis, each cost function class will specify if it needs to be called at each iteration, if it needs access to $\Psi_{j}$, and if it needs access to $K_{j}$. The optimization can then avoid using unecessary memory and time accordingly.

Dave believes that we should disregard $K_{j}$ altogether. Instead, he would have each problem specified as a state transfer or multi-state transfer problem. Note that a unitary transfer problem is the same as a multi-state transfer problem on the basis states. It may be more efficient to propagate a matrix in the case of the multi-state transfer; I suspect that performing $n$ matrix-vector multiplications is slower than performing one matrix-matrix multiplication where the second matrix has $n$ columns. If matrices are stored in row-major order, however, the matrix-matrix multiplication may be slower because the values ofeach column are spaced further apart in memory.

Computing gradients at each time step and adding them to a total gradient sum means that we cannot have cost functions that compute non-linear combinations of the costs they achieve at each time step. E.g. costs computed at different time steps can only be summed. Otherwise, it would be difficult to compute the gradient of that non-linear cost contribution to the total cost function. However, we don't anticipate needing this functionality.

\section{Numerical Compuatation Performance}
GRAPE 2.0 will expose more sophisticated methods for calculating the time-dependent schroedinger equation propagator. Namely, it will implement the second, fourth, and sixth order mangus integrator methods with commutators described in \cite{auer2018magnus}. More details can be found in \cite{blanes2009magnus}. I will try implementing the mutliple-exponential magnus integrators described in \cite{auer2018magnus} and compare their run time to the commutator methods. However, I expect that the commutator methods will be faster because I expect matrix exponentiation to be more expensive than matrix multiplication (see Table 5). Note that GRAPE 1.0 uses the second order magnus integrator method $U = \textrm{exp}(-i H \delta t)$.

GRAPE 2.0 could calculate the matrix exponential and the derivative of the matrix exponential using \href{https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.linalg.expm_frechet.html}{scipy.linalg.expm\_frechet}. Scipy's algorithm \href{https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.linalg.expm.html#scipy.linalg.expm}{scipy.linalg.expm} takes longer to perform than the algorithm used in GRAPE 1.0 for the $T = 10$ case (see Table 5 and Figure 9). However, Scipy's algorithm is more numerically accurate because it accounts for floating point round-off error \cite{al2009new}.

Note that if the drift and control hamiltonians are hermitian, then their linear combination with real coefficients is hermitian. Therefore, the system hamiltonian may be \href{https://en.wikipedia.org/wiki/Matrix_exponential#Computing_the_matrix_exponential}{diagonalized and exponentiated} easily. Similarly, the derivative of the matrix exponential for a diagonal matrix $A$ is given by $\frac{\partial}{\partial t} e^{A(t)} = e^{A(t)} \frac{\partial A(t)}{\partial t}$ which is easy to compute given the original exponentiated matrix. In particular, the matrix we exponentiate will be skew hermitian since $U = exp^{-i H \delta t}$ with $H$ hermitian. Since skew hermitian matrices are diagonalizable, we may consider an efficient matrix exponentiation algorithm with diagonalization.
\begin{table}
  \begin{center}
    \begin{tabular}{c | c | c | c}
      Matrix Size & Scipy & GRAPE 1.0, T = 10 & GRAPE 1.0, T = 20\\
      \hline
      $2^{1}$  & 0.000237 & 0.000057 & 0.000091\\
      $2^{2}$  & 0.000184 & 0.000058 & 0.000094\\
      $2^{3}$  & 0.000206 & 0.000062 & 0.000100\\
      $2^{4}$  & 0.000227 & 0.000079 & 0.000125\\
      $2^{5}$  & 0.000334 & 0.000134 & 0.000203\\
      $2^{6}$  & 0.001352 & 0.000353 & 0.000488\\
      $2^{7}$  & 0.002921 & 0.001032 & 0.001622\\
      $2^{8}$  & 0.016121 & 0.003776 & 0.006518\\
      $2^{9}$  & 0.047553 & 0.029418 & 0.049804\\
      $2^{10}$ & 0.274228 & 0.250185 & 0.418202\\
      $2^{11}$ & 2.121346 & 1.965816 & 3.065884\\
    \end{tabular}
  \end{center}
  \caption{Matrix exponentiation run times in seconds for Scipy and GRAPE 1.0 respectively. The reported values are the average over 100 matrices. All matrices are dense square matrices with row and column lengths equal to the reported matrix size. For GRAPE 1.0, the scaling factor $p$ is chosen such that $\frac{||A||}{2^{p}} \le 1$. $T$ corresponds to the number of taylor terms chosen for the GRAPE 1.0 algorithm. Computations were run on Fermium. Fermium has an Intel i7-6700k @ 4.00GHz w/ 8 CPUs.}
\end{table}

\begin{figure}
  %% \includegraphics[width=\linewidth]{data/expm.png}
  \caption{Plot corresponding to the data in Table 5.}
\end{figure}

\section{Time Discretization}
Sometimes we have a parameter in our system Hamiltonian that acts very quickly. Consider $H = \omega_{c}a^{\dagger}a$ where $\omega_{c} = 5$GHz. The osciallation of our system is on the order of $\frac{1}{5\textrm{GHz}} = \frac{1}{5}$nanoseconds. This suggests that we use an evolution time step of $\frac{1}{5}$ns. However, the sampling rate of our arbitrary waveform generator may only be 1 sample per ns. We typically get around this problem by performing a rotating frame transformation to our system Hamiltonian (e.g. $U=\textrm{exp}(i\omega_{c}a^{\dagger}at)$) that cancels the term $\omega_{c}a^{\dagger}a$ in our Hamiltonian. Consider a case where no such simple rotating frame transformation exists or where it makes the other terms in the Hamiltonian prohibitively hard to compute. In GRAPE 1.0 we cannot differentiate between the system rate and the sampling rate, so we must optimize the control pulse at $\frac{1}{5}$ steps per nanosecond even though we cannot realize the output pulse. In GRAPE 2.0 we could implement a scheme where control amplitudes are updated at one time step, but the system evolves at another. Let the rate at which we update the discrete pulse be known as the pulse rate. Let the rate at which we must account for changes in our system be known as the system rate. The optimization parameters will be updated at pulse steps and interpolated at system steps. The user will provide an interpolation scheme which will be differentiated with autograd. The gradient of each of the parameters will be calculated at both pulse and system steps. For simplicity, the number of system steps must be an integer multiple of the pulse steps.

Another way to overcome this obstacle is to optimize an analytical pulse to fit the specified problem. The optimization problem then turns to optimizing the parameters of the anlaytical pulse. Note that these optimization parameters act on the system for all time steps, as opposed to the discrete case. Since the pulse is continuous in time, its value does not need to be interpolated numerically. Therefore, there is no need to differentiate between a system and pulse time step for this case. GRAPE 2.0 will implement both a discrete and a continuous strategy seperately.

\section{Open System}
If our system can be modeled as an open markovian system, we may account for dissipative processes by evolving the probability density matrix $\rho$ under the \href{https://en.wikipedia.org/wiki/Lindbladian}{Lindbladian}
\[
\dot{\rho} = -i[H, \rho] + \Gamma(p) = \mathcal{L}(p)\textrm{.}
\]
Note that if $\Gamma(p) = 0$ for all time then the Lindbladian reduces to the Schroedinger equation, the PDE we ordinarily evolve under.

Implementing this evolution is computationally analogous to implementing the evolution of a unitary $U$ under the Schroedinger equation. Thus, to implement this evolution, we can use the same methods as discussed above. We need to propagate $\rho$ through a series of transformations at time step j of $L_{j} = exp(\mathcal{L}_{j}\delta t)$. Note that methods have been developed to simulate Lindbladian evolution without matrix exponentiation \cite{cleve2016efficient}. However, these methods incur some error, do not garauntee proper treatment of floating point arithmetic out of the box, and are not garaunteed to give a speedup over matrix exponentiation for our use case. For example, the cited method requires representation of the Lindbladian as a string of kronecker products of pauli matrices. I find it hard to believe performing a decomposition of this type would be time efficient given the matrix exponentiation times reported above (Table 5).

The cost functions for this evolution method will be dependent upon the probability density matrix at some time step, rather than states or unitaries. I expect the most useful cost function to be $C \propto -|Tr(\rho^{\dagger}_{T} \rho_{N})|$ to maximize the realization of a target probability density matrix.

In this case, we evolve probability density matrices under the PDE instead of individual state vectors. Thus, for each state we wish to transform, we will need to specify a corresponding probability density matrix \cite{basilewitsch2019reservoir}. Similar to the Schroedinger equation case, the function to evolve under the Lindbladian will require a set of initial probability density matrices and corresponding final probability density matrices. The reader should see why this is more expensive than our previous task. If we want to evolve every basis state in the hilbert space, instead of requiring the evolution of $d$ vectors of length $d$, we must now evolve $d$ matrices of size $d \times d$. Note that we expect the probability denisty matrices to be sparse, so we should see reasonable speedups by employing sparse multiplication. We may also employ the technique of turning each probability density matrix to a column vector of length $d^{2}$ and the Lindbladian superoperators to matrices of size $d^{2} \times d^{2}$. I will run tests to see which of these options is most memory and time efficient. If the matrices are stored in row-major order, then the memory layout of the probability density matrix should be the same in matrix and column vector format, so I wouldn't expect better cache performance. Further, increasing the size of the Lindbladian superoperators would seem to give worse cache performance because redundant values need to be referenced from different locations in memory.

\section{Further Performance Considerations}
Autograd implements gradients for numpy operations. Numpy operations are currently limited to running on CPUs, although it takes advantage of access to multiple CPUs for parallelism. Furthermore, Scipy's sparse matrix operations are not currently supported by autograd. To overcome this obstruction, we could implement derivates for these functions by hand or extend autograd.

GRAPE 2.0 will use \href{https://scikit-cuda.readthedocs.io/en/latest/}{scikit-cuda} on top of \href{https://documen.tician.de/pycuda/}{PyCUDA} to perform GPU operations. GRAPE 2.0 will extend autograd to provide derivatives of scikit-cuda functions. Sparse matrix operations are implemented by \href{https://pyculib.readthedocs.io/en/latest/cusparse.html}{cuSPARSE}.

\section{Gradient Based Optimization}
The question is: Which gradient-based optimizer should we use? GRAPE 1.0 made use of Adam and L-BFGS-B. GRAPE 2.0 will allow the user to create their own optimizer classes to provide updates to learning parameters. GRAPE 2.0 will implement Adam, Adadelta, and L-BFGS-B natively. Adam and Adadelta will be implemented following their \href{https://github.com/keras-team/keras/blob/master/keras/optimizers.py}{keras implementations}. L-BFGS-B will use the \href{https://docs.scipy.org/doc/scipy/reference/optimize.minimize-lbfgsb.html}{scipy implementation}. Adam and L-BFGS-B were chosen because they yielded good results in GRAPE 1.0. Adadelta was chosen because it requires less memory than Adam. Adam needs to store information about all of the parameters it is optimizing. This memory usage scales poorly for $10,000 <$ learning parameters. If time allows, both Dave and I think it would be interesting to see if providing hessians to L-BFGS-B would be useful. I also think it would be interesting to try Newton's method if we have access to hessians. Second-order methods should be more expensive, but I think if they yield better performance they would be worth the value. We care about achieving a specific tolerance for our cost functions, e.g. time, fidelity, etc. The main constraint in constructing higher order derivatives is that we need to be able to take higher order derivatives of the matrix exponential, which likely means implementing a custom solution. I may be thinking about this the wrong way and there is an easier approach.

\section{Software Design}
GRAPE 2.0 will be python3 official and linted. It will adhere to \href{https://www.python.org/dev/peps/pep-0008/}{PEP8}. It will have unit tests on its modules.

\section{Miscellaneous Features}
\begin{enumerate}
\item Examples to include: Gate Smash, HPO.
\item Include a library of hamiltonians.
\end{enumerate}

\bibliography{report/refs}
\bibliographystyle{plainnat}

\end{document}

max_stars_repo_name: WFKala/qoc

max_issues_repo_name: WFKala/qoc

max_forks_repo_name: WFKala/qoc


text:
\section{The widget Banner}

A "Banner" is a simple widget displaying a text linked to a variable.  Since all the widgets are linked to a variable, the variable modification will update the widget.

\subsection{Construction}

The primitive {\tt Banner} is used to build a new Banner widget. Its syntax is :\\

{\tt Banner} {\it word word (list (words))}\\

The first input word is the variable name given to the widget. If the variable doesn't already exist, it will be created. The second word is the justification for the text within the widget. It must be the word : {\tt "center "left} or {\tt "right}. The third input, if specified, is a list which indicates the size of the widget in characters. This list has two elements : width and height. An empty list will be the same as no list and the size of the widget will adapt to fit the size of the displayed text. All the inputs left are the flags which may be specified. The primitive outputs the widget object.

\subsection{Methods}

The Banner widget has a few methods uncommon to all the widgets :\\

{\bf justify\index{Banner@\textbf{Banner}!Methods!justify}}
\begin{verbatimtab}
$banner~justify word (word)
\end{verbatimtab}
Set or get (according to the value of the first input : {\tt "set} or {\tt "get}) the text justification in the widget. When setting a value, the second input must be one of the valid words : {\tt "left "center} or {\tt "right}.\\

{\bf text\index{Banner@\textbf{Banner}!Methods!Text}}
\begin{verbatimtab}
$banner~text word (string | word)
\end{verbatimtab}
Set or get (according to the value of the first input : {\tt "set} or {\tt "get}) the text displayed by the widget. The second input could be a string or a word. The linked variable to the widget will have its value changed if we set a new text to be displayed.

\subsection{Configuration}

Only one configuration is added to the Banner widget :
\begin{table}[ht]
\centering
\begin{tabular}{|c|p{5cm}|p{5cm}|}
\hline
\bf Configuration & \bf Purpose & \bf Value \\
\hline
\tt "variable\index{Banner@\textbf{Banner}!Configuration!variable} & Set or get the linked variable of the widget & the name of the variable (a word)\\
\hline
\end{tabular}
\caption{Banner's configuration}
\end{table}
\subsection{Hooks}

The Banner widget has no more hooks than the common widget.

\subsection{Example}

\example{ex22}
\begin{listing}{1}
make "win Window "titled 'Banner' [100 100]
make "msg 'Click on the button!'
make "widget Banner "msg "center
make "button Button 'The Button'
$button~config "expand.x "set true
Hook :button "invoked {
	make "msg 'You done it!'
}
Glue :win "top [] :widget :button
$win~show
\end{listing}

In this example, the linked variable is updated when the button is invoked. Lines 6 to 8 set the hook for the button.  Line 7 just sets a new value to the variable. The widget is updated at this moment:

\begin{figure}[ht!]
\centering
\psfig{figure=images/eps/ex3-1.eps}
\psfig{figure=images/eps/ex3-2.eps}
\label{s22}
\caption{Banner updated}
\end{figure}


text:
\documentclass[10pt]{report}

\usepackage{subcaption} % for subfigures
\usepackage{amsthm} % for QED
%\usepackage{algpseudocode} % for pseudo-code
\usepackage{mathtools} % for delimiter

\usepackage{listings} % for code
\lstset
{
	language=Matlab,
	frame=single,
	basicstyle=\footnotesize,
	captionpos=b,
	numbers=left,
	stepnumber=1,
	showstringspaces=false,
	tabsize=4,
	breaklines=true,
	breakatwhitespace=false,
}

\usepackage{siunitx} % for scientific notation
% for `e' in scientific notation
\sisetup{output-exponent-marker=\ensuremath{\mathrm{e}}}

\usepackage{float} % for figure [H]
\usepackage{booktabs} % for tabular
\usepackage{caption} % for \caption*
\usepackage[export]{adjustbox} % for valign=t
\usepackage{array} % for column type m
\usepackage{verbatim}
\usepackage{graphicx}
\graphicspath{ {imgs/} }
\usepackage{fancyhdr}
\usepackage{amssymb}
\usepackage{amsmath}

%%%%%% Pagination
\setlength{\topmargin}{-.3 in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.in}
\setlength{\textwidth}{6.5in}

%Title page
\newcommand{\hwTitle}{Homework \#4}
\newcommand{\hwCourse}{Numerical Differential Equations/Computational Mathematics II}
\newcommand{\hmwkClassInstructor}{Professor Shuwang Li}

\title{
	\vspace{2in}
	\textmd{\textbf{\hwCourse\\\hwTitle}}\\
	\vspace{0.3in}\large{\textit{\hmwkClassInstructor}}
	\vspace{3in}
}

%\title{Homework 1}
\author{\textbf{Zhihao Ai}}
\date{}

%Header setting.
\pagestyle{fancy}
\fancyhead[L]{Zhihao Ai}
\fancyhead[C]{Math 478}
\fancyhead[R]{Homework 4}
%%%%%%

%Global setting.
%\everymath{\displaystyle}
\setlength\parindent{0pt}

%Custom general commands.
\newcommand{\ds}{\displaystyle}
\newcommand{\ts}{\textstyle}
\newcommand{\f}[1] {f\left(#1\right)}
\newcommand{\eva}[2] {\left. #1 \right|_{#2}}
\newcommand{\dintt}[4] {\int_{#1}^{#2} #3 d#4}

\newcolumntype{N}{ >$ c <$}
\newcolumntype{M}[1]{>{\centering\arraybackslash $}m{#1}<{$}}

\newcommand{\abs}[1] {\left| #1 \right|}

\DeclarePairedDelimiter\autoparen{(}{)}
\newcommand{\pa}[1]{\autoparen*{#1}}
\DeclarePairedDelimiter\autodvert{\Vert}{\Vert}
\newcommand{\norm}[1]{\autodvert*{#1}}

\begin{document}

\maketitle

\section*{Question 1}
% Fundamental concepts on multistep methods.
\begin{enumerate}
	\item
	(Problem 2.1) Derive explicitly the three-step and four-step Adams-Moulton methods and the three-step Adams-Bashforth method.

	Three-step Adams-Moulton:
	\begin{align*}
		b_3 &= \dintt{t_{n+2}}{t_{n+3}}{
			\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+2}) }{ (3h)(2h)(h) }}{t}
		= \frac{3}{8}h\\
		b_2 &= \dintt{t_{n+2}}{t_{n+3}}{
			\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+3}) }{ (2h)(h)(-h) }}{t}
		= \frac{19}{24}h\\
		b_1 &= \dintt{t_{n+2}}{t_{n+3}}{
			\frac{ (t-t_{n})(t-t_{n+2})(t-t_{n+3}) }{ (h)(-h)(-2h) }}{t}
		= -\frac{5}{24}h\\
		b_0 &= \dintt{t_{n+2}}{t_{n+3}}{
			\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+2}) }{ (3h)(2h)(h) }}{t}
		= \frac{1}{24}h
	\end{align*}
	Therefore, the three-step Adams-Moulton method is
	\[
	y_{n+3} = y_{n+2} + h \pa{\frac{3}{8} f(t_{n+3},y_{n+3}) + \frac{19}{24} f(t_{n+2},y_{n+2}) - \frac{5}{24} f(t_{n+1},y_{n+1}) + \frac{1}{24} f(t_n,y_n)}
	\]
	Four-step Adams-Moulton:
	\begin{align*}
	b_4 &= \dintt{t_{n+3}}{t_{n+4}}{
		\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+2})(t-t_{n+3}) }{ (4h)(3h)(2h)(h) }}{t}
	= \frac{251}{720}h\\
	b_3 &= \dintt{t_{n+3}}{t_{n+4}}{
		\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+2})(t-t_{n+4}) }{ (3h)(2h)(h)(-h) }}{t}
	= \frac{323}{360}h\\
	b_2 &= \dintt{t_{n+3}}{t_{n+4}}{
		\frac{ (t-t_{n})(t-t_{n+1})(t-t_{n+3})(t-t_{n+4}) }{ (2h)(h)(-h)(-2h) }}{t}
	= -\frac{11}{30}h\\
	b_1 &= \dintt{t_{n+3}}{t_{n+4}}{
		\frac{ (t-t_{n})(t-t_{n+2})(t-t_{n+3})(t-t_{n+4}) }{ (h)(-h)(-2h)(-3h) }}{t}
	= \frac{53}{360}h\\
	b_2 &= \dintt{t_{n+3}}{t_{n+4}}{
		\frac{ (t-t_{n+1})(t-t_{n+2})(t-t_{n+3})(t-t_{n+4}) }{ (-h)(-2h)(-3h)(-4h) }}{t}
	= -\frac{19}{720}h
	\end{align*}
	Therefore, the four-step Adams-Moulton method is
	\begin{multline*}
	y_{n+4} = y_{n+3} + h \left( \frac{251}{720} f(t_{n+4},y_{n+4}) + \frac{323}{360} f(t_{n+3},y_{n+3}) - \frac{11}{30} f(t_{n+2},y_{n+2}) \right.\\
	\left. + \frac{53}{360} f(t_{n+1},y_{n+1}) - \frac{19}{720} f(t_n,y_n) \right)
	\end{multline*}
	Three-step Adams-Bashforth:
	\begin{align*}
	b_2 &= \dintt{t_{n+2}}{t_{n+3}}{
		\frac{ (t-t_{n})(t-t_{n+1}) }{ (2h)(h) }}{t}
	= \frac{23}{12}h\\
	b_1 &= \dintt{t_{n+2}}{t_{n+3}}{
		\frac{ (t-t_{n})(t-t_{n+2}) }{ (h)(-h) }}{t}
	= -\frac{4}{3}h\\
	b_0 &= \dintt{t_{n+2}}{t_{n+3}}{
		\frac{ (t-t_{n})(t-t_{n+1}) }{ (2h)(h) }}{t}
	= \frac{5}{12}h
	\end{align*}
	Therefore, the three-step Adams-Bashforth method is
	\[
	y_{n+3} = y_{n+2} + h \pa{\frac{23}{12} f(t_{n+2},y_{n+2}) - \frac{4}{3} f(t_{n+1},y_{n+1}) + \frac{5}{12} f(t_n,y_n)}
	\]

	\item
	(Problem 2.4) Determine the order of the three-step method
	\[
	y_{n+3} - y_n = h\left[\frac{3}{8}f(t_{n+3}, y_{n+3})+ \frac{9}{8}f(t_{n+2}, y_{n+2}) + \frac{9}{8}f(t_{n+1}, y_{n+1}) + \frac{3}{8}f(t_{n}, y_{n})\right]
	\]
	the \textit{three-eighths} scheme. Is it convergent?

	The method can be characterized in terms of the polynomials
	\[
	\rho(w) = w^3 - 1, \sigma(w) = \frac{3}{8}w^3 + \frac{9}{8}w^2 + \frac{9}{8}w + \frac{3}{8} = \frac{3}{8}(w+1)^3
	\]
	Let $w = \xi + 1$,
	\begin{align*}
	\rho(w) - \sigma(w) \ln{w}
	&=(\xi + 1)^3 - 1 - \frac{3}{8}(\xi+2)^3 \ln(\xi + 1) \\
	&=(\xi + 1)^3 - 1 - \frac{3}{8}(\xi+2)^3 (\xi - \frac{\xi^2}{2} + \frac{\xi^3}{3} - \frac{\xi^4}{4} + O(h^5))\\
	&=\frac{9}{16}\xi^5 + \frac{7}{16}\xi^6 + \frac{3}{32}\xi^7 + O(\xi^5)\\
	&=\frac{9}{16}(w-1)^5 + \frac{7}{16}(w-1)^6 + \frac{3}{32}(w-1)^7 + O((w-1)^5)
	\end{align*}
	Thus, the order of the \textit{three-eighths} scheme is 4. Since the roots of $\rho(w) = w^3 - 1$ all reside in the closed complex unit disc and are all simple roots, it satisfies the root condition. Therefore, it's convergent.

	\item
	(Problem 2.8) Find the explicit form of the BDF for $s = 4$.
	\begin{align*}
	\beta &= \pa{\sum_{m=1}^{4} \frac{1}{m}}^{-1} = \frac{12}{25}\\
	\rho(w) &= \beta \sum_{m=1}^{4} \frac{1}{m} w^{4-m}(w-1)^m = w^4 - \frac{48}{25}w^3 + \frac{36}{25}w^2 - \frac{16}{25}w + \frac{3}{25}
	\end{align*}
	Therefore, the BDF for $s = 4$ is
	\[
	y_{n+4} - \frac{48}{25}y_{n+3} + \frac{36}{25}y_{n+2} - \frac{16}{25}y_{n+1} + \frac{3}{25}y_{n} = \frac{12}{25}hf(t_{n+4}, y_{n+4})
	\]
\end{enumerate}

\end{document}


text:
\section{Technical Preliminaries}
\label{sec:summary}
%This section explains at a high level our proof techniques and the road-map of the proofs.
In this section, we present some useful preliminary results and ideas for  proving the impossibility results, by showing existence of certain contradictory executions.
In each proof, we use a simple system consisting of two servers, $s_x$ and $s_y$, denote the stored values as $x$ and $y$, respectively, and either two or three clients.
One of the clients is a writer $w$, which initiates only \wots{}.
One or two of the clients are readers, $r_1$ and $r_2$, which initiate only \rots{}.

%{ \color{blue}
{\bf Client-to-client (C2C) communication.}
We consider two types of settings pertinent to communication among the clients: $(i)$ allow C2C communication, where a client can send a message to any other client, and $(ii)$ disallow C2C communications, where a client cannot send any message directly to another client in the system.
%}

%\wl{Note, i tried to unify definition above so it can be used in 5 and 6.1 and need not be repeated.}

Servers $s_x$ and $s_y$ store values for objects $o_x$ and $o_y$, respectively.
%the values  in $o_1$ and $o_2$ belong to the domains $V_1$ and $V_2$, respectively;
the initial values of $o_x$ and $o_y$ are $x_0$ and $y_0$, respectively. Because there is one  object on each server  the server and object identifiers are often used interchangeably to remove redundancy. For instance, we simply say that $s_x$ returns $x_0$ to the client that initiated the transaction, which means that $s_x$ returns the value $x_0$ of object $o_x$ at the end of the READ transaction.
%We denote the automata for servers $s_x$ and $s_y$ by $s_x$ and $s_y$, respectively, and the automata for the clients  $r_1$, $r_2$ and $w$ by $r_1$, $r_2$  and $w$, respectively.
% We denote by $S_1$  the subsystem consisting of $s_x$, $s_y$, $r_1$ and $w$,  and  by $S_1$  the  automata composed of  $s_x$, $s_y$, $r_1$ and $w$, i.e., $s_x \times s_y \times w$.
% Also, we  denote by $\mathcal{A}$,  the automaton representing the entire system consisting of $S_1$ and $r_2$ (i.e., $s_x \times  s_y$  $\times$ $r_1$ $ \times w$ $ \times r_2$).
 %We assume that between any pair of processes $p_1$ and $p_2$,   such that $p_1 \neq p_2$,   there are channel automata $Channel_{p_1, p_2}$ and $Channel_{p_2, p_1}$.
%Again, with abuse of notation we denote by $\mathcal{S}$ the automata composed of the automatons $s_x$, $s_y$ and $w$. Also, by $\mathcal{T}$ we denote the composition of automaton $\mathcal{S}$ and $r$, i.e., represents the entire system.
%We used the notation $\writeop{o}{v}$ to mean a write operation with value $v$ on object $o$; and similarly, by $\readop{o}$ we mean a read operation on $o$.
%We  denote by $S_2$ the system, and also the  composed automaton,  consisting of  $s_x$, $s_y$, $r$ and  $w$, by composing the automatons $S_1$ and $r$, i.e., the automaton $S_1 \times r$.
%
%Here, we consider only fair  executions of ${\mathcal A}$.
%For the purpose of proving by contradiction, we  also assume that  any fair execution of $\mathcal{A}$  respects  the SNOW properties.
 %Also, we assume that in any execution  of $\mathcal{A}$  we can identify each transaction with a unique identifier.
 %Also, we  denote by $\mathcal{A}$, which can also be interpreted as the algorithm, the automaton representing the entire system consisting of $S_1$ and $r$ (i.e., $s_x \times  s_y$ $ \times w$ $ \times r$).

%``All finite executions are fair and in every infinite fair execution all processes takes steps infinitely often.''
%\hl{I commented out the informal def of fair executions here. It's currently not helpful. We either need a formal def of it or omit it for not making it come back to us. No previous reviews questioned it either. I propose not defining it and even take out fair executions from later proofs.}
\remove{
\sloppy Consider an execution of ${\mathcal A}$ with  three transactions: a \wot{} $W \equiv $ $WRITE($$ (o_1, x_1),  (o_2, y_1) )$ initiated by  $w$, where $x_1 \neq x_0$ and $y_1 \neq y_0$; and  \rots{} $R_1 \equiv READ$$(o_1, o_2)$  and   $R_2 \equiv READ$$(o_1, o_2)$
 initiated by $r_1$ and $r_2$, respectively.  Let us denote by
$op_1^r$ and $op_2^r$  the read operations of types $\readop{o_1}$ and  $ \readop{o_2} $, respectively. Any distributed algorithm $\mathcal{A}$ in this setting can be represented by the composition of the individual process and channel automatons.
}
\remove{
Now we describe the set of actions corresponding to the  \rots{} in a fair execution $\epsilon$ of $\mathcal{A}$.
%Consider an arbitrary execution $e$ of $\mathcal{A}$ where $R$ is a \rot{} and $W$ is a \wot{}.
 %During the execution of $R$,  in $\epsilon$, each of  the read operations $op_1^r$ and $op_2^r$ in  $R$  is associated  with a sequence of external actions.
   Clearly,  in $\epsilon$, the actions $\inv{op_i^r}$ and $\resp{op_i^r}$ appear between the actions $\INV{R}$ and $\RESP{R}$. The  action  $\inv{op_i^r}$ is followed by action $send(m_i^r)_{r, s_i}$, which is
 for  sending  the read object value request to server $s_i$. This request $m_i^r$ is communicated to $s_i$, via the channel automaton $Channel_{r, s_i}$.  Automaton
 $s_i$ eventually receives the request
  via the action
   $recv(m_i^r)_{r, s_i}$,  and subsequently, responds back to $r$, with object value $v_i$,  through the action $send(v_i)_{s_i, r}$.  Next,
   value $v_i$, $v_i \in V_i$,  communicated by the automaton  $Channel_{s_i, r}$,  is
received at $r$ via the action  $recv(v_i)_{s_i, r}$, and finally,  $op_i^r$ completes with  response action $\resp{op_i^r}$ and returns $v_i$ to $r$.
}

Our proofs often use a special type of execution fragment, named non-blocking fragments, that represent the \rot{} algorithm is non-blocking and returns one version of each object. The one-round property is captured by allowing only one non-blocking fragment on each server for a \rot{}. Our proof strategy plays non-blocking fragments against the requirements of strict serializability and write isolation under the freedom of network asynchrony. We explain non-blocking fragments and helper notations in the context of execution $\alpha$, of the system described as above, as follows:

%Due to the wait-free requirement for  the \wots{}, $W$ completes, and we denote by $\INV{W}$ the invocation action and $\RESP{W}$ the response action in $\alpha$.
%We assume an omniscient  adversary that can control the  patterns of  sequences of invocations of transactions,  the times of these invocations,  and delays in local computation and message deliveries.

% We assume that the  patterns of  sequences of invocations of transaction,  the times of these invocations,  and delays in local computation and message deliveries,  are controlled by an omniscient entity.
% which we refer to as the \emph{adversary}. The assumption of such an adversary is in accordance with  the asynchronous nature of the model.
%This is also important in practical systems, because such executions are possible to occur and thus important for making  the system safe.
%In the rest of the section,  in order to reduce notational clutter, for any   execution of $\mathcal{A}$,
%$\finiteprefix{k-1}{k}\cdots$, where $\sigma$'s and $a$'s are states and actions,
%we use the notation  $\finiteprefixt{k-1}{k}\cdots$ that shows only the actions while leaving out the states.
%

%\paragraph{\textbf{Notations and Definitions.}}
%We  introduce  the following notations and definitions in the context of a fair execution $\alpha$, of $\mathcal{A}$, with transactions $R$ and $W$ in it,
%
%\begin{notation}
%We introduce the following notations for   actions relevant to $R$ in $\epsilon$,
% where  $ j \in \{1, 2\}$:

%\wl{The first 4 bullet points are redundant with things in Section 2 I think.}

\begin{enumerate}[leftmargin=*]
%\item $\INV{R}$ and  $\RESP{R}$:  invocation and  response actions for  $R$,  at  $r$;
%\item $\INV{W}$ and   $\RESP{W}$: invocation and  response actions for  $W$, at $w$;
%\item $\send{m_j^{r}}{r, s_j}$: an  output action at $r$,  which sends a message $m_j^{r}$ from reader $r$ to server $s_j$, requesting the value for $o_j$;
%\item $\recv{m_j^{r}}{r, s_j}$: an input action at $s_j$, that receives the message $m_j^{r}$, sent from $r$;
%\item $\send{v_j}{ s_j, r}$: an output action at $s_j$,  that  sends value $v_j$, for   $o_j$, to $r$.
%\item $\recv{v_j}{ s_j, r}$: an input action at $r$,  to receive a message $v_j$ from $s_j$ at  $r$.
%
%\end{notation}
%
%\begin{definition}
\item \emph{Non-blocking fragments.}
 For a \rot{} $R_i$ by reader $r_i$, $i\in \{1, 2\}$, suppose there is a execution fragment that starts with $recv(m_j^r)_{r_i, s_j}$ and ends with
 $send(v_j)_{s_j, r_i}$, both of which  occur  at $s_j$. Moreover, suppose there is
 no other input action at $s_j$ in this fragment. Then we call this execution fragment
   a \emph{non-blocking fragment} for $R_i$ at  $s_j$ and denote by $\frage{F_{i,j}}{\alpha}{v_j}$, $j \in \{x, y\}$(Fig.~\ref{fig:exe3_fragments}).
%
   When the context is clear, we omit the first subscript of $F$. For instance, for a \rot{} $R$, $\frage{F_{x}}{\alpha}{x_0}$ denotes the non-blocking fragment of $R$ on $s_x$.
%We use the notation  $\frage{F_i}{\alpha}{v_j}$ to denote this fragment of   execution of $\alpha$ (Fig.~\ref{fig:exe3_fragments}). In the context of a \rot{} $R_i$, for $i\in \{1, 2\}$, we use the notation $\frage{F_{i,j}}{\alpha}{v_j}$ to denote $\frage{F_j}{\alpha}{v_j}$.

%
%\end{notation}
%
%\begin{definition}
\item Suppose \rot{} $R_i$ completes in $\alpha$. Consider the execution fragment in $\alpha$  between the event
$\INV{R_i}$  and  whichever of the events  $\send{m_y^{r_i}}{r_i, s_y}$ and  $\send{m_x^{r_i}}{r_i, s_x}$ that occurs later. If all the
actions in this fragment occur at  $r_i$, then we denote this fragment as $\frage{I_i}{\alpha}{}$ (Fig.~\ref{fig:exe3_fragments}).
%In case of a \rot{} $R_i$, for $i\in \{1, 2\}$, we use the notation $\frage{I_i}{\alpha}{}$ for $\frage{I}{\alpha}{}$.

% Similarly, corresponding to  $R_2$ the fragment of $\epsilon$
%between $\INV{R_2}$ and   $\send{m_2^{r_2}}{ r_2, s_y}$,   with $\send{m_1^{r_1}}{ r_1, s_x}$  in between, contains only actions at $r_2$ then we denote this
%fragment as $\frage{I_2}{\epsilon}{}$ (Fig.~\ref{fig:exe3_fragments}).

   %Similarly, if such an execution fragment occurs  with $m_2^r$, $y$ and $s_y$ then we denote this by  $\frag{2}{\epsilon}$ and refer to it as a non-blocking response fragment for $op_2^r$ at  $s_y$.
 %\end{definition}
\item Suppose \rot{} $R_i$  completes in $\alpha$. Consider the execution fragments in $\alpha$ that
occurs between the later of the events   $\recv{x}{ s_x, r_i}$ or  $\recv{y}{s_y, r_i}$, i.e., at the point in $\alpha$ when $r_i$ receives responses from both servers,  and the event $\RESP{R_i}$. If all the
actions in this fragment occur at $r_i$, then we denote this fragment by $\frage{E_i}{\alpha}{x, y}$, where $R_i$ returns the values $(x, y)$  (Fig.~\ref{fig:exe3_fragments}) to the external client.  %   In case of a \rot{} $R_i$, for $i\in \{1, 2\}$, we use the notation $\frage{E_i}{\alpha}{x, y}$ for $\frage{E}{\alpha}{x, y}$.
%Similarly, corresponding to  $R_2$ if  all the actions in  the execution fragment,  in $\epsilon$,
% between the later of the events   $\send{x}{ s_x, r_2}$ or  $\send{y}{s_y, r_2}$,  and $\RESP{R_2}$ are at $r_2$ then we denote this
%fragment as $\frage{E_2}{\epsilon}{x, y}$  (Fig.~\ref{fig:exe3_fragments}).

%\begin{notation}
\item We use $R(\alpha)$ and $W(\alpha)$ to denote the READ and WRITE transactions in the context of $\alpha$. When the the context is clear, we simply use $R$ and $W$.
%\item For any $v^i_j\in V_j$,  the superscript $i$ corresponds to the version identifier, which uniquely identifies a version from a totally ordered  set.
\item We use the subscript of a returned value to denote the version identifier, which uniquely identifies a version from a totally ordered set. For instance, $x_0$ is the $0^{\textit{th}}$ version of $x$ (the initial value of object $o_x$) on server $s_x$.
%\end{notation}

%\begin{notation}
 %\item
%$\frage{F}{\alpha}{x_1}$ $\frage{F}{\alpha}{}$  $\frage{F}{}{y_1}$  $\frage{G}{\epsilon}{y_1}$ $\frage{G_2}{}{+}$
%If the non-blocking fragment $\frag{1}{\epsilon}$ appears in $\epsilon$ such that $recv(m^r_2)_{r, s_y}$, at $s_y$,  does not occur before
% $\frag{1}{\epsilon}$ completes and $\epsilon$ is of the form $\finiteprefix{\ell-1}{\ell} \circ \frag{1}{\epsilon} \circ a_m , \sigma_{m}\ldots$  for some positive integers $\ell$ and $m$, then we denote $\finiteprefix{\ell-1}{\ell} $ by $\prefix{\epsilon}$.
%\end{notation}
\end{enumerate}

\remove{
%\vspace{-1.5em}
 \begin{figure}[t]
      \centering
         %\includegraphics[scale=0.5]{figures/executions_3_2.pdf}
         \includegraphics[width=4in]{figures/executions_3_2.png}
         \caption{
\small{The relevant actions in the execution fragments $I_i(\alpha)$, $F_{i,x}(\alpha)^{x}$,    $F_{i,y}(\alpha)^{y}$ and   $E_{i}(\alpha)^{(x,y)}$ for any \rot{} $R_i$, $i \in \{1, 2\}$
of a fair execution $\alpha$ of $\mathcal{A}$.}}
         \label{fig:exe3_fragments}
 \end{figure}
}

In our proofs, we frequently use arguments that rely on the existence of   non-blocking fragments and the constraints of strict serializability and write isolation. We derive the following use lemmas. In these lemmas, all \rots{} are assumed to have all SNOW properties, and we will derive contradictions in our main proofs. Due to space constraints, we explain these lemmas at a high level. %The proofs of these lemmas can be found in Appendix~\ref{app:lem_exec3_consistent}.

%We construct executions using \rots{} and \wots{} that always contact both servers $s_x$ and $s_y$.
%Because there is only one writer this makes objects $o_1$ and $o_2$ progress through versions together.
%This progression and strict serializability ensure that any \rot{} $R$ always returns the same version from both servers, e.g., $x_1$ and $y_1$.

%\wl{I'm not sure the purpose of the below paragraph now. Can we cut it out and just say the proof of the lemma is in the appendix? (I've cut it, but please confirm that's okay)}

%% Any  \rot{} $R$ initiated at a reader $r$, via the
%% invocation action  $\INV{R}$ at $r$, after which the  actions $send(m_1^{r})_{r, s_x}$ and $send(m_2^{r})_{r, s_y}$, at $r$, send message $m_1^r$  to $s_x$ and $m_2^r$ to $s_y$, respectively. Once
%% $s_x$   receives $recv(m_1^{r})_{r, s_x}$  then  $s_x$ responds to $r$,  in a
%% non-blocking manner,  with value $x$ via  action $send(x)_{s_x, r}$. Similarly,  after $s_y$  receives $m_2^{r}$ it  responds with $y$ to
%% $r$ in a non-blocking manner via the action $send(y)_{s_y, r}$. After  $r$ receives $x$ and $y$ via actions $recv(x)_{s_x, r}$ and $recv(y)_{s_y, r}$, respectively,  $R$  completes
%%  with the response action $\RESP{R}$ and  returns $(x, y)$.
%%
%% From the above discussion we can derive a lemma, which states in any  execution of $\mathcal{A}$,  if
%% a server $s_i$  responds with a value $v_i$ during a
%% \rot{}  then the \rot{} returns
%% $v_i$ for  object $o_i$ and also, the pair of values $(x_t, y_t)$ are from some version $t$.
%% The result follows from the reliable channel model, where messages  reach at their destinations unaltered;  and by the S property  the object values, for objects $o_1$ and $o_2$,  returned by $R$  are of the same version.
%%
%% \wl{My cut of that paragraph ends here}
%%

%From the above discussion, it is easy to see that for any fair execution of $\mathcal{A}$ where $R_i$ is invoked, the adversary can always induce a fair execution of $\mathcal{A}$ where the fragments $I_i$, $\frage{F_{i,1}}{}{}$, $\frage{F_{i, 2}}{}{}$ and $E_i$ appear consecutively.
%Similarly, for any fair execution of  $\mathcal{A}$ where $R_2$ is invoked the adversary can always induce a fair execution of $\mathcal{A}$ where the fragments $I_2$, $\frage{F_{2,1}}{}{}$, $\frage{F_{2, 2}}{}{}$ and $E_2$ appear

%From this observation we can derive a lemma, which states in any execution of $\mathcal{A}$,  if
%a server $s_i$ responds with a value $v_i$ during a
%\rot{}  then the \rot{} returns
%$v_i$ for  object $o_i$ and also, the pair of values $(x_t, y_t)$ are from some version $t$.
%The result follows from the reliable channel model, where messages reach at their destinations unaltered;  and by the S property  the object values, for objects $o_1$ and $o_2$,  returned by $R$  are of the same version.
The following lemma  proves that a \rot{} has to return the same version from both servers in order to satisfy strict serializability and write isolation.

\begin{lemma}\label{lem:exec3_consistent}
Suppose $\alpha$ is any execution of $\mathcal{A}$ such that \rot{} $R$ is in $\alpha$. Suppose the  execution fragment $\frage{I}{\alpha}{} \circ \frage{F_{x}}{\alpha}{x_{t}} \circ \frage{F_{y}}{\alpha}{y_{s}} \circ \frage{E}{\alpha}{x_{t'}, y_{s'}}$ in $\alpha$, corresponds to $R$,  where   $x_t, x_{t'} \in V_1$ and  $y_s, y_{s'} \in V_2$,
%then $(i)$ $s = s'$  and $ t=t'$ and $(ii)$ $s'=t'$.
then $s=s'=t=t'$.
%Similarly, if  the execution fragment $\frage{I_1}{\epsilon}{} \circ \frage{F_{2,1}}{\epsilon}{x} \circ \frage{F_{2,2}}{\epsilon}{y} \circ \frage{E_1}{\epsilon}{x', y'}$ appears, where   $x, x' \in V_1$ and  $y, y' \in V_2$, then $x = x'$ and $y=y'$.
\end{lemma}

%\wl{the removed proofs should all have pointers to their real proofs in the appendix, e.g., ``Proof given in Appendix~\ref{app:lem_exec3_consistent}''}

\remove{
\begin{proof}
Suppose $R$ is invoked at reader $r$.  Then, via the action $send(x_t)_{s_x, r}$, in
execution fragment  $\frage{F_{1}}{\alpha}{x_{t}}$, server $s_x$ sends the value $x_t$ to $r$,   which is received at $r$ through the action
$recv(x_{t'})_{s_x, r}$ in $\frage{E}{\alpha}{x_{t'}, y_{s'}}$.
 By the assumptions of the reliable channel automata in our model,  we have $x_{t}=x_{t'}$, i.e., $t=t'$. Similar argument for
$\frage{F_{2}}{\alpha}{y_{s}}$  and $\frage{E}{\alpha}{x_{t'}, y_{s'}}$ leads us to conclude $s=s'$. Next, $R$ responds with $(x_{t'}, y_{s'})$, which implies  by the S property for executions of
 $\mathcal{A}$ that  $x_{t'}$ and $y_{s'}$ must correspond to the same version, i.e., $s'=t'$. %Therefore, we have $s = s' = t=t'$.
\end{proof}
}

%Note that the above results hold even if there are any other  execution fragments, that do not contain any actions at $r$, $s_x$ or $s_y$,   in-between the $I$, $F_i$ and $E$ execution  fragments.

\remove{
\begin{corollary}\label{lem:exec3_consistent_corollary}
Suppose $\alpha$ is any execution of $\mathcal{A}$ such that a \rot{} $R$ is in $\alpha$. Suppose the  execution fragment $\frage{I}{\alpha}{} \circ  X_1 \circ \frage{F_{1}}{\alpha}{x^{t}} \circ X_2 \circ  \frage{F_{2}}{\alpha}{y_{s}} \circ X_3 \circ \frage{E}{\alpha}{x_{t'}, y^{s'}}$ in $\alpha$,  corresponds to $R$,  where   $x_t, x_{t'} \in V_1$ and  $y^s, y^{s'} \in V_2$, $X_1, X_2, X_3$ are some execution fragments that do not contain any action at $r$, $s_x$ or $s_y$, and $s, s', t, t' $ are version identifiers  then $(i)$ $s = s'$  and $ t=t'$ and $(ii)$ $s'=t'$.
\end{corollary}

\begin{proof}
The constraint $(i)$ in the statement can be derived  from the fact that $\mathcal{A}$ satisfies the O property,  which implies that any version returned by $R$ for object value $o_1$ (or $o_2$) and this  must be the only version sent by the server $s_x$ (or $s_y$) to $r$. Constraint
$(ii)$ from the S property of $\mathcal{A}$.
\end{proof}
}

%The following lemma states that new fair executions of $\mathcal{A}$ can be created by swapping execution fragments that
%\blue{
%either $(a)$ have no input actions or
%$(b)$ one of the fragments have no external (input or output) actions,
%}
% and in which   each fragment contains
%actions that occur  only at one automaton and the automata for the two fragments are different.
The following lemma states that we can create a new execution $\alpha'$ that is indistinguishable to $\alpha$ by swapping two fragments, which happen on two distinct automata in $\alpha$ if either $(a)$ both fragments have no input actions or
$(b)$ one of the fragments have no external (input or output) actions. Our proofs leverage this lemma to create new executions by swapping such fragments and finally derive an execution that violates strict serializability.
  \begin{lemma}[Commuting fragments] \label{lem:exec3_commute}
  Let $\alpha$ be an execution of $\mathcal{A}$. Suppose $\frage{G_1}{\alpha}{}$ and $\frage{G_2}{\alpha}{}$ are any  execution fragments in $\alpha$ such that
  all actions in each fragment occur only at one automaton and  either $(a)$ none of the fragments contain input actions, or $(b)$
  at least one of the fragments have no external actions. Suppose $\frage{G_1}{\alpha}{}$
  and $\frage{G_2}{\alpha}{}$  occur at two distinct automata and the execution
  fragment $\frage{G_1}{\alpha}{}\circ \frage{G_2}{\alpha}{}$ occurs in $\alpha$.
  Then there exists an execution $\alpha'$ of $\mathcal{A}$, where  the execution fragment  $\frage{G_2}{\alpha}{}\circ \frage{G_1}{\alpha}{}$ appears in $\alpha'$, such that
  %\blue{
  $(i)$  $\frage{G_1}{\alpha}{} \sim \frage{G_1}{\alpha'}{}$ and  $\frage{G_2}{\alpha}{} \sim \frage{G_2}{\alpha'}{}$
  %}
  $(ii)$
the prefix  in $\alpha$  before  $\frage{G_1}{\alpha}{} \circ \frage{G_2}{\alpha}{}$
 is identical to the prefix  in $\alpha'$ before  $\frage{G_1}{\alpha'}{} \circ \frage{G_2}{\alpha'}{}$; and $(ii)$
the suffix in $\alpha$  after
 $\frage{G_1}{\alpha}{} \circ \frage{G_2}{\alpha}{}$
is identical to the suffix in $\alpha'$ after the execution fragment
 $\frage{G_2}{\alpha'}{} \circ \frage{G_1}{\alpha'}{}$.
 % Similar results  hold for the traces of $\alpha$ and $\beta$  in terms of the
 %trace fragments   $\fragt{G_1}{\alpha}{}$ and $ \fragt{G_2}{\alpha}{}$
  \end{lemma}
 \remove{
  \begin{proof}
  This is clear because the adversary can move the actions in $G_2$ to occur before $G_1$ at their respective automata, and  because
   either $(a)$ none of the fragments have any input action or $(b)$ at least one of them has no external actions, and hence
  the actions in one of these fragments cannot affect the actions in the other fragment.
  \end{proof}
}

%The following lemma states that if there are two fair executions of $\mathcal{A}$ with a \rot{}  $R$ in each of them, and suppose at any server the non-blocking execution fragments  of $R$  are identical (in terms of the sequence of states and actions)  then in both executions, $R$   returns the same object value.
The following lemma states that if there are two fair executions of $\mathcal{A}$ with \rot{} $R$ in each of them, and suppose at any server the non-blocking fragments of $R$ are identical (in terms of the sequence of states and actions), then $R$ returns the similar values in both executions.
\begin{lemma}[Indistinguishability]  \label{lem:exec3_equiv}
Let $\alpha$ and $\beta$ be executions of $\mathcal{A}$ and let $R$ be any \rot{}. Then
$(i)$  if $\frage{F_{x}}{\alpha}{} \stackrel{s_x}{\sim}\frage{F_{x}}{\beta}{}$ then both
$R(\alpha)$ and $R(\beta)$ respond with the same value $x$ at $s_x$; and
$(ii)$ if  $\frage{F_{y}}{\alpha}{} \stackrel{s_y}{\sim}\frage{F_{y}}{\beta}{}$ then both
$R(\alpha)$ and $R(\beta)$ respond with the same value $y$ at $s_y$.
\end{lemma}

\remove{
\begin{proof}
Suppose $R$ is invoked at some reader $r$. Let $j \in \{1, 2\}$ and  suppose the fragments  $\frage{F_{j}}{\alpha}{}$ and  $\frage{F_{j}}{\beta}{}$
appears in $\alpha$ and $\beta$ respectively, where in $\frage{F_{j}}{\alpha}{}$ server $s_j$
sends  $v_j \in V_j$ to $r$. Then $R(\alpha)$ must return $v_j$ for object $o_j$ by the O property  of $\mathcal{A}$. Then since $\frage{F_{j}}{\alpha}{} \stackrel{s_j}{\sim} \frage{F_{j}}{\beta}{}$ then
in  $\frage{F_{j}}{\beta}{}$  the server $s_j$
must also  send $v_j$ to $r$,  therefore,  both $R(\alpha)$ and $R(\beta)$ must return value $v_j$ for $o_j$.
%Then by the $S$ property  $R(\beta)$ must return $(x_t, y_t)$, which proves the result of the lemma.
%
\end{proof}
}

%Below we show that in any finite execution of $\mathcal{A}$ where the final action is an invocation of  \rot{} $R$ at a reader $r$, the adversary can always induce a fair execution of $\mathcal{A}$ where the fragments $I$, $\frage{F_{1}}{}{}$, $\frage{F_{2}}{}{}$ and $E$ appear consecutively in that order.
 The following lemma shows that for any finite execution of $\mathcal{A}$ that ends with the invocation of  \rot{} $R_1$, it is always possible to have an execution of $\mathcal{A}$ where the fragments $I$, $\frage{F_{x}}{}{}$, $\frage{F_{y}}{}{}$ and $E$ appear consecutively due to the asynchronous network.
\begin{lemma}\label{lem:read_format}
%If a \rot{} $R_i$ is invoked in $\mathcal{A}$ then there exists a fair execution $\epsilon$ of $\mathcal{A}$ such that
%the fragments $\frage{I_i}{\epsilon}{}$, $ \frage{F_{i, 1}}{\epsilon}{x}$, $\frage{F_{i, 2}}{\epsilon}{y}$ and
 %$\frage{E_i}{\epsilon}{x, y}$ appear in $\epsilon$.
If any finite execution of  $\mathcal{A}$ ends with $\INV{R}$, for a \rot{} $R_1$ then there exists an extension $\alpha$ which is a fair execution of $\mathcal{A}$ and  is  of the form
   $\frage{P}{\alpha}{} \circ\frage{I}{\alpha}{} \circ \frage{F_{1,x}}{\alpha}{x} \circ \frage{F_{1,y}}{\alpha}{y} \circ \frage{E}{\alpha}{x, y} \circ \frage{S}{\alpha}{}$, where $\frage{P}{\alpha}{}$ is the prefix and $\frage{S}{\alpha}{}$ denotes the rest of the execution.
 \end{lemma}

 \remove{
 \begin{proof}
 Consider a finite execution of $\mathcal{A}$  that end with  $INV(R)$, which  occurs at some reader  $r$,
then the  adversary  induces the execution fragment $\frage{I}{\alpha}{}$  by delaying all actions, except the internal and output actions at $r$, between
the actions $\INV{R}$ and the later of the actions $send(m_1^{r})_{r, s_x}$ and $send(m_2^{r})_{r, s_y}$. Next, the adversary
delivers $m_1^{r}$ at $s_x$ (via the action $recv(m_1^{r})_{r, s_x}$) and delays all actions, other than internal and output actions at $s_x$, until $s_x$ responds with $x$, via  $send(x)_{s_x, r}$;
we identify this  execution fragment
 as $\frage{F_{1}}{\alpha}{x}$. Subsequently, in a similar manner,
the  adversary  delivers the message  $m_2^{r}$ and delays appropriate actions to induce the execution fragment
$\frage{F_{2}}{\alpha}{y}$. Finally, the adversary  delivers the values $x$ and $y$ to $r$ (via the events $recv(x)_{s_x, r}$ and $recv(y)_{s_y, r}$),
and delays all actions at other automata until $R$ completes  with action $\RESP{R}$ by returning $(x, y)$.  As a result, we  arrive at a fair execution of $\mathcal{A}$ of the form
 $\frage{I}{\alpha}{} \circ \frage{F_{1}}{\alpha}{x} \circ \frage{F_{2}}{\alpha}{y} \circ \frage{E}{\alpha}{x, y} \circ \frage{S}{\alpha}{}$.
\end{proof}
}

\remove{
 \begin{figure}[t]
      \centering
         %\includegraphics[width=4.0in,  height=4in]{figures/executions_3_1-crop.pdf}
        \includegraphics[scale=0.4]{figures/executions_3_1-crop.pdf}
          %\vspace{-2.5em}
         \caption{
        \small{Executions of $\mathcal{A}$ with three clients and operations $W$, $R_1$ and $R_2$ leading to the contradiction of S in $\alpha_{10}$.
        Arrows show the transposition of execution fragments from the previous execution.
         % The external requests and responses  at the clients  to and from the end-users are represented as invocation and responses for the transaction.
         }}
         \label{fig:executions3}
 \end{figure}
}

\begin{figure}[t]
	%\centering
	\hspace*{-0.0cm}

		\centering
	     \includegraphics[width=3.0in]{figures/executions_3_2.pdf}
	     \caption{\small{
	      The relevant actions in the execution fragments $I_i(\alpha)$, $F_{i,x}(\alpha)^{x}$,    $F_{i,y}(\alpha)^{y}$ and   $E_{i}(\alpha)^{(x,y)}$ for any \rot{} $R_i$, $i \in \{1, 2\}$
			of a fair execution $\alpha$ of $\mathcal{A}$.
	     }}
	     \label{fig:exe3_fragments}
\end{figure}

\begin{figure}[t]
		\centering
		%\includegraphics[width=3.2in]{figures/executions_3_2.pdf}
		\includegraphics[width=3.0in]{figures/executions_3_1-cropa.pdf}
		\caption{\small{Executions of $\mathcal{A}$ with three clients and operations $W$, $R_1$ and $R_2$ leading to the contradiction of S in $\alpha_{10}$.
			Arrows show the transposition of execution fragments from the previous execution.
		}}
           	\label{fig:executions3}
%\label{fig:executions3}
\end{figure}