Khoa học máy tính - Chapter 17: Theoretical issues in distributed systems

Chapter 17Theoretical Issues in Distributed SystemsCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionNotions of Time and StateStates and Events in a Distributed SystemTime, Clocks and Event PrecedencesRecording the State of a Distributed System2Operating Systems, by Dhananjay Dhamdhere*Notions of Time and StateTime indicates when an event occurredState of an entity is the condition/mode of its beingDepends on its featuresGlobal state of a system comprises the states of all entities in the system at a specific instant of timeOS uses the notions of time and state for performing scheduling of resources and the CPU:Find chronological order in which requests occurredDistributed OS uses them for recoveryProblem: lack of global clock in distributed systems3Operating Systems, by Dhananjay Dhamdhere*States and Events in a Distributed SystemLocal and Global StatesEvents4Operating Systems, by Dhananjay Dhamdhere*Local and Global StatesEach entity in a system has its own stateState of a memory cell is the value contained in itState of CPU is contents of PSW and GPRsState of process:State of memory allocated to it, CPU state (if running), state of interprocess communicationThe state of an entity is a local stateState of process Pk at time t: SktGlobal state: collection of local states of all entities at the same instant of timeGlobal state of system at time t: St={S1t, S2t,, Snt}5Operating Systems, by Dhananjay Dhamdhere*EventsAn event can be: sending/receiving a message (over a channel), or other (no messages involved)Channel: an interprocess communication pathProcess state changes when an event occurs in itWe represent an event as follows:(process id, old state, new state, event description, channel, message)Channel and message are “–” if event does not involve sending or receiving of a message6Operating Systems, by Dhananjay Dhamdhere*Time, Clocks, and Event PrecedencesGlobal clock: abstract clock that can be accessed from different sites of a distributed system with identical resultsCannot be implemented in practice due to unbounded communication delaysAlternative: use local clocks in processesLocal clocks should be reasonably well synchronized7Operating Systems, by Dhananjay Dhamdhere*Event Precedencee1 → e2 indicates event e1 precedes e2 in timei.e., e1 occurred before e2Event ordering implies arranging a set of events in a sequence such that each event in the sequence precedes the next oneA total order (with respect to “→”) exists if all events that can occur in a system can be orderedA partial order implies that some events can be ordered but not all events can be orderedA casual relationship is used to deduce precedencesA “message send” event precedes “message receive”8Operating Systems, by Dhananjay Dhamdhere*Event Precedence (continued)ei precedes ej : If ek and el exist such that ek →el , ei → ek or ei ≡ ek, and el →ej or el ≡ ej ei follows ej : If eg and eh exist such that eg → eh, ej →eg or ej ≡ eg, and eh →ei or eh ≡ eiei is concurrent with ej : If ei neither precedes nor follows ej9Operating Systems, by Dhananjay Dhamdhere*Example: Event PrecedenceTiming diagram: plot of the activities of different processes against timeEvents in Pi are denoted as ei1, ei2, ..e23 is a message send event for message m1e12 is a message receive event10Operating Systems, by Dhananjay Dhamdhere*Logical ClocksTimestamping (according to local clock) of events provides a direct method of event orderingClocks are loosely synchronized using causality11Operating Systems, by Dhananjay Dhamdhere*Logical Clocks (continued)A logical clock (LCk) is incremented by 1 only when an event occurs in process Pkts(ei) vts(ej )[l]vts(ei ) < vts(ej )[l] if and only if ei → ej15Operating Systems, by Dhananjay Dhamdhere*Example: Synchronization of Vector ClocksTotal order can be obtained using a pair pvts(ei) ≡ (local time, process id) as timestamp of ei16Operating Systems, by Dhananjay Dhamdhere*Recording the State of a Distributed SystemProblem: it is not possible to get all nodes to record their states at the same time instantLocal clocks are not perfectly synchronizedAny other collection of local states may be inconsistentAlternative: algorithm for obtaining a consistent collection of local statesCollected state not a substitute for the global stateHowever, has properties that facilitate some of the control functions in a distributed OS17Operating Systems, by Dhananjay Dhamdhere*Recording the State of a Distributed System (continued)Example: inconsistent state recordingBanking application: P1 in N1 and P2 in N2Actions:P1 debits $100 to account A in node N1P1 sends message to P2 to credit $100 to account BP2 credits $100 to account B in node N2Inconsistent if A’s balance is recorded before (1) and B’s balance is recorded after (3)18Operating Systems, by Dhananjay Dhamdhere*Consistent State RecordingState recording: collection of local states of entities in a system obtained through some algorithmConsistent state recording: one in which process states of every pair of processes in the system are consistent according to:19Operating Systems, by Dhananjay Dhamdhere*Properties of a Consistent State RecordingA cutProcess states are recorded at tP1.. tP420Operating Systems, by Dhananjay Dhamdhere*Properties of a Consistent State Recording (continued)“A cut is taken” means that a collection of local states is recordedA cut represents a consistent state recording of a system if the states of each pair of processes satisfy Definition 17.1State of a channel is the set of messages it containsA cut may intersect with a message:Forward or backward intersectionBackward intersection makes a cut inconsistent21Operating Systems, by Dhananjay Dhamdhere*Properties of a Consistent State Recording (continued)Consistency condition for a cut:CC: Cut C represents a consistent state recording of a distributed system if future of cut is closed under the precedes relation on events (closed under “→”)22Chandy–Lamport Algorithm for state recordingAssumptions of the algorithmChannels are FIFOChannels are unidirectionalChannels have unbounded message buffering capacitiesThe state of a process indicates the messages sent and received by itA special message called a marker is sent to ask a process to record its stateProcess receives markers over all channels incident on itRecords state of channel over which it received a markerIf it is the first marker received, it also records its own stateOperating Systems, by Dhananjay Dhamdhere*23Operating Systems, by Dhananjay Dhamdhere*An Algorithm for Consistent State RecordingNotation:Receivedij : Messages received by Pj over channel ChijRecorded_recdij : Messages recorded as received in the state of Pj24Operating Systems, by Dhananjay Dhamdhere*Example: Operation of the Chandy−Lamport Algorithm25Operating Systems, by Dhananjay Dhamdhere*Example: Recorded State versus Global State26Operating Systems, by Dhananjay Dhamdhere*SummaryOperating systems use notions of time and stateLocal state: State of an entityGlobal state: States of all entities at the same time instantPrecedence of events may be deduced using the causal relationship, i.e., cause-and-effect relationship, and transitivity property of precedenceSome events may be concurrentIt is laborious to deduce the precedence of events by using transitivity, hence timestamps are used insteadUse local clocks in processes 27Operating Systems, by Dhananjay Dhamdhere*SummaryUsing local clocks in processesLogical clocksVector clocksInclude process ids in timestamps for total orderingIt is not possible to record the global state of a systemChandy-Lamport algorithm obtains consistent recording of process states using special messages called markers28