UFMG - Pós-graduação em Ciência da Computação - Programação Paralela

A seguir: O Problema dos Filósofos Acima: The Drinking Philosophers Problem[#!Drinking!#] Anterior: Grafos de Conflitos e

Grafo de Precedências

• H só pode ser modificado por mudanças nas direções das arestas
• Proposta: implementação distribuída de H que garanta que

  1.

  H permanece acíclico

  2.

  H muda de maneira a garantir que todo processo em conflito chegue à profundidade 0 num tempo finito

  3.

  toda mudança em H possa ser feita localmente

• Regra da Aciclicidade: todas as arestas incidentes em um nó podem ser dirigidas a êle numa ação atômica
• Regra da Equidade: Todo processo vencedor de um conflito deve dar precedência a todos os seus vizinhos num tempo finito após a vitória
• Problema: implementação distribuída de H: decisões devem ser tomadas com base em dados locais