Trabalho de Graduação --- Algortimos Distribuídos Probabilísticos

• Aluno: Felipe Velloso Alves
• Monografia: .pdf.gz - versão não corrigida
• Conteúdo: Probabilidade; Algoritmos distribuídos; Soluções probabilísticas para problemas distribuídos clássicos: jantar dos filósofos, roteamento no hipercubo, eleição de líder e generais bizantinos
• Objetivos: Entender como a aleatorização de algoritmos ajuda na solução de problemas distribuídos, escrever um texto auto-contido sobre os problemas clássicos em Algoritmos Distribuídos.
• Carga horária: 120+120 >Créditos: 8+8
• Prof Responsável: Jair
• Bibliografia:
  1. Angluin, D. (1980). Local and global properties in networks of processors (extended abstract). In STOC, pages 82­93. ACM.
  2. Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In PODC, pages 27­30.
  3. Borodin, A. e Hopcroft, J. E. (1985). Routing, merging, and sorting on parallel models of computation. J. Comput. Syst. Sci., 30(1):130­145.
  4. Bracha, G. (1985). An O(lg n) expected rounds randomized byzantine generals protocol. In STOC, pages 316­326. ACM.
  5. Chang, E. J. H. e Roberts, R. (1979). An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM, 22(5):281­283.
  6. Chor, B. e Coan, B. A. (1985). A simple and efficient randomized byzantine agreement algorithm. IEEE Trans. Software Eng., 11(6):531­539.
  7. Dijkstra, E. W. (1971). Hierarchical ordering of sequential processes. Acta Inf., 1:115­138.
  8. Fischer, M. J. e Lynch, N. A. (1982). A lower bound for the time to assure interactive consistency. Inf. Process. Lett., 14(4):183­186.
  9. Fischer, M. J., Lynch, N. A., e Paterson, M. (1985). Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374­382.
  10. Gupta, R., Smolka, S. A., e Bhaskar, S. (1994). On randomization in sequential and distributed algorithms. ACM Comput. Surv., 26(1):7­86.
  11. Hadzilacos, V. (1986). Ben-or's randomized protocol for consensus in asynchronous systems. Course notes: Computer Science.
  12. Itai, A. e Rodeh, M. (1990). Symmetry breaking in distributed networks. Inf. Comput., 88(1):60­87.
  13. Lamport, L. e Lynch, N. A. (1990). Distributed computing: Models and methods. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pages 1157­ 1199.
  14. Lamport, L., Shostak, R. E., e Pease, M. C. (1982). The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382­401.
  15. Lehmann, D. J. e Rabin, M. O. (1981). On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In POPL, pages 133­138.
  16. Pease, M. C., Shostak, R. E., e Lamport, L. (1980). Reaching agreement in the presence of faults. J. ACM, 27(2):228­234.
  17. Perry, K. J. (1985). Randomized byzantine agreement. IEEE Trans. Software Eng., 11(6):539­ 546.
  18. Peterson, G. L. (1982). An O(n log n) unidirectional algorithm for the circular extrema problem. ACM Trans. Program. Lang. Syst., 4(4):758­762.
  19. Rabin, M. O. (1983). Randomized byzantine generals. In FOCS, pages 403­409. IEEE.
  20. Valiant, L. G. e Brebner, G. J. (1981). Universal schemes for parallel communication. In STOC, pages 263­277. ACM.