Slashdot Mirror
"Evolved" Caches Could Speed the Net
SpaceDilbert writes "According to New Scientist, evolutionary algorithms could make many network caches twice as efficient. This article describes a study carried out by a US researcher and two German academics, who "evolved" algorithms to determine what data should be held at a cache and for how long."
Well, I have found one flaw in the methodology:
I would think this would breed out of the caching system any affinity to locality-of-reference.One of the things I did each morning when I was running a cybercafé was "prime" the Squid cache by running a little script that did a wget -p on all of the URLs in the portal page, and a few sites that were not. And it definitely did improve performance for most users.
One of my unrealized dreams would be some sort of speculative-fetch algorithm for Squid that would basically do a breadth-first fetch on a page while the user was busy reading it.
Of course in my not-so-humble opinion, the biggest problem with any caching system is the population of websites that, through either malice or incompetence develop content that is cache-hostile, and call it "experience enhanced".
How does the Slashdot Effect happen given that no slashdotters ever RTFA?
"Priming the cache" and "doing a breadth-first fetch on a page" are both things that create *more* network traffic on the off-chance that it might save some number of microseconds for the user. It's basically a Tragedy of the Commons situation. Everyone would be better off if no one pre-fetched links, but any given person is better off if they don't cooperate with that global model. So everyone just grabs what they can get and everyone is worse off.
Score:3 Insightful? when did creationist trolls become insightful?
Nature makes no distinction between your so called macro and micro-evolution. Rather there are to separate processes at work that combine to produce evolution.
1. Survival of the fittest (what you call environmental adaptation) starts with a population with a mixture of genes and states that those best able to reproduce in the current environment will probably make up a larger percentage of the next generation.
2. Genetic crossover during reproduction and random mutation, happens to keep the gene pool mixed and introduces new adaptations. This provides the "raw material" for survival of the fittest to work on.
Large changes are unlikely in nature because 99.999999% of major random changes to an organism will result in something that is less fit than its siblings (a giraffe with gills for instance will either suffocate in the savannah, or be unable to eat if by some miracle it also finds itself in the ocean), small changes however have better chance of being an incremental improvement that will become dominant in a population through natural selection. These small changes WILL compound over time to produce major changes in physiology (for example the way whales have adapted back to living in the oceans (actually for a really good example go read Richard Dawkins description of how eyes have evolved in many different creatures as it strikes down very effectively the old creationist chestnut of "the eye is far to complex to have ever evolved in stages")).
ARRGGHHHHH why did I bother writing all this, I know you are a troll.
Most computer scientists loosely use the term "evolutionary programming" to talk about algos that have inherently unpredictable ("emergent") results rather than modelling actual evolutionary processes observed in nature, although that's also a fair part of it all. (Incidentally, I also believe the "Science" topic assigned to this story is wrong for this reason.)
The meta-algo is evolutionary programming in that the algo fianlly "developed" by the meta-algo is apparently result that isn't immediately apparent, indeed, one that perhaps unpredictable by humans.
More than mere navel gazing.
It seems to make sense to me, if only because the two are complimentary problems. Caching is figuring out what stuff is valuable so you keep it around. GC is figuring out what stuff is valuable so you can throw away the rest. Kind of like in probability where it's easier to figure out the likelihood of something not happening and then subtracting from 1 to figure out how likely it is to happen.
Not A Sig
Evolution implies ... e.g. An ameba suddenly mutates into a multi-celled configuration. Or a giraffe suddenly develops gills (Emphasis added).
Rubbish. There's nothing sudden implied.
My Karma: ran over your Dogma
StrawberryFrog
Humbug, the big difference is: in GC there's perfect knowledge about what you want to throw away (unreferenced or only circularly referenced objects), and the problem is how to find out efficiently.. In caching the whole problem is to figure out which objects to keep, and beyond that, efficiency is no problem.
Garbage collection is required to be correct, but is allowed to keep extra stuff around as memory permits. Everything that must be kept can be calculated deterministically without future knowledge, and the same holds true for everything that can be discarded. Approximation merely allows the what can be discarded calculation to progress faster. In garbage collection it is not correct to throw out something that will not be used in the future unless it is also unreachable.
For cacheing there is no requirement of correctness. Performance is improved when things that will be used in the future are kept. There is no correctness requirement for keeping things around, and indeed best performance often requires discarding things that will be used in the future. In addition, there is no way of determining what will be used in the future without knowledge of the future. The correctness requirements of a cache are related to security (don't cache sensitive information) and staleness (don't cache stuff that is too old), but even those may be relaxed rather than strict requirements.
Fundamentally the two problems are very different, and algorithms that deal are successful in the two different cases will likely be very different.
Caching information can also be used as a backup of data in case the server crashes or has its data compromised by a virus , hacker, whatever you feel like ..
so what happens if you, for instance, have a security hole in one of your "smart" servers?? or even a breach in the protocol structure (DoS)?
you could get the server to "breed" algorithms that would stop all servers by either corrupting the data in all servers that are providing the service or just DoS-ing them.
I guess i'm not yet convinced that this solution is of any good for real world network which the whole structure is based on insecure protocols.
maybe after IPV6, IPV9, who knows?
What is best in life? To crush your enemies, to see them driven before you and to hear the lamentations of their women.
Garbage collection problems are far easier than caching problems in networks. There are many reasons. The most important one is that in garbage collection, 'references' are basically 'pointers'. An object that's not pointed to by any other objects is considered garbage. And don't forget, in garbage collection, you can even 'stop the world'!
By contrast, in caching, 'references' are 'client requests', which are unpredictable and highly variable. Furthermore, on busy networks, there is seldom a moment for you to 'stop the world' and 'evolve' for a while!
In the story, people use network simulators and randomly generated requests. Since network simulators are notoriously simplistic and inaccurate, and caching is heavily influenced by real-life workloads, I'm interested to know whether their algorithm is applicable in reality.