We address the problem of building a reliable distributed read/write storage from unreliable storage units, e.g. a collection of servers, of which up to one-third can fail by not responding or by undetectably corrupting the data stored on them. Our contribution consists in the development of Byzantine-resilient storage algorithms that for the first time combine strong consistency and liveness guarantees with space-efficiency. Previous solutions featuring equivalent properties resort to storing an unlimited number of data versions in the storage units, thus eventually running into problems of space exhaustion. © ACM 2008.