Stochastic automata network
# Stochastic automata network

Sistemas computacionais complexos tendem a ter o desempenho como fator primordial de avaliação, pois qualquer componente pode falhar. Uma das maneiras de se verificar o desempenho é através da utilização de métodos analíticos matemáticos. O formalismo SAN - Stochastic Automata Network - é uma rede de autômatos estocástico com finalidade de avaliar o desempenho de sistemas (sistemas distribuídos, redes de computadores e outros).
O formalismo SAN foi proposto por Plateau e o objetivo básico é representar um sistema por meio de uma coleção de sub-sistemas com um comportamento independente (transições locais) e interdependências ocasionais (taxas funcionais e eventos sincronizantes) sob os pressupostos das Cadeias de Markov [Ste94].
Este formalismo é uma forma compacta de descrever realidades complexas, otimizando ainda a busca de soluções estacionárias, utilizando-se das noções de estado e de transições entre estados para representação dos eventos, assim como as Cadeias de Markov. Os eventos em SAN podem estar associados a um único autômato, ou a vários ao mesmo tempo, ocorrendo de acordo com taxas específicas. Dá-se o nome de estado local ao estado individual de cada autômato e estado global como sendo a combinação de todos os estados locais de cada autômato componente da SAN.
Dessa forma, o formalismo de redes de autômatos estocásticos é particularmente interessante para a modelagem de sistemas distribuídos, nos quais as unidades de processamento não interagem entre si a todo instante. Um autôomato é um modelo matemático de um sistema com entradas e saídas discretas. O princípio do formalismo SAN é descrever um sistema complexo dividindo-o em sub-sistemas quase independentes, pois estes interagirão ocasionalmente. Neste sistema, cada sub-sistema é modelado por um autômato.
A Stochastic Automata Network (SAN) é um formalismo para a descrição e a avaliação de processos estocásticos baseados em métodos analíticos e matemáticos. O princípio básico da modelagem de SAN é a construção de sistemas como um conjunto de interação de subsistemas. Cada subsistema é modelado por um autômato e a interação entre autômatos é modelado por regras de transições relacionando os estados internos dos autômatos.
Uma característica a ser observada em um modelo SAN é o comportamento dos autômatos. A avaliação do desempenho e a análise do comportamento de uma SAN se dá pela verificação dos estados, que ao serem atingidos, representam procedimentos realizados pelo sistema modelado. Estados sucessores e predecessores indicam, no espaço de estados de uma SAN, a trajetória e evolução dos padrões comportamentais do sistema modelado. Por ser baseado em cadeias de Markov, no formalismo SAN a representação dos estados pode se tornar inviável devido a grande explosão de espaços de estados, o que consistirá em elevado consumo de memória para representar os diferentes estados aplicáveis a realidade de um modelo.

## References

* ↑ BENOIT, A., BRENNER, L., FERNANDES, P., PLATEAU, B. Aggregation of Stochastic Automata Networks with Replicas
* 1 2 FERNANDES P., PLATEAU B., STEWART W. J. Optimizing tensor product computations in stochastic automata networks. RAIRO - Operations Research, Vol. 32(3), p. 325-321, 1998. Gauthiers-Villars, France. July, 1998
* ↑ B. Plateau. On the stochastic structure of parallelism and synchronization models for distributed algorithms. ACM SIGMETRICS - Conference on Measurements and Modeling of Computer Systems, pages 147–154, 1985.
* ↑ P. Fernandes. Méthodes Numériques pour la Solution de Systèmes Markoviens à Grand Espace d'États. PhD thesis, Institut National Polytechnique de Grenoble, Grenoble, 1998.
* ↑ J.E. Hopcroft and J.D. Ullman. Introduction to automata theory, languages and computation. Addison-Wesley, 1979.
* ↑ WEBBER T., FERNANDES P. Multiplicação Vetor-Descritor no Formalismo de Redes de Autômatos Estocásticos
* ↑ Plateau, B. On the stochastic structure of parallelism and synchronization models for distributed algorithms. ACM SIGMETRICS - Conference on Measurements and Modeling of Computer Systems, pages 147–154.