Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systems

• First Byzantine-rrsilient read/write memory.
• Introduction of new concurrency objects.
• An impossibility result.

This paper is on the construction and use of a shared memory abstraction on top of an asynchronous message-passing system in which up to tt processes may commit Byzantine failures. This abstraction consists of arrays of nn single-writer/multi-reader atomic registers, where nn is the number of processes. These registers enable Byzantine tolerance by recording the whole history of values written to each one of them. A distributed algorithm building such a shared memory abstraction is first presented. This algorithm assumes t