Horizontal partitioning can handle a transaction by accessing a single node only if the transaction is restricted along the single partitioned dimension. Composite partitioning allows for partitioning along more than one dimension, but can only handle a transaction by accessing a single node if the transaction is limited along all partitioned dimensions. A partitioning method partitions a tuple space along more than one dimension and, by storing tuples redundantly, allows transactions restricted along one or more of the partitioned dimensions to be handled by accessing a single node. Other embodiments include a computer program product and a system for partitioning a tuple space.