A request to implement a topology support and then an ask to ignore it in the design is very confusing.
Challenge #3a: Single-Node Broadcast · Fly Docs
This message informs the node of who its neighboring nodes are. Maelstrom has multiple topologies available or you can ignore this message and make your own topology from the list of nodes in the
Node.NodeIDs()method. All nodes can communicate with each other regardless of the topology passed in.
- Normally you would expect that if there is a topology a node either can’t communicate directly to all the other nodes but only to the neighbors or there is a routing and that at least the packet route length affects the latency sufficiently. Is that the case?
- If the topology does not matter then why bother about it for the algorithm design and ask to implement the topology message handling?
- Why have n.NodeIDs() on the API level and the topology on the app level? How do they correlate? Does it matter at all…
in 3b we are offered to use it, but not given how (what are topology restrictions):
Challenge #3b: Multi-Node Broadcast · Fly Docs
It can use the topology passed to your node in the
topologymessage or you can build your own topology.
But then comes 3d, which
Challenge #3d: Efficient Broadcast, Part I · Fly Docs
The neighbors Maelstrom suggests are, by default, arranged in a two-dimensional grid. This means that messages are often duplicated en route to other nodes, and latencies are on the order of
2 * sqrt(n)network delays.
Messages-per-operation is below
Maximum latency is below
First, the limit of 30 basically asks to drop the fault-tolerance support. Why? But ok…
Then, the stale limit:
for example, I put topology into an account before in the following way: a node can’t communicate to the non-directly connected nodes. The challenge asks to have a max latency of 600ms max with the 25 nodes placed into the grid and minimum latency of 100ms and O(2n^2) order… guess what is the minimal latency over the path between 2 distant nodes through that grid/graph… Hints: grid size is 5x5, minimal edge 100ms. Ok, we are enforced to drop the topology support here…
From the constraints, I can guess that sending the message to the farest node in the grid will cost actually only 100ms and will not depend on the number of hops as otherwise, we would not hit the constraints.
Generally, if I get everything correctly, I am ok with that, but it would be cool to have the steps more sequentially aligned. If the topology is not needed and does not affect the system - don’t ask for it.
Then the documentation says nothing if the topology can change through time. Seems like not. Thank god.
Anyway, thanks for sharing those challenges.
It’s a pleasure to solve them.