04-09-06 - 4


We watched "Battle of Algiers" last night, which is an old movie about the anti-colonial guerilla revolution against the French in Algeria. Of course it's a very different situation than Iraq, but it does strike a few similar notes. For one thing, the French were even more brutal about capturing suspected terrorists and torturing them to try to extract information, and striking back at the populace. These methods have never worked.

It also made me think of an ideal terrorist cell structure. The binary tree described in "Battle of Algiers" is ridiculous. Basically they claim the FLM had a tree structure where each node (a person) knows only his parent and two children. This gives you a minimum knowledge of other people in the structure, so if you are taken out or caught, you spoil a minimum of direct neighbors. That's true, but it also means huge branches of the tree can be easily cut off, if you capture anyone near the top, it severs a big fraction of the tree. It's sort of tricky to improve this and seems like a fun CS problem. The idea is that if someone gets caught, you want to cut him and everyone he can identify out of the tree. Then you want to be able to re-link the tree and keep as much of it intact as possible. The direct neighbors of the caught node can communicate their knowledge to help relink the tree before they themselves are cut.

One idea is just the circularly linked list. Instead of a tree everyone is just in a circular list. There's still a leader, but he just passes his message to each side, and they keep passing it along anonymously. Even if the leader is cut out of the tree it only removes his direct neighbors. When a cut is made, you now just have a linear list. This can be easily fixed by broadcasting a message like "if you only know one neighbor, go to meeting spot X", then two people will go there and establish a link. This seems ideal. If you want the structure to be robust to possibly having 2 simultaneous cuts, you need more links. Probably best is to give each node 3 links - two to direct neighbors in the circular list, and 1 to the opposite on the circle, or perhaps just to a random other node. Now when someone is caught you have to remove 4 nodes, but you easily have enough links to recreate the circle. Obviously in the modern era with computers you don't actually need any direct links at all. Each of your operatives can just be a PGP key. Operatives who are available for missions just broadcast their public key. Commanders issuing orders can broadcast the instructions encrypted. The two can communicate thus without any direct knowledge of each other and won't be able to give the other up if captured.

It also reminded me how strange the image of the French is in this country. Our politicians for some reason paint this picture of the pacifist wussy French who don't stand up to aggressors and are generally weak and limp. Nothing could be farther from the truth. The French have been probably the second most aggressive nation in the world after WW2 (outside their own borders), after only the U.S. (the USSR maybe falls in there too depending on how you define its borders). They've personally fought major wars in WW1, WW2, Algeria, Indochina (long before we got involved). Since then they've been one of the most active western powers (again, after only the US) at sending Special Forces and arms to foment war all over the world, including such places as Rwanda, Uganda, Iraq & Iran. I'm sure there's a lot more I don't know about. It got me wondering about the French mind set after WW2. Perhaps their pride was injured by their humiliating poor performance defending their country, and they wanted to prove their toughness, and so tried to hold onto Indochina and Algeria, so that they could hold something over the Brittish and Americans by being the last colonial power.

No comments:

old rants