[BUG] frequent desyncs when modifying roads

[Mariculous]

Yes, I had stated that as a notice at the last paragraph of section one.

Keep in mind, we will need to ensure that congestion data does not change within our calculation timeframes.
Using old congestion data should work well. We already maintain such "stats" for the current and the previous month.
Maintaining a third, more recent but not live congestion "stat" should not be an issue.

Using last-months data might be too outdated to actually react on congestion changes properly.
Running a preparation step before step 1 to initialise persistent congestion should be quite fast. We do this in karte_t::new_month, which is called each new month in step, besides many further things.


About your question from yesterday:
The server seems to be running quite stable in terms of desynchs. There had been a few crashes that could not be located yet.
Further, private car routes seem to be gone entirely. I'd expect them to get recalculated soon. Will file a bugreport if they don't seem to be recalculated within the next few ingame years.

[jamespetts]

Thank you for clarifying.

I am not sure that I understand the point that the routes "seem to be gone entirely" - can you elaborate? So far as I can see from my debug build, which lists all the routes going through a tile of road in the road's information window, the routes are all still present.

[jamespetts]

I have split the post replying to the question about private car routes being "gone entirely" into a different thread, as that is a separate issue.

Returning to the losses of synchronisation, I have been testing further. It seems that divergences can occur even if there are no changes to congestion or to the roads themselves between the first and second calculation. I have tested this by temporarily moving the place where the multiple threads for the private car routing start and stop to make sure that this is not concurrent with anything other than player vehicle movement and testing on a map (Ranran's saved game) with no player vehicles.

This seems to occur where two routes have the same cost, and it then appears to be indeterminate which of the two routes be chosen. I am wondering whether there is a way to deal with this and force Dijekstra's Algorithm to be deterministic about routes of the same cost.

[Mariculous]

That's strange, I'd need to look into how exactly the Dijkstra is implemented and what exactly we are calculating.

Generally, Dijkstra itself is deterministic. There is no randomisation anywhere in the algorithm itself.
For sure, one could implement the iteration of neighbors in a randomised way without breaking Dijkstra, but there is no reason in doing so.
The step of selecting the next node might also be implemented in a randomised way in case there are two different nodes with the same weight, but again there is no reason in doing so.

So either the weight, the processing order of neighbors or the processing order of two nodes with the same weight is kind of randomised.
The first would break Dijkstra in a way that it does not neccessarily return the shortest path, the latter two would only result in different routes if both have the same weight.

In any case, if there is any randomisation involved, I am really wondering why there are no desyncs if the calculation runs in a single thread.

[jamespetts]

I do not think that there is any actual randomisation: I believe that it is deterministic when the ultimate starting point of the route is the same, but not between any given mid point in the route and any given destination. There is code that takes into account the starting direction. Thus, if two routes to the same destination converge on a tile, and have arrived at that tile from different directions, they might take a different route out of that tile. Because the private car routing system recognises only one route from a tile to the destination, whichever is written last will be the route that private cars take, and so the order of writing must be the same between server and all clients.

I have started experimenting with this in my new testing branch (parallel-private-car-routing or somesuch: I am currently in my model railway shed and cannot recall the precise name). I have there disabled the code that obviously diverges depending on the starting direction (i.e. the code that adds cost penalties for turning) in the case of private car routing, but this seems not to be enough, so I suspect that there is also some other code that has this effect, but I have not found it.

Any assistance in finding this code so that it can be disabled for private car routing would be very helpful; ultimately, making this deterministic will be far more efficient than any means of making sure that the routes are all written in the same order.

[Mariculous]

So the weight in between two koors is kind of randomised.
Hopefully it is modelled in a way that relates multiple nodes to a koord, otherwise Dijkstra itself would break.
At least from the descriptions it sounds like it's relating multiple nodes to the same koord.
I did not study route search code in simutrans so far, but I guess I should do this just now...

[jamespetts]

So the weight in between two koors is kind of randomised.
Hopefully it is modelled in a way that relates multiple nodes to a koord, otherwise Dijkstra itself would break.
At least from the descriptions it sounds like it's relating multiple nodes to the same koord.
I did not study route search code in simutrans so far, but I guess I should do this just now...

That would be very helpful, as my attempts did not discover what was happening.

[jamespetts]

I have undertaken some further investigation on this, but have not found anything clear yet. I have eliminated all possible places where direction per se might have any effect on private car routing, and yet the loss of synchronisation still occurs.

Testing carefully inside the routing algorithm, it seems that the tiles are always inserted into the queue (queue.insert(k)) in the same order (in the case of Ranran's saved game, when the starting tile is 75,293, tile 75,294 is always inserted before 74,293), so there is no lack of determinism in this part of the code. Testing when the route is relaxed (previous = tmp->gr->get_pos()) seems to show that it is always 75,294 and never 74,293 accessed here, too, but it is difficult to be sure of this since the sample size for this test was very low because of the very large time between hits on my conditional breakpoint, which significantly slowed my code. It therefore remains very obscure where and how these indeterminisms are occurring.

Any assistance would be much appreciated.