Attiya - Ba.r-Noy - Dolev algorithm

  • Write(v)
  • Read()
  • Async model
  • Faults: Crash/Restart
  • 3 реплики
  • реплики не меняются
  • Клиент общается с машинами напрямую
  • single producer multi consumers

02-lec-atomic-register.png

quorum

Проблемы

  • предложенная реализация не линеаризуема:

02-lec-quorum-non-linearizable.png

Доказательство корректности

02-lec-quorum-proof.png

Эффективность алгоритма

  1. Round Trip
  2. Disk

Улучшение на большое количество writer’ов

02-lec-many-writers.png

На подумать

  • cas?

truetime optimization

abd-algorithm-true-time.png

  • wait $\longrightarrow$ quorum
  • better: wait + quorum