What are some approaches to optimize a directed graph (v,e), where the vertices are nodes participating in the transmission of a message to a subset of the vertices using the gossip protocol, and where each outgoing edge represents the transmission of any incoming message to the edge's destination vertex. Each edge has a weight, which is the latency for sending a message from the src vertex to the destination vertex. I am looking at a choice in optimization, optimizing for the minimum amount of message exchanges, or optimizing for the minimum time it takes for a message to flow to all destination vertices (as approximated by summing the latencies of the edges traversed).

I suspect this is a well-researched problem, and will need further constraints to make it practical for implementation, but I'm hoping the community here can give me a good jump start on my research to implement this for the software application I am writing.

  • $\begingroup$ You may solve the time problem with the Floyd Warshall algorithm. $\endgroup$ – LinAlg Jan 3 '17 at 20:47
  • $\begingroup$ Hey @Bill Barnhill, I have a few questions. Is there a single source vertex and a single destination vertex or are there multiple sources / destinations? If there are multiple sources / destinations, do you care how much of the message each source vertex sends or how much each destination vertex receives? Knowing this would help to write a better answer for you. $\endgroup$ – Chris Harshaw Jan 4 '17 at 1:11
  • $\begingroup$ Note that setting all of the latencies (edge weights) equal to some positive constant would solve the problem of minimum amount of message exchanges. $\endgroup$ – Chris Harshaw Jan 4 '17 at 1:14
  • $\begingroup$ Also, do you have constraints on the edges? For instance, is there a limit to how much of a message can pass through an edge? $\endgroup$ – Chris Harshaw Jan 4 '17 at 1:18
  • $\begingroup$ Regarding constraints on the edges @Chris Harshaw - right now I am only exploring situations where the message is transferred in an all or nothing approach, so no partial message transfers. Also the latencies are determined by real world measurements, so cannot be set equal outside of a test environment. $\endgroup$ – Bill Barnhill Jan 4 '17 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.