Block placement strategies for fault-resilient distributed tuple spaces: an experimental study

The tuple space abstraction provides an easy-to-use programming paradigm for distributed applications. Intuitively, it behaves like a distributed shared memory, where applications write and read entries (tuples). When deployed over
a wide area network, the tuple space needs to efficiently cope with faults of link and nodes. Erasure coding techniques are increasingly popular to deal with such catastrophic events, in particular due to their storage efficiency with respect to
replication. When a client writes a tuple into the system, this is first striped into blocks and encoded into n > k blocks, in a fault-redundant manner. Then, any out of the n blocks are sufficient to reconstruct and read the tuple. This paper
presents several strategies to place those blocks across the set of nodes across a wide area network that together form the tuple space.We present the performance trade-offs of different placement strategies, based on simulations as well as on Python implementation of a distributed tuple space. Our results reveal important differences in the efficiency of the different strategies, for example in terms of block fetching latency, and that having some knowledge of the underlying network graph topology is highly beneficial.