Unformatted text preview:

Distributed CoordinationJonathan GeislerMay 10, 2006Jonathan Geisler Distributed CoordinationDistributed AlgorithmsInformation spread between multiple processorsProcessors may only make decisions based on local informationAvoid single points of failureGlobal time is unavailable!Jonathan Geisler Distributed CoordinationDistributed AlgorithmsInformation spread between multiple processorsProcessors may only make decisions based on local informationAvoid single points of failureGlobal time is unavailable!Jonathan Geisler Distributed CoordinationDistributed AlgorithmsInformation spread between multiple processorsProcessors may only make decisions based on local informationAvoid single points of failureGlobal time is unavailable!Jonathan Geisler Distributed CoordinationDistributed AlgorithmsInformation spread between multiple processorsProcessors may only make decisions based on local informationAvoid single points of failureGlobal time is unavailable!Jonathan Geisler Distributed CoordinationEvent OrderingSome tasks have strict ordering requirements (e.g., resource usemust follow its allocation). The last property from the previousslide makes this a difficult requirement to fulfill.Jonathan Geisler Distributed CoordinationLeslie Lamport’s logical clockLeslie took the ideas from Einstein’s theory of relativity andapplied them to this problem. He started by defining a transitiverelationship (→) for time dependence (i.e., if A happens prior toB, then A → B). If there is no timing relationship, the two tasksare said to be concurrent.Jonathan Geisler Distributed CoordinationRules for the logical clockMessages imply an ordering between se nder and receiverEach process keeps track of its local event orderingWhen a process sends a message, it includes its local logicaltime. The receiver will update its local logical time if it is tooearly.Actual time is not as important as the ordering in this system!If an event depends on something else, it will either run onthe same processor or wait for a message to arrive.Jonathan Geisler Distributed CoordinationRules for the logical clockMessages imply an ordering between se nder and receiverEach process keeps track of its local event orderingWhen a process sends a message, it includes its local logicaltime. The receiver will update its local logical time if it is tooearly.Actual time is not as important as the ordering in this system!If an event depends on something else, it will either run onthe same processor or wait for a message to arrive.Jonathan Geisler Distributed CoordinationRules for the logical clockMessages imply an ordering between se nder and receiverEach process keeps track of its local event orderingWhen a process sends a message, it includes its local logicaltime. The receiver will update its local logical time if it is tooearly.Actual time is not as important as the ordering in this system!If an event depends on something else, it will either run onthe same processor or wait for a message to arrive.Jonathan Geisler Distributed CoordinationRules for the logical clockMessages imply an ordering between se nder and receiverEach process keeps track of its local event orderingWhen a process sends a message, it includes its local logicaltime. The receiver will update its local logical time if it is tooearly.Actual time is not as important as the ordering in this system!If an event depends on something else, it will either run onthe same processor or wait for a message to arrive.Jonathan Geisler Distributed CoordinationRules for the logical clockMessages imply an ordering between se nder and receiverEach process keeps track of its local event orderingWhen a process sends a message, it includes its local logicaltime. The receiver will update its local logical time if it is tooearly.Actual time is not as important as the ordering in this system!If an event depends on something else, it will either run onthe same processor or wait for a message to arrive.Jonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationMutual exclusionThere are three basic options:1Lock manager2Token passing3Fully distributedRequest lock from all other processes (with timestamp)Respond to all messages you don’t care aboutResolve conflicts via timestampsJonathan Geisler Distributed CoordinationAtomic actionsThe key is to use transactions to ensure multiple actions s ucce edor fail as a unit. The traditional two phase commit (see COS 341for details) is used for implementation.Jonathan Geisler Distributed CoordinationConcurrency Control(i.e., handling shared data at multiple locations)It is trivial to deal with this situation if the data only exists at onelocation because that location can monitor its data usingtechniques we’ve already looked at. What do we do when data isreplicated?Have a single site manage all the locksRequire a majority of data holders to agree to a lockFavor shared locks to exclusive locksGive one data holder the exclusive rights to the dataJonathan Geisler Distributed CoordinationConcurrency Control(i.e., handling shared data at multiple locations)It is trivial to deal with this situation if the data only exists at onelocation because that location can monitor


View Full Document

TAYLOR COS 421 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?