A linearizabilidade é equivalente ao problema de consenso?

9

Na introdução deste artigo Objetos Compartilhados Eventualmente Linearizáveis ​​(PODC'10) , os autores apresentaram a seguinte declaração sem referências:

A linearidade, no entanto, pode ser alcançada se e somente se o consenso puder ser resolvido.

Aqui, linearizabilidade é a propriedade de consistência mais forte conhecida de objetos compartilhados, proposta no artigo Linearizabilidade: uma condição de correção para objetos simultâneos .

Fico confuso com a afirmação acima devido aos seguintes argumentos:

No documento Compartilhando Memória Robusta em Sistemas de Passagem de Mensagens (JACM95) , sabemos que a linearizabilidade pode ser alcançada no sistema de passagem de mensagens assíncrona, enquanto toleramos uma minoria de falhas no processo:

Qualquer algoritmo sem espera baseado em registros atômicos de múltiplos leitores com um único gravador pode ser emulado automaticamente em sistemas de passagem de mensagens, desde que pelo menos a maioria dos processadores não esteja com defeito e permaneça conectada.

Por outro lado, o artigo Impossibilidade de consenso distribuído com um processo defeituoso (JACM85) provou o resultado impossível de consenso, mesmo com apenas uma falha no processo:

O problema de consenso envolve um sistema assíncrono de processos, alguns dos quais podem não ser confiáveis. O problema é que os processos confiáveis ​​concordem com um valor binário. Neste artigo, é mostrado que todo protocolo para esse problema tem a possibilidade de não-término, mesmo com apenas um processo defeituoso.

Portanto, podemos chegar à seguinte conclusão:

o consenso é mais forte que a linearizabilidade?

O que há de errado com meus argumentos? Existem algumas referências diretas para a conclusão da equivalência ?

reference-request dc.distributed-comp hengxin
fonte
11
De longe, não é um especialista em computação distribuída, mas parece-me que a razão pela qual você é capaz de obter seu resultado é por causa das suposições feitas nos resultados na referência JACM85. A linearidade pode ser equivalente ao consenso em um modelo de computação específico, mas isso pode não ser o caso se restringirmos bastante nosso modelo de computação.
chazisop

Respostas:

4

O que você entendeu errado é "sabemos que a linearizabilidade pode ser alcançada no sistema de passagem de mensagens assíncronas, enquanto toleramos uma minoria de falhas no processo". Não sabemos isso e, de fato, está errado.

O que a citação do artigo JACM95 mostra é que os registros de vários leitores com um único gravador podem ser implementados usando a passagem de mensagens. E apenas esse tipo de registrador ou qualquer outro objeto que possa ser implementado (dada uma minoria de falhas) desses registradores. Isso inclui, por exemplo, registros multi-gravadores e multi-gravadores (MWMR).

Por outro lado, a linearizabilidade não se limita a objetos que podem ser implementados usando registros de múltiplos leitores de gravador único. Um exemplo de tais objetos são aqueles que suportam operações de leitura-modificação-gravação (atômicas).

De fato, como Attiya e cols. Apontam (Seção 7), esses objetos não podem ser implementados precocemente pelos registros MWMR porque permitem resolver consensos (cf. sincronização sem espera por Herlihy) e, portanto, a implementabilidade contradiz o resultado do FLP.

Martin B.
fonte
Desculpe o atraso. No entanto, 1. Como a linearizabilidade é uma propriedade local , não acho que o número de objetos envolvidos seja o ponto. Poderia explicar melhor? 2. Qual é o seu significado de usar "isto é," de se relacionar atomicity of operations on a single objectcom sequential specifications are not violated?
Hengxin
Verdade. Deixe-me pensar novamente ....
Martin B.
Eu reescrevi completamente a resposta ... Acho que agora faz sentido. Não me lembro do que eu estava pensando antes.
Martin B.
Eu acho que seu argumento atual faz sentido. Após sua resposta, verifiquei o artigo Eventually Linearizable Shared Objects (PODC'10)e notei que objetos arbitrários (em vez de apenas registros SWMR) foram considerados.
Hengxin
Agradecemos sua atenção e esforços. Você está trabalhando na teoria da computação distribuída / simultaneidade? Então, você se importaria de avaliar meu outro problema: algoritmos de instantâneos atômicos em registros compartilhados estruturados em árvore ? Você acha que é um problema que vale a pena estudar?
Hengxin