Distributed computing

Case Study: Mars Spirit

• Rover lands and also is silent.
• Workers on earth detect the problem so they load some files.
• No transactional guarantee however, so net result is only some of the files are loaded.
• System in an inconsistent state.
• How would you do this in a wait-free manner?

Case Study: Mars Spirit

• Send processes replacing files f1, f2, …., fk to files f1new, f2new, …, fknew. Then have a process that renames those files en masse. Only the last has to be transactional.
• Transmission is easier than consensus.

COMPONENTS OF SECURITY

• Authentication – Proving that you are who you say you are.
• Access Rights – Giving you the information for which you have clearance.
• Integrity – Protecting information from unauthorized exposure.
• Prevention of Subversion – Guard against Replay attacks, Trojan Horse attacks, Covert Channel analysis attacks…

AUTHENTICATION AND ZERO KNOWLEDGE PROOFS

• The parable of the Amazing Sand Counter:
• Person S makes the following claim:
• You fill a bucket with sand. I can tell, just by looking at it, how many grains of sand there are. However, I won’t tell you.
• You may test me, if you like, but I won’t answer any question that will teach you anything about the number of grains in the bucket.
• The test may include your asking me to leave the room.
• What do you do?

SAND MAGIC

• The Amazing Sand Counter claims to know how many grains of sand there are in a bucket just by looking at it.
• How can you put him to the test?

AUTHENTICATING THE AMAZING SAND COUNTER

• Answer:
• Tester tells S to leave the room.
• Tester T removes a few grains from bucket and counts them, then keeps in T’s pocket.
• T asks S to return and say how many grains have been removed.
• T repeats until convinced or until T shows that S lies.
• Are there any problems left? Can the tester use the Amazing Sand Counter’s knowledge to masquerade as the Amazing Sand Counter?