Object-Oriented Satellite Network: Message Propagation Simulator

Design and implement an object-oriented SatelliteNetwork that processes a stream of instructions to simulate message propagation and determine the report-back order and times for satellites.

Assumptions and Scope

• The network topology (satellites and undirected relationships) persists across calls.
• Propagation state resets per message: each call to MessageReceived starts a fresh propagation using the current topology (typical semantics for independent messages).
• The graph is simple (no parallel edges); neighbor lists are maintained in strictly increasing SatelliteId order.

API

Implement the following methods:

1. SatelliteConnected(SatelliteId)
   • Add the satellite node to the network if not already present.
2. RelationshipEstablished(SatelliteId1, SatelliteId2)
   • Add an undirected connection between the two satellites.
   • Maintain neighbors in strictly increasing SatelliteId order (stable over time).
3. MessageReceived(M, SatelliteId_1, ..., SatelliteId_M) → List[(SatelliteId, reportTimeSeconds)]
   • Treat the given M satellites as simultaneously notified at time t=0.
   • Simulate propagation according to the rules below.
   • Return a list of (SatelliteId, reportTimeSeconds) for all satellites that become notified in this propagation, ordered by report time ascending, using SatelliteId as a tie-breaker.

Simulation Rules

• Forwarding Latency:
  • It takes exactly 10 seconds for a satellite to forward a message to one direct neighbor.
  • A sender can forward to only one neighbor at a time (sequential), each attempt consuming 10 seconds.
  • Forwarding to neighbors is synchronous and atomic per sender.
• Forwarding Order:
  • Each satellite forwards to all of its direct neighbors it has not already notified (from its own perspective), strictly in increasing SatelliteId order.
• Single Effective Notify:
  • Once a receiver is notified (by any source), it is considered notified; further attempts do not change its state.
  • However, concurrent or later attempts to the same receiver still consume 10 seconds of the sender’s time.
• No Immediate Back-Edge:
  • A satellite never forwards to the specific neighbor that most recently notified it (its effective notifier). For initial satellites at t=0, there is no prior notifier, so nothing is excluded.
• Processing and Reporting Delay:
  • After a satellite completes all of its own forwarding attempts (per the ordered list it performs, with the above back-edge exclusion), it waits 30 seconds, then reports back to Earth.
• Tie-breaking:
  • Reporting: If two satellites finish processing at the same time, the smaller SatelliteId reports first.
  • Simultaneous Notify Arrivals: If multiple notify attempts arrive to the same satellite at the exact same time, the attempt from the smaller sender SatelliteId is deemed the effective notifier.

Output and Complexity Expectations

• MessageReceived returns a stable ordering of (SatelliteId, reportTimeSeconds) for all satellites reached during that propagation.
• Describe and justify your data structures (e.g., adjacency lists with sorted neighbors, event queue/simulator, per-node state with first-notify time and effective notifier) and the event scheduling strategy (e.g., priority queue of notify-attempt completions).
• Provide time and space complexity in terms of V (satellites), E (relationships), and the degree distribution.

Edge Cases to Handle

• Disconnected components: satellites never reached must not appear in the output.
• Multiple concurrent attempts to notify the same target: only the earliest arrival sets its notify time; all senders still incur 10 seconds per attempt.
• Large hubs with many neighbors: honoring strict SatelliteId order significantly impacts timelines.
• Re-entrant calls to MessageReceived with overlapping or disjoint initial sets: topology persists; propagation state resets.