# Algorithm for executing a command against a million hosts

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?

• This seems more suited to stackoverflow. – Yuval Filmus Oct 12 '15 at 12:39
• @YuvalFilmus, this is a classic algorithmic question in distributed systems, not a programming question. – Wandering Logic Oct 12 '15 at 13:12
• @YuvalFilmus Apart from the “any product?” part, I don't see what's not CS here. – Gilles 'SO- stop being evil' Oct 12 '15 at 13:58

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