******************************
Least Recently used (LRU)
Dining Philosophy
******************************
Distributed Systems
A collection of 【autonomous computers】 linked by a 【computer network】, and 【communicate and coordinate】 their actions only by message passing.
Centralization Disadvantage:
--Communications Bottleneck
--Single Point Failure
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
Basic Design Issues
Scalability
Load Balance
Fault Tolerance
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
Difficulties:
Concurrency(Interference)
Fault Tolerance(Domino effect in failures)
Scalability
Platform Heterogeneity(portability)
Lack of Global Knowledge
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~ Lack of Global Knowledge ~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1.
Leader election: how to efficiently elect a leader among a
set of processes?
--Problem application:
----Token generation
----Coordinator election
2.
Image a group of people in a wide field that can
communicate with each other only via cell phones.
--How to elect a leader among them given that
----Some may “fail” unexpectedly
--How to evaluate a solution?
----# of calls made
----How fast can a leader be elected
----Any other criterion?
3.
How to cope with arbitrary failure (Byzantine failures)?
--Each component proposes some value, say, 0 or 1
--How do they agree on the final system outcome?
----Applications: highly secure systems
Lack of Global Clock
--Physical clock
----Need precise clock synchronization to keep time in sync
--Logical clock
----Need clock synchronization to reflect “causal ordering”
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Distributed Systems vs. Parallel Systems
Loosely coupled vs. tightly coupled
Asynchrony vs. Synchrony
Coarse-grained parallelism vs. fine-grained parallelism
Scale up & Scale out
Both are limited by Amdahl's Law.
Amdahl’s Law
α: Proportion of a program can paralleled.
N: processor_num
1
Speeup= ------------- => max_speedup = 1/(1-α)
(1-α) + α/N
Scale out:
Load Balance (distribute workload evenly)
--Concern CPU clocks, Bandwidth, Storage
Cluster: a group of 【Tightly Coupled】 computers
Clusters VS Grids
Cluster
--Tightly coupled
--Typically homogeneous
--Nodes are typically dedicated to the cluster
----Single system image
----Centralized Job management & scheduling system
Grids:
--Loosely coupled
--Typically heterogeneous
--Nodes can run their own apps, and the gird uses their spare CPU time or computing resources
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Part2
