CS8603
DISTRIBUTED
SYSTEMS
UNIT I INTRODUCTION
Introduction: Definition –Relation to computer system components –
Motivation –Relation to parallel systems – Message-passing systems
versus shared memory systems –Primitives for distributed
communication –Synchronous versus asynchronous executions –Design
issues and challenges. A model of distributed computations: A
distributed program –A model of distributed executions –Models of
communication networks –Global state – Cuts –Past and future cones
of an event –Models of process communications. Logical Time: A
framework for a system of logical clocks –Scalar time –Vector time –
Physical clock synchronization: NTP.
Challenges in Distributed System
• Heterogeneity – In h/w, OS,N/W, Programming languages etc . Mobile code:
code transferred from one computer to another as executables are
dependent on an instruction set & OS. Ex: Java applets
• Transparency – concealing from the user about the separation of components
- Access transparency : hide differences in data representation and how
resources are accessed.
- Location transparency : hide where a resource is located
- Migration transparency : hide a resource may move to another location
- Relocation transparency: hide a resource has moved to another location
- Replication transparency: hide a resource may be copied to another place
Challenges in Distributed System
- Concurrency transparency: hide distributed serializable or hide that a resource is shared with
competitive users.
- Failure transparency: hide the failure & the recovery of a resource
- Persistence transparency: hide whether a resource is in memory / disk
• Openess: s/s can be extended/ reimplemented. Ex: Twitter & facebook provides extendability
to add s/w using APIs.
• Concurrency: multiple clients access resources which is bound to change objects like bidding
in auctions, results displayed post exams in Universities. Through semaphore we achieve
concurrency
• Security: Sharing of sensitive resources . Availability , Integrity, Confidentiality are to be taken
care of.
• Scalability: Size – overloading problem communication ; geographical – reliability problem,
administrative mess (as controllable feature)
• Failure handling – h/w or s/w failure could happen, but computation should continue without
interrupts.
Relation to computer system
components
Relation to computer system
components
• Each computer has a memory & processing unit connected by
communication network
• Every computer uses its OS and network protocol stack for
functioning.
• Distributed software-> middleware
• Distributed Execution: Execution of the processes across the
distributed systems to achieve a common goal. Also called as
Computation or Run.
• Layered architecture – to reduce the complexity.
• Middleware: distributed software that drives the distributed system
to provide transparency of heterogeneity.
Relation to computer system
components
• Schematic diagram, displays the s/w – middleware communication
between the s/s components of the processor.
• http, ftp, mail, telnet protocols are not present in the application layer
of the middleware.
• Middleware libraries: have primitives and the function calls
embedded into the user program.
• Libraries contain functions for reliable and ordered multicasting.
• Reliable multicast : allows a group of processes to agree on a set of
messages received by the group which does not consider ordering ,
but ordered multicast resolves this as well.
Relation to computer system
components
• Standards like OMGs – Object Management Group like CORBA –
Common Object Request Broker Architecture, RPC- Remote Method
Invocation – which works like a local procedure call.
• Commercial versions of Middleware use: CORBA, DCOM- Distributed
Component Object Model, Java, RMI- Remote Method Invocation,
MPI – Message Passing Interface.
Parallel vs Distributed Systems
Parallel Systems vs Distributed
Systems
Parallel Systems Distributed Systems
Memory : Tightly coupled , shared memory Loosely coupled , distributed memory
Processor Interconnection is in terms of Tbps. Processor Interconnection is in terms of Gbps.
Main focus: Performance & Scientific Computing. Performance in terms of cost, scalability. Reliability
and Resource sharing are the main focus.
Relation to parallel multiprocessor
systems
• Multiprocessor systems
• Multicomputer parallel systems
• Array processors
• Flynn’s taxonomy
• Coupling, parallelism , concurrency & granularity
Relation to parallel multiprocessor
systems -UMA
Relation to parallel multiprocessor systems - UMA
Characteristics of Parallel System:
• Multiprocessor system – parallel system - where multiple processors have
direct access to shared memory in a common address space.
• No common clock
• Has a Uniform Memory Access(UMA) – access latency for all the processors
are same.
• Processors – close proximity, same OS, same type, are housed in a same
container with shared memory. H/W & S/W are tightly coupled.
• IPC – read /write to memory.
• Interconnection Network – bus, Multistage Switch – for greater efficiency.
• Multistage Switch – only one data unit can be sent out on an output wire or
else collision occurs.
Relation to parallel multiprocessor
systems
Omega Network
• n X n inputs, k x k switch
• Number of stages = log kn
• Number of switches in a stage, n/k
• Interconnection function :
• iterative/recursive generating function ,
• i= inputs to the switch, j = outputs a perfect shuffle pattern, with a
left – rotation operation
Omega Network – Interconnection
function
Butterfly Network
Multicomputer Parallel Systems -
NUMA
• Do not have direct access to shared memory.
• Do not form a common address space
• Do not have a common clock
• NUMA – Non Uniform Memory Access multiprocessor parallel system – latency to
access different memory locations vary.
• Ex: NYU Ultracomputer & sequent shared memory machine, CM * Connection Machine
and processor.
Multicomputer Parallel Systems -
NUMA
• Topology – Array of mesh, ring, torus, cube , hypercube – symmetrical
topologies provide easy routing.
• 2-D mesh with wrap around – called torus
• k x k mesh => k 2 processors, here 4x4 mesh
• Path length b/w processors= 2(k/2 - 1)
• Routing done along the Manhattan Grid
k dimensional hypercube
4 dimensional hypercube
• K dimensional hypercube – 2 k processors & memory units.
• Each memory & processor unit – node in hypercube , k –bit label.
• Labelling – shortest path the shortest path b/w any 2 processors –
hamming distance. [number of bit positions in which 2 equal sized strings
differ]
• Routing – hop by hop, message are sent along any dimension.
• Edges of 4D hypercube formed - prepend 0, edges of left 3D hypercube &
prepend 1 , edges of right 3D hypercube , logic for constructing higher
dimension hypercubes.
• Multiple routes – fault tolerance & congestion control mechanism.
Array processors
• Class of parallel computers, physically co-located, tightly coupled.
• Have a common system clock – but no shared memory.
• Communicate by passing messages.
• Perform tightly synchronised processing .
• Data exchange – lock-step [fault tolerant systems that run same set of
operations at same time in parallel]
• Applications – DSP , image processing [data here have large number
of iterations.]
• NUMA & message passing multicomputers – less suitable due to fine
granularity in accessing shared data & communication.
• Parallel systems – used for higher throughput & divides workload
among processors.
• Disadvantages of parallel systems:
- less market requirement for high speed applications.
- Manufacturing cost is high
Flynn’s taxonomy
• Has 4 processing modes checks if,
1.Processors execute same / different instructions at the same time
2. Processors process the same data at the same time
Mode 1: Single Instruction Stream, single data stream (SISD)
- vonNeuman architechture : a single CPU, single memory unit connected
by bus.
Mode 2: Single instruction stream, multiple data stream (SIMD)
- Homogeneous processors execute lock-step on different data.
- Ex: Illiac-iv, MPP, CM2, MassPar, Array processors, systolic processors
Flynn’s taxonomy
Mode 3: Multiple instruction stream, single data stream (MISD)
- Processors execute different operations in parallel on same data.
- Applications –Visualizations.
Mode 4: Multiple instruction stream, multiple data stream (MIMD)
- Processors execute different code on different data
- Applications: Distributed systems & in most parallel systems like Sun
Ultra servers, multicomputer PC’s & IBM SP machines.
Flynn’s taxonomy
