ALCOMFT-TR-01-76

Panagiota Fatourou and Maurice Herlihy
Brief Announcement: Adding Networks
MPI. Work package 2. May 2001.

Abstract: An adding network is a distributed data structure that supports a concurrent, lock-free, low-contention implementation of a fetch&add counter. We give a lower bound showing that adding networks have inherently high latency. We prove that our lower bound is tight.

Postscript file: ALCOMFT-TR-01-76.ps.gz (48 kb).