It was/is a clever combination of remotely running jobs, understand the Makefile DAG of what needs to be built and observing file system accesses to detect when the DAG doesn't reflect the files that are actually accessed (and therefore cause parallelism problems).
The initial version was built by a small group of people led by me and John Ousterhout.
Electric Make is the large scale makefile maintainers dream basically. You're not going to get that much out of it for a small linux package but once you have a build that can manage a lot of parallelism it makes life easy. It makes your build run across a cluster of machines but presents a filesystem on each machine that makes your build think it's on one computer. It has a filesystem module that does this and which also perfectly spots all your dependencies even when they're not C or C++ header files - just any file that got used when a target was being made.
It's so smart that it spots parallelism issues as they happen and reruns everything in the correct ordering that they would have got run in if the build was running on a single core - so it can make horrible old makefiles work properly in parallel without you needing to update them. It remembers what happened so that it gets everything right first time in the next build.
It remembers what build times things had and schedules longer items earlier. Its dependency mechanism lets it cache build objects with great certainty that you'll never pull a stale item out of a the cache.
And the icing on the cake is that it has a visualisation tool that lets you look at your build across all CPUs/computers and see almost at a glance why it is slow and how to fix it.
It's just the last word. But it is not free at all and again my opinion is that it's mostly going to pay off on larger builds. I also think that if you're building something where the developers take build time very seriously and fix problems a lot then it won't help as much.
"Thy build shall be nondeterministic!" is quite a curse to spring on someone :)
The worst problems are when nobody realises that a parallelism issue has happened and the binary for some tool on your phone OS gets generated from the old rule instead of the new one and it's just an invisible random bug. Not sure shuffling would help that exact problem of course.
For new development, however, a nondeterministic default ensures no one relies on accidental behavior and is good practice. Golang did this with the order of traversing a map and it's wonderful in practice - if you want to depend on an ordering, sort it yourself.
Backwards compatibility is one of the most important things to do to keep people using your product - if I have to debug and change my code to use version 2 of your product, it's not much more work to switch to a competitor. It's also incredibly difficult to deliver backwards compatibility and requires intentional planning in advance.
That all but ensures nobody will care then. Performance is, sadly, not a big motivator in most projects.
Both could be satisfied with a single-threaded make keeps the standard order to ensure backwards compatibility, but `make -j` that also turns on --shuffle. Which is also backwards compatible, because timing of each target might rearrange them.
It was pretty smart - I suspect you could write a really crappy makefile and coast.
this was probably 20 years ago.