From 5feb15a870c6badada43517a2a2dea6287f60ddc Mon Sep 17 00:00:00 2001 From: Rodrigo Lazo Date: Thu, 10 Feb 2011 03:58:59 -0200 Subject: [PATCH] broadcasting (sub)subsection is almost done. --- mscMonografia.tex | 193 ++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 130 insertions(+), 63 deletions(-) diff --git a/mscMonografia.tex b/mscMonografia.tex index 479fd1e..4851033 100644 --- a/mscMonografia.tex +++ b/mscMonografia.tex @@ -111,14 +111,15 @@ mais próximas das alcançáveis na realidade. Os algoritmos no modelo temporal assíncrono não dependem do tempo para a sua correção é portanto são preferíveis, já que na prática esta caraterística temporal é introduzida pelas variações no desempenho do -sistema \cite{chandra96c}. 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 dificuldade da -assincronia com falhas de processo é que existem problemas -solucionáveis em outros modelos que não possuem solução, e.g. consenso -no modelo síncrono \cite{dwork88}. 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}. +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 +dificuldade da assincronia com falhas de processo é que existem +problemas solucionáveis em outros modelos que não possuem solução, +e.g. consenso no modelo síncrono \cite{dwork88}. 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}. %solucao e repetido muitas vezes Os detetores de falhas são, informalmente, módulos distribuídos que fornecem informação (não necessariamente correta) sobre o estado atual @@ -173,7 +174,8 @@ projeto e o seu respectivo conograma. \todo[noline]{corregir \section{Contexto da Pesquisa} \label{sec:contexto} -\todo{Conteudo?} +\todo{Que conteudo é adequado? Qual é a diferença com a fundamentação + teórica?} \section{Fundamentação Teórica} \label{sec:teoria} @@ -209,11 +211,11 @@ e Úrban\cite{Defago:2004}. Seja \(\Pi = {1, \ldots, n}\) um conjunto de \(n\) processos que conformam o sistema. A comunicação é baseado no envio de mensagens, onde \(\mathcal{M}\) é o conjunto de mensagens válidos, \(sender(m) \in \Pi \) designa o processo originador do -mensagem \(m\) e \(dest(m) \subseteq \Pi \) é o conjunto de processos +mensagem \(m\) e \(Dest(m) \subseteq \Pi \) é o conjunto de processos não vazio ao qual o mensagem \(m\) e enviado. Além disso, seja \(\Pi_{sender}\) o conjunto de todos os processos que podem enviar uma mensagem válida \(m \in \mathcal{M}\), e seja \(\Pi_{dest} -\stackrel{\mathrm{def}}{=} \bigcup_{m \in \mathcal{M}} dest(m)\) o +\stackrel{\mathrm{def}}{=} \bigcup_{m \in \mathcal{M}} Dest(m)\) o conjunto de destinos possíveis para as mensagens válidas. A seguinte classificação dos processos em função a seu comportamento @@ -233,30 +235,32 @@ processo se \textit{recupera} no tempo \(t\) se está inativo no tempo \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 está sempre ativo. + vez, mas após algum momento \(t\), o processo está sempre + ativo. \todo[noline]{traduções corretas?} \item \textit{Eventualmente Inativo}: Após algum momento \(t\), o processo é está sempre inativo. \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 não é -eventualmente inativo ou instável. Denota-se \(bom(F)\), \(ruim(F)\) e -\(instável(F)\) aos conjuntos de processos (em \(F\)) bons, ruins e -instáveis, respetivamente. +Um processo é \textit{bom}\todo{é bom o termo correto?} ~(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)\)\todo{é ruim o termo correto?} e \textit{instável}\((F)\) +aos conjuntos de processos (em \(F\)) bons, ruins e instáveis, +respetivamente. -\subsection{Consenso e Broadcast confiavel} +\subsection{Consenso e o Broadcast de ordem total} \label{sec:consenso_broadcast} - +% agregar um paragrafo introductorio sobre a relação entre o consenso +% e o broadcast confiavel para estabelecer a razão de ter uma seção só +% para ambos. Esta é estabelecida neste paper +% \cite{Chandra:1996:UFD:226643.226647} O problema do consenso\cite{Lamport:1982:BGP:357172.357176} é um dos mais fundamentais da área dos algoritmos distribuídos. No consenso, cada um dos processos propõe um valor e, eventualmente, um desses é escolhido por todos. Existem três propriedades que devem-se de -satisfazer: - - \todo{é bom o termo correto?} -\todo{é ruim o termo correto?} +satisfazer\todo[noline]{a definição é muito informal?}: \begin{description} \item[Validade uniforme] Se um dos processos escolhe o valor $v$, @@ -276,49 +280,105 @@ dos processos \textit{ruins}: i.e. \textit{decidem}, valores distintos. \end{description} -O resultado de impossibilidade obtido por Fisher, Lynch e Patterson +% estabelecer que o problema e resolvível no caso síncrono, e depois +% apresentar o resultado de impossibilidade +O resultado de impossibilidade obtido por Fischer, Lynch e Patterson \cite{fischer85} mostra que o problema não pode-se resolver de maneira determinista em um sistema distribuído assíncrono com apenas um processo falhado. +% ainda não tem boa conexão os paragrafos, carece de coerência + +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 os membros todos \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. Quando um processo \(p\) 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\)) \todo{tem se que incluir esta aclaração, não?}. 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 quaisquer mensagem \(m\), e em quaisquer execução, a chamada +\textit{TO-broadcasts}\((m)\) e feita uma vez só. Neste contexto, o +broadcast de ordem total é definido pelas seguintes propriedades +\cite{Chandra:1996:WFD:234533.234549,hadzilacos94}: + +% Já foi definido o termo "processo correto"? +\begin{itemize} +\item \textit{Validade} Se um processo correto \textit{TO-broadcasts} + a mensagen \(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 corretos eventualmente + \textit{TO-deliver} \(m\). +\item \textit{Integridade uniforme} Para quaisquer 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} -O \textit{broadcast} confiável é uma primitiva de comunicação -assíncrona de alto nível que garanta as seguentes três propriedades -\cite{Chandra:1996:UFD:226643.226647}: +Se a primitiva de comunicação não satisfaz todas ordem total uniforme, +portanto não garanta ordem nenhum, e chamada broadcast confiável. No +caso que a primitiva cumpra todas as propriedades prévias, é chamada +uniforme, i.e. impõe restrições ao comportamento de todos os +processos, corretos é com falhas; mas se as propriedades de acordo e +integridade são não uniformes, só se aplica aos processos corretos +\todo{e preciso incluir as definições das propriedades 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 mensagens enviadas pelo +broadcast de ordem total e o conjunto de processos do sistema, gera a +seguinte classificação: +\begin{inparaenum}[\itshape a\upshape)] +\item Se o conjunto destino é igual ao total dos processos no sistema, + i.e \(\forall m \in \mathcal{M} (Dest(m) = \Pi)\), a primitiva e + chamada de broadcast; +\item Se o conjunto destino e um subconjunto dos processos, onde + distintas mensagens têm distintos conjuntos destinos e o remetente + pode não ser incluso no destino, 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 e chamada de multicast. +\end{inparaenum} +Além da distinção anterior, a presença do remetente no conjunto +destino, gera uma classificação adicional: \begin{inparaenum}[\itshape a\upshape)] -\item todos os processos corretos entregam o mesmo conjunto de - mensagens, -\item todas as mensagens enviadas por um processo correto são - entregues, -\item mensagens falsas nunca são entregues. +\item Se o remitente é membro dos destinatários, i.e. \(\forall m \in + \mathcal{M} (sender(m) \in Dest(m))\), o grupo é chamado + \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 chamado \textit{aberto}. \end{inparaenum} -Além disso, no caso possa-se garantir que os mensagens são entregues -no mesmo ordem por todos os processos, a primitiva chama-se -\textit{broadcast} com ordenação total ou \textit{broadcast} atômico -\cite{Defago:2004}. Foi mostrado por Chandra e Toueg -\cite{Chandra:1996:UFD:226643.226647} que o problema do consenso -uniforme e o \textit{broadcast} atômico em sistemas assíncronos com -falhas de parada são equivalentes, i.e. quaisquer algoritmo que possa -resolver um deles também pode-se adaptar para resolver o -outro. Portanto, o \textit{broadcast} atômico é sujeito ao mesmo -resultado de impossibilidade de Fischer, Lynch e Patterson. - -% O problema foi descrito por Aguilera, Chen e Toueg -% \cite{springerlink:aguilera98} e pode-se descrever, informalmente, -% assim: os detetores de falhas tradicionais não são adecuados para o -% modelo de falhas no qual os processos podem-se recuperar já que -% eles, pela sua definição, devem de \textit{suspeitar}, i.e. supoer -% que o processo caiu, permanentemente dos processos com falhas, ainda -% se eles voltam ao sistema, excluindo-lhes. + +% MARK + +% apagar a primeira parte deste paragrafo no caso se +Foi mostrado por Chandra e Toueg \cite{Chandra:1996:UFD:226643.226647} +que o problema do consenso uniforme e o \textit{broadcast} atômico em +sistemas assíncronos com falhas de parada são equivalentes, +i.e. quaisquer algoritmo que possa resolver um deles também pode-se +adaptar para resolver o outro. Portanto, o \textit{broadcast} atômico +é sujeito ao mesmo resultado de impossibilidade de Fischer, Lynch e +Patterson. + \subsection{Detetores de falhas } \label{sec:detetores} - Existem distintas soluções para evitar o resultado de impossibilidade: o uso de randomização \cite{Chor89}, definição de problemas mais deveis e suas soluções \cite{dolev87}, entre outros. Nós vamos a centrar em detetores de falhas não confiáveis -\cite{chandra96c,Chandra:1996:UFD:226643.226647}. Informalmente, os -detetores de falhas são um conjunto de módulos distribuídos, um por +\cite{Chandra:1996:WFD:234533.234549,Chandra:1996:UFD:226643.226647}. Informalmente, +os detetores de falhas são um conjunto de módulos distribuídos, um por processo do sistema, que possuem uma visão do sistema, i.e. uma listagem dos processos que são suspeitos de ter falhado, mas não precisasse garantir que a visão seja correta, e.g. pode-se incluir na @@ -328,17 +388,22 @@ do consenso (\textit{broadcast} atômico) em sistemas com falhas de processo. Uma das deficiências da proposta de Chandra e Toueg -\cite{chandra96c,Chandra:1996:UFD:226643.226647}, é que consideram as -falhas como permanentes, i.e. os processos não podem-se recuperar. É -claro que na prática os processos podem falhar e se recuperar -múltiplas vezes, Aguilera et al. \cite{springerlink:aguilera98} propõe -um novo tipo de detetores de falhas que não retornam uma lista de -processos suspeitos de ter falhado mas uma lista dos processos que -podem estar funcionando corretamente mais uma estimativa do número de -vezes que ele falho até o momento. +\cite{Chandra:1996:WFD:234533.234549,Chandra:1996:UFD:226643.226647}, +é que consideram as falhas como permanentes, i.e. os processos não +podem-se recuperar. É claro que na prática os processos podem falhar e +se recuperar múltiplas vezes, Aguilera et +al. \cite{springerlink:aguilera98} propõe um novo tipo de detetores de +falhas que não retornam uma lista de processos suspeitos de ter +falhado mas uma lista dos processos que podem estar funcionando +corretamente mais uma estimativa do número de vezes que ele falho até +o momento. \section{Treplica} \label{sec:treplica} +E melhor utilizar os relatório técnico +\cite{vieira08a-tr,vieira10:implementing-tr} ou o artigo +\cite{vieira08:_trepl}\todo{Vou incluir aspectos gerais do treplica, + ou algum em particular?} \section{Proposta de pesquisa} \label{sec:proposta} @@ -346,14 +411,16 @@ vezes que ele falho até o momento. \section{Metodologia Científica} \label{sec:metodologia} -\todo[noline]{Fill}Esta seção traz a metodolodia de pesquisa: teoria, experimentos, etc. +\todo{experimentos? qual é a diferença com a proposta de + pesquisa} \subsection{Tarefas e cronograma} \label{sec:planodetrabalho} Esta seção detalha as tarefas planejadas para o desenvolvimento do Mestrado e o conograma proposto (Tabela~\ref{projtimetable}): -\todo[noline]{check times and items} +\todo[noline]{o conteudo é correcto e completo? o calendário de + atividades?} \begin{enumerate} \addtolength{\itemsep}{-0.35\baselineskip} -- 2.11.4.GIT