Algorithm for executing a command against a million hosts

Question

Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the moment, let us suppose you want to run one command at a time. How to do that efficiently?

Is also desirable to have the ability to query at any moment the progress (status of execution on each host), as well as to consult afterwards the outcome of each individual execution (both exit code and stdout/stderr); hence, the outcome must be persisted somewhere.

Ideally, if you could deliver instantaneously the command at all the hosts, and coordinate them to start at the same time, you would have an ideal time of the command duration (assuming command takes same time on every host). Thus, I presume that a big part of the problem is how to deliver as fast as possible the command to all the hosts; the problem may get more elaborated if we add the quality of being fault-tolerant (that is, to ensure that the execution does take place on all available hosts even if some of the auxiliary machines used for the delivery fail or have issues).

If I execute a dummy echo command using ssh on an intranet I have access to (after having automated the authentication with keys); the time for getting back a response is at best 0.25 secs. Thus, running one million times ssh against each one of the hosts does not sound promising if done serially (it would take almost 3 days to finish the execution serially on this environment).

Even if we could deliver the command within a few milli-seconds to each machine using a custom protocol other than ssh, doing the delivery from a single source may not be the best approach. I suppose that the problem may benefit from some parallel/distributed algorithms, as well as network/graph theory. It would also be nice to avoid using a centralized approach too, if one does not want to rely on the availability of a fixed set of machines for doing the delivery (which ideally should be a subset of the one million hosts, so we do not need additional infrastructure machines).

Is there an standard name for this kind of problem? Any known algorithms or approaches?

Answer 1

Assuming the hosts and network are reliable, and that the cost of sending a message from any machine to any other machine is the same, then you would use some sort of broadcast tree. For example, if the machines are all numbered 0, ..., 7, then node 0 would send to node 4, 2, and 1, node 4 would send to nodes 6, and 5. Node 2 would send to node 3. Node 6 would send to node 7.

Generalize that to $2^n$ nodes, and the total time is $O(n)$. So with 2²⁰ nodes, node 0 would send about 20 messages, rather than 1 million.

As you make the assumptions weaker, the problem gets increasingly more difficult.

If the cost of sending messages is different for different pairs of machines, then you would want to do some kind of minimum spanning tree based algorithm, maybe.

If you don't know anything about the network as a whole, but each node knows something about its neighbors then you might use some kind of flooding algorithm.

If the network is not reliable (links can appear and disappear) then the problem gets quite difficult. I think there are various ways of posing the problem as a Steiner tree problem, but now you are way outside my area of expertise.