Forum > General
Process to elect a node in a connected graph to perform a task
Gustavo 'Gus' Carreno:
Hey Y'all,
I would like to present you with a puzzle, that may or may not be new. I'm guessing it's not, because not a lot is new under the Sun these days :)
Imagine that you have a graph of nodes each connected to at least 5 others.
Every 5 or 10m the whole entirety of the nodes must elect, randomly, a single node in order for this node to perform a task that is then propagated through the graph(or network).
For the time being, lets ignore repetition from election to election, I'll tackle that once I understand/come up with the election mechanism.
So, how would you go about it?!
If by any chance I'm asking about something that has already been solved and I'm unaware of the solution, please would you be so kind as to provide a link to it or at least a good term that I can feed Google, or even maybe ChatGPT :D
Cheers,
Gus
af0815:
Do you mean Dijkstra's algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode or http://www.delphiforfun.org/Programs/graph_traverse.htm ?
MathMan:
--- Quote from: af0815 on March 15, 2023, 02:05:26 pm ---Do you mean Dijkstra's algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode or http://www.delphiforfun.org/Programs/graph_traverse.htm ?
--- End quote ---
Well af0815 beat me by some seconds. I was just to reply in the same direction.
The issue surely is not the random selection of a node, i guess. So it must be in the distribution of the process from that node across the graph - Gus wasn't totally clear about it.
I would first look for a package on graph algorithms - I think there are some implementations. Then excercise Dijkstra's algorithm with the randomly selected selected node as origin and finally execute the process on all nodes in order of distance handed back by the spanning tree generation.
avk:
Gus' conditions do not restrict the choice of vertex in any way.
Just choose random.
Curt Carpenter:
Not sure what "elect, randomly" means.
Do you mean that each node selects some random number, and that the ensemble of all the numbers somehow "elects" one node?
Navigation
[0] Message Index
[#] Next page