One-write algorithms for multivalued regular and atomic registers

摘要

This paper presents an algorithm for implementing a k-valued regular register(the logical register )using k (k-1)/2 binary regular registers (the physical registers) that requires only one physical write per logical write. The same algorithm using binary atomic registers implements a k- valued atomic register. The algorithm is simple to describe and depends on properties of paths in a related graph.