Slightly smaller splitter networks

James Aspnes. Slightly smaller splitter networks. Available as YALEU/DCS/TR-1438, November 2010, and as arXiv:1011.3170.

Abstract

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

• Technical report: PDF.
• ArXiv version: arXiv:1011.3170.

BibTeX

@techreport{Aspnes2010splitters,
author = {James Aspnes},
title = {Slightly smaller splitter networks},
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1438",
month=nov,
year = 2010
}