Optimality of wait-free atomic multiwriter variables

Known implementations of concurrent wait-free atomic shared mul-tiwriter variables use Θ(n) control bits per subvariable. It has been shown that implementations of sequential time-stamp systems require Ω(n) con-trol bits per subvariable. We exhibit a sequential wait-free atomic shared multiwriter variable construction using log n control bits per subvariable. There arises the question of the optimality of concurrent implementations of the same, and of weak time-stamp systems. We also show that our solu-tions are self-stabilizing