Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems

Paper: Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems. Achour Mosteafoui, Matoula Petrolia, Michel Raynal, and Claude Jard. 2015

We can implement an (1,N)-Atomic Register using Bracha Broadcast.

Protocol

Local Variables:
- \(reg[1..C]\) is the local representation of the array \(REG[1..C]\)
- Each register contains two fields:
  - \(sn\): A sequence number
  - \(val\): The value
- Each register is initialized to the pair \(\)
- \(wsn\) is an integer initialized to \(0\).
- \(rsn[1..C]\) is an array of sequence numbers initialized to \(0\).
Events:
- RBC instance: \(rbc\)
  - \(\)
  - \(\)
- Atomic Register \(i\):
  - \(\)
  - \(\)
  - \(\)
  - \(\)
- Internal Events:
Server Code for \(p_{i}\):
- Upon \(
  \) where \(M :=
  \) from \(c\):
  - wait \(wsn = reg_{i}[c].sn+1\)
  - \(reg_{i}[c].sn \leftarrow wsn\)
  - \(reg_{i}[c].val \leftarrow v\)
  - send \(\) to \(c\)
- Upon \(
  \) from \(c\):
  - send \(\)
- Upon \(
  \) from \(c\):
  - wait \((reg_{i}[c].sn \ge wsn)\)
  - send \(\) to \(c\)
Client Code for \(c\):
- Upon \(
  \):
  - \(wsn_{c} \leftarrow wsn_{c}+1\)
  - \(M\leftarrow \)
  - trigger \(\)
  - wait \(\) from \((n-t)\) different processes
  - trigger \(\)
- Upon \(
  \):
  - \(rsn_{c}[c'] \leftarrow rsn_{c}[c'] +1\)
  - multicast \(\)
  - wait \(reg_{c}[c'].sn \ge \max(wsn_{1},\ldots,wsn_{n-t})\) where \(wsn_{1}\), …, \(wsn_{n-t}\) are from messages \(\) received from \((n-t)\) different processes
  - let \((wsn, w)\) be the value of \(reg_{i}[c'].sn, reg_{i}[c'].val\) which allows the previous wait to terminate
  - multicast \(\)
  - wait \(\) from \((n-t)\) different processes
  - trigger \(\)

References

Achour Mosteafoui, Matoula Petrolia, Michel Raynal, and Claude Jard. 2015. “Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems.” http://arxiv.org/abs/1604.08161.