View
218
Download
2
Category
Preview:
Citation preview
On The Complexity of Determining Autonomic Policy Constrained Behaviour
Sobre a Complexidade de Determinação de Política Autônoma de Comportamento
Restrito
Apresentado por:Cristian StroparoAurélien Coget
Bacharelado em Ciência da Computação 27/10/2008
CI365
Roteiro
1. Introdução e Motivação
2.Comportamento dos Computadores
3.Configuração
4.Complexidade Algorítmica
5.Complexidade de Operações
Introdução: Objeto de estudo. Metas.
Motivação: Por quê? Incentivar trabalhos futuros.
Meta da Computação Autônoma:Permitir operação sem intervenção humana.
Objeto de estudo: complexidade/custo computacional dos métodos autônomos.
Referência: Modelo de operações convergentes cfengine.
Muitas medidas podem ser feitas: Numero de linhas de código. Tempo projetando/planejando. Ciclos CPU (foco principal). Memória.
Motivação
Modelos existentes envolvem problemas NP-difíceis e PSPACE.
Soluções:Restringir domínio do problema (autonomia) para
alternativa com solução de custo polinomial.Heurística e aproximações.
Existem poucos trabalhos recentes que associam teoria de complexidade com gerenciamento autônomo.
Portanto, o presente trabalho visa servir como motivação a trabalhos futuros.
Comportamento dos Computadores
Configuração
Estado complexo, possivelmente distribuído.
Σ= {0,1} Mas há diversos níveis de codificação.
Mudança de estado – operadores:Criar...Apagar...Alterar... ... atributos de objetos gerenciados. Estes objetos podem
ser entidades de sistemas de arquivos, bases de dados relacionais etc.
Configuração
As mudanças de estado têm de ser previsíveis e confiáveis, conforme as políticas estabelecidas.
Para tal, incluir certas propriedades aos operadores de mudança de estado: Idempotência: Repetição não altera mais, após primeira
aplicação - f(f(x)) = f(x)Convergência a um ponto fixo: a primeira aplicação da
operação leva ao resultado especificado na política, independente do estado inicial.
Injetividade: inverso é único (permite rollback’s).
ComplexidadeAlgorítmica
Qual o custo para uma mudança simples?Linear quanto aos valores na entrada, a substituir.
E se levar em conta valores corretos e a determinação da implementação?A complexidade cresce de uma mudança simples para uma busca em um conjunto potencialmente enorme de operações possíveis.
Classes de complexidade:Tempo: P e NPEspaço: LINSPACE e PSPACE (LIN contido em P).
ComplexidadeAlgorítmica
“Sabemos como implementar o software gerenciador de configuração?” é a questão relevante e não o custo temporal.
Dificuldade administrativa: Determinar a configuração correta, satisfazendo as restrições de política de maneira eficiente.
Em geral, problemas de configuração alfabética já são NP-hard.
B4: mais de 10^19 operadores.
B8: mais operadores que partículas elementares no universo.
ComplexidadeAlgorítmica
Necessidade: linguagem que expressa operadores em Bn de forma conveniente.
Expressão de operador e = <α1, α2, ..., αn>, αi é expr. booleana. Nas expr.’s booleanas da sequência são permitidas apenas as variáveis x1, x2, ..., xn.
Notação: [[e]] é o operador sobre Bn, definido por e. [[e]](b), b em Bn, é um valor também em Bn.Suponha b em B4 tal que b = 0111, então:
b1 = 0, b2 = 1, b3 = 1, b4 = 1 (DEF bi) [[e]](b), valor em Bn, é definido pela expr. “e” e em cada
uma das exp. booleanas αi, xi=bi(DEF bi), i=[1..n].
ComplexidadeAlgorítmica
4 problemas principais nas operações de gerenciamento: IDM. Entrada: uma expr. de operador e.
Questão: [[e]] é idempotente? [[e]]( [[e]](x) ) = [[e]](x) ? INJ. Entrada: uma expr. de operador e.
Questão: [[e]] é injetora? [[e]](x)≠[[e]](y) se x≠y?CON. Entrada: uma expr. de operador e.
Questão: [[e]] é convergente? Existe k natural tal que [[e]]^(k) (x) = [[e]]^(k+1) (x) ?
CONx. Entrada: par <e,b>, e exp. de op., e b em Bn.Questão: [[e]] é convergente em b? Existe k natural tal que [[e]]^(k) (b) = [[e]]^(k+1) (b) ?
ComplexidadeAlgorítmica
Foco: CON. Uma exp. de operador “e” é convergente? [[e]](x) é meta de política para toda configuração inicial
x?SE sim ENTÃO problema foi solucionado com [[e]]SENÃO problema não solucionado com [[e]]
Complexidadede Operações
SAT intratável. IDM e INJ redutíveis (polinomial) a SAT.Então IDM e INJ são, no mínimo, também intratáveis.Heurísticas ou limitação de escopo são necessárias.
Problemas PSPACE-hard (espaço) geralmente muito mais difíceis que problemas NP-hard (tempo) e fora do alcance de algoritmos de tempo polinomial. CONx é PSPACE-hard. CON parece ser mais difícil que CONx, mas pode não ser. Não foi possível provar que CON é PSPACE-hard
nem que NÃO é PSPACE-complete (se pertence a NP). Problema em aberto – interessante para teóricos de
complexidade.
ConclusõesIndicação do que pode ser conseguido através destas
investigações apresentadas.
Ponto de partida para trabalhos inter-disciplinares futuros.
Quando usar heurísticas. Tais heurísticas são o caminho a ser tomado.
Computação autônoma: semelhança com autômatos e existência de operadores com propriedades especiais (IDM,INJ,CON) possibilitam a implementação automática das politicas
ConclusõesProblemas PSPACE e NP-Hard.
Isso quer dizer: sem esperanças?Resposta: Não! O cfengine* mostra que não. Ele mostra que se deve limitar o escopo ou as pretenções a algo com solução barata/viável.
Em contra-posição, não é aconselhável busca com força-bruta em uma wish-list genérica, por exemplo.
* - Um sistema de gerenciamento autônomo bastante utilizado
Recommended