Updated presentation

[rodrigo-msc.git] / mscMonografia.tex

\documentclass[10pt]{article}

\usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}
\usepackage{todonotes}
\usepackage{times}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{url}
\usepackage{paralist}
\usepackage[hyperfootnotes=false]{hyperref}
\usepackage{amssymb}
\usepackage{setspace}

\newcommand{\mytitle}{Avaliação do impacto de mecanismos de
  armazenamento de estado no desempenho de sistemas replicados} %PT
\newcommand{\f}{$\blacksquare$}

\hypersetup{
     pdftitle={\mytitle},
     pdfauthor={Rodrigo E. Lazo Paz},
     pdfdisplaydoctitle=true,
     pdfborder=0 0 0
}

\title{\mytitle}

\author{
Rodrigo E. Lazo Paz\\%\thanks{Grants.} \\
IC, Unicamp \\
Campinas, Brasil \\
{\small \url{rodrigo.lazo@students.ic.unicamp.br}} \\
\and
Luiz E. Buzato \\ %\thanks{Identificação de projetos aqui.}\\
IC, Unicamp \\ Campinas, Brasil \\ {\small
\url{buzato@ic.unicamp.br}}
}

\hyphenation{par-ti-cu-lar-men-te}
\hyphenation{su-fi-ci-en-tes}

\begin{document}
\doublespacing

\maketitle

\begin{abstract}
  \noindent Nos sistemas distribuídos replicados, a queda e
  subsequente recuperação de pelo menos uma réplica produz uma
  degradação no desempenho do sistema devido a dois fatores: (i) a
  re-distribuição da carga de trabalho entre as réplicas
  remanescentes, e (ii) o impacto negativo que a re-introdução de um
  processo falho tem sobre o sistema como um todo, porque a
  recuperação tem um custo diretamente proporcional ao tamanho do
  estado persistente que deve ser recuperado. Esse projeto avalia
  alternativas para o armazenamento do estado persistente que não
  requerem o uso de memória estável. Por exemplo, é possível que uma
  réplica mantenha o seu estado na memória principal de um outro
  computador. É possível ainda que algumas réplicas mantenham seu
  estado em memória estável local enquanto outras utilizam somente
  memória volátil. Neste projeto, avaliaremos múltiplas configurações
  de sistemas distribuídos replicados com armazenamento híbrido,
  combinando memoria estável local e repositórios remotos localizados
  em memória volátil de outros computadores, de maneira a tentar
  minimizar o impacto da recuperação de réplicas falhas no desempenho
  do sistema replicado. Os resultados serão aplicados na melhora da
  biblioteca Tréplica para a construção de aplicações de alta
  disponibilidade, desenvolvida no Laboratório de Sistemas
  Distribuídos do Instituto de Computação da Universidade Estadual de
  Campinas.
\end{abstract}


\newpage

\section{Introdução}
\label{sec:introduction}

Algoritmos  distribuídos  são  aqueles  projetados  para  executar  em
sistemas  compostos  por   um  conjunto  interconectado  de  processos
autônomos que  trocam informação. O progresso do  algoritmo depende de
dois elementos: o  progresso individual de cada um  dos processos e da
troca    de   informação   entre    eles.   Os    modelos   distintos,
i.e.\  suposições, que  descrevem  características específicas  desses
elementos do sistema são:

\begin{itemize}
\item \textit{Modelo de intercomunicação dos processos}, admite duas
  possibilidades: a troca de mensagens (enviando mensagens
  ponto-a-ponto ou um-para-varios; mantendo o ordem de envio na
  recepção ou não), ou a leitura e escrita de variáveis comuns na
  memoria compartilhada.
\item \textit{Modelo temporal}, distingue três possibilidades:
  \begin{inparaenum} [\itshape a\upshape)]
  \item \textit{sistemas síncronos}: todos os processos executam cada
    passo do algoritmo simultaneamente e o tempo de demora é
    conhecido;
  \item \textit{sistemas assíncronos}: cada processo pode tomar uma
    quantidade indeterminada de tempo para executar cada passo do
    algoritmo;
  \item \textit{sistemas parcialmente síncronos}, algumas suposições
    sobre o tempo de demora de algumas operações são possíveis, mas
    não se garante que os processos executem simultaneamente os passos
    do algoritmo.
  \end{inparaenum}
\item \textit{Modelo de falhas}, classifica o comportamento dos
  processos na presencia de falhas em: \textit{falha-e-para}: o
  processo falha e deixa de participar do sistema;
  \textit{falha-e-recuperação}: o processo falha, mas, em algum
  momento no futuro, volta ao sistema; \textit{falha de omissão}: o
  processo não realiza algumas ações arbitrariamente, e.g.\ enviar uma
  mensagem; e \textit{falha bizantina}: o comportamento do processo é
  aleatório. Além dos processos, os canais de comunicação também podem
  apresentar falhas; por exemplo, no caso da comunicação por troca de
  mensagens, perder, duplicar ou corromper as mensagens.
\end{itemize}

É claro que, as combinações distintas dos modelos apresentados, dão
lugar a uma multiplicidade de ambientes muito ampla e, portanto, não é
possível, ou ao menos prático, desenhar algoritmos distribuídos que
sejam capazes de executar em modelo qualquer; é por isso que somente
se pode avaliar a correção dos algoritmos sob as condições
determinadas por um certo modelo computacional. Por exemplo, um
algoritmo desenhado para um sistema síncrono e sem falhas não vai
funcionar se for executado por um sistema assíncrono sujeito a falhas
arbitrárias. Assim, um modelo determina o arcabouço teórico e prático
para o desenvolvimento e aplicação de um algoritmo distribuído.

Neste projeto adotamos o modelo assíncrono onde processos falham e
depois se recuperam, isto é, se re-integram ao sistema. Nesse modelo é
necessário lidar com dois problemas importantes que têm impacto sobre
o desempenho do sistema: (i) memória estável e (ii) detecção de
falhas. Como essa proposta não desenvolverá novos mecanismos para
detecção de falhas, esse estudo e objeto de um outro Mestrado
relacionado a este, discutiremos a seguir somente o problema relacionado
à necessidade de memória estável.

Quando um processo falha, ele perde o seu estado local, isto é, aquele
armazenado em memória volátil. Uma maneira de resolver esse problema é
supor que periodicamente o processo transfere fotografias de seu
estado para memória estável. Assim, após uma falha o processo
recém-iniciado pode recompor o seu estado a partir do última
fotografia armazenada em memória estável, o último \emph{checkpoint}.
Infelizmente, operações de leitura e escrita em memória estável são
lentas e custosas e, portanto, devem ser evitadas ao máximo. Isto nos
leva diretamente às questões de pesquisa deste projeto:

\begin{itemize}
\item \emph{O uso de memória estável é sempre necessário para se
    manter a consistência e tolerância a falhas de sistemas replicados
    baseados em consenso?}
\item \emph{Se o uso de memória estável não é sempre necessário, então
    que mecanismos e meios alternativos de armazenamento podem ser
    utilizados para reduzir o custo da recuperação de um processo
    falho?}
\end{itemize}

O restante do projeto é organizado da seguinte forma. A próxima seção
contextualiza este projeto dentro da pesquisa já realizada no
Laboratório de Sistemas Distribuídos sobre replicação ativa. A
seção~\ref{sec:teoria} apresenta os fundamentos sobre modelos
computacionais no cenário de falha-e-recuperação para algoritmos
distribuídos que se comunicam através de \textit{broadcast} de ordem
total. A seção~\ref{sec:treplica} apresenta a plataforma Treplica,
empregada para os testes e a avaliação de nossa projeto. Na
seção~\ref{sec:proposta} são discutidos os argumentos que dão
sustentação ao nosso projeto, assim como os modelos que podem ser
empregados para ajudar na resposta da nossa pergunta de pesquisa.
Finalmente, a seção~\ref{sec:metodologia} apresenta concisamente a
metodologia de pesquisa, as etapas a serem cumpridas no projeto e o
seu respectivo cronograma.

\section{Contexto da Pesquisa}
\label{sec:contexto}
Esta  seção sumariza  o  contexto  dentro do  qual  este projeto  será
desenvolvido.  Nos últimos  quatro anos  o Prof.  Buzato  trabalhou em
replicação ativa com o seu aluno  de Doutorado, Gustavo M. D. Vieira e
o Prof.\  Willy Zwaenepoel, EPFL.  O trabalho com o  Prof.\ Zwaenepoel
foi  desenvolvido  durante  a   licença  sabática  do  Prof.\  Buzato,
realizada  durante 2008 no  Instituto de  Comunicação e  Computação da
EPFL, Lausanne,  Suiça. Até o momento a pesquisa em replicação resultou
nos seguintes trabalhos:

\begin{description}
\item \textsl{Treplica: Ubiquitous
    replication}~\cite{vieira08:_trepl}, publicado em 2008 , apresenta
  detalhadamente a conceição e im\-ple\-men\-ta\-ção de Treplica.

\item \textsl{Dynamic Content Web Applications: Crash, Failover, and
    Recovery Analysis}~\cite{buzato09}, mostra o efeito das falhas e
  recuperações no desempenho de um aplicação Web implementada com
  Treplica. Neste artigo, a medição do desempenho é baseada no
  \emph{benchmark} TPC-W aumentado com medidas de disponibilidade. Os
  resultados mostraram bom desempenho, excelente escalabilidade e
  disponibilidade ininterrupta. Este artigo foi publicado nos anais da
  \textsl{39th International Conference on Dependable Systems and
    Networks (DSN 2009)}, Estoril, Portugal
  (doi:10.1109/DSN.2009.5270331).

\item \textsl{The Performance of Paxos and Fast
    Paxos}~\cite{vieira09}, caracteriza e compara, em execuções com e
  sim presencia de falhas, o desempenho dos algoritmos de consenso
  Paxos e Fast Paxos. Os resultados mostraram que no ambiente LAN
  Paxos teve um melhor desempenho que Fast Paxos; isto devido às
  violações de temporização deste último e não, como se poderia
  intuir, à suposição otimista deste. Esse é o primeiro indício de que
  é possível considerar modelos parcialmente síncronos para produzir
  uma versão de Fast Paxos com desempenho melhor. Este artigo foi
  publicado nos anais do 27º Simpósio Brasileiro de Redes de
  Computadores e Sistemas Distribuídos (SBRC 2009), Recife, Brasil.

\item \textsl{On the Coordinator's Rule for Fast
    Paxos}~\cite{vieira08b}, mostra uma análise da implementação da
  regra de consistência do algoritmo Fast Paxos como implementada pelo
  processo coordenador em função do número de processos no quórum. Com
  base nesta análise, os autores propuseram uma regra simplificada de
  consistência interessante para implementação. Este artigo foi
  publicado no periódico \textsl{Information Processing Letters},
  volume 107, 2008.

\item \textsl{A Recovery Efficient Solution for the Replacement of
    Paxos Coordinators}~\cite{vieira-tr10a}, mostra uma otimização do
  procedimento de substituição de um coordenador no algoritmo
  Paxos. Devido à importancia deste, o processo de substituição pode
  deter. Mostro-se um procedimento que provoca o mínimo de
  perturbação. Uma observação interessante é que em sistemas
  sobrecarregados, ainda na ausência de falhas de processos, a
  coordenação é trocada frequentemente.
\end{description}

Os resultados de pesquisa obtidos nos trabalhos listados aqui
constituem o contexto que nos motivou à formulação da nossa questão de
pesquisa: Qual é o método de armazenamento e recuperação de estado que
minimiza o impacto da recuperação de um processo sobre o desempenho do
sistema replicado? Antes de nos aprofundarmos na questão é necessário
descrever um pouco os conceitos importantes associados à replicação.

\section{Fundamentação Teórica}
\label{sec:teoria}

O fornecimento de um serviço altamente disponível através do uso de
processos replicados é uma técnica bem
conhecida~\cite{Schneider:1990:IFS:98163.98167}.  Existem duas formas
de replicação: a ativa ou de máquina de
estados~\cite{lamport1978implementation}, onde todos as réplicas
recebem e executam as mesmas requisições, no mesmo ordem para
garantirem a consistência do estado replicado; e a passiva, onde um
único processo recebe todas as requisições, as aplica localmente, e
depois transfere um estado resultante para demais réplicas.  Na
replicação ativa, um dos métodos mais utilizados em sua implementação
é baseado em algoritmos de consenso
distribuído~\cite{Lamport:1998:PP:279227.279229,
  Schneider:1990:IFS:98163.98167,Oki:1988:VRN:62546.62549} e o
\textit{broadcast} de ordem total~\cite{vieira10:implementing-tr}.

Nesta seção discute-se a fundamentação teórica da solução de
replicação ativa, no modelo assíncrono com falha-e-recuperação,
utilizada nossa nossa proposta de pesquisa.  Na
seção~\ref{sec:notacao}, definiremos a notação utilizado ao longo do
texto além dos modelos computacionais adotados.  A
seção~\ref{sec:consenso} descreve o problema do consenso e sua solução
utilizando o algoritmo Paxos.  Na seção~\ref{sec:broadcast}, o
\textit{broadcast} de ordem total é definido, e suas caraterísticas
detalhadas.

\subsection{Modelo do sistema e notação}
\label{sec:notacao}
O modelo suposto neste trabalho é assíncrono, portanto, não existe
suposição nenhuma acerca do tempo de demora da comunicação ou do
processamento. Todos os processos no sistema estão conectados, e a
co\-mu\-ni\-ca\-ção é através da troca de mensagens, as quais se podem
perder durante a transmissão. Os processos podem falhar e voltar ao
sistema. Após falhar, os processos perdem seu estado atual, mas, têm a
possibilidade de armazenar, de maneira persistente, informação
suficiente para a recuperação de algum estado anterior.

% \begin{table}[h]
%   \small
%   \centering
%   \begin{tabular}{|l|p{5cm}|l|p{5.4cm}|}
%     \hline
%     \(\Pi\) & Conjunto de processos. &
%     \(\mathcal{M}\) & Conjunto de mensagens. \\
%     \(sender(m)\) & Processo remitente de \(m\). &
%     \(Dest(m)\) & Conjunto destinatário de \(m\).  \\
%     \(\Pi_{sender}\) & Conjunto de processos que podem enviar mensagens. &
%     \(\Pi_{dest}\) & Conjunto de processos que podem receber mensagens. \\
%     \(\mathcal{T}\) & Relógio global. &
%     \(F(t)\) & Conjunto de processos caídos no tempo \(t\). \\
%     \(Bom(F)\) & Conjunto de processos bons (em F). &
%     \(Ruim(F)\) & Conjunto de processos ruins (em F). \\
%     \textit{Instável}\((F)\) & Conjunto de processos instáveis (em F).& & \\
%     \hline
%   \end{tabular}
%   \caption{Notação}
%   \label{tab:notacao}
% \end{table}

% Neste trabalho vamos a seguir a notação utilizada por Défago, Schiper
% e Úrban~\cite{Defago:2004}, resumida na tabela~\ref{tab:notacao}. Seja
% \(\Pi = \{P_1, \ldots, P_n\}\) um conjunto de \(n\) processos que
% conformam o sistema. A comunicação é baseada no envio de mensagens,
% tal que \(\mathcal{M}\) é o conjunto de mensagens válidos. Seja \(m
% \in \mathcal{M}\) uma mensagem válida em \(\mathcal{M}\), \(sender(m)
% \in \Pi \) designa o processo originador da mensagem \(m\), e
% \(Dest(m) \subseteq \Pi \) é o conjunto não vazio de processos aos
% quais a mensagem \(m\) foi enviada. Além disso, seja \(\Pi_{sender}\)
% o conjunto de todos os processos que podem enviar mensagens válidas, e
% seja \(\Pi_{dest} \stackrel{\mathrm{def}}{=} \bigcup_{m \in
%   \mathcal{M}} Dest(m)\) o conjunto de destinos possíveis das
% mensagens válidas.

Neste trabalho vamos a seguir a notação utilizada por Défago, Schiper
e Úrban~\cite{Defago:2004}. Seja \(\Pi = \{P_1, \ldots, P_n\}\) um
conjunto de \(n\) processos que conformam o sistema. A comunicação é
baseada no envio de mensagens, tal que \(\mathcal{M}\) é o conjunto de
mensagens válidos. Seja \(m \in \mathcal{M}\) uma mensagem válida em
\(\mathcal{M}\), \(sender(m) \in \Pi \) designa o processo originador
da mensagem \(m\), e \(Dest(m) \subseteq \Pi \) é o conjunto não vazio
de processos aos quais a mensagem \(m\) foi enviada. Além disso, seja
\(\Pi_{sender}\) o conjunto de todos os processos que podem enviar
mensagens válidas, e seja \(\Pi_{dest} \stackrel{\mathrm{def}}{=}
\bigcup_{m \in \mathcal{M}} Dest(m)\) o conjunto de destinos possíveis
das mensagens válidas.

Para simplificar a apresentação  do modelo, suponha-se a existência de
um relógio discreto global  \(\mathcal{T}\) com domínio de valores nos
números naturais;  os processos não  têm conhecimento ou  contato como
ele.

A seguinte classificação dos processos em função a seu comportamento
de falhas é tomada de Aguilera, Chen e
Toueg~\cite{Aguilera:2000:FDC:1035750.1035753}. Seja o padrão de falhas \(F\)
uma função de \(\mathcal{T}\) a \(2^\Pi\), tal que \(F(t)\) representa
o conjunto dos processos que não estão presentes no sistema no tempo
\(t\). Um processo está \textit{ativo no tempo} \(t\) (em \(F\)) se
\(p \in F(t)\), e está \textit{inativo no tempo} \(t\) (em \(F\)) no
caso contrario. Um processo \textit{cai} no tempo \(t\) se está ativo
no tempo \(t-1\) e inativo no tempo \(t\)\footnote{Um processo
  \textit{cai} no tempo \(t=0\) se está inativo no tempo \(t=0\) }. Um
processo se \textit{recupera} no tempo \(t\) se está inativo no tempo
\(t-1\) e está ativo no tempo \(t\). Os processos, em função a seu
comportamento, podem se classificar como:

\begin{itemize}
\item \textit{Sempre Ativo}: O processo \(p\) nunca cai.
\item \textit{Eventualmente Ativo}: O processo caiu pelo menos uma
  vez, mas, após algum momento \(t\), o processo mantém-se ativo.
\item \textit{Eventualmente Inativo}: O processo caiu pelo menos uma
  vez, e, após algum momento \(t\), o processo não volta à atividade.
\item \textit{Instável}: O processo cai e volta um número infinito de
  vezes.
\end{itemize}

Um processo é \textit{bom} (em \(F\)) se é sempre ativo ou
eventualmente ativo. Um processo é \textit{ruim} (em \(F\)) se é
eventualmente inativo ou instável. Denota-se \(Bom(F)\), \(Ruim(F)\) e
\textit{Instável}\((F)\) aos conjuntos de processos (em \(F\)) bons,
ruins e instáveis, respetivamente.

\subsection{Consenso}
\label{sec:consenso}
O problema do consenso~\cite{Pease:1980:RAP:322186.322188} é um dos
mais fundamentais da área dos algoritmos distribuídos. Considere um
conjunto \(\Pi = \{p_1,\ldots,p_n\}\) de \(n\) processos; seja \(V =
\{v_1^0, \ldots, v_n^0\}\) o conjunto de estados inicias dos
processos, tal que \(v_i^0\) é o valor inicial do processo
\(p_i\). Eventualmente cada processo \(p_i\) tem que \textit{decidir}
um valor \(decide(p_i) = v_i\), tal que todos os processos corretos
concordem neste, e as seguintes propriedades forem
satisfeitas~\cite{Aguilera:2000:FDC:1035750.1035753}:

\begin{description}
\item[Validade uniforme] se um processo decide $v$, então algum
  processo o propôs, i.e.\ \(\forall p \in \Pi(decide(p) \in V)\).
\item[Consenso] Todos os processos \textit{bons} decidem o mesmo
  valor, i.e.\ \(\exists ! v \in V \forall p \in Bom(F) (decide(p_i) = v)\).
\item[Terminação] Se todos os processos \textit{bons} propõem um
  valor, eventualmente um daqueles é escolhido, i.e.\ \(\exists ! v
  \in V~\forall p \in Bom(F)~\exists T \in \mathcal{T}~\forall t > T
  (v^0_p \in V \Rightarrow decide(p) = v)\).
\end{description}

Existe uma variação mais estrita, o consenso
uniforme~\cite{Neiger:1990:AIF:83334.83337}, que impõe restrições às
escolhas dos processos \textit{ruins}:

\begin{description}
\item[Consenso uniforme] Os processos não \textit{decidem} valores
  distintos, i.e.\ \(\exists ! v \in V~\forall p \in \Pi (decide(p_i) = v)\).
\end{description}

No   caso    síncrono   sem   falhas,   o    problema   é   facilmente
resolvível~\cite{Lynch:1996:DA:525656},   porém,    o   resultado   de
impossibilidade obtido por Fischer, Lynch e Patterson~\cite{fischer85}
mostra que o problema não se pode resolver de maneira determinista num
sistema distribuído  assíncrono com apenas um  processo falho. Existem
distintas  soluções propostas:  o uso  de aleatorização~\cite{Chor89},
definição de problemas mais restritos e suas soluções~\cite{dolev87} e
o         uso          detetores         de         falhas         não
confiáveis~\cite{Chandra:1996:WFD:234533.234549,
  Chandra:1996:UFD:226643.226647}, etc.

\paragraph{Algoritmo de consenso Paxos}
O algoritmo de consenso Paxos, originalmente proposto por
Lamport~\cite{Lamport:1998:PP:279227.279229}, é um dos mais utilizados
na prática~\cite{Burrows:2006:CLS:1298455.1298487,
  Camargos:2007:SMH:1272998.1273036,
  MacCormick:2004:BAF:1251254.1251262,
  Saito:2004:FBD:1024393.1024400}. Neste algoritmo, os processos
assomem pelo menos um dos seguintes papéis:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{proponente}, que propõe valores;
\item \textit{receptor}, que escolhe um único valor; e
\item \textit{aprendiz}, que aprende o valor escolhido.
\end{inparaenum}

O algoritmo pode precisar uma ou varias rodadas para alcançar o
consenso, cada uma identificada por um número de rodada \(r\). No
começo de cada rodada os proponentes eligem um coordenador, quem
avalia se a maioria \(\lfloor n/2 \rfloor +1\) dos \(n\) receptores
participou da rodada anterior \(r-1\), e, portanto, o consenso foi
alcançado. No caso contrario, o algoritmo continua em duas fases com
dois passos cada uma:

\begin{itemize}
\item \textit{Fase 1a}, o coordenador invita aos receptores a
  participar da rodada \(r\), os quais aceitam somente se não
  participam de uma rodada \(r' \geq r\). A partir desse momento, os
  receptores que aceitaram o convite \textit{prometem} não participar
  em outra rodada, \(r'' < r\).
\item \textit{Fase 1b}, os receptores que aceitaram o convite enviam
  ao coordenador o valor da última proposta que votaram e o número de
  rodada na qual aquilo aconteceu, ou \textit{nulo} no caso contrario.
\item \textit{Fase 2a}, se suficientes respostas forem recebidas pelo
  coordenador, \(\lfloor n/2 \rfloor +1\), ele escolhe dentro dos
  valores retornados aquele que poderia ter sido \textit{decidido} em uma
  rodada \(r' < r\), ou no caso seja \textit{nulo}, escolhe a
  proposta feita pelos proponentes. Logo, ele pede aos receptores que
  votem na proposta escolhida.
\item \textit{Fase 2b}, após receber o pedido de votar do coordenador,
  e sempre que não houveram \textit{prometido} participar na rodada
  \(r\), os receptores votam enviando o número de rodada \(r\) e o
  valor decidido aos aprendizes.
\item O consenso é alcançado no momento que suficientes receptores,
  \(\lfloor n/2 \rfloor +1\), votam na fase 2b.
\end{itemize}

Uma caraterística interessante do Paxos é que sua tolerância a falhas
fundamenta-se no uso de \textit{quorum} de processos, e não no
conhecimento do estado atual deles, como os detetores de falhas. O
algoritmo garante que se um valor é eleito, a escolha não muda,
portanto um processo que caiu e volta, pode aprendê-lo. Para que isso
aconteça, cada participante do algoritmo tem que armazenar
persistentemente as rodadas nas quais ele participou e os valores que
votou.

\subsection{Broadcast de ordem total}
\label{sec:broadcast}
% seção muito longa?
O \textit{broadcast} de ordem total, ou atômico, é uma primitiva de
comunicação assíncrona de alto nível que garanta que as mensagens
enviadas a um conjunto de processos sejam recebidas, no mesmo ordem,
por todos os membros~\cite{Defago:2004}. O problema é definido
formalmente em função de duas primitivas, \textit{TO-broadcast}\((m)\)
e \textit{TO-deliver}\((m)\), onde \(m \in \mathcal{M}\) e uma
mensagem válida. Quando um processo \(p \in \Pi\) executa
\textit{TO-broadcast}\((m)\) (respectivamente,
\textit{TO-deliver}\((m)\)) diz-se que o processo \(p\)
\textit{TO-broadcasts} \(m\) (respectivamente, \textit{TO-delivers}
\(m\)). Todas as mensagens têm identificadores únicos, e levam consigo
a identidade de seu remetente, denotado \textit{sender}\((m)\). Além
disso, supomos que para qualquer mensagem \(m\), e em quaisquer
execução, a chamada \textit{TO-broadcasts}\((m)\) é feita uma vez
só. Neste contexto, o \textit{broadcast} de ordem total é definido
pelas seguintes
propriedades~\cite{Chandra:1996:WFD:234533.234549,hadzilacos94}:

\begin{itemize}
\item \textit{Validade}, se um processo bom \textit{TO-broadcasts} a
  mensagem \(m\), então ele eventualmente \textit{TO-delivers} \(m\).
\item \textit{Acordo uniforme}, se um processo \textit{TO-delivers} uma
  mensagem \(m\), então todos os processos bons eventualmente
  \textit{TO-deliver} \(m\).
\item \textit{Integridade uniforme}, para qualquer mensagem \(m\),
  cada processo \textit{TO-delivers} \(m\) no máximo uma vez, se
  somente se \(m\) foi \textit{TO-broadcast} por
  \textit{sender}\((m)\) anteriormente.
\item \textit{Ordem total uniforme}, se os processos \(p\) e \(q\)
  \textit{TO-deliver} as mensagens \(m\) e \(m'\), então \(p\)
  \textit{TO-delivers} \(m\) antes de \(m'\), se somente se \(q\)
  \textit{TO-delivers} \(m\) antes de \(m'\).
\end{itemize}

Se a primitiva de comunicação satisfaz todas as propriedades exceto
ordem total uniforme é chamada \textit{broadcast} confiável. No caso a
primitiva cumpra todas as propriedades prévias, é chamada uniforme,
porque impõe restrições ao comportamento de todos dos processos. O
broadcast não uniforme só se aplica aos processos bons (propriedades
de acordo e integridade não uniformes).

% Não gosto do paragrafo, é uma simples enumeração, não é muito
% legível.
A relação entre o conjunto destino das mensagense, o conjunto de
processos do sistema e a presença do remetente como destinatario da
mensagem gera a seguinte classificação:
\begin{inparaenum}[\itshape a\upshape)]
\item Se ambos são iguais, i.e \(\forall m \in \mathcal{M} (Dest(m) =
  \Pi)\), a primitiva é \textit{broadcast};
\item Se o conjunto destino é um subconjunto dos processos, e
  distintas mensagens têm distintos conjuntos destinos e os remetentes
  podem não ser destinatários, i.e.\ \(\exists m \in \mathcal{M}
  (sender(m) \notin Dest(m)) \wedge \exists m_i,m_j \in \mathcal{M}
  (Dest(m_i) \neq Dest(m_j))\), a primitiva é multicast.
\item Se o remitente é membro dos destinatários, i.e.\ \(\forall m \in
  \mathcal{M} (sender(m) \in Dest(m))\), o grupo é \textit{fechado};
\item Se o remitente não precisa pertencer ao grupo destino, i.e.\
  \(\exists m \in \mathcal{M}(sender(m) \notin Dest(m))\), o grupo e
  \textit{aberto}.
\end{inparaenum}

A conformação do conjunto de processos do sistema não precisa ser
fixa. Se os processos podem entrar, sair e ser removidos dele, o grupo
é \textit{dinâmico}, contraposto ao grupo \textit{estático}, que não
permite a mudanca de membros durante a execução. Às distintas
configurações ao longo do tempo são
\textit{vistas}~\cite{Chockler:2001:GCS:503112.503113}. A primitiva de
comunicação equivalente ao \textit{broadcast} confiável nos grupos
dinâmicos é a \textit{sincronia de vista}, que cumpre as mesmas regras
de validade, integridade uniforme e uma versão de acordo relaxada aos
membros atuais. Uma sincronia de vista que cumpre adicionalmente a
propriedade de ordem total é o equivalente ao \textit{broadcast} de
ordem total nos grupos estáticos.

Existem diversos mecanismos pelos quais se pode definir a ordem de
entrega das mensagens~\cite{Defago:2004}, porém, em todos são
distinguíveis três papéis: remetente (i.e.\ \(p \in \Pi_{sender}\)),
destinatário (i.e.\ \(p \in \Pi_{dest}\)) e o sequenciador que define
o ordem de entrega das mensagens. Existem as seguintes cinco classes:

\begin{itemize}
\item \textit{Sequenciador fixo} (e.g.\ Garcia-Molina e
  Spauster~\cite{garcia2002message}). Um único sequenciador é
  escolhido. Possui três variantes:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{unicast-broadcast}, se o remetente envia as mensagens
    ao sequenciador, e ele se responsabiliza pela entrega ordenada;
  \item \textit{broadcast-broadcast}, se o remetente envia as
    mensagens diretamente aos destinatários e ao sequenciador, e logo
    este envia a ordem de entrega;
  \item \textit{unicast-unicast-broadcast}, se o remetente envia as
    mensagens ao sequenciador, logo este retorna os identificadores de
    sequencia das mensagens, e finalmente o remetente envia
    diretamente as mensagens.
  \end{inparaenum}
\item \textit{Sequenciador móvel} (e.g.\
  Pinwheel~\cite{cristian97:high_performance}). É muito similar ao
  sequenciador fixo, mas o papel de sequenciador é transferível entre
  um conjunto de processos. Na literatura, o principio utilizado pelos
  sequenciadores móveis é equivalente ao \textit{broadcast-broadcast}
  dos sequenciadores fixos~\cite{Defago:2004}.
\item \textit{Baseados em privilégios} (e.g.\ Gopal e
  Toueg~\cite{Gopal:1989:RBS:645946.675018}). A diferença das classes
  anteriores, os papéis do sequenciador e do remetente são
  desenvolvidos pelo mesmo processo. O principio é que só o processo
  que possui o privilegio, e.g.\ token, pode enviar mensagens, mas
  este privilegio é circulado entre os remetentes.
\item \textit{Baseados na historia da comunicação}(e.g.\
  Atom~\cite{Bar-Joseph:2002:EDA:645959.676132}). São os destinatários
  os que definem a ordem de entrega das mensagens baseando-se na
  historia deles, i.e.\ os destinatários são os sequenciadores. Os
  dois métodos utilizados são:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{historia causal}, onde algoritmos de ordem causal
    parcial~\cite{Lamport:1978_clocks} são aumentados com políticas
    comuns para a ordenação de mensagens concorrentes, e o ordem
    total resultante é utilizado para ordenação das mensagens;
  \item \textit{união determinista}, onde não existe uma ordenação
    causal das mensagens, senão uma política determinista de união dos
    fluxos de mensagens de cada remetente.
  \end{inparaenum}
\item \textit{Acordo dos destinatários}(e.g.\ Chandra e
  Toueg~\cite{Chandra:1996:UFD:226643.226647}). Como o nome o indica,
  os destinatários acordam a ordem das mensagens a ser entregues. As
  variantes são:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{acordo na sequencia de mensagens}, cada destinatário
    assina uma \textit{timestamp} local a mensagem, logo a maior
    destas é escolhida como a \textit{timestamp} global e é utilizada
    para ordenar a entrega;
  \item \textit{acordo no conjunto de mensagens}, algoritmos de
    consenso são utilizados para determinar um subconjunto de
    mensagens a ser entregues simultaneamente por todos os processos
    (a ordenação no subconjunto é definida por algum parâmetro
    predefinido);
  \item \textit{acordo na aceitação de ordens propostas}, um processo
    propõe uma ordem das mensagens e os demais destinatários acordam
    se é aceitado o não, utilizando algum protocolo de \textit{commit}
    atômico.
  \end{inparaenum}
\end{itemize}

Chandra e Toueg~\cite{Chandra:1996:UFD:226643.226647} mostraram
que o problema do consenso uniforme e o \textit{broadcast} de ordem
total em sistemas assíncronos com falhas de parada são equivalentes,
i.e.\ qualquer algoritmo que possa resolver um deles também se pode
adaptar para resolver o outro. Portanto, o \textit{broadcast} de ordem
total é sujeito ao mesmo resultado de impossibilidade de Fischer,
Lynch e Patterson.

Existem múltiplos mecanismos pelos quais se pode prover alguma
tolerância a falhas ao \textit{broadcast} de ordem total. Na prática, os
algoritmos implementam vários mecanismos simultaneamente. Os mecanismos
são:

\begin{itemize}
\item \textit{Detecção de falhas} Baseados nos detetores de falhas não
  confiáveis propostos inicialmente por Chandra e
  Toueg~\cite{Chandra:1996:UFD:226643.226647}.
\item \textit{Serviço de configuração do grupo}, profundamente
  relacionado com os grupos dinâmicos. No evento de um processo cai, o
  serviço gera uma nova vista do grupo e a envia aos processos ativos,
  portanto, eles podem assumir que na vista atual todos os processos
  estão ativos. Se um processo foi excluído erroneamente, é forçado a
  cair para manter a correção. A diferença dos detetores de falhas,
  provê notificações de falhas consistentes.

\item \textit{Padrões de comunicação tolerantes a falhas}, são aqueles padrões
  que consideram, dentro do número \(n\) total de processos, um número
  \(f\) máximo de processos que podem falhar, e trabalham sob o
  pressuposto que sempre vão receber pelo menos \(n-f\) mensagens de
  resposta.

\item \textit{Estabilidade das mensagens}. Além da possibilidade que
  um processo fique bloqueado esperando a resposta de outro que caiu,
  tem que se considerar a estabilidade das mensagens. Uma mensagem
  \(m\) é \(k\)-estável se \(m\) e recebida por \(k\) processos. Se
  num sistema podem cair ao mais \(f\) processos, é importante detetar
  que as mensagens são \(f+1\)-estáveis, também chamadas estáveis, já
  que permite aos algoritmos garantir que, eventualmente, as mensagens
  são recebidas por todos os processos bons.
\item \textit{Consenso} O \textit{broadcast} de ordem total pode
  reduzir se a uma série de execuções do problema do consenso,
  portanto é possível delegar toda a responsabilidade da tolerância a
  falhas ao algoritmo de consenso.
\end{itemize}

\section{Treplica}
\label{sec:treplica}

Esta seção sumariza a plataforma Treplica, sobre a qual este projeto
será desenvolvido. Treplica é uma biblioteca desenvolvida para apoiar
a construção de aplicações replicadas altamente disponíveis no modelo
de falha e
recuperação~\cite{vieira08:_trepl,vieira10:implementing-tr}.  O
objetivo da ferramenta é garantir consistência e persistência de dados
através de abstrações de programação simples e descomplicadas.

A abstração  de programação fundamental oferecida pela  biblioteca é a
de filas  assíncronas persistentes, que são utilizadas  como canais de
comunicação em grupo com as seguintes propriedades:

\begin{inparaenum}[\itshape a\upshape)]
\item as mensagens são entregues no mesmo ordem;
\item todos os processos, ainda aqueles que caem e voltam ao sistema,
  recebem todas as mensagens; e
\item a persistência das mensagens é garantida.
\end{inparaenum}
A similaridade com o \textit{broadcast} de ordem total com sincronia
de vista (seção~\ref{sec:broadcast}) e
clara~\cite{Birman:1987:EVS:41457.37515}, mas a entrega das mensagens
é restrito ao estado da aplicação, não à vista atual. Porém, pode-se
implementar as filas persistentes utilizando \textit{broadcast} de
ordem total uniforme. Em Treplica, cada fila tem um identificador
único chamado \textit{queue id}. Os processos que participam da
comunicação criam pontos de conexão exclusivos chamados \textit{queue
  endpoints}, um para cada fila que utilizam. As primitivas oferecidas
pela fila são simples:

\begin{itemize}
\item \texttt{create(queueId)}, gera um ponto de conexão associado à
  fila.
\item \texttt{getProcessId()}, retorna o identificador do processo
  associado ao ponto de conexão.
\item \texttt{put(message)}, envia uma mensagem aos participantes da fila.
\item \texttt{get()}, recebe a próxima mensagem armazenada na fila.
\end{itemize}

A \emph{persistência} das mensagens é garantida pela fila e o ponto de
conexão que registra as mensagens já entregues. Portanto, no evento de
geração de um novo ponto de conexão, o processo vai receber todas as
mensagens enviadas pela fila. Esta propriedade, atrativa para o
desenvolvedor de aplicações, não se pode implementar efetivamente na
prática. Treplica suporta aplicações de grupos estáticos, nos quais os
participantes, i.e.\ pontos de conexão, são conhecidos desde o inicio
da aplicação e não mudam, mas podem cair e voltar ao sistema,
obrigarando o armazenamento permanente de toda a historia das
mensagens. A solução é o uso de persistência baseada na
fila~\cite{vieira10:implementing-tr} que armazena periodicamente de
maneira persistente uma copia do estado atual da aplicação e da fila,
i.e.\ \textit{snapshot} e o historial das mensagens já entregues
limpado. Este procedimento precisa suporte de parte da aplicação, a
qual deve delegar o controle de seu estado à fila através das
seguintes duas primitivas adicionais:

\begin{itemize}
\item \texttt{bind(stateHolder)}, cria uma relação entre o ponto de
  conexão e o processos, através do \textit{stateHolder}, um
  componente da aplicação que implementa \texttt{getState()} e
  \texttt{setState(state)}.
\item \texttt{checkpoint()}, solicita a geração do \textit{snapshot}
  do estado da aplicação e da fila.
\end{itemize}

É garantido que os \textit{snapshot} com a seguinte mensagem a ser
entregue. No caso que o processo falhe e quede atrasado no progresso
do sistema, a copia do estado de outra réplica pode-se utilizar para
sua atualização. Ainda em casos que o processo não falha mas fica
retrasado, é possível que seu estado seja trocado pelo estado de um
processo atualizado. Isto permite, e exige, que a aplicação seja
\textit{stateless}.

A implementação das filas assíncronas persistentes de Treplica utiliza
um algoritmo de \textit{broadcast} de ordem total uniforme baseado em
consenso, especificamente Paxos (ver seção~\ref{sec:consenso}) e Fast
Paxos~\cite{lamport06a}, uma variante que reduz uma das rondas de
comunicação, já que assume que as mensagens são ordenadas naturalmente
pelo canal de comunicação. A transição entre ambos algoritmos é
transparente ao usuário: em uma configuração de \(N\) réplicas, se
pelo menos \(\lceil 3N/4 \rceil\) estão disponíveis, Fast Paxos é
utilizado, no caso que pelo menos \(\lfloor 2N/1 \rfloor + 1\) estão
disponíveis, o algoritmo escolhido é Paxos; se nenhuma das dois
condições é cumprida o sistema é bloqueado até que suficientes
processos se recuperem.

\section{Proposta de pesquisa}
\label{sec:proposta}
Pesquisas anteriores~\cite{gray07:empirical,
  Pinheiro:2007:FTL:1267903.1267905,
  Schroeder:2007:DFR:1267903.1267904,  10.1109/SRDS.2008.9}  mostraram
que, na  prática, as falhas  dos componentes de hardware  dos sistemas
distribuídos  de   produção  são  maiores  que   as  publicadas  pelos
fabricantes; além  disso, erros no  software também causam  quedas nos
processos, portanto, a tolerância a falhas é vital.

Esta  proposta de  pesquisa tem  o  foco em  sistemas distribuídos  de
replicação      ativa      no      modelo      de      máquina      de
estados~\cite{Schneider:1990:IFS:98163.98167},  com \textit{broadcast}
de ordem total uniforme. Os processos têm as seguintes caraterísticas:
\begin{inparaenum}[\itshape a\upshape)]
\item acesso a memória estável e a memória volátil;
\item participação no \textit{broadcast} como remetentes e
  destinatários, i.e.\ \(\forall p,j \in \Pi~\exists m \in \mathcal{M}
  (sender(m) = p \wedge j \in Dest(m))\);
\item suscetibilidade às falhas de software ou hardware, as quais
  causam que os processos percam o conteúdo de sua memória volátil e
  não participem do sistema por um tempo limitado mas desconhecido,
  depois \textit{recuperam}-se e voltam à atividade.
\end{inparaenum}
As propriedades da comunicação pelo \textit{broadcast} uniforme,
definidas na seção~\ref{sec:broadcast}, que caracterizam o modelo são:
\begin{inparaenum}[\itshape a\upshape)]
\item o grupo de processos é fechado e estático;
\item a sequencia das mensagens é decidida por acordo dos
  destinatários, utilizando o algoritmo de consenso Paxos.
\end{inparaenum}

O mecanismo de tolerância a falhas do sistema é fornecido pelo
\textit{broadcast} de ordem total uniforme que garanta a entrega
ordenada das mensagens, ainda aos processos com falhas. É possível,
porém não prático, que sejam armazenadas todas as mensagens enviadas
pelo \textit{broadcast} e, no caso de falhas, estas sejam entregues
novamente ao processo recuperado. Ao invés, cada nó vai armazenar
\textit{checkpoints} em períodos regulais. Não precisasse utilizar
protocolos de \textit{checkpoint} distribuídos tais como os
apresentados em~\cite{Chandy:1985:DSD:214451.214456,
  Koo:1986:CRD:324493.325074} já que, a principal motivação do uso
deles, é garantir a consistência dos estados armazenados através do
sistema, mas neste caso não precisa; o \textit{broadcast} garanta a
consistência das mensagens entregues às replicas, e o algoritmo de
consenso fornece o mecanismo de coordenação e sincronização dos
estados.

% \begin{table}[h]
%   \small
%   \centering
%   \begin{tabular}{|l|p{5cm}|l|p{5cm}|}
%     \hline
%     \(\Pi\) & Conjunto de processos do sistema. &
%     \(\Pi_{local}\) & Conjunto de processos que armazenam localmente seus \textit{checkpoints}. \\
%     \(\Pi_{remote}\) & Conjunto de processos que armazenam remotamente seus \textit{checkpoints}. &
%     \(\Pi_{storage}\) & Conjunto de processos que armazenam localmente \textit{checkpoints} remotos, além dos próprios. \\
%     \(\Pi'_{storage}\) & Conjunto de processos externos que armazenam localmente \textit{checkpoints} remotos. &
%     \(P_{storage}\) & \(\Pi_{storage} \cup \Pi'_{storage}\). \\
%     \(States_i\) & Conjunto de estados do processo \(p_i\). &
%     \(S_i(t)\) & Estado do processo \(p_i\) no tempo \(t\). \\
%     \(\mathcal{M}_b\) & Conjunto das mensagens dos algoritmos (\textit{broadcast} e consenso). &
%     \(\mathcal{M}_s\) & Conjunto das mensagens de armazenamento dos \textit{checkpoints}. \\
%     \hline
%   \end{tabular}
%   \caption{Notação adicional.}
%   \label{tab:notacion_proposta}
% \end{table}

% Vamos definir mais formalmente o sistema; a
% tabela~\ref{tab:notacion_proposta} contém o resumo da notação
% utilizada adicional à já definida na tabela~\ref{tab:notacao}. Seja
% \(\Pi = \{p_1, \ldots, p_n\}\) um conjunto de \(n\) processos que
% conformam o sistema, i.e.\ participam do \textit{broadcast} de ordem
% total. Cada processo do sistema é modelado como uma máquina de
% estados, onde \(States_i\) é o conjunto (não necessariamente finito)
% de estados do processo \(p_i\). Seja \(S_i\) uma função de
% \(\mathcal{T}\) a \(States_i\), tal que \(S_i(t)\) representa o estado
% do processo \(i\) ao tempo \(t\); o estado especial \(\bot\)
% representa inatividade, e.g.\ \(S_i(t) = \bot \iff p_i \in F(t)\). Os
% processos só mudam de estado pelo intercambio de mensagens \(m \in
% \mathcal{M}\), ou pelos eventos de falha e recuperação.

O  modelo computacional  adotado  para a  discussão das  configurações
possíveis  de   armazenamento  de  estados  é  o   mesmo  descrito  na
seção~\ref{sec:notacao}.

Cada  processo do  sistema  é  modelado  como uma  máquina  de
estados, onde  \(States_i\) é o conjunto  (não necessariamente finito)
de  estados   do  processo  \(p_i\).   Seja  \(S_i\)  uma   função  de
\(\mathcal{T}\) a \(States_i\), tal que \(S_i(t)\) representa o estado
do  processo  \(i\)  ao   tempo  \(t\);  o  estado  especial  \(\bot\)
representa inatividade, e.g.\ \(S_i(t) =  \bot \iff p_i \in F(t)\). Os
processos  só  mudam  de  estado  pela  troca  de  mensagens  \(m  \in
\mathcal{M}\), ou pelos eventos de falha e recuperação.

O \textit{checkpoint} do processo \(p_i\) no tempo \(t\) é definido
como a copia não modificável do estado \(S_i(t)\). A operação que os
gera é atômica~\cite{Randell:1978:RIC:356725.356729} e só pode-se
executar no tempo \(t\) se \(S_i(t) \neq \bot\). Formalmente, a
recuperação, ou reconstrução~\cite{Okun:2002:NSR:829526.831119}, no
tempo \(t'\) do processo \(p_i\) é uma operação especial, executável
se \(p_i \in F(t')\), que transforma do estado inicial \(S_i(0)\) ao
estado \(S_i(t)\) armazenado pelo \textit{checkpoint} gerado no tempo
\(t\), tal que \(t'> t\). O procedimento descrito só volta o processo
a seu último estado armazenado; a responsabilidade da atualização
deste até o estado atual das demais réplicas é delegada ao algoritmo
de consenso. Os \textit{checkpoints} são gerados em intervalos
regulais.

Sejam \(\Pi_{local}\), \(\Pi_{remote}\) e \(\Pi_{storage}\), três
subconjuntos disjuntos do \(\Pi\) tais que sua união é igual a
este. Se \(p \in \Pi_{local}\), o processo \(p\) armazena seus
\textit{checkpoints} em sua memoria estável local. Se \(p \in
\Pi_{remote}\), o processo \(p\) delega a responsabilidade do
armazenamento a outros processos, enviando-lhes os
\textit{checkpoints}. Se \(p \in \Pi_{storage}\), o processo \(p\)
armazena seus \textit{checkpoints} em sua memoria estável local, além
de armazenar \textit{checkpoints} de processos remotos em suas duas
memórias: a estável e a volátil. Além dos processos já definidos,
existem um conjunto de processos \(\Pi'_{storage}\) que não participam
do \textit{broadcast} de ordem total, e portanto não são replicas do
sistema, i.e.\ \(\Pi_{storage} \cap \Pi = \emptyset\): se \(p \in
\Pi'_{storage}\), o processo \(p\) é um repositório, e tem a única
função de armazenar \textit{checkpoints} de processos remotos em suas
duas memorias: a estável é a volátil. Existe uma relação entre os
processos que delegam o armazenamento de seus \textit{checkpoints},
\(\Pi_{remote}\), e aqueles que assumem a responsabilidade,
representados pelo conjunto de processos \(P_{storage} = \Pi_{storage}
\cup \Pi'_{storage}\)~: seja \(Store\) uma relação de \(\Pi_{remote}\)
a \(2^{P_{storage}}\), tal que \(Store(p)\) representa o conjunto de
processos em \(P_{storage}\) que armazenam os \textit{checkpoints} de
\(p\); diz-se que \(j\) é um \textit{store} de \(p\) se somente se \(j
\in Store(p)\). Todos os processos de armazenamento devem ser
\textit{store} de pelo menos um processo remoto, i.e.\ \(\forall j \in
P_{storage} \exists p \in \Pi_{remote} (j \in Store(p))\), e todo
processo remoto tem que armazenar seus \textit{checkpoints} em pelo
menos um \textit{store}, i.e.\ \(\forall p \in \Pi_{remote} (Store(p)
\neq \emptyset)\).

%% As mensagens válidas são de duas classes: sejam \(\mathcal{M}_b\) e
%% \(\mathcal{M}_s\) dois subconjuntos disjuntos de \(\mathcal{M}\), tais
%% que \(\mathcal{M}_b \cap \mathcal{M}_s = \emptyset \wedge
%% \mathcal{M}_b \cup \mathcal{M}_s = \mathcal{M}\). \(\mathcal{M}_b\) é
%% o conjunto de todas as mensagens válidas do sistema que estão
%% relacionadas com o progresso dos algoritmos de consenso e de
%% \textit{broadcast} de ordem total uniforme; os remetentes e
%% destinatários destas mensagens são processos que participam do
%% consenso, i.e.\ \(\forall m \in \mathcal{M}_b (sender(m) \in \Pi \wedge
%% Dest(m) \subseteq \Pi)\).  \(\mathcal{M}_s\) é o conjunto de todas as
%% mensagens válidas do sistema que transmitem valores de
%% \textit{checkpoint} entre os processos que participam do armazenamento
%% remoto de dados, i.e.\ \(\forall m \in \mathcal{M}_s(sender(m) \in
%% (\Pi_{remote} \cup P_{storage}) \wedge Dest(m) \in (\Pi_{remote} \cup
%% P_{storage}))\).

\begin{figure}[h]
  \centering
   \includegraphics[width=120mm]{images/system_arch}
  \caption{Arquitetura do sistema}
  \label{fig:arquitetura}
\end{figure}

O objetivo desta pesquisa é encontrar a melhor configuração em termos
de desempenho num sistema com as caraterísticas descritas na
figura~\ref{fig:arquitetura}. As medidas de desempenho utilizadas são:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{disponibilidade}, razão entre o tempo que a aplicação
  está operacional e o tempo total de execução;
\item  \textit{desempenho}, é  a  razão entre  o  desempenho médio  da
  aplicação em requisições atendidas por segundo durante o período sem
  falhas  e o desempenho  promédio durante  o período  de recuperação;
  está  medida  quantifica  o  impacto  das falhas  no  desempenho  da
  aplicação;
\end{inparaenum}

As possíveis configurações do sistema são:

\begin{itemize}
\item \(\Pi_{local} = \Pi\), está é a configuração atual de
  Treplica. Todos os processo armazenam seus \textit{checkpoints},
  portanto o custo de recuperação do estado é dominado pela latência
  da memoria estável, e o procedimento não gera tráfego de rede ou
  carga adicional aos nós vizinhos\footnote{É claro que a falha de um
    processo vai gerar uma carga de trabalho adicional aos demais
    membro do sistema, devido à redistribuição de tarefas, mas é
    considerado um custo inerente ao modelo e portanto não considerado
    nos cálculos.}
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} =
  \emptyset \), alguns processos armazenam seus estados em processos
  remotos que participam do \textit{broadcast}, portanto o custo de recuperação
  desses processos é dominado pela latência de rede, e o procedimento
  gera tráfego de rede e carga adicional aos vizinhos, mas é uma
  quantidade limitada aos processos que utilizam armazenamento remoto.
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), alguns processos armazenam seus estados em processos
  remotos que participam ou não do \textit{broadcast}, portanto o custo de
  recuperação desses processos é dominado pela latência de rede, e o
  procedimento gera tráfego de rede e carga adicional aos vizinhos,
  mas é uma quantidade menor à opção anterior, já que o tráfego e a
  carga gerados aos nós repositório não tem impacto sobre o desempenho do
  sistema.
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} = \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), alguns processos armazenam seus estados em processos remotos
  que não participam do \textit{broadcast}, portanto o custo de recuperação
  desses processos é dominado pela latência de rede, e o procedimento
  não gera tráfego de rede ou carga adicional aos vizinhos.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} =
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que participam do \textit{broadcast}, portanto o custo de recuperação
  está dominado pela latência de rede, e o procedimento gera tráfego
  de rede e carga adicional aos vizinhos.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que participam ou não do \textit{broadcast}, portanto o
  custo de recuperação está dominado pela latência de rede, e o
  procedimento gera tráfego de rede e carga adicional aos vizinhos,
  mas é uma quantidade menor à proposta anterior.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} = \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que não participam do \textit{broadcast}, portanto o custo
  de recuperação está dominado pela latência de rede, e o procedimento
  não gera tráfego de rede ou carga adicional aos vizinhos.
\end{itemize}

A avaliação das opções tem que considerar não só a melhor opção, senão
qual é a proporção de cada conjunto de processo que gera o resulta
mais ótimo. Um aspecto importante a considerar se é o desempenho das
soluções sobre as distintas classes de processos em relação as falhas:
ativo, eventualmente ativo, eventualmente inativo e instável (ver
seção~\ref{sec:notacao}).

% LAS TECNICAS PROPUESTAS TAMBIEN HAN SIDO HECHAS PARA EL AMBIENTE
% HPC. [ver paper de Bautista Gomez] REVISAR ARTICULO DE ISLENE

% As alternativas a avaliar são as seguintes:

% % hay que tener en consideracion que en este caso no se asume las
% % fallas de disco dentro de la evaluacion. El metodo necesario para
% % soportar esa situacion seria, por ejemplo, el uso de un sistema de
% % archivos distribuido con replicacion, como hdfs. Aunque el impacto
% % sobre el desempenho del sistema no es, necesariamente, despreciable,
% % puede asumirse que afecta de manera uniforme a todos los nodos del
% % sistema que utilizan la memoria estable.


\section{Metodologia Científica}
\label{sec:metodologia}

O trabalho divide-se em duas fases. Na primeira, faremos o projeto do
sub-sistema de persistência e recuperação de estados para o Treplica,
levando em conta as possibilidades de armazenamento listadas na
seção~\ref{sec:proposta}.

Na segunda fase, codificaremos o sub-sistema de armazenamento remoto e
compararemos experimentalmente o seu desempenho em distintas
configurações. Durante essa fase os experimentos serão realizados com
o mesmo método experimental e com as duas aplicações já implementadas
para testar Treplica: um benchmark TPC-W e um hash
replicado~\cite{buzato09}.  As medidas de interesse são
disponibilidade, desempenho e tempo de recuperação~\cite{buzato09}.

Durante todo o mestrado haverá a preocupação com a escrita e
publicação dos resultados na forma de relatórios técnicos e artigos em
veículos científicos arbitrados.


\subsection{Tarefas e cronograma}
\label{sec:planodetrabalho}

Esta seção detalha as tarefas planejadas, e o cronograma proposto,
para o desenvolvimento do Mestrado (Ta\-bela~\ref{projtimetable}):

\begin{enumerate}
\addtolength{\itemsep}{-0.35\baselineskip}

% Ago-Julho 2010
\item \label{t1} Créditos em disciplinas

% Abril-Julho 2010
\item \label{t2} Revisão bibliográfica

% Maio-Ago 2010
\item \label{t3} Estudo dirigido

% Jul-Ago 2010
\item \label{t4} Elaboração do projeto de mestrado

% Ago 2010 - Jul 2011
\item \label{t5} Estudo comparativo de algoritmos

% Jan 2011 - Dez 2011
\item \label{t6} Proposta, análise e prova de algoritmos.

% Dez 2011 - Dez 2011
\item \label{t7} Implementação da solução sobre a plataforma
Tréplica~\cite{vieira08:_trepl}. Testes de desempenho da solução com
diversas cargas de trabalho, tanto na presença como na ausência de
falhas de processos.

% Mai 2011 - Jan 2012
\item \label{t8} Escrita da Dissertação de Mestrado

% Fev 2012 - Mar 2012
\item \label{t9} Defesa da Dissertação de Mestrado

% Dez 2010 - Mar 2012
\item \label{t10} Escrita e submissão de artigos para publicação

\end{enumerate}

\begin{table}[h]
\begin{center}
\setlength{\tabcolsep}{1.5pt}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
  &  \multicolumn{5}{c|}{\scriptsize 2010} & \multicolumn{12}{c|}{\scriptsize 2011} & \multicolumn{7}{c|}{\scriptsize 2012} \\ \cline{2-25}
{\small Tarefas } &
\rotatebox{90}{\scriptsize ago } &
\rotatebox{90}{\scriptsize set } &
\rotatebox{90}{\scriptsize out } &
\rotatebox{90}{\scriptsize nov } &
\rotatebox{90}{\scriptsize dez } &
\rotatebox{90}{\scriptsize jan } &
\rotatebox{90}{\scriptsize fev } &
\rotatebox{90}{\scriptsize mar } &
\rotatebox{90}{\scriptsize abr } &
\rotatebox{90}{\scriptsize mai } &
\rotatebox{90}{\scriptsize jun } &
\rotatebox{90}{\scriptsize jul } &
\rotatebox{90}{\scriptsize ago } &
\rotatebox{90}{\scriptsize set } &
\rotatebox{90}{\scriptsize out } &
\rotatebox{90}{\scriptsize nov } &
\rotatebox{90}{\scriptsize dez } &
\rotatebox{90}{\scriptsize jan } &
\rotatebox{90}{\scriptsize fev } &
\rotatebox{90}{\scriptsize mar } &
\rotatebox{90}{\scriptsize abr } &
\rotatebox{90}{\scriptsize mai } &
\rotatebox{90}{\scriptsize jun } &
\rotatebox{90}{\scriptsize jul } \\ \hline

\quad\ref{t1}  & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\quad\ref{t2}  &    & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\quad\ref{t3}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\quad\ref{t4}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\quad\ref{t5}  &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    \\ \hline
\quad\ref{t6}  &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    \\ \hline
\quad\ref{t7}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f &    &    \\ \hline
\quad\ref{t8}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f   &    \\ \hline
\quad\ref{t9}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f \\ \hline
\quad\ref{t10} &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f \\ \hline
\end{tabular}
\caption{Cronograma do projeto}
\label{projtimetable}
\end{center}
\end{table}


\begin{small}
\phantomsection
\addcontentsline{toc}{section}{\bibname}
\bibliographystyle{plain}
\bibliography{bibliography}
\end{small}

\end{document}