Added methodology and context.

[mymsc.git] / mscMonografia.tex

\documentclass[10pt]{article}

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

\newcommand{\mytitle}{Impacto do armazenamento remoto de estados na
  recuperação de replicas} %PT
\newcommand{\f}{$\blacksquare$}

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

\title{\mytitle}

\author{
Rodrigo Eduardo 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 de um, ou
  vários processos durante a execução, produz uma degradação no
  desempenho devido à re-distribuição de trabalho. Além de possíveis
  perdas de informação, a carga adicional poderia ultra-passar a
  capacidade dos componentes disponíveis.  É, portanto, fundamental
  reduzir ao mínimo o tempo de recuperação dos processos. Um dos
  procedimentos que contribui a este é a leitura dos dados necessários
  para voltar ao estado prévio à queda. Nós propomos a avaliação
  minuciosa de múltiplas configurações de sistemas distribuídos
  replicados com armazenamento híbrido, combinando memoria estável
  local e repositórios remotos, tal que se minimize o uso de
  dispositivos de alta latência durante a recuperação sem sacrificar a
  consistência. Adicionalmente, o projecto contempla a implementação de
  detetores de falhas mais acordes ao modelo de falha-e-recuperação,
  como os propostos por Aguilera et al.\, devido à possibilidade de
  queda dos repositórios remotos e a necessidade de tomar previsões
  nesse cenário.  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 desenhados para executar se em
sistemas compostos por um conjunto interconectado de processos
autônomos que intercambiam informação. O progresso do algoritmo
depende de dois elementos: o progresso individual de cada um dos
processos, e a troca de informação entre eles. Os distintos modelos,
i.e.\ presunções, que descrevem características específicas desses
elementos no 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 presunçõ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 distintas combinações dos modelos apresentados, dão
lugar a uma multiplicidade de ambientes muito amplia e, portanto, não
é possível, ou ao menos prático, desenhar algoritmos distribuídos que
sejam capazes de executar se em qualquer modelo; é por isso que
somente pode avaliar se a correção dos algoritmos se suas presunções
sobre o sistema são válidas. Por exemplo, um algoritmo desenhado para um
sistema de memoria compartilhada, síncrono e sem falhas não vai
funcionar, mesmo seja correto, se o sistema é assíncrono, utiliza
troca de mensagens ponto-a-ponto é apresenta falhas bizantinas.

Os modelos supostos pelo algoritmo vão definir as caraterísticas do
sistema, portanto, se são muito restritivos, a aplicabilidade do
algoritmo é menor. Aqueles mais estritos fazem o desenvolvimento, e as
provas de correção, mais simples, já que garantem comportamentos mais
previsíveis; porém, construir um sistema que cumpra aquelas condições
fortes é muito complexo ou altamente custoso, além de não ser sempre
possível. Portanto, a eleição de modelos mais relaxados é preferível,
embora introduzam uma maior complexidade, apresentam condições mais
próximas das alcançáveis na realidade.

Os algoritmos no modelo temporal assíncrono não dependem do tempo para
seu correção e, portanto, são preferíveis, uma vez que esta
caraterística temporal é introduzida pelas variações no desempenho do
sistema~\cite{Chandra:1996:WFD:234533.234549}. Além da assincronia, a
tolerância a falhas é outra caraterística importante, já que, seja por
erros no software ou por falhas do hardware, elas vão acontecer. A
desvantagem da assincronia com falhas de processo é que existem
problemas solucionáveis em outros modelos que não são resolvíveis,
e.g.\ consenso no modelo
síncrono~\cite{Dwork:1988:CPP:42282.42283}. Nestos casos, uma solução
pode-se alcançar só se os requerimentos de correção são debilitados, o
modelo fortalecido, ou ambos~\cite{Lynch:1996:DA:525656}.

Os detetores de falhas são, informalmente, módulos distribuídos que
fornecem informação (não necessariamente correta) sobre o estado atual
dos processos no sistema, i.e.\ quais são suspeitos de estar
inativos. Os detetores acrescentam o modelo assíncrono, possibilitando
a solução de problemas como o problema de consenso
distribuído~\cite{Chandra:1996:UFD:226643.226647}.

No modelo de \textit{falha-e-recuperação}, os processos podem voltar ao
sistema e, portanto, precisam de armazenar, com segurança, suficiente
informação para voltar a seu estado anterior se uma falha acontecer;
no caso contrario, i.e.\ se fossem amnésicos, pode-se argumentar que um
processo em recuperação é indistinguível de um processo novo,
i.e.\ \textit{falha-e-para}.

Os processos só podem armazenar de maneira persistente os dados
necessários para recuperar se em dois lugares: localmente, em sua
memoria estável, ou remotamente, em outro processo. No primeiro caso, o
custo é determinado pela latência do disco; no segundo caso, é
determinado pela latência da rede mais o custo do aceso à informação,
i.e.\ memoria volátil ou memoria estável. Neste contexto, a nossa
questão de pequisa é a seguente:

\begin{quotation}
  \noindent \textit{Qual é o método, ou combinação deles, de
    armazenamento e obtenção da informação necessária para a
    recuperação de processos após falhas com melhor desempenho e menor
    impacto no sistema?}\todo{pergunta correta?}
\end{quotation}

A recuperação é um procedimento que volta o estado de um processo em
recuperação, a um estado anterior à falha. Os dados que permitem
aquela operação, normalmente uma copia do estado anterior, são
chamados de
\textit{checkpoints}~\cite{Randell:1978:RIC:356725.356729}, os quais
têm que ser gerados periodicamente e armazenados
persistentemente. Portanto, o custo da solução escolhida, tem um
impacto no sistema ainda durante os períodos sem falhas. Além disso,
tem que se considerar a robustez: se a informação é armazenada em na
memoria volátil, não se pode suportar uma falha massiva dos
processos. Por conseguente, a adequação da escolha depende dos
cenários supostos.

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, ainda em caráter inicial, 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.  Nestos últimos quatro anos o Prof. Buzato trabalhou em
replicação ativa com o seu aluno de Doutorado, Gustavo M. D. Vieira e
com 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.  Os seguintes trabalhos são o resultado desse
período de pesquisa:

\begin{description}
\item \textsl{Treplica: Ubiquitous
    replication}~\cite{vieira08:_trepl}, publicado em 2008 , apresenta
  detalhadamente a conceição e implementaçã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 troca constantemente.
\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, ou combinação deles, de armazenamento e
obtenção da informação necessária para a recuperação de processos após
falhas com melhor desempenho e menor impacto no
sistema?. \todo{pregunta de pesquisa repetida}

\section{Fundamentação Teórica}
\label{sec:teoria}
Fornecer um serviço altamente disponível empregando múltiplos
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}, se todos os processos
recebem e executam as mesmas requisições, no mesmo ordem; e a passiva,
se um único processo recebe todas as requisições, as aplica
localmente, e depois seu estado é copiado pelas demais réplicas. Na
replicação ativa, um dos métodos mais utilizados em sua implementação
são os algoritmos de consenso~\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}, nos definiremos a notação utilizado ao longo
do texto além dos modelos supostos. 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. Finalmente, na
seção~\ref{sec:detetores}, os detetores de falhas propostos por
Chandra e Toueg~\cite{Chandra:1996:UFD:226643.226647} são descritos,
incluindo as melhoras para sua adequação ao modelo de
falha-e-recuperação, introduzidas por Aguilera et
al.~\cite{springerlink:aguilera98}.

\subsection{Modelo do sistema e notação}
\label{sec:notacao}
O modelo suposto neste trabalho é assíncrono, portanto, não existe
presunção nenhuma acerca do tempo de demora da comunicação ou do
processamento. Todos os processos no sistema estão conectados, e a
comunicaçã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 rango de valores dos
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{springerlink:aguilera98}. 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{springerlink:aguilera98}:

\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
resolú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 randomização~\cite{Chor89},
definição de problemas mais débeis e suas soluções~\cite{dolev87},
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}

\todo[noline]{Multipaxos? Fast Paxos? devo incluir?}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}

Foi mostrado por Chandra e Toueg~\cite{Chandra:1996:UFD:226643.226647}
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}, os quais são discutidos
  com detalhe na seção~\ref{sec:detetores}
\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{Patrões de comunicação resistentes}, são aqueles patrõ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}

\subsection{Detetores de falhas }
\label{sec:detetores}
Os detetores de falhas não confiáveis, propostos inicialmente por
Chandra e Toueg~\cite{Chandra:1996:WFD:234533.234549,
  Chandra:1996:UFD:226643.226647}, são, informalmente, um conjunto de
módulos distribuídos, um por processo, que possuem uma visão do
sistema, i.e.\ uma listagem dos processos que são suspeitos de estar
inativos, mas não precisasse garantir a correção desta, e.g.\ pode-se
incluir na listagem processos ativos.

Formalmente, a \textit{historia de um detetor de falhas} \(H\) é uma
função de \(\Pi \times \mathcal{T}\) a \(2^\Pi\), onde \(H(p,t)\) é o
valor do detetor de falhas do processo \(p\) ao tempo \(t\). Se o
processo \(q \in H(p,t)\) diz-se que o processo \(p\) suspeita \(q\)
ao tempo \(t\). Já que os detetores não são confiáveis, e possível que
dois processos distintos \(p \neq q\) possuam informação distinta,
i.e.\ \(H(p,t) \neq H(q,t)\). Um detetor de falhas \(\mathcal{D}\) é
uma função que mapeia cada padrão de falhas \(F\) a um conjunto de
historias de detetores de falhas \(D(F)\), sendo este o conjunto de
todas as historias do detetor de falhas \(D\) que podem acontecer em
execuções com o padrão de falhas \(F\).

Na proposta original de Chandra e
Toueg~\cite{Chandra:1996:UFD:226643.226647,
  Chandra:1996:WFD:234533.234549}, definem se duas propriedades de
completude e quatro de precisão que podiam cumprir os detetores de
falhas:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{completude forte}, eventualmente todo processo que caiu é
  suspeito permanentemente por \textit{todos} os processos bons;
\item \textit{completude fraca}, eventualmente todo processo que caiu
  é suspeito permanentemente por \textit{alguns} processos bons;
\item \textit{precisão forte}, nenhum processo é suspeito antes de cair;
\item \textit{precisão débil}, alguns processos bons não são
  suspeitos nunca;
\item \textit{precisão forte eventual}, após algum tempo \(t \in
  \mathcal{T}\), nenhum processo bom é suspeito por nenhum outro
  processo bom.
\item \textit{precisão franca eventual}, após algum tempo \(t \in
  \mathcal{T}\), alguns processos bons não são suspeitos por nenhum
  outro processo bom.
\end{inparaenum}
Das possíveis oito classes de detetores de falhas que se podem criar
baseando-se nas combinações daquelas propriedades, os autores mostram
que são \textit{reduzíveis} só a quatro, onde \(\mathcal{D'}\) e
reduzível a \(\mathcal{D}\) se existe um algoritmo distribuído que
possa transformar \(D\) em \(D'\). Eles mostram que é possível
resolver o problema do consenso com cada uma das classes de detetores
de falhas resultantes: perfeito \(\mathcal{P}\) (completude forte,
precisão forte), forte \(\mathcal{S}\) (completude forte, precisão
fraca), eventualmente perfeito \(\diamond \mathcal{P}\) (completude
forte, precisão forte eventual), e eventualmente forte \(\diamond
\mathcal{S}\) (completude forte, precisão fraca).

O modelo de falhas utilizado por Chandra e Toueg não permite a
recuperação dos processos, portanto, a diferença da definição da
seção~\ref{sec:notacao}, os processos bons eram aqueles que nunca
falhavam e os ruins aqueles que caiam e não voltavam. Oliveira et
al.~\cite{oliveira97:consensus} e Hurfin et
al.~\cite{Hurfin:1998:CAS:829523.830974} apresentaram soluções para o
modelo de falha e recuperação, mas Aguilera et
al.~\cite{springerlink:aguilera98} mostraram que a propriedade de
completude forte das que elas dependiam, pode gerar comportamento
indesejável para satisfazer aquela propriedade, forçando aos detetores
de falhas a suspeitar de processos bons eventualmente para sempre. A
raiz deste comportamento é o fato que a abordagem tradicional tenta
pronosticar se um processo que caiu e volto, vai volver a cair ou
não. Este comportamento não impede que o algoritmo progresse, mas pode
ter um efeito negativo em seu desempenho.

Aguilera et al.~\cite{springerlink:aguilera98} propõem um novo tipo de
detetores de falhas que não exibem este comportamento e, portanto, são
mais apropriados ao modelo de falha e recuperação. Cada detetor produz
como saída dois elementos \(\langle trustlist, epoch \rangle\):
\(trustlist\) é um conjunto de processos, onde \(q \in trustlist\) se
\(p\) suspeita que \(q\) está ativo, e \(epoch\) é um vector de
inteiros indexado pelos elementos de \(trustlist\), onde \(epoch[q]\)
é o estimado de \(p\) do número de vezes que \(q\) caiu e
voltou. Existem duas classes de detetores de falhas descritas por
Aguilera et al.\
\begin{itemize}
\item \(\diamond S_e\), caraterizada pelas seguintes propriedades de:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{monotonicidade}, os valores de \(epoch\) produzidos
    pelos detetores dos processos \textit{bons} são eventualmente no
    decrescentes;
  \item \textit{completude}, por cada processo ruim \(r\), e por cada
    processo bom \(b\), ou eventualmente \(b\) suspeita
    permanentemente de \(r\) ou o \(epoch\) de \(b\) aumenta sem
    limites.
  \item \textit{precisão}, algum processo bom \(K\) e cada processo
    bom \(b\), eventualmente \(g\) permanentemente confia em \(K\) e o
    valor \(epoch\) de \(K\) em \(g\) para de cambiar.
  \end{inparaenum}
\item \(\diamond S_u\), que aumenta a classe \(\diamond S_e\) com a
  propriedade de precisão forte que inclui processos instáveis e
  permite-lhes suspeitar de todos os processos bons: \textit{precisão
    forte}, seja algum processo bom \(K\):
  \begin{inparaenum}[\itshape a\upshape)]
  \item por cada processo bom \(g\), eventualmente \(g\) confia
    permanentemente de \(K\) e o \(epoch\) de \(K\) em \(g\) para de
    cambiar; e
  \item por cada processo instável \(u\), eventualmente quando \(u\)
    está ativo, \(u\) confia em \(K\) e o \(epoch\) de \(K\) em \(u\)
    para de cambiar.
  \end{inparaenum}
\end{itemize}

\section{Treplica}
\label{sec:treplica}
Esta seção sumariza a plataforma Treplica, sobre a qual este projeto
será desenvolvido. Treplica é uma biblioteca desenhada para suportar 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.

Na raiz da biblioteca estão as colas assíncronas persistentes, que são
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 colas persistentes utilizando \textit{broadcast} de
ordem total uniforme. Em Treplica, cada cola 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 por cada cola que utilizam. As primitivas das colas
são simples:

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

A persistência das mensagens é garantida pela cola 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 cola. 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
cola~\cite{vieira10:implementing-tr} que armazena periodicamente de
maneira persistente uma copia do estado atual da aplicação e da cola,
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 à cola 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 os métodos
  \texttt{getState()} e \texttt{setState(state)}.
\item \texttt{checkpoint()}, solicita a geração do \textit{snapshot}
  do estado da aplicação e da cola.
\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 colas 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,
  Schroeder:2007:DFR:1267903.1267904, 10.1109/SRDS.2008.9,
  Pinheiro:2007:FTL:1267903.1267905} mostraram que, na prática, as
falhas dos componentes de hardware dos sistemas distribuídos de
produção são maiores às reportadas pelos fabricantes; além disso,
erros no software também causam quedas nos processos, portanto, a
tolerância a falhas é vital.

A proposta de pesquisa vai-se focar nos 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 aceso 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.

Vamos definir mais formalmente o sistema;. 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 \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 de ser o
\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 dois 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}, ratio entre o tempo que a aplicação
  está operacional e o tempo total de execução;
\item \textit{perfomability}, é o ratio entre o desempenho promédio da
  aplicação (AWIPS) 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;
\item \textit{precisão}, ratio entre o número de requisições com erro
  e o total destas durante a execução;
\item \textit{autonomia}, ratio entre o número de intervenções humanas
  precisadas para o reinicio das replicas e o número de falhas no
  sistema.
\end{inparaenum}
\todo{Os parâmetros de desempenho supostos são os mesmos que no
  trabalho de tréplica do 2009\cite{buzato09}}

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 intestável (ver
seção~\ref{sec:notacao}). Portanto, além de implementar os mecanismos
necessários para dar suporte às distintas classes de processos, é
preciso a implementação de detetores de falhas no modelo proposto por
Aguilera et al.~\cite{springerlink:aguilera98} (ver
seção~\ref{sec:detetores}), que possam fornecer melhor informação
sobre os processos bons, ruins é instáveis.

% 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, sob o método de
comparação (formal), será realizada uma evaluação de distintas
soluções a problemas similares propostas na literatura, por exemplo no
trabalho de Menderico e Garcia~\cite{10.1109/SRDS.2010.17}, tomando em
conta as caraterísticas proprias de um sistema de replicação ativa com
comunicação de \textit{broadcast} de ordem total, no qual não é
necessario um protocolo distribuído de \textit{checkpoint}.

Na segunda fase, codificaremos o sub-sistema de armazenamento remoto
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}.

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

Esta seção detalha as tarefas planejadas para o desenvolvimento do
Mestrado e o cronograma proposto (Tabela~\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{mscMonografia,bibliography}
\end{small}

\end{document}