Slightly smaller splitter networks

Abstract

The classic renaming protocol of Moir and Anderson (1995) uses a network of Theta(n^2) splitters to assign unique names to n processes with unbounded initial names. We show how to reduce this bound to Theta(n^{3/2}) splitters.