© 2000 by British Computer Society
Wait-Free Handshaking Using Rainbow Colouring
1 Computing Sciences Department, Chalmers University of Technology and Göteborg University, S-412 96 Göteborg, Sweden, Sweden Email: ptrianta@cs.chalmers.se
The construction of shared data objects is a fundamental issue in asynchronous concurrent systems, since these objects provide the means for communication and synchronization between processes. Constructions which guarantee that concurrent access to the shared object by processes is free from waiting are of particular interest, since they help to increase the amount of parallelism and to provide fault-tolerance. The problem of constructing a $k$-valued wait-free shared register out of binary subregisters of the same type, where each write access consists of one subwrite (constructions with one-write) is important, since it lies at the heart of studying lower bounds of the complexities of register constructions and trade-offs between them. The first such construction was for the safe register case; it uses $k$ binary safe registers and exploits the properties of a rainbow colouring function of a hypercube graph. The best known construction for the regular (atomic) case uses ${k \choose 2}$ binary regular (resp. atomic) registers, while if the one-write requirement is lifted, there exists a construction that uses $4 (\log k+1)$ binary registers. Here we show how rainbow colouring can be extended to simulate handshaking between the reader and the writer of the register, thus offering a wait-free solution for the atomic case with one reader, using only $3k-2$ binary registers. The best known lower bound for such a construction is $k-1$.
Received 19 March, 1998. Revised 30 December, 1999.