CI365
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 Stroparo
Aurélien Coget
Bacharelado em Ciência
da Computação
27/10/2008
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).
Complexidade
Algorí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 NP
 Espaço: LINSPACE e PSPACE (LIN contido em P).
Complexidade
Algorí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 NPhard.
 B4: mais de 10^19 operadores.
 B8: mais operadores que partículas elementares no
universo.
Complexidade
Algorí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].
Complexidade
Algorí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) ?
Complexidade
Algorí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]]
Complexidade
de 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ões
 Indicaçã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ões
 Problemas 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