2013/05/28 by Vance Faber, Faber, Vance
Computer Science · Mathematics · #68M10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO #msc:68M10
paper · pdf · doi:10.48550/arxiv.1305.6349
25 pages
arxiv created 2013/09/12 · arxiv updated 2013/09/13
We discuss several combinatorial problems that arise when one looks at computational algorithms for highly symmetric networks of processors. More specifically, we are interested in minimal times associated with four communication tasks (defined more precisely below): universal broadcast, every processor has a vector that it wishes to broadcast to all the others; universal accumulation, every processor wishes to receive the sum of all the vectors being sent to it by all the other processors; universal exchange, every processor wishes to exchange a vector with each other processor; and global summation, every processor wants the sum of the vectors in all the processors