|
UNIT – 1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-01/Lecture-01 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Distributed
system(Dec-2011) We define a distributed system as one in which hardware or
software components located at networked computers communicate and coordinate
their actions only by passing
messages. Example
-Google, the market leader in web search technology, has put significant
effort intothe design of a sophisticated distributed system infrastructure to
support search (andindeed other Google applications and services such as
Google Earth). This representsone of the largest and most complex distributed
systems installations in the history ofcomputing. ……………Reference
{George
Coulouris,DISTRIBUTEDSYSTEMSConcepts and
Design,5}
Architecture of Distributed System(Dec-2011-13) A
distributed System(DS) is one in which (i)
Hardware and software components,
located at remote networked computers, coordinate and communicate their
actions only by passing messages. Any distance may separate computers in the
network (ii)
Sharing of resources is the main
motivation of distributed systems. Resources may be managed by servers and
accessed by clients, or its users as single virtual machine and runs its own
OS.
Fig 1:Architecture of Distributed System Each computer
node has its own memory. Example of Distributed system are: Internet,
Interanet, Mobile and ubiquitous computing. As a consequence of this
definition, the characteristics of distributed system or networked computers
are: (i)
Concurrency: How to handle the sharing of
resources between clients? Execution of concurrent programs share resources:
e.g. web pages, files,etc. (ii)
No global clock: In a distributed system,
computers are connected through network and have their own clocks.
Communication between program is only through message and their co-ordination
depends on time .Every client’s(computer) perception of time is different
.Accurate time synchronization is not possible in DS .How to synchronize
activities? (iii)
Independent Failure: Distributed system should be
planned for consequence of possible failure of its components.How to handle a
failure in the network or in a particular client? Other clients of its
clients might not be immediately aware of a failure .Each component of the
distributed system can fail independently leaving others still running.
Faults in the network results in isolation of the field component only,but
system continue running. ---------------Reference
{architecture-of-distributed-systems,www.slideshare.net } Unit-01/Lecture-02
Difference between tightly coupled and loosely
coupled multiprocessor system(Dec-2012)
Difference between network operating
system and distributed operating system:
Unit-01/Lecture-03 Goals of
Distributed Systems (Dec-2013) (i) Making Resources
Accessible (ii)
Transparency (iii)
Openness (iv)
Scalability (i)
Making Resources
Accessible
: ·
The main goal of a distributed system is to make it easy
for the users (and applications)to access remote resources, and to share them
in a controlled and efficientway. ·
Resources can be
just about anything, but typical examples include things like printers,
computers, storage facilities, data, files, Web pages, and networks .For
example, it is cheaper to let a printer be shared by several users in a small
office than having to buy and maintain a separate printer for each user. ·
Connecting users and resources also makes it easier to
collaborate and exchange information, as is clearly illustrated by the
success of the Internet with its simple protocols for exchanging files, mail.
documents, audio, and video. (ii)
Transparency: An important goal of a distributed system is
to hide the fact that its processes and resources are physically distributed
across multiple computers. A distributed system that is able to present
itself to users and applications as if it were only a single computer system
is said to be transparent. Access
transparencyenables local and remote resources to
be accessed using identical operations. Location
transparencyenables resources to be accessed
without knowledge of their physical or network location (for example, which
building or IP address). Concurrency transparencyenables several processes to operate
concurrently using shared
resources without interference between them. Replication transparencyenables multiple instances of
resources to be used to increase reliability and performance without knowledge of
the replicas by users or application programmers. Failure transparencyenables the concealment of faults,
allowing users and application programs to complete their tasks despite the
failure of hardware or software components. Mobility transparencyallows the movement of resources and
clients within a system without affecting the operation of users or programs. Performance transparencyallows the system to be reconfigured
to improve performance as loads vary. Scaling transparencyallows the system and applications to
expand in scale without change
to the system structure or the application algorithms. (iii)
Openness: ·
An open distributedsystem is a
system that offers services according to standard rules that describe the syntax
and semantics of those services. ·
For example, in computer networks, standard rules govern
the format, contents, and meaning of messages sent and received. Such rules
are formalized in protocols. ·
In distributed systems, services are generally specified
through interfaces, which are often described in an Interface Definition
Language (IDL). (iv)
Scalability: ·
Scalability
of a system can be measured along at least three different dimensions. ·
First, a
system can be scalable with respect to its size,meaning that we can easily
add more users and resources to the system. ·
Second,
ageographically scalable system is one in which the users and resources may
lie farapart. ·
Third, a system can be administratively
scalable that it can still be easy to manage even if it spans many
independent administrative organizations. ……………Reference {Tanenbaum&Steen,DISTRIBUTED
SYSTEMS,8}
Unit-01/Lecture-04
Hardware Concept ·
Even though all distributed systems
consist of multiple CPUs, there are several different ways the hardware can
be organized, especially in terms of how they are interconnected and how they
communicate. In this section we will take a brief look at distributed system
hardware, in particular, how the machines are connected together. In the next
section we will examine some of the software issues related to distributed
systems. ·
Various classification schemes for
multiple CPU computer systems have been proposed over the years, but none of
them have really caught on and been widely adopted. Probably the most
frequently cited taxonomy is Flynn's (1972), although it is fairly
rudimentary. Flynn picked two characteristics that he considered essential:
the number of instruction streams and the number of data streams. A computer
with a single instruction stream and a single data stream is called SISD. All
traditional uniprocessor computers (i.e., those having only one CPU) fall in
this category, from personal computers to large mainframes. ·
The next category is SIMD, single
instruction stream, multiple data stream. This type refers to array
processors with one instruction unit that fetches an instruction, and then
commands many data units to carry it out in parallel, each with its own data.
These machines are useful for computations that repeat the same calculation
on many sets of data, for example, adding up all the elements of 64
independent vectors. Some supercomputers are SIMD. ·
The next category is MISD, multiple
instruction stream, single data stream. No known computers fit this model.
Finally, comes MIMD, which essentially means a group of independent
computers, each with its own program counter, program, and data. All
distributed systems are MIMD, so this classification system is not
tremendously useful for our purposes. ·
Although Flynn stopped here, we will
go further. In Fig. 1-4, we divide all MIMD computers into two groups: those
that have shared memory, usually called multiprocessors,and those that do not, sometimes
called multicomputers.
The essential difference is this: in a multiprocessor, there is a single
virtual address space that is shared by all CPUs. If any CPU writes, for
example, the value 44 to address 1000, any other CPU subsequently reading
from its address 1000 will get the value 44. All
the machines share the same memory.
SOFTWARE CONCEPTS
·
Operating system: – Interface between users and hardware – Implements a virtual machine that is easier to program than raw
hardware ·
Primary functions: – Services: file system, virtual memory, networking, CPU scheduling,
... – Coordination: concurrency, memory protection, security,
networking,... SOFTWARE CONCEPTS
Unit-01/Lecture-05 Distributed
Computing Model(Dec-2011) Distributed
Computing system models can be broadly classified into five categories. They
are (i)
Minicomputer model (ii)
Workstation model (iii)
Workstation – server model (iv)
Processor – pool model (v)
Hybrid model Minicomputer
Model ·
The minicomputer model is a simple extension
of the centralized time-sharing system. A distributed computing system based
on this model consists of a few minicomputers (they may be large
supercomputers as well) interconnected by a communication network. Each
minicomputer usually has multiple users simultaneously logged on to it. For
this, several interactive terminals are connected to each minicomputer. ·
Each user is logged on to one specific
minicomputer, with remote access to other minicomputers. The network allows a
user to access remote resources that are available on some machine other than
the one on to which the user is currently logged. ·
The minicomputer model may be used when
resource sharing (such as sharing of information databases of different types,
with each type of database located on a different machine) with remote users
is desired. The early ARPA net is an example of a distributed computing
system based on the minicomputer model. Workstation
Model ·
A distributed computing system based on the
workstation model consists of several workstations interconnected by a
communication network. An organization may have several workstations located
throughout a building or campus, each workstation equipped with its own disk
and serving as a single-user computer. ·
It has been often found that in such an
environment, at any one time a significant proportion of the workstations are
idle (not being used), resulting in the waste of large amounts of CPU time. ·
Therefore, the idea of the workstation model
is to interconnect all these workstations by a high-speed LAN so that idle
workstations may be used to process jobs of users who are logged onto other
workstations and do not have sufficient processing power at their own
workstations to get their jobs processed efficiently. Workstation
– Server Model ·
The workstation model is a network of personal
workstations, each with its own disk and a local file system. A workstation
with its own local disk is usually called a diskful workstation and a
workstation without a local disk is called a diskless workstation. ·
With the proliferation of high-speed networks,
diskless workstations have become more popular in network environments than
diskful workstations, making the workstation-server model more popular than
the workstation model for building distributed computing systems. ·
A distributed computing system based on the
workstation-server model consists of a few minicomputers and several
workstations (most of which are diskless, but a few of which may be diskful)
interconnected by a communication network. ·
Note that when diskless workstations are used
on a network, the file system to be used by these workstations must be
implemented either by a dishful workstation or by a minicomputer equipped
with a disk for file storage. ·
One or more of the minicomputers are used for
implementing the file system. Other minicomputers may be used for providing
other types of services, such as database service and print service.
Therefore, each minicomputer is used as a server machine to provide one or
more types of services. ·
Therefore in the workstation-server model, in
addition to the workstations, there are specialized machines (may be
specialized workstations) for running server processes (called servers) for
managing and providing access to shared resources. For a number of reasons,
such as higher reliability and better scalability, multiple servers are often
used for managing the resources of a particular type in a distributed
computing system. ·
For
example, there may be multiple file servers, each running on a separate minicomputer
and cooperating via the network, for managing the files of all the users in
the system. Due to this reason, a distinction is often made between the
services that are provided to clients and the servers that provide them. That
is, a service is an abstract entity that is provided by one or more servers.
For example, one or more file servers may be used in a distributed computing
system to provide file service to the users. ·
In this model, a user logs onto a workstation
called his or her home workstation. Normal computation activities required by
the user's processes are performed at the user's home workstation, but
requests for services provided by special servers (such as a file server or a
database server) are sent to a server providing that type of service that
performs the user's requested activity and returns the result of request
processing to the user's workstation. Therefore, in this model, the user's
processes need not migrated to the server machines for getting the work done
by those machines. Processor
– Pool Model ·
The processor-pool model is based on the
observation that most of the time a user does not need any computing power
but once in a while the user may need a very large amount of computing power
for a short time (e.g., when recompiling a program consisting of a large
number of files after changing a basic shared declaration). ·
Therefore, unlike the workstation-server model
in which a processor is allocated to each user, in the processor-pool model
the processors are pooled together to be shared by the users as needed. The
pool of processors consists of a large number of microcomputers and
minicomputers attached to the network. Each processor in the pool has its own
memory to load and run a system program or an application program of the
distributed computing system Hybrid Model ·
Out of the four models described above, the
workstation-server model, is the most widely used model for building
distributed computing systems. This is because a large number of computer
users only perform simple interactive tasks such as editing jobs, sending
electronic mails, and executing small programs. ·
The workstation-server model is ideal for such
simple usage. However, in a working environment that has groups of users who
often perform jobs needing massive computation, the processor-pool model is
more attractive and suitable ……………Reference {P.K.Sinha, DISTRIBUTED OPERATING SYSTEMS,5}
Unit-01/Lecture-06 Advantages
of Distributed Systems Performance: very often a collection of processors
canprovide higher performance (and betterprice/performance ratio) than acentralizedcomputer. Distribution: many applications involve, by their
nature,spatially separated machines (banking,commercial, automotive system). Reliability (fault tolerance): if some of the
machinescrash, the system can survive. Incremental growth: as requirements on processingpower grow,
new machines can be addedincrementally. Sharing of data/resources: shared data is essential tomany
applications (banking, computer-supported cooperative work, reservation systems); other resources can be alsoshared (e.g. expensive printers). Communication: facilitates human-to-humancommunication Disadvantages of Distributed Systems
Difficulties of
developing distributed software: howshould operating systems, programminglanguages and applications
look like? Networking problems: several problems are created bythe network
infrastructure, which have tobe dealt with: loss of messages, overloading, .. . Security problems: sharing generates the problem of data
security
Design issues that arise specificallyfrom the distributed nature of
the application: • Transparency • Communication • Performance & scalability • Heterogeneity • Openness • Reliability & fault tolerance • Security 1. Transparency: Ø
How to achieve the single system image? Ø
How to "fool" everyone into thinking that the collection of
machines is a "simple" computer? •Access transparency- local and remote resources are accessed
usingidentical operations. •Location transparency- users cannot tell where hardware and software
resources (CPUs, files, data bases) are locat-ed; the name of the resource
shouldn’t encode the location of the resource. •Migration (mobility) transparency- resources should be free to move
from one location to another without having their names changed •Replication transparency- the system is free to make additional
copies offiles and other resources (for purpose ofperformance and/or
reliability), without theusersnoticing.Example: several copies of a file; at
a certainrequest that copy is accessed which is theclosest to the client. •Concurrency transparency- the users will not notice the existence of
otherusers in the system (even if they access thesame resources). •Failure transparency- applications should be able to complete
theirtask despite failures occurring in certaincomponents of the system. •Performance transparency- load variation should not lead to
performancedegradation.This could be achieved by automaticreconfiguration as
response to changes of theload; it is difficult to achieve ` Unit-01/Lecture-07 2. Communication: Ø
Components of a distributed system have tocommunicate in order to
interact. This implies support at two levels a)
Networking infrastructure (interconnections & network software). b)
Appropriate communication primitives and models and their
implementation:
i.
communication primitives: - send - receive - remote procedure call(RPC)
ii.
communication models: - client-server communication: implies amessage exchange between two
proc-esses: the process which requests a service and the one which provides
it; -group multicast: the target of a message isa set of processes, which
are members ofa given group. 3. Performance & scalability: Several factors are influencing the performance of a distributed
system: • The performance of individual workstations. • The speed of the communication infrastructure. • Extent to which reliability (fault tolerance) is provided
(replication and preservation of coherence imply large overheads). • Flexibility in workload allocation: for example, idle processors
(workstations) could be allocatedautomatically to a user’s task. Scalability- The system should remain efficient even with asignificant increase in
the number of users and resources connected: - cost of adding resources should be reasonable; - performance loss with increased number of users and resources should
be controlled; - software resources should not run out (numberof bits allocated to
addresses, number of entries in tables, etc.) 4. Heterogeneity: Distributed applications are typically heterogeneous: ·
-different hardware: mainframes, workstations,PCs, servers, etc.; ·
-differentsoftware: UNIX, MS Windows, IBM OS/2,Real-time OSs, etc.; ·
-unconventional devices: teller machines,telephone switches, robots,
manufacturingsystems, etc.; ·
-diverse networks and protocols: Ethernet,FDDI, ATM, TCP/IP, Novell
Netware, etc ·
The solution- Middleware, an additional software layer to
maskheterogeneity 5. Openness: One of the important features of distributed systemsis openness and
flexibility: ·
every service is equally accessible to everyclient (local or remote); ·
it is easy to implement, install and debug new services; ·
users can write and install their own services
6. Reliability & fault tolerance: One of the main goals of building distributed systemis improvement of
reliability. Availability: If machines go down, the system should workwith the
reduced amount of resources. • There should be a very small number of criticalresources (single
points of failure);critical resources: resources which have to be up in order the distributed system to work. • Key pieces of hardware and software (criticalresources) should be
replicated⇒if one of themfails
another one takes up -redundancy Data on the system must not be lost, and copies storedredundantly on
different servers must be keptconsistent • The more copies kept, the better the availability, butkeeping
consistency becomes more difficult. Fault-toleranceis a main issue related to reliability:
thesystem has to detect faults and act in a reasonable way: •ask the fault: continue to work with possiblyreduced performance but
without loss of data/information. •fail gracefully: react to the fault in a predictable wayand possibly
stop functionality for a short period,but without loss of data/information 7. Security: Security of information resources: a)
ConfidentialityProtection against disclosure to unauthorised person b)
Integrity Protection against alteration and corruption c)
Availability Keep the resource accessible Distributed systems should allowcommunication between
programs/users/resources on different computers.
Security risks associated with free access ……………Reference
{PetruEles,
DISTRIBUTED
OPERATING SYSTEMS,PDF,P.K.SINHA Distributed operating system,19}
Unit-01/Lecture-08 Design principles of Scalable, Distributed System (Dec-2011)Designing scalable, distributed systems
involves a completely different set of principles and paradigms when compared
to regular monolithic client-server systems. Typical large distributed
systems of Google, Facebook or Amazon are made up of commodity servers.
These servers are expected to fail, have disk crashes, run into network
issues or be struck by any natural disasters. Rather than assuming that failures and
disasters will be the exception these systems are designed assuming the worst
will happen. The principles and protocols assume that failures are the
rule rather than the exception. Designing distributed systems to accommodate
failures is the key to a good design of distributed scalable systems. A key
consideration of distributed system is the need to maintain consistency,
availability and reliability. This of course is limited by the CAP Theorem
postulated by Eric Brewer which states that a system can only provide any two
of “consistency, availability and partition tolerance” fully, Some key techniques in distributed systems Vector Clocks: An obvious issue in distributed systems with
hundreds of servers is that each server will have its own clock running at a
slightly different rate. It is difficult to get a view of a global time
considering that each system has slightly different clock speeds. How does
one determine causality in such a distributed system? The solution to this
problem is provided by Vector Clocks devised by Leslie Lamport. Vector Clocks
provide a way of determining the causal ordering of events. Each system
maintains an array of timestamps based on its own internal clock which it
keeps incrementing. When a system needs to send an event to another system it
sends the message with the timestamp generated from its internal array.
When the receiving system receives the message at a timestamp that is less
than the sender’s timestamp it increments its own timestamp by 1 and
continues to increments its internal array through its own internal clock. In
the figure the event sent from System 1 to System 2 is assumed to be fine
since the timestamp of the sender “2” < “15. However when System 3
sends an event with timestamp 40 to System 2 which received it timestamp 35,
to ensure a causal ordering where System 2 knows that it received the event
after it was sent from System the vector clock is incremented by 1 i.e. 40 +
1 = 41 and System 2 increments at it did before, This ensures that partial
ordering of events is maintained across systems.
Vector clocks have been used in Amazon’s
e-retail website to reconcile updates. The use of vector clocks to
manage consistency has been mentioned in Amazon’s Dynamo Architecture Distributed Hash Table (DHT): The Distributed Hash Table uses a 128 bit
hash mechanism to distribute keys over several nodes that can be conceptually
assumed to reside on the circumference of a circle. The hash of the largest
key coincides with the hash of the smallest key. There are several algorithms
that are used to distribute the keys over this conceptual circle. One such
algorithm is the Chord System. These algorithms try to get to the exact node
in the smallest number of hops by storing a small amount of local data at
each node. The Chord System maintains a finger table that allows it to get to
the destination node in O (log n) number of hops. Other algorithms try to get
to the desired node in O (1) number of hops. Databases like Cassandra,
Big Table, and Amazon use a consistent hashing technique. Cassandra spreads
the keys of records over distributed servers by using a 128 bit hash key. Quorum Protocol: Since systems are essentially limited
to choosing two of the three parameters of consistency, availability and
partition tolerance, tradeoffs are made based on cost, performance and user
experience. Google’s BigTable chooses consistency over availability while
Amazon’s Dynamo chooses ‘availability over consistency”. While the CAP
theorem maintains that only 2 of the 3 parameters of consistency,
availability and partition tolerance are possible it does not mean that
Google’s system does not support some minimum availability or the Dynamo does
not support consistency. In fact Amazon’s Dynamo provides for “eventual
consistency” by which data become consistent after a period of time. Since failures are inevitable and a number of
servers will fail at any instant of time writes are replicated across many
servers. Since data is replicated across servers a write is considered
“successful” if the data can be replicated in N/2 +1 servers. When the
acknowledgement comes from N/2+1 server the write is considered successful.
Similarly a quorum of reads from >N/2 servers is considered successful.
Typical designs have W+R > N as their design criterion where N is the
total number of servers in the system. This ensures that one can read their
writes in a consistent way. Amazon’s Dynamo uses the sloppy quorum
technique where data is replicated on N healthy nodes as opposed to N nodes
obtained through consistent hashing. Gossip Protocol: This is the most preferred protocol to allow
the servers in the distributed system to become aware of server crashes or
new servers joining into the system, Membership changes and failure detection
are performed by propagating the changes to a set of randomly chosen
neighbours, who in turn propagate to another set of neighbours. This ensures
that after a certain period of time the view becomes consistent. Hinted Handoff and Merkle trees: To handle server failures replicas are
sometimes sent to a healthy node if the node to which it was destined was
temporarily down. For e.g. data destined for Node A is delivered to
Node D which maintains a hint in its metadata that the data is to be
eventually handed off to Node A when it is healthy. Merkle trees
are used to synchronize replicas amongst nodes. Merkle trees minimize the
amount of data that needs to be transferred for synchronization. ……………Reference{www.ibm.com/.../design_principles_of_scalable_distributed_system}.
Different
failure of Distributed Systems (Dec-2013)
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
