Exercises

  1. The Byzantine Generals problem is this: Two generals are on hills either side of a valley. They each have an army of 1000 soldiers. In the woods in the valley is an enemy army of 1500 men. If each general attacks alone, his army will lose. If they attack together, they will win. They wish to send messengers out through the wood to agree when to attack. However, the messengers may get lost or caught in the woods (or brainwashed into delivering different messages). How can they devise a scheme by which they either attack with high probability, or not at all?
  2. A network runs a dynamic distributed routing algorithm. This is a scheme to permit automatic avoidance of broken links and routers. In what way does this differ from a distributed application such as an electronic mail system?