In some of the previous posts we discussed distribute computing . My next book reading is going to be on search.
Meanwhile here is a quick summary of things that we discussed.
1) We talked about reasoning of programs and how to give proof of correctness for the program.
2) We talked about some sample programs such as Earliest Meeting time and Greatest Common Divisor of two integers X and Y
3) We talked about time, clocks and synchronization. In particular we discussed what a logical time is and how to maintain a logical clock. There are vector clocks that keep track of time at all other processes. We talked about synchronizing clocks.
4) We talked about diffusing computations or gossip and how we know that it progresses and terminates. We mentioned interesting applications of gossip.
5) We discussed mutual exclusion as a layer that resolves conflicts between processes.
6) We discussed solutions for mutual exclusion that relied on distributed atomic variables and non-token based solutions including Lamport's algorithm of sending acknowledgements and optimizations.
7) we discussed token based solutions including a simple token ring and token ring with requests and a token tree
8) The token tree approach let us generalize a token graph solution. The key ideas were that tokens were neither created nor destroyed which guarantees safety.
9) Tree is directed and token is always at the root. Process sends only one request and may maintain a list of pending requests. The tree is generalized to a partial order. To maintain the partial order, make all the edges incoming for node with token.
10) We discussed dining philosophers problem and the partial order solution aka hygienic solution. The key idea was to break the symmetry by forming a partial order. To lower a philosopher in the partial order, make all the edges outgoing. Tokens called forks are used for mutual exclusion. Priority is encoded in clean and dirty forks. Request tokens are used to determine whether a neighbor is hungry.
11) We discussed snapshots and how to cut through timeline for various processes. We discussed solutions to taking snapshot including logical time based solution and marker algorithm. We included a proof of correctness. The marker algorithm was meant to flush the channel of messages.
12) We discussed termination detection and the use of special detector process. We applied snapshot to help with the detection.
13) We discussed garbage collection and its relationship to termination detection. We discussed the principle of superposition and the use of a marker witht the mutator. We made first and second attempts with a propagator to spread the marks in a gossip like manner and check to see which garbage is not root i.e. it's manure.
14) We talked about tolerating faults in a distributed system both for byzantine failures and crashes. We talked about the use of authenticated messages and building a consensus tree.
15) We also talked about discrete event simulation with sequential and time driven simulation. We talked about conservative approaches using null events and look aheads. We also talked about optimistic approaches where we allow mistakes that can be undone i.e allow stragglers and do roll-backs.
Meanwhile here is a quick summary of things that we discussed.
1) We talked about reasoning of programs and how to give proof of correctness for the program.
2) We talked about some sample programs such as Earliest Meeting time and Greatest Common Divisor of two integers X and Y
3) We talked about time, clocks and synchronization. In particular we discussed what a logical time is and how to maintain a logical clock. There are vector clocks that keep track of time at all other processes. We talked about synchronizing clocks.
4) We talked about diffusing computations or gossip and how we know that it progresses and terminates. We mentioned interesting applications of gossip.
5) We discussed mutual exclusion as a layer that resolves conflicts between processes.
6) We discussed solutions for mutual exclusion that relied on distributed atomic variables and non-token based solutions including Lamport's algorithm of sending acknowledgements and optimizations.
7) we discussed token based solutions including a simple token ring and token ring with requests and a token tree
8) The token tree approach let us generalize a token graph solution. The key ideas were that tokens were neither created nor destroyed which guarantees safety.
9) Tree is directed and token is always at the root. Process sends only one request and may maintain a list of pending requests. The tree is generalized to a partial order. To maintain the partial order, make all the edges incoming for node with token.
10) We discussed dining philosophers problem and the partial order solution aka hygienic solution. The key idea was to break the symmetry by forming a partial order. To lower a philosopher in the partial order, make all the edges outgoing. Tokens called forks are used for mutual exclusion. Priority is encoded in clean and dirty forks. Request tokens are used to determine whether a neighbor is hungry.
11) We discussed snapshots and how to cut through timeline for various processes. We discussed solutions to taking snapshot including logical time based solution and marker algorithm. We included a proof of correctness. The marker algorithm was meant to flush the channel of messages.
12) We discussed termination detection and the use of special detector process. We applied snapshot to help with the detection.
13) We discussed garbage collection and its relationship to termination detection. We discussed the principle of superposition and the use of a marker witht the mutator. We made first and second attempts with a propagator to spread the marks in a gossip like manner and check to see which garbage is not root i.e. it's manure.
14) We talked about tolerating faults in a distributed system both for byzantine failures and crashes. We talked about the use of authenticated messages and building a consensus tree.
15) We also talked about discrete event simulation with sequential and time driven simulation. We talked about conservative approaches using null events and look aheads. We also talked about optimistic approaches where we allow mistakes that can be undone i.e allow stragglers and do roll-backs.
No comments:
Post a Comment