Distributed Systems

1
Distributed Systems

Comparison of three kinds of multiple CPU

systems
2
Application Layer
• Function:
Application
• Whatever you want
Presentation • Implement your app using the
network
Session • Key challenges:
Transport • Scalability
Network • Fault tolerance
• Reliability
Data Link • Security
Physical • Privacy
• …
3
 What are Distributed Systems?
• From Wikipedia:
A distributed system is a software system in which components located on
networked computers communicate and coordinate their actions by
passing messages.

• Essentially, multiple computers working together

• Computers are connected by a network
• Exchange information (messages)

• System has a common goal

4
Definitions
• No widely-accepted definition, but…
• Distributed systems comprised of hosts or nodes where
• Each node has its own local memory
• Hosts connected via a network

• Originally, requirement was physical distribution

• Today, distributed systems can be on same host
• E.g., VMs on a single host, processes on same machine

5
Outline

Brief History of Distributed

Systems
Examples
Fundamental Challenges
Design Decisions
6
History
Distributed systems developed in
conjunction with networks

Early applications:
Remote procedure calls (RPC)
Remote access (login, telnet)
Human-level messaging (email)
Bulletin boards (Usenet)
7
 Early Example: Sabre
• Sabre was the earliest airline Global Distribution System
• The system that they use at the airports

8
Sabre
American Airlines had a central office with cards for each
flight
Travel agent calls in, worker would mark seat sold on card

1960’s – built a computerized version of the cards

Disk (drum) with each memory location representing
number of seats sold on a flight
Built network connecting various agencies
Distributed terminals to agencies

Effect: Removed human from the loop

9
10
Move Towards Microcomputers
In the 1980s, personal computers became popular
Moved away from existing mainframes
Required development of many distributed systems
Email
Web
DNS
…
Scale of networks grew quickly, Internet came to
dominate
11
Today
Growth of pervasive and mobile computing
End users connect via a variety of devices, networks
More challenging to build systems

Popularity of “cloud computing”

Essentially, can purchase computation and
connectivity as a commodity
Many startups don’t own their servers
All data stored in and served from the cloud
How do we build secure, reliable systems?
12
Outline
Brief History of Distributed
Systems
Examples
Fundamental Challenges
Design Decisions
13
 Example 1: DNS
• Distributed database
• Maps “names” to IP addresses, and
vice-versa Root

• Hierarchical structure
• Divides up administrative tasks
• Enables clients to efficiently resolve edu com org
names
• Simple client/server architecture
• Recursive or iterative strategies for [Link] [Link]
traversing the server hierarchy

[Link] 14
 Example 2: The Web

Web is a widely popular distributed system

Has two types of entities:
Web browsers: Clients that render web pages
Web servers: Machines that send data to clients
All communication over HTTP 15
 Example 3: BitTorrent

Popular P2P platform for large content distribution

All clients “equal”
Collaboratively download data
Use custom protocol over HTTP
Robust if (most) clients fail (or are removed) 16
Example 4: Stock Market
• Large distributed system (NYSE, BATS, etc.)
• Many players
• Economic interests not aligned
• All transactions must be executed in-order
• E.g., super hot IPO’s, a la Facebook

• Transmission delay is a huge concern

• Hedge funds will buy up rack space closer to exchange
datacenters
• Can arbitrage millisecond differences in delay
17
Outline

Brief History of Distributed

Systems
Examples
Seven Fundamental Challenges
Design Decisions
18
Challenge 1: Global Knowledge
• No host has global knowledge
• Need to use network to exchange state information
• Network capacity is limited; can’t send everything
• Information may be incorrect, out of date, etc.
• New information takes time to propagate
• Other changes may happen in the meantime
• Key issue: How can you detect and address
inconsistencies?

19
Challenge 2: Time
• Time cannot be measured perfectly
• Hosts have different clocks, skew
• Network can delay/duplicate messages

• How to determine what happened first?

• In a game, which player shot first?
• In a GDS like Sabre, who bought the last seat on the plane?

• Need to have a more nuanced abstraction to represent

time
20
 Challenge 3: Failures
A distributed system is one in which the failure of a
computer you didn't even know existed can render your
own computer unusable. — Leslie Lamport

Failure is the common case

As systems get more complex, failure more
likely
Must design systems to tolerate failure

E.g., in Web systems, what if server fails?

Systems need to detect failure, recover 21
Challenge 4: Scalability
Systems tend to grow over time
How to handle future users, hosts, networks, etc?

E.g., in a multiplayer game, each user needs to send

location to all other users
O(n2) message complexity
Will quickly overwhelm real networks
Can reduce frequency of updates (with
implications)
Or, choose nodes who should update each other
22
Challenge 5: Concurrency
To scale, distributed systems must leverage concurrency
E.g. a cluster of replicated web servers
E.g. a swarm of downloaders in BitTorrent
Often will have concurrent operations on a single object
How to ensure object is in consistent state?
E.g., bank account: How to ensure I can’t overdraw?
Solutions fall into many camps:
Serialization: Make operations happen in defined order
Transactions: Detect conflicts, abort
Append-only structures: Deal with conflicts later
….
23
Challenge 6: Security
Distributed systems often have many different entities
May not be mutually trusting (e.g., stock market)
May not be under centralized control (e.g. the Web)

Economic incentives for abuse

Systems often need to provide

Confidentiality (only intended parties can read)
Integrity (messages are authentic)
Availability (system cannot be brought down)
24
Challenge 7: Openness
• Can system be extended/re-implemented?
• Can anyone develop a new client?

• Requires specification of system/protocol published

• Often requires standards body (IETF, etc) to agree
• Cumbersome process, takes years
• Many corporations simply publish own APIs (force of market share)

• IETF works off of RFC (Request For Comment)

• Anyone can publish, propose new protocol
• “Rough consensus and running code”
25
Outline
Brief History of Distributed
Systems
Examples
Seven Fundamental Challenges
Five Design Decisions
26
Distributed System Architectures
• Two primary architectures:
• Client-server: System divided into clients (often limited in
power, scope, etc) and servers (often more powerful, with
more system visibility). Clients send requests to servers.
• Peer-to-peer: All hosts are “equal”, or, hosts act as both
clients and servers. Peers send requests to each other. More
complicated to design, but with potentially higher resilience.

27
Messaging Interface
• Messaging is fundamentally asynchronous
• Client asks network to deliver message
• Waits for a response

• What should the programmer see?

• Synchronous interface: Thread is “blocked” until a message
comes back. Easier to reason about.
• Asynchronous interface: Control returns immediately,
response may come later. Programmer has to remember all
outstanding requests. Potentially higher performance.

28
 Transport Protocol
• At a minimum, system designers have two choices for
transport
• UDP
• Good: low overhead (no retries or order preservation), fast (no congestion
control)
• Bad: no reliability, may increase network congestion
• TCP:
• Good: highly reliable, fair usage of bandwidth
• Bad: high overhead (handshake), slow (slow start, ACK clocking, retransmissions)
• However, you can always roll your own protocol on top of UDP
• Microtransport Protocol (uTP) – used by BitTorrent
• QUIC – invented by Google, used in Chrome to speed up HTTP
• Warning: making your own transport protocol is very difficult
29
Serialization/Marshalling
• All hosts must be able to exchange data, thus choosing
data formats is crucial
• On the Web – form encoded, URL encoded, XML, JSON, …
• In “hard” systems – MPI, Protocol Buffers, Thrift
• Considerations
• Openness: is the format human readable or binary? Proprietary?
• Efficiency: text is bloated compared to binary, but easy to debug
• Versioning: can you upgrade your protocol to v2 without
breaking v1 clients?
• Language support: do your formats and types work across
multiple languages?

30
Distributed Systems
• Why do we develop distributed systems?
• availability of powerful yet cheap microprocessors (PCs,
workstations), continuing advances in communication
technology,

• What is a distributed system?

• A distributed system is a collection of independent computers
that appear to the users of the system as a single system.
• Examples:
• Network of workstations
• Distributed manufacturing system (e.g., automated
assembly line)
• Network of branch office computers

31
Advantages of Distributed Systems
over Centralized Systems
• Economics: a collection of microprocessors offer a better price/performance than mainframes.
Low price/performance ratio: cost effective way to increase computing power.
• Speed: a distributed system may have more total computing power than a mainframe. Ex.
10,000 CPU chips, each running at 50 MIPS. Not possible to build 500,000 MIPS single processor
since it would require 0.002 nsec instruction cycle. Enhanced performance through load
distributing.
• Inherent distribution: Some applications are inherently distributed. Ex. a supermarket chain.
• Reliability: If one machine crashes, the system as a whole can still survive. Higher availability
and improved reliability.
• Incremental growth: Computing power can be added in small increments. Modular expandability
• Another deriving force: the existence of large number of personal computers, the need for
people to collaborate and share information.

32
Advantages of Distributed Systems
over Independent PCs
• Data sharing: allow many users to access to a common data
base
• Resource Sharing: expensive peripherals like color printers
• Communication: enhance human-to-human communication,
e.g., email, chat
• Flexibility: spread the workload over the available machines

33
Disadvantages of Distributed Systems

• Software: difficult to develop software for distributed systems

• Network: saturation, lossy transmissions
• Security: easy access also applies to secrete data

34
Hardware Concepts
• Taxonomy

• MIMD (Multiple-Instruction Multiple-Data)

• Tightly Coupled versus Loosely Coupled
· Tightly coupled systems (multiprocessors)
o shared memory
o intermachine delay short, data rate high
· Loosely coupled systems (multicomputers)
o private memory
o intermachine delay long, data rate low

35
Bus versus Switched MIMD

• Bus: a single network, backplane, bus, cable or other

medium that connects all machines. E.g., cable TV
• Switched: individual wires from machine to machine,
with many different wiring patterns in use.
• Multiprocessors (shared memory)
• Bus
• Switched
• Multicomputers (private memory)
• Bus
• Switched

36
Switched Multiprocessors

• Switched Multiprocessors
· for connecting large number (say over 64) of processors
· crossbar switch: n**2 switch points
· omega network: 2x2 switches for n CPUs and n memories, log n
switching stages, each with n/2 switches,
· total (n log n)/2 switches
· delay problem: E.g., n=1024, 10 switching stages from CPU to
memory. a total of 20 switching stages. 100 MIPS 10 nsec
instruction execution time need 0.5 nsec switching time
· NUMA (Non-Uniform Memory Access): placement of program and
data
· building a large, tightly-coupled, shared memory multiprocessor is
possible, but is difficult and expensive
38
Multicomputers
• Bus-Based Multicomputers
· easy to build
· communication volume much smaller
· relatively slow speed LAN (10-100 MIPS, compared to 300
MIPS and up for a backplane bus)

• Switched Multicomputers
· interconnection networks: E.g., grid, hypercube
· hypercube: n-dimensional cube

39
Software Concepts
• Software more important for users
• Three types:
1. Network Operating Systems
2. (True) Distributed Systems
3. Multiprocessor Time Sharing

40
Network Operating Systems
· loosely-coupled software on loosely-coupled
hardware
· A network of workstations connected by LAN
· each machine has a high degree of
autonomy
· Files servers: client and server model
· Clients mount directories on file servers
· Best known network OS:
o Sun’s NFS (network file servers) for shared file
systems
· a few system-wide requirements: format and
meaning of all the messages exchanged

41
NFS
• NFS Architecture
• Server exports directories
• Clients mount exported directories
• NSF Protocols
• For handling mounting
• For read/write: no open/close, stateless
• NSF Implementation

42
(True) Distributed Systems

 tightly-coupled software on loosely-coupled

hardware
 provide a single-system image or a virtual
uniprocessor
 a single, global interprocess communication
mechanism, process management, file system;
the same system call interface everywhere
 Ideal definition:
“ A distributed system runs on a collection of computers
that do not have shared memory, yet looks like a
single computer to its users.”

43
Multiprocessor Operating Systems

· Tightly-coupled software on tightly-coupled hardware

· Examples: high-performance servers
· shared memory
· single run queue
· traditional file system as on a single-processor system:
central block cache

44
Design Issues of Distributed Systems

• Transparency
• Flexibility
• Reliability
• Performance
• Scalability

45
1. Transparency
• How to achieve the single-system
image, i.e., how to make a collection of
computers appear as a single computer.
• Hiding all the distribution from the
users as well as the application
programs can be achieved at two
levels:
1) hide the distribution from users
2) at a lower level, make the system look
transparent to programs.
1) and 2) requires uniform interfaces such as
access to files, communication.

46
Types of transparency

– Location Transparency: users cannot tell where hardware and software resources
such as CPUs, printers, files, data bases are located.
– Migration Transparency: resources must be free to move from one location to
another without their names changed.
E.g., /usr/lee, /central/usr/lee
– Replication Transparency: OS can make additional copies of files and resources
without users noticing.
– Concurrency Transparency: The users are not aware of the existence of other
users. Need to allow multiple users to concurrently access the same resource. Lock
and unlock for mutual exclusion.
– Parallelism Transparency: Automatic use of parallelism without having to program
explicitly. The holy grail for distributed and parallel system designers.
• Users do not always want complete transparency: a fancy printer 1000 miles away

47
2. Flexibility

• Make it easier to change

• Monolithic Kernel: systems calls are trapped and
executed by the kernel. All system calls are served by
the kernel, e.g., UNIX.
• Microkernel: provides minimal services.
• 1) IPC
2) some memory management
3) some low-level process management and scheduling
4) low-level i/o
E.g., Mach can support multiple file systems, multiple
system interfaces.
48
3. Reliability

• Distributed system should be more reliable than single

system. Example: 3 machines with .95 probability of
being up. 1-.05**3 probability of being up.
– Availability: fraction of time the system is usable. Redundancy
improves it.
– Need to maintain consistency
– Need to be secure
– Fault tolerance: need to mask failures, recover from errors.

49
4. Performance

• Without gain on this, why bother with distributed

systems.
• Performance loss due to communication delays:
– fine-grain parallelism: high degree of interaction
– coarse-grain parallelism
• Performance loss due to making the system fault
tolerant.

50
5. Scalability

• Systems grow with time or become obsolete. Techniques that

require resources linearly in terms of the size of the system are
not scalable. e.g., broadcast based query won't work for large
distributed systems.
• Examples of bottlenecks
o Centralized components: a single mail server
o Centralized tables: a single URL address book
o Centralized algorithms: routing based on complete information

51
Communication Networks
• Computers are connected through a communication
network
• Wide Area Networks (WAN)
connect computers spread over a wide geographic area
point-to-point or store-and-forward -- data is transferred
between computers through a series of switches
switch -- a special purpose computer responsible for routing
data (to avoid network congestion)
data can be lost due to: switch crashes, communication link
failures, limited buffers at switches, transmission errors, etc.

52
• Packet Switching versus Circuit Switching
• i) circuit switching -- a dedicated path between a source and a
destination e.g., telephone connection.
wastes bandwidth (bandwidth = amount of data transmitted
in a given time period)
• ii) packet switching -- message or data is broken into packets
packets are routed independently
better network utilization
disassemble and assembler overheads
The ISO OSI Reference Model
• Local Area Networks (LAN)

53