It doesn't require an amazingly dependable logistics system, just normal employment-style logistics. Example: en.wikipedia.org/wiki/Semaphore_line

@jdunlop I did not know about Semaphores that's dang cool. I still maintain that maintaing a line of Semaphores (or horse stations ) that is 86,140 miles long would be amazingly amazing. You would have to plan a year in advance to make sure food gets to the farthest station and what do you do if something happens to the food while in transit? or what if bandits kill allthe workers as one of the stations? It would take you anywere from 1 month to a year to respond and fix the situation.

Well, once you had the line established, you wouldn't need years. With each station you'd add, communication time to that station would be as fast as the semaphore could carry it. Based on the French model, messages traveled at 120 mph, so only a month for end-to-end communication. Then the stations would be arranged like subsidiaries in a business - most day-to-day functions would be managed locally, with only occasional directives coming down from "head office".

@jdunlop, Ya I mentioned self sufficiency as an possible option. But you still have to get the pay roll to them. And you what about bandits, or an invading army. If the land is pleasant enough to support a large enough population to man a fort then your going to get other peoples wanting some of the land and now you have to get an army involved.

Except that, as with network infrastructure on the descendant of the semaphore, it behooves whoever's territory the chain passes through to maintain their own section, as it allows them to communicate at speed with the other connected territories. So payroll would also be (relatively) local.

And what if a station 6 months away starts feeling like they don't need the empire, and would rather go it alone? At some point the return on investment just is not worth it.

the loyalist station next along the chain sends a message back to the nearest station associated with a garrison. They have the communication chain advantage. Easily resolved. The value of rapid communications is almost incalculable.

@jdunlop Are you viewing these stations as being with in the empire?

The OP's post doesn't suggest that there are vast tracts of unclaimed land between the communicating entities, just that there's distance to cover. Since oceans aren't in play, my assumption is that the only problems would be inaccessibility, not falling outside some country's borders.

ok I see were you are coming from. the logistics would be much simplified if it were all inside the empire. I still think it would be amazing. Semaphores are amazing to me as is the pony express. But it would certainly no longer be a nightmare.

When the OP said "If there somehow was a very, very large gap between these countries" I assume that the gap between them is unclaimed land. And unclaimed land is usually not very hospitable. So it seems we were operating on two very different geo-political worlds, no?

Would not their be local government of some form? In the past, given the length of time to communicate, you really had a far more decentralized government model than we have with current civilizations. You would have an empire, but it could have multiple sub countries in it. These would in turn be broken down into smaller jurisdictions. The different rulers would be different classes of nobility, with each having certain duties at their level and expected to serve those above them.

A simplified example would be a empire with multiple kingdoms, with each king loyal to the emperor. Each kingdom would have multiple duchies, with each duke loyal to their king. The king would be responsible for all the semaphores in their kingdom, but would mostly delegate the operations to dukes who are each responsible for the semaphores in their own duchies, and so on.

A king would only need to act if the threat in any area was bigger than what the duke could handle, or if the duke was failing to act (and often that would be by getting the duke to handle it, or replacing them).

There is also the possibility that different countries could maintain their semaphores and use them together because they both would benefit by communicating with each other. This would breakdown during times of war, but would also explain some redundancies in a system that crossed a continent.

To overcome barriers, you could also add in something like a Guild that ran them, charging local merchants to use them, while not charging rulers in return for the rulers protecting them (or have some sort of arrangement worked out).

I was actually thinking about something akin to the East India Company.

And anyone who managed a semaphore tower would, unless in a state of war against their neighbours, want to keep it running - for the same reason that most nations don't really want to keep the Internet out.

@DanAnderson - The pony express was a neat idea, but is only really superior to the semaphore chain for really long messages (books, say) or packages. There's no way you can out-do 120 MPH with anything short of modern technology. If the semaphore towers have lamps on the semaphore shutters, the only thing that'd slow it down would be seriously inclement weather.

Obviously there'd be lots of tweaking for visibility and whatnot, but if you were designing a permanent system, a 4x4 grid of shutters using black and white would allow for a lot of throughput. You'd implement something like TCP, where a seventeenth shutter would indicate receipt, and have four grids on each tower - two "upstream" and two "downstream". One would be used for message transmit, the other for "acks".

Assuming you used something like ASCII for your alphabet, the full 16-bit space could be used for common words/phrases, substantially increasing your transmission speed, too.