Geração Quase-Instantânea de Orientações Acíclicas em Sistemas Distribuídos Anônimos

• Gladstone Moises Arantes Junior UFRJ
• Felipe Maia Galvão França UFRJ

DOI: https://doi.org/10.5753/wscad.2001.19123

Resumo

Este artigo discute um conjunto de algoritmos distribuídos não-determinísticos para a geração de orientações acíclicas em um sistema distribuído anônimo de topologia arbitrária. Embora possam ser concebidas outras aplicações práticas para essa forma de quebra de simetria, estaremos focando o problema da inicialização de um sistema para a operação do Escalonamento por Reversão de Arestas (ERA), um simples e poderoso algoritmo de escalonamento distribuído. O ERA requer uma orientação acíclica inicial no grafo que representa o compartilhamento de recursos do sistema alvo para executar corretamente e tal condição inicial determina a "quantidade de concorrência" associada à dinâmica do escalonamento. Os algoritmos são analisados tanto em termos de tempo de convergência quanto em termos de quantidade de concorrência produzida. Em particular, é proposto um novo algoritmo chamado Alg-Arestas que, em certas condições, é capaz de produzir orientações acíclicas quase instantaneamente, isto é, em menos de dois (2) passos.

Palavras-chave: sistemas anônimos, escalonamento distribuído, algoritmos distribuídos randômicos, quebra de simetria

Referências

BARBOSA, V. C. "Concurrency in Heavily Loaded Neighborhood-Constrained Systems", ACM Transactions on Programming Languages and Systems, Vol. 11, n. 4, pp. 562-584, Outubro 1989.

BARVOSA, V. C. An Introduction to Distributed Algorithms, MIT Press 1996.

CALABRESE, A., FRANÇA, F.M.G. "Randomized Distributed Primer for the Updating Control of Anonymous ANNs", Proceedings of ICANNR94, Sorrento, ltaly, 1994.

CALABRESE. A. "Distributed Acyclic Orientation of Asynchronous Networks", 11th International Symposium of Fundamentals of Computation Theory, pp.129-137, Kraków, Poland, Setembro 1997.

FRANÇA, F.M.G. "A Self-Organizing Updating Network", Artificial Neural Network, eds. T. Kohonen, K, Mckisara, O. Simula, and J. Kangas. Elsevier Science Publisher B. V. (North-Holland), pp. 1349-1352, 1991.

FARIA, L., FRANÇA, F. M. G. Comunicação Pessoal

GOLDBERG, A. V., PLOTKIN, S. A. "Parallel (Δ+l)-Coloring of Constant-Dregree Graphs", lnformation Processing Letters, n. 25, pp. 241-245. 1987.

GOLDBERG, A. V., PLOTKIN, S. A. "Parallel Symmetry-Breaking in Sparse Graphs", SIAM Journal of Discrete Mathematics, Vol. 1, n.4, pp. 434-445, Novembro 1988.

ITAI, A., RODEH, M. "Symmetry-Breaking in Distributed Networks", lnformation and Control, n. 88, pp. 60-87, 1990.

LUBY, M., "A Simple Parallel Algorithm for the Maximal Independent Set Problem", SIAM Journal of Computing. Vol. 15, n. 4, pp. 1036-1053, Novembro 1986.

PANCONESI, A., SRINIVASAN, A., "lmproved Distributed Algorithms for Coloring and Network Decomposition Problems", 24th ACM Symposium on Theory of Computation, pp. 581-591, Victoria B. C., Canada, Maio 1992.

SZEGEDY, M., YISHWANATHAN, S. "Locality Based Graph Coloring", 25th ACM Symposium on Theory of Computation. pp. 201-207, California, USA, Maio 1993.