Utilidade do número de consenso

Question

Que informação e utilidade traz conhecer o número de consenso de um objeto compartilhado me dá?

Answer 1

Você provavelmente não poderá fazer nada melhor do que citar o resumo de Artigo original de Herlihy:

Uma implementação sem espera de um objeto de dados simultâneo é aquela que garante que qualquer processo pode concluir qualquer operação em um número finito de etapas, independentemente das velocidades de execução dos outros processos.O problema de construir uma implementação sem espera de um objeto de dados a partir de outro está no centro de muitos trabalhos recentes em algoritmos concorrentes, estruturas de dados concorrentes e arquiteturas de multiprocessadores.Primeiro, introduzimos uma técnica simples e geral, com base na redução de um protocolo de consenso, para provar declarações do formulário: "Não há implementação sem espera de X por Y." Derivamos uma hierarquia de objetos, de modo que nenhum objeto em um nível tenha uma implementação livre de espera em termos de objetos em níveis mais baixos.Em particular, mostramos que os registros atômicos de leitura/gravação, que têm sido foco de muita atenção recente, estão na parte inferior da hierarquia:eles não podem ser usados ​​para construir implementações sem espera de muitos tipos de dados simples e familiares.Além disso, as primitivas de sincronização clássicas, como test&set e fetch&add, embora mais poderosas que a leitura e a gravação, também são computacionalmente fracas, assim como as primitivas padrão de passagem de mensagens.Em segundo lugar, contudo, mostramos que existem objetos universais simples a partir dos quais se pode construir uma implementação sem espera de qualquer objeto sequencial.