2012/01/19 by Vance Faber, Faber, Vance
Computer Science · Mathematics · #05E15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #Parallel #and Cluster Computing (cs.DC) #cs.DC #math.CO #msc:05E15
paper · pdf · doi:10.48550/arxiv.1201.4153
5 pages
arxiv created 2012/01/19 · openalex publication_date 2012/01/19 · arxiv updated 2012/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We are interested in the following problem we call global sum. Each processor starts with a single real value. At each time step, every directed edge in the graph can simultaneously be used to transmit a single (bounded) number between the processors (vertices). How many time steps s are required to ensure that every processor acquires the global sum? We know that s is bounded below by the diameter and above by two times the diameter. We conjecture that for vertex symmetric graphs, s is equal to the diameter. We show this is true if the diameter is 2.