Publications Details

A lower bound for routing on a completely connected optical communication parallel computer

Goldberg, L.A.

The task of routing a 2-relation on an n-processor completely connected optical communication parallel computer (OCPC) is considered. A lower bound is presented that applies to any randomized distributed algorithm for this task: specifically, it is shown that the expected number of steps required to route a 2-relation is {Omega}({radical} log log n) in the worst case. For comparison, the best upper bound known is O(log log n).