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."
According to New Scientist, evolutionary algorithms could make many network caches twice as efficient.
That's easy, just cache 4 boobs at a time instead of two
It would be cool if it didn't suck.
It would be interesting to see exactly which algorithms they are talking about here. I wouldn't be surprised if they drew some ideas from garbage collection algorithms also.
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?
I wonder if they evolved logic to counter the slashdot effect. 1. Scan slashdot.org for new stories every five minute. 2. Scan new story for links. 3. Cash those pages.
From what I can tell a good majority of the traffic that my machine receives is worm traffic. Would these genetic routines be setup to disregard those as cache data? If that's the case would they be setup to just block that data?
That alone would save me quite a bit of traffic as people on my subnet hit me constantly with their infected machines.
66.41.161.120 hit my machine 57 different times (that isn't individual requests, that's total times).
For the uninitiated, elements are added to an LRU cache until it fills up; thereafter, whenever a new element is added, space is made for it by throwing away the least-recently used one. Note, least recently used, not the least recently added, i.e. the oldest, since an element that was cached long ago may be used all the time, and so be well worth its place in the cache. For example, consider the company-logo image that your browser caches when you visit a new site and that is embedded in every page on that site. However old it gets, it's likely to continue to be used while you're on the site. As soon as you move to another site, it gradually shuffles its way down the deck until it falls off the bottom - which is precisely what you want.
--
What short sigs we have -
One hundred and twenty chars!
Too short for haiku.
It already takes forever for DNS changes to propagate through every network, which can be extremely frustrating when you have a high bandwidth domain. There definitely needs some optimization on the DNS front.
GroupShares Inc.
-------
artlu.net
I"ve always wondered if something along the lines of cache complimented with a Bittorrent type of scheme couldn't help speed up the internet. that way bits would be mirrored all over, and a server could pull them in faster since more servers did less work each.
just something I'm thinking about today, well, that and the Kerry/Edwards pairing.
PCBRwer342$#
free ipod and free gmail!
From the article:
He[Pablo Funes] suggests networks might in the future be designed to work out who deserves the most help for themselves. "Sophisticated network behaviours might implement rules for reciprocity and trust," he says. "And conversely, for not cooperating with other others who try to abuse our resources."
The future of network security? Imagine the next computer virus outbreak: Every network in the world could recognize the virus type activity and allocate them lesser or zero resources, maybe sending them a "Virus detected, please run antivirus software or contact your IT Department" notice, and detecting outside attacks from viruses and automatically flagging them as unsafe, and not give much(or any) attention to traffic from or to that site
Actually, I do genetic algorithm / genetic programming research at the university of michigan. It's unlikely that these guys are using genetic algorithms to develop a new algorithm, but are rather using an existing algorithm and *tuning* the associated parameters using a GA. Given a list of parameters, GA's work by finding the best combination of parameters. As a result, the settings could be constantly tweaked (say on a daily/hourly basis) and different servers could still have different regional settings. My only problem with the concept is that it still depends on the tuning of pre-existing algorithms... but still - the results they share (2x improvement) is encouraging.
Once again, Al Gore has his hand in the shaping of the internet.
I'm sure everyone in the Slashdot community will miss him - even if you didn't enjoy his work, there's no denying his contributions to popular culture. Truly an American icon.
If the search space is not dominated by local maxima, basic hill climbing (go for the best neighboring value) will work. And it will be fast. If the function is differentiable, it can be orders of magnitude faster than other methods, because you can use a variant of Newton's Method.
If the search space is small, random search (just guessing) will work by exhaustively searching the space. This is obvious, but tends to be ignored in academic papers all too often.
This discussion also applies to neural nets and simulated annealing.
Now this article at least describes a problem for which a GA might actually be useful. Many such articles don't. But they haven't demonstrated that you need a bumpy hill-climbing algorithm.
This is why, despite all the hype, GAs, neural nets, and such aren't used all that much. The search space has to have the right properties. Not too small, not too big, bumpy, but not too bumpy.
The is even a link to an online Tron game where us humans can play versus his evolving algorithms. The win/loss stats for his algorithm is approaching even. Given that humans can also evolve in the Tron game play, I imagine that the algorithm will have a head start over the new influx of slashdot visitors and start to win more often than not over the next week. I never got to play though. The SQL db to mange the stats was already down then I tried.
What happens if someone caches Metallica, or the new super hot J-Lo movie? Then how is the guy who brings the director a warm towel ever going to make his money?
You guys should really think before you go out and start making technology that blatently abuses copyrights
</sarcasm>
Evolution is the change in allele frequencies over time. Pure and simple, that's all it is. Check any evolutionary biology book. The notion of giraffes sprouting gills is absurd and not even remotely what evolution is except in the creationist strawmen. What prevents a whole lot of small changes from adding up? No one has discovered a barrier or any reason that this wouldn't occur. It's like saying that water can move grains of sand, but there's no proof that a lot of water will eventually erode a beach.
The evolutionary algorithm will have a range of all possible algorithms that can be developed, so in a sense it is limited to "test various algorithms", though it would be testing all possible algorithms. Similarly biological evolution is limitted to testing various imperfect self-replicators, meaning all possible imperfect self-replicators. It is further constrained by the current state, but then that's the problem with non-biological GAs as well, the King of the Hill effect.
"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.
ANY environmental adaptation of genetic code over multiple generations is evolution. It does not have to be a major change. BTW, creationists are the only ones that make a distinction between macro-evolution and micro-evolution. If fact, creationists are the only ones that I have ever heard use the terms.
Technoli
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.
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
If you had studies GAs, you would know that GAs do "create" new information that doesn't exist in the original solution set (i.e. any given generation of potential solutions).
GA systems both propogate "good" information, as well as generate and test new information incrementally across generations. Of course, this is done within whatever limitations you choose to impose on the solution set (i.e. if you're using a fixed N-bit string to represent entities in the solution space, then you'll search across all 2^N possible solutions in the N-bit string space).
Fundamentally, GAs are just a way of searching a solution space for good solutions. They are slow, but can tackle a more diverse set of problems easier than the traditional backpropogation-based neural network. I would consider neural networks to be more in line with your description of an 'adapting' learning algorithm.
The following analogy can only be taken so far, but you can compare backpropogation-based neural networks to be akin to hill-climbing algorithms - you start from one solution, move some limited distance towards what you think is a better solution. For a neural network with N vertices, you can think of neural network learning as hill-climbing in an N-dimensional space over whatever field used to specify edge weights.
GAs, on the other hand, do a much more disparate search over any solution space. And it is surprising how well it finds near-optimal solutions even for problems where the relation between solutions is complex and non-intiuitive (e.g. minimums for seemingly chaotic functions).
-Laxitive
with Critticall tool.
Original site.
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.
50% of all bits sent over the internet are 0s. Just cache that and we have a 50% cache hit rate. :)
Natural selection is one of the methods (the other being sexual selection) by which all evolution (macro and micro) proceeds.
Technoli
Evolution is *not* the "change in allele frequencies over time." Or at least that's a secondary issue, historically, conceptually, and causitively. Well, on the last, allele frequency is pretty important (but still not exclusive). But evolution as a concept is firstly a question of PHENOTYPIC change, even before it's about GENOTYPIC change.
Evolution was a well known phenomenon (e.g. from the geological record) long before the work of Mendel was known. Specifically, the rather well known Darwin had no concept of an allele when he came up with the Theory of Evolution by Natural Selection. In fact, Darwin's approach was most certainly not the only explanation of evolution floated in 19th century biology. For example, Lamarckian mechanisms had a plausibility at the time... in fact, Lamarckian mechanisms still represent an important underexamined area of evolutionary mechanisms, for historical reasons (Lysenko etc.)--see, for example, the work of Ruth Hubbard and the role of viral insertions into the genome. So the whole allele thing is only part of one (important) mechanism, only understood relatively late in the scientific study of evolution.
Moreover, even in modern terms, mutation still exists; admittedly, the high-school text book focus on point mutations of genes is vastly overplayed. But just looking at allele frequencies misses also both the role of regulatory genes, and also ignores structural changes in chromosomes. Genes and smaller sequences migrate within and between chromosomes--this has nothing to do with alleles. Stephen Gould's work on phentotypic growth regulation in _Ontogeny and Phylogeny_ is good here, as is the tome _Structure of Evolutionary Theory_.
Buy Text Processing in Python
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.
No, it's not that simple. Evolution has been defined as changes adding up enough so that a single celled organism becomes a multi-celled organism, which develops RNA and DNA, which then grows in complexity to develop various "macro" level systems such as a cardio-pulminary system, a digestive tract, a nervous system, and a central control "brain" system. Each of these changes requires a macro change of which no predecessor exists in the current chain of organics.
That is one of the facts that it explains, not the definition. You're doing the equivalent of saying that a ball falling is the definition of gravity. Evolution is the collection of mechanisms by which these occur, which under the modern synthesis is by various alleles changing over time in a population.
Actually, my first example was the very real issue of a single celled ameba becoming multi-celled.
And oddly, stages between single cell and multicell still exist. The Volvox are single cell creatures that only function in colonies. A colony is a sphere that can grow a daughter colony inside it, then give birth to a new colony. Yet all of the cells involved are generic, not specialized into tissues. Sponge and jellyfish are on the other end of the gap. They both show tissue level specialization without organs.
A giraffe sprouting gills would be an evolutionary change, but is highly unlikely.
A giraffe sprouting gills would be a challenge to modern evolutionary theory, not an example. Modern evolution relies on the existing material being gradually changed or coopted.
A more realistic example is a fish developing lungs. According to the current theories, most life originated in the ocean. I don't remember if the current thought is that lungs and gills developed simultaneously or if they developed in unison. Either way, the effect is much the same. A low order life form developed features not currently in its genetic makeup.
Such as a mud skippers and lung fish? They both occupy niches and use mechanism similar to the first air-breathers using modified gills and air bladders, respectively. Not only are the transition species possible, but they're descendants still exist.
Which is exactly my point. No new algorithm will be generated through the "genetic breeding". Only existing algorithms will rise to the top.
That's interesting. I can write a program that contains the Axioms and rules from ZF Set theory, then randomly applies them to create new theorems. But that would be pointless since only theorems that existed in the orginal data and algorithms "will rise to the top". The whole of mathematics is pointless since all theorems are tautologies from the axioms and rules of manipulation.
Doesn't Freenet already do this within its own network?
\ This was on data where the distance the document had travelled was taken into account. So, given some available input data they evolved a priority function (using GP) that servers as the center for a caching strategy. This with apparent great success.
I don't believe you understand the word "evolution". Evolution is not a huge jump that rapidly redefines something, it's an almost unnoticable change over time.
No, the current theories state that it is a unnoticable change over a long period of time. On a higher level, evolution simply states that major changes occurred over a long period of time. It also states that those changes occurred in an "organic vacuum". e.g. Lungs developed where no lungs had ever existed before.
Evolution can be understood as a search through a problem space. The caching algorithm sets up a problem space of "all possible caching algorithms". A P2P server would be completely outside of the problem space and thus irrelavent.
If that was really the case, then higher organisms should never have developed. The problem space for the "simple" organism was to survive in its wet environment. I believe you named colonies of amebas as an example of "vestigal organisms" at one point. Without arguing that point, what forced these successful organisms to then develop different cell types? How did different cell types improve their success rate? From there, how did developing complex DNA improve their success rate? From there, how did specialized macro-organs improve their success rate?
In evolutionary theory, the "simple" life form was striving to become a better adapted life form. It obviously exceeded its problem space by a wide margin, or you and I would not be having this discussion today. Thus if GAs are really indicitive of "real" evolution, then why can't they eventually evolve into "higher algorithms"? A P2P network could very well improve the GA's success rate for its problem domain. It can start by accidentally reusing its network connections, then accidentally making contact with other cache hosts with the same mutation, then it can evolve a protocol by accidentally learning each communication packet through a torrent of random spam packets, etc.
While that sounds somewhat silly, that's not my point. My point is that evolution states exactly that sort of behavior over a long enough period of time. If a GA is a good emulation of micro-evolution, and macro-evolution is based on micro-evolution, then shouldn't we be able to compute a set of mutations that take the program out of its pre-programmed algorithms? Shouldn't it be able to leverage parameters that we didn't program it to leverage?
Javascript + Nintendo DSi = DSiCade
Will you make up your mind, first you agree with the grandparent poster that one particular example doesn't prove the general case, and then you make the claim that the SCA example does suggest the general case is zero sum.
I have made up my mind. The parent of my post made a statement that was factually correct: SCA does not "prove" that positive mutations can't happen. I then go on to show that everything from SCA to genetic manipulation has so far shown us that genetics is a zero sum game. It's perfectly possible that it's not, but we haven't yet proved it either way. All we have is a mountain of data that suggests genetics is a zero-sum game.
Come on man, make up your mind! which side of the fence are you on?
How is that scientific? If you always approach a problem from the angle that "X must be right", then you'll never make any new discoveries. If something can be observed then proven to be true, then we must adjust our world-view and move on.
It is worth noting that there is a natural bias towards observing negative mutations, not only are they probably far more common but also they stand out against the background, i.e. when people start dieing, or are born with gills, or no legs then people are going to notice pretty damn quick and start saying "ohhhh, mutation==bad!"
This is quite true.
however a beneficial mutation (for example a resistance to the common cold) is much more likely to go unnoticed at first,
The difficulty here is that until we can isolate and identify "positive" mutations, they are nothing but speculation. It's possible that it's just a matter of time before such mutations are discovered, but we can't say they exist until we can demonstrate them. It's a bit like Tachyons in physics. Theory said they should exist, therefore they existed, right? (If it's on Star Trek, it must be true!) Turns out that Tachyons are now considered to have been a "glitch" in string theory that has now been worked out. No time-traveling phantom particle, sorry.
as it is a lot harder to notice or prove that something hasn't happened during a persons lifetime.
It's very difficult to prove a lot of things in science. That's what we have laboratories for. By direct manipulation of creatures with short life spans, scientists can observe how genetics work and test theories on how a positive mutation might be induced. With more and more computing power at their disposal, it should only be a short time before we're able to begin very fast computer modeling of entire genomes.
The first surprise has already come in the form of shorter gene sequences than predicted. It wouldn't surprise me if biologists find themselves completely rewriting the books on genetics in the near future. If there's anything that physics has taught me, it's that the Universe is not one to easily give up its secrets.
I apologise if you took offence at being called a troll earlier, I meant it in the original sense of someone who deliberately posts inflammatory content in the hopes of sparking a debate. (anti-evolution posts certainly qualify on Slashdot)
Apology accepted, but with one caveat. I never claimed that evolution was false. It's not very nice to stomp all over the theories of others just because you don't like it. My specific complaint was the outright confusion caused by the "micro-evolution" renaming of environmental adaption. I don't like it, because no link has been demonstrated. This gives people the mistaken impression that they can write software using genetic adaption type algorithms, and actually produce software that "evolves" in the macro-evolutionary sense. The truth is that the software doesn't go anywhere. It merely "adapts" to the situation at hand until the most powerful solution can be found.
As for calling you a creationist.... well are you are aren't you, you claim to not believe in evolution, so how do you think we got here?
Ac
Javascript + Nintendo DSi = DSiCade