CS 603 Mid-Semester Review .


56 views
Uploaded on:
Category: Sales / Marketing
Description
Maybe a couple Day Review?. One day: Skim material and Test OverviewWhat to do with Wednesday?More on replicationStart on dispersed processesTwo day: Discuss material to dateWednesday:Finish ReviewWork out example question. Fundamentals. Why do we need dispersed systems?ScalingHeterogeneityGeographic DistributionWhat is a disseminated system?Transparency versus Uncovering DistributionHardware BasicsCommunica
Transcripts
Slide 1

CS 603 Mid-Semester Review March 4, 2002

Slide 2

One or Two Day Review? One day: Skim material and Test Overview What to do with Wednesday? More on replication Start on disseminated forms Two day: Discuss material to date Wednesday: Finish Review Work out example address

Slide 3

Basics Why do we need conveyed frameworks? Scaling Heterogeneity Geographic Distribution What is a conveyed framework? Straightforwardness versus Uncovering Distribution Hardware Basics Communication Mechanisms

Slide 4

Basic Software Concepts Hiding versus Uncovering Distribution – Distributed OS Location, however not conveyance – Middleware None – Network OS Concurrency Primitives Semaphores Monitors Distributed System Models Client-Server Multi-Tier Peer to Peer

Slide 5

Communication Mechanisms Shared Memory Enforcement of single-framework view Delayed consistency: δ - Common Storage Message Passing Reliability and its points of confinement Stream-arranged Communications Remote Procedure Call Remote Method Invocation

Slide 6

RPC Example: DCE Language/Platform Independent Implementation Issues: Data Conversion Underlying Mechanisms Fault Tolerance Approaches

Slide 7

Java RMI Supports remote summon of Java articles Key: Java Object Serialization Stream protests over the wire Language particular Advantages True question introduction: Objects as contentions and qualities Mobile conduct: Returned items can execute on guest Integrated security Built-in simultaneousness (through Java strings) Disadvantage – Java just Implementation/Use Registry

Slide 8

SOAP Goal: RPC convention that works over wide range systems Interoperable Language autonomous Problem: Firewalls Solution: HTTP/XML Client side: Ability to produce http calls and tune in for reaction Server: Listen for HTTP Bind to strategy Respond with HTTP SOAP message organization and utilize instruments

Slide 9

Naming Requirements Disambiguate just Access asset given the name Build a name to discover an asset Do people need to utilize name? Static/Dynamic Resource Performance Requirements

Slide 10

Naming Approaches Scope Global versus Various leveled Unique ID versus Non-Unique Description Namespaces URN, URI, URL Registries

Slide 11

Registry Example: X.500 Goal: Global "white pages" Lookup anybody, anyplace Developed by Telecommunications Industry ISO standard index for OSI systems Idea: Distributed Directory Application utilizes Directory User Agent to get to a Directory Access Point

Slide 12

Directory Information Base ( X.501 ) Tree structure Root is whole catalog Levels are "gatherings" Country Organization Individual Entry structure Unique name Build from tree Attributes: Type/esteem sets Schema upholds sort leads Alias passages

Slide 13

X.500 Directory Entry: Organization level – CN=Purdue University, L=West Lafayette Person level – CN=Chris Clifton, SN=Clifton, TITLE=Associate Professor Directory Operations Query, Modify Authorization/Access control To registry Directory as instrument to execute for others

Slide 14

X.500 – Distributed Directory System Agent Referrals Replication Cache versus Shadow duplicate Access control Modifications at Master just Consistency Each passage must be inside predictable DSA giving duplicate must distinguish as duplicate

Slide 15

X.500 Subsets LDAP X.500 without OSI Intended for use over IP Active Directory Microsoft\'s response to LDAP Extensible "default" naming composition Limited replication offices

Slide 16

Clock Synchronization Definition: All hubs concede to time What do we mean by time? What do we mean by concur? Lamport Definition: Events in part requested Clock "tallies" the request

Slide 17

Event-based definition (Lamport \'78) Define incomplete request of procedures A  B: An "occurred before" B: Smallest connection with the end goal that: If An and B in same process and A happens initial, A  B If An is communicating something specific and B is receipt of a message, A  B If A  B and B  C, then A  C Clock: C(x) is time x happens: C(x) = C i (x) where x running on hub i. Timekeepers rectify if  a,b: a b  C(a) < C(b)

Slide 18

Lamport Clock Implementation Node i Increments C i between any two progressive occasions If occasion an is sending of a message m from i to j, m contains timestamp T m = Ci(a) Upon getting m, set C j ≥ current C j and > T m Can now characterize add up to requesting. a  b iff: C i (a) < C j (b) C i (a) = C j (b) and P i < P j

Slide 19

What on the off chance that we need "divider clock" time? C i should keep running at right rate:  κ << 1 to such an extent that | dC i (t)/dt – 1 | < κ Synchronized:  little ε to such an extent that  i,j: | C i (t) – C j (t) | < ε Assume transmission time amongst μ and μ + ξ Algorithm: Upon getting message m, set C j (t) = max(C j (t), T m + μ ) Theorem: Assume each τ seconds a message with unusual postpone ξ is sent over each bend. At that point  t ≥ t 0 + τ d, ε ≈ d(2 κτ + ξ )

Slide 20

Clock Synchronization: Limits Best Possible: Delay Uncertainty Actually ε (1 – 1/n ) Synchronization with Faults Faulty clock Communication Failure Malicious processor Worst case: Can just synchronize if < 1/3 processors broken Better if timekeepers can be confirmed

Slide 21

Real case: NTP I question you have to survey this...

Slide 22

Process Synchronization Problem: Shared Resources Model as consecutive or parallel process Assumes worldwide state! Elective: Mutual Exclusion when Needed Coordinator approach Token Passing Timestamp

Slide 23

Mutual Exclusion Requirements Does it ensure shared avoidance? Does it counteract starvation? Is it reasonable? Does it scale? Does it deal with disappointments?

Slide 24

CS 603 Mid-Semester Review March 6, 2002

Slide 25

Mutual Exclusion: Colored Ticket Algorithm Goals: Decentralized Fair Fault tolerant Space Efficient Idea: Numbered Tickets Next number gets asset Problem: Unbounded Space Solution: Reissue pieces

Slide 26

Multi-Resource Mutual Exclusion New Problem: Deadlock Processes utilizing all assets Each necessities extra asset to continue Dining Philosophers Problem Coordinated versus genuinely appropriated arrangements Problems with deterministic arrangements Probabilistic arrangement – Lehman & Rabin Starvation/decency properties

Slide 27

Distributed Transactions ACID properties Issues: Commit Protocols Fault Tolerance Why is this enough? Disappointment Models and Limitations Mechanisms: Two-stage submit Three-stage confer

Slide 28

Two-Phase Commit (Lamport \'76, Gray \'79) Central facilitator starts convention Phase 1: Coordinator inquires as to whether members can submit Participants react yes/no Phase 2: If all votes yes, organizer sends Commit Participants react when done Blocks on disappointment Participants must supplant organizer If member and facilitator fizzle, sit tight for recuperation While blocked, exchange must stay Isolated Prevents different exchanges from finishing

Slide 29

Transaction Model Transaction Model Global Transaction State Reachable State Graph Local states possibly simultaneous if a reachable worldwide state contains both nearby states Concurrency set C( s ) is all states conceivably simultaneous with s Sender set S( s ) = {local states t | t sends m and s can get m } Failure Model Site disappointment accepted when expected message not got in time Independent Recovery

Slide 30

Problems with 2-PC Blocking on disappointment 3-PC as arrangement Theorems on recuperation limits Independent recuperation: No two-site disappointment Non-free recuperation Anything shy of aggregate disappointment approve Recovery convention for aggregate disappointment

Slide 31

c 1 a 1 c 2 a 2 3PC accepting timeout on receipt of message Coordinator Participant q 1 q 2 begin xact/no begin xact/yes xact ask for/begin xact prematurely end/ - w 1 w 2 no/prematurely end yes/pre-confer pre-submit/ack p 1 p 2 ack/confer/ -

Slide 32

Termination Protocol If member times out in w 2 or p 2 : Elect new Coordinator If organizer alive, would have conferred/prematurely ended New organizer demands condition of all procedures. End rules: If any prematurely ended, communicate prematurely end If any dedicated, communicate confer If all w 2 , communicate prematurely end If any p 2 , send pre-submit and enter state p 1 Complete disappointment convention

Slide 33

Test Basics Mechanics: Open book/noticed No electronic guides Two inquiries Each multi-part Will incorporate scoring proposals Underlying inquiry: Do you comprehend the material? No compelling reason to spew "best in writing" answer Reasonable self-planned arrangement fine Key: Do you truly comprehend your answer Can you assemble CORRECT dispersed frameworks?

Slide 34

Develop synchronization convention for a four processor framework with completely associated processors. Straight envelope of constant Bounded contrast between timekeepers on right processors. Time set to 0 when the convention starts (however not synchronized). Accept: Clocks don\'t float Messages take between time 0 and e At most one broken processor No validation Discuss the accuracy of your calculation, including the sorts of deficiencies dealt with. Scoring: Protocol: Up to five focuses Argument for accuracy: 2 focuses requires reasonable evidence draw for full 2 focuses Faults upheld/not bolstered: 1-3 focuses 3 focuses requires verification portray that it handles bolstered deficiencies and cases demonstrating disappointment with unsupported blame sorts. Test Question: Clock Synchronization

Recommended
View more...