Okeanos: Reconfigurable fault-tolerant transactional storage supporting object deletions

Over the past years, many peer-to-peer (P2P) distributed hash-tables (DHTs) have been proposed. Given their excellent scalability properties they are nowadays core technologies used in the industry, e.g. by Amazon and Facebook. However, most DHTs still exhibit major drawbacks limiting their applicability: They hardly give consistency guarantees and do not support transactional semantics, which precludes applications that rely on strong consistency (e.g. banking, trading, accounting). Second, a key functionality yet missing is the ability to consistently delete data objects physically from master-less data partitions. All existing DHTs either use soft-state objects that expire after a certain amount of time or simulate deletions by marking objects as deleted but keep them allocated. In this paper, we present Okeanos, the first fault-tolerant transactional master-less key/value store supporting true physical deletions. Okeanos itself is no DHT, but can be used as a building block to implement consistent partitions of larger distributed storage systems. Further, the nodes that host an Okeanos store can be exchanged at runtime (reconfiguration) without significant times of unavailability. We intend to use Okeanos to build a reliable large-scale P2P storage system.