Avalanche Effect

Briefly, this is when changing one input bit on your data that you're encrypting results in a change of roughly half the bits of the ciphertext. One bit causes a few other bits to change, which causes further bits to change, and soon 50% of your bits are different. It is named such due to the similiarity that one piece of snow can start an entire avalanche. This effect happens often in such ciphers as DES, and makes it harder to analyze the ciphertext.

Alternately, if you like formal logic:
-for each bit i, 0 <= i < m
-if the 2^m plaintext vectors are divided into 2^m-1 pairs x and x_i with each pair differing only in bit i
-then when the 2^m-1 exclusive-or sums, termed avalanche vectors, V_i = f(x) XOR f(x_i) are compared, about half of these sums should be found to be 1.

Here is a demonstration. (thanks to http://www-theory.dcs.st-and.ac.uk/~sal/school/CS3010/Lectures/forhtml/node4.html)
It shows the differences which arise from an input and a permutation, and the resulting differences in the output.

Input:    ...............................................................*

Permuted: .......................................*........................

Round  1: .......*........................................................

Round  2: .*..*...*.....*........................*........................

Round  3: .*..*.*.**..*.*.*.*....**.....**.*..*...*.....*.................

Round  4: ..*.*****.*.*****.*.*......*.....*..*.*.**..*.*.*.*....**.....**

Round  5: *...**..*.*...*.*.*.*...*.***..*..*.*****.*.*****.*.*......*....

Round  6: ...*..**.....*.*..**.*.**...*..**...**..*.*...*.*.*.*...*.***..*

Round  7: *****...***....**...*..*.*..*......*..**.....*.*..**.*.**...*..*

Round  8: *.*.*.*.**.....*.*.*...**.*...*******...***....**...*..*.*..*...

Round  9: ***.*.***...**.*.****.....**.*..*.*.*.*.**.....*.*.*...**.*...**

Round 10: *.*..*.*.**.*..*.**.***.**.*...****.*.***...**.*.****.....**.*..

Round 11: ..******......*..******....*....*.*..*.*.**.*..*.**.***.**.*...*

Round 12: *..***....*...*.*.*.***...****....******......*..******....*....

Round 13: **..*....*..******...*........*.*..***....*...*.*.*.***...****..

Round 14: *.**.*....*.*....**.*...*..**.****..*....*..******...*........*.

Round 15: **.*....*.*.*...*.**.*..*.*.**.**.**.*....*.*....**.*...*..**.**

Round 16: .*..*.*..*..*.**....**..*..*..****.*....*.*.*...*.**.*..*.*.**.*

Output:   ..*..**.*.*...*....***..***.**.*...*..*..*.*.*.**.*....*.*.*.**.