Brief Announcement: A Step Optimal Implementation of Large Single-Writer Registers

摘要

A register is a fundamental object that supports READ and WRITE operations. Implementing large l-bit registers from small k-bit registers in a wait-free manner is a classic problem in distributed computing. We consider this problem for single-writer atomic registers shared by n readers. This problem arises naturally in practice when l-bits need to be written atomically on a system that provides only k-bit registers.