Chapter Three

Processes

Introduction
Communication takes place between processes.
Process = Program in execution.
Process management and scheduling are crucial from OS perspective.
Other important issues arise in distributed systems.

• Multithreading for performance enhancement.

• Organization of clients and servers.
• Process or code migration for scalability and dynamic configuration of clients and
servers.

Threads and their Implementation

Threads can be used in both distributed and non-distributed systems.

Threads in Non-distributed Systems

A process includes an address space (containing program text and data), a single thread of
control, and additional resources like open files, child processes, accounting information, etc.
Threads within a process have individual program counters, registers, stacks, and states, while
sharing an address space, global variables, and resources like open files.
Threads take turns in running. It means that in a multitasking or multithreading environment,
different threads are scheduled and given the opportunity to execute their instructions one
after the other.
Threads enable concurrent execution within a single process environment, known as
multithreading.
Why do we need threads?
1. They simplify the programming model by handling multiple activities simultaneously.
2. They are easier to create and destroy compared to processes, as they do not have
attached resources.
3. Performance improves by overlapping activities, especially when heavy input/output
(I/O) is involved. This prevents blocking while waiting for input or performing
calculations, such as in a spreadsheet.
4. Real parallelism is possible in a multiprocessor system.
Using multiple threads per process (Having finer granularity) instead of processes improves
performance and simplifies building distributed applications.
Threads can replace processes in non-distributed systems, reducing context-switching overhead
in interprocess communication (IPC) by using shared data.
Thread Implementation
Threads are usually provided in the form of a thread package.
The thread package includes operations for creating and destroying threads and synchronization
variables like mutexes and condition variables.
Two approaches for constructing a thread package
a. Construct a user-mode thread library (executed entirely in user mode and the OS is not aware
of the threads)

• Cheap thread creation and destruction: Allocate and free memory only.
• Efficient context switching: Store and reload CPU register values with few instructions.
• Disadvantage: Blocking system calls can block the entire process and all its threads.
b. Implement them in the OS’s Kernel

• Kernel awareness and scheduling of threads.

• Thread operations (creation and deletion) are expensive due to system calls.
• Solution: Lightweight process (LWP) is a hybrid form that combines user-level and kernel-
level threads.
• LWPs run within a single heavy-weight process, allowing multiple LWPs per process.
• User-level thread package provides thread operations, and synchronization (mutexes,
condition variables).
• The thread package can be shared by multiple LWPs.

Threads in Distributed Systems

Multithreaded Clients
In a web browser, different page parts can be fetched using separate threads. Each thread can
open its TCP/IP connection to the server or replicated servers.
Results are displayed as each thread receives its part of the page.
Multithreaded Servers
Servers are constructed in three ways.
A. Single-Threaded Process
• Server request handling: Requests are processed one at a time, completing each before
moving to the next.
 • Server idle during disk reads: System calls for disk reads are blocking, causing the server
to wait.
B. Threads
• Threads are crucial for server implementation.
• Example: file server.
• The dispatcher thread handles incoming requests for file operations from clients and
forwards them to an available worker thread.
• The worker thread performs a blocking disk read, allowing other threads such as the
dispatcher or another worker thread to continue.
C. Finite-State Machine
- used when threads are not available.
- It gets a request, examines it, and tries to fulfill the request from the cache.
- If the request is not found in the cache, it sends a request to the file system.
- Instead of blocking, records the state of the current request and proceeds to the next request
without waiting for the file system response.
Summary
Model Characteristics
Single-Thread Process No parallelism, blocking system calls
Threads Parallelism, blocking system calls (thread
only)
Finite-state machine Parallelism, non-blocking system calls

Anatomy of Clients
There are two issues here.

A. User Interfaces
• Creating a user-server interaction environment for devices like mobile phones with
simple displays and keys.
• Graphical User Interfaces (GUIs) are commonly used.
• The X Window System (X) is a widely used system.
o X has the X kernel responsible for controlling the terminal (monitor, keyboard,
pointing device) and is hardware dependent.
o The X system includes terminal-specific device drivers accessed through the xlib
library.
 B. Client-Side Software for Distribution Transparency
• Client-server applications involve processing and data execution at the client side,
along with the user interface.
• Examples include embedded client software used in ATMs, cash registers, etc.
• Client software can also include components to achieve distribution transparency.
• E.g. Replication transparency
• In a distributed system with replicated servers, the client proxy can send requests
to multiple replicas.
• Client-side software can collect all the responses transparently and pass a single
return value back to the client application.
Client-side software can be used to achieve access transparency and failure transparency in a
system.

3.3 Servers and Design Issues

General Design Issues
A. How to Organize Servers?
Iterative Server
The server itself handles the request and returns the result.
Concurrent Server
• Concurrent server: A type of server that handles multiple requests simultaneously.
• It passes each request to a separate process or thread and waits for the next incoming
request.
• Examples include a multithreaded server, where each request is assigned to a separate
thread, or forking a new process in Unix to handle each request.
B. Where do clients contact a server?
• Clients contact a server using endpoints or ports on the machine where the server is
running. Each server listens to a specific endpoint.
• Clients can know the endpoint of a service through various means.
• Well-known services have globally assigned endpoints, such as FTP on TCP port 21 and
HTTP on TCP port 80.
• For services that don't require preassigned endpoints, the local operating system can
dynamically assign an available endpoint.
• Port numbers are divided into three ranges by the Internet Assigned Numbers Authority
(IANA).
✓ Well-known ports (0-1,023): IANA assigns and controls them for standard
services, like DNS using port 53.
✓ Registered ports (1,024-49,151): Not assigned or controlled by IANA, but can be
registered with IANA to avoid duplication. For example, MySQL uses port 3306.
 ✓ Dynamic ports or ephemeral ports (49,152-65,535): Neither controlled nor
registered by IANA. These ports are dynamically assigned by the operating
system for temporary connections.
The client can know the endpoint using two approaches.
Approach 1: Have a daemon running and listening to a well-known endpoint.
• This daemon keeps track of all endpoints of services on the collocated server.
• The client first contacts the daemon, which provides it with the endpoint information.
Then, the client can directly contact the specific server using the provided endpoint.
Approach 2: use a super server (common in UNIX systems) that listens to all endpoints.
• When a request arrives, the super server forks a process to handle the request, avoiding
the need for multiple servers running simultaneously with many of them being inactive.
C. Whether and how a server can be interrupted?
A user may want to interrupt a file transfer if it was the wrong file.

• Approach 1: The client can exit the client application, which will break the connection to
the server. The server, assuming that the client crashed, will then tear down the
connection.
• Approach 2: The client can send out-of-band data, which is processed by the server
before any other data from the client. The server may listen on a separate control
endpoint or receive it on the same connection as urgent data in TCP.
D. Whether or not the server is stateless
• Stateless server: Does not retain information about the state of its clients. For example,
a web server.
• Soft state: A server guarantees to maintain its state for a limited time. For instance, it
may keep a client informed about updates. After the specified time expires, the client
needs to poll for updates.
• Stateful server: Maintains information about its clients. For example, a file server that
allows clients to keep a local copy of a file and perform update operations.

Server Clusters
• It is a group of machines connected via a network, typically a LAN with high bandwidth
and low latency. Each machine runs one or more servers.
• The server cluster is logically divided into three tiers or layers.
✓ First Tier = Logical Switch (possibly multiple)
✓ Second Tier = Application/compute servers
✓ Third Tier = Distributed file/database system

Distributed Servers
• Problem with server clusters: If the logical switch or single access point fails, the entire
cluster becomes unavailable.
 • Solution: Multiple access points can be provided to ensure availability, where publicly
available addresses lead to a distributed server setup.
• Example: DNS (Domain Name System) can return multiple addresses for the same host
name, allowing clients to connect to different servers.

Code Migration
• Code migration involves transferring programs, even while they are running, across
heterogeneous systems.
• Communication previously focused on passing data, but now programs themselves can
be transferred.
• Code migration also includes moving associated data. When a program migrates while
running, its status, pending signals, and other environment variables such as the stack
and program counter need to be moved as well.

Reasons for Migrating Code

• Improving performance: Moving processes from heavily-loaded machines to lightly-
loaded machines to achieve load balancing.
• Reducing communication: Moving a client application that performs frequent database
operations to a server where the database resides. This way, only the results are sent
back to the client, minimizing communication.
• Exploiting parallelism: used in non-parallel programs. For example, multiple copies of a
mobile program, like a web crawler used in search engines, can be migrated from site to
site, allowing simultaneous searching of the web leveraging parallel processing.
• Flexibility in configuring distributed systems: Instead of a multi-tiered client-server
application deciding in advance where specific parts of a program should run,
dynamically configure the system to allocate program execution as needed.

Modes for Code Migration

A process consists of three segments:

• Code segment: Contains a set of instructions that make up the program.

• Resource segment: Holds references to external resources such as files and printers.
• Execution segment: Stores the current execution state of the process, including private
data, the stack, and the program counter.

Weak Mobility
• It involves transferring only the code segment and possibly some initialization data.
• In this case, a program always starts from its initial stage.
• Examples include Java Applets, where execution can occur either by the target process in
its own address space or by a separate process.
Strong Mobility
• It involves transferring both the code and execution segments of a process.
• Enables the migration of a process during execution.
• Can be supported by remote cloning, where an exact copy of the original process runs
on a different machine and executes in parallel.
• UNIX achieves this through forking a child process, creating a clone of the original
process.
Migration can occur in two ways:
- Sender-initiated migration: Initiated by the machine where the code resides or is
currently running.
o Examples include uploading programs to a server, which may require
authentication or verification that the client is registered.
- Receiver-initiated migration: Initiated by the target machine.
o Examples include Java Applets, which facilitate easier implementation of
migration from the server to the client machine.

Chapter Four
Naming

Introduction
• Names play a crucial role in:
o Sharing resources.
o Uniquely identifying entities.
o Referring to locations.
• Resolving a name to its corresponding entity is an important issue.
• To resolve names, a naming system needs to be implemented.
• In a distributed system, the implementation of a naming system is often distributed,
unlike in non-distributed systems.
• Efficiency and scalability of the naming system are the primary concerns.

1. Naming Entities
Names, Identifiers, and Addresses
• In a distributed system, a name is a string of bits or characters used to refer to an entity.
• An entity can be anything, such as hosts, printers, disks, files, objects, processes, or
users.
 • Entities can be operated on and offer interfaces with operations specific to them. For
example, a printer entity may offer operations for printing documents or requesting job
status.
• To interact with an entity, it is necessary to access it through its access point, which is
also an entity, typically a special one.

Access Point
• The name of an access point is known as an address, such as an IP address and port
number used by the transport layer.
• The address of an access point is also considered the address of the entity it belongs to.
• An entity can have multiple access points, similar to accessing an individual through
different telephone numbers.
• An entity may change its access point over time, for example, a mobile computer
obtaining a new IP address as it moves.

Address
• An address is a special kind of name.
• It refers to at most one entity.
• Each entity is referred to by at most one address, even in cases of replication, such as
with web pages.
• An entity may change its access point, or an access point may be reassigned to a
different entity, similar to how telephone numbers can be reassigned in offices.
• Separating the name of an entity from its address provides easier and more flexible
management. Such a name is known as location independent.

Identifier
• There are other types of names that uniquely identify an entity.
• An identifier is a name with the following properties:
o It refers to at most one entity.
o Each entity is referred to by at most one identifier.
o It always refers to the same entity and is never reused.
• Identifiers allow unambiguous reference to an entity.
• Examples of identifiers include
o the name of an FTP server,
o the URL of the FTP server,
o the address of the FTP server (IP number and port number), etc.
o The address of an FTP server may change over time.

2. Name Spaces and Name Resolution

• Names in a distributed system are organized into a namespace.
 • A namespace is typically structured as a labeled, directed graph with two types of
nodes.
o Leaf node: Represents the named entity and stores information such as its
address or state.
o Directory node: Special entity with outgoing edges labeled by names, leading
to other nodes in the namespace.
• Each node in a naming graph is considered another entity with an identifier.
• Directory nodes store a directory table, representing outgoing edges as pairs of edge
labels and node identifiers.
• Paths in a naming graph can be represented by a sequence of labels corresponding
to the edges and the identifier of the first node.
𝑁: < 𝐿𝑎𝑏𝑒𝑙1, 𝐿𝑎𝑏𝑒𝑙2, … . , 𝐿𝑎𝑏𝑒𝑙𝑛 >
Where N refers to the first node of the path
• This sequence is called a path name.
• If the first node is the root, it is an absolute path name; otherwise, it is a relative
path name.
• Path names can be represented using string notation, such as "/home/steen/mbox"
for the path name n0:<home, steen, mbox>.
• Multiple paths can lead to the same node, for example, node n5 can be represented
as "/keys" or "/home/steen/keys".
• The common approach for organizing names in a distributed system is to use a tree
structure, resembling a hierarchical file system.
• The tree structure is a directed acyclic graph, where each node except the root has
exactly one incoming edge, and the root has no incoming edges.
• Each node in the tree has an associated absolute path name, uniquely identifying its
location within the tree.
• This hierarchical naming scheme provides a clear and structured organization of
names within the system.

Resolution
• Name resolution refers to the process of looking up a stored name in a node by
following the given path name, ultimately finding the associated address.

Linking and Mounting

• Linking involves providing an additional name (alias) for the same entity. This can be
seen in UNIX environment variables like HOME, which refers to the user's home
directory.
• There are two types of links that can be used to implement aliases:
o Hard link: Enables multiple absolute path names to refer to the same node in a
naming graph. For example, in the previous graph, node n5 can be accessed
using two different path names: /keys and /home/steen/keys.
 o Symbolic link: In a symbolic link, an entity is represented by a leaf node. Instead
of storing the address or state of the entity, the node stores an absolute path
name.
• When resolving an absolute path name stored in a node (e.g., /home/steen/keys in node
n6) for the first time, the name resolution process will return the path name stored in
the node (/keys). The resolution can then continue by resolving the new path name
(/keys).
Name resolution within a single namespace has been discussed.
Name resolution can also be used to merge different name spaces transparently.
Two methods for merging name spaces are mounting and adding a new root node and making
the existing two nodes its children.
1. Mounting
• Mounting is demonstrated by a mounted file system but can be applied to other
namespaces as well.
• In mounting, a directory node stores the directory node from a different namespace.
• The directory node storing the node identifier is called a mount point.
• The directory node in the foreign namespace is called a mounting point, typically the
root of a namespace.
• During name resolution, the mounting point is located, and resolution proceeds by
accessing its directory table.
• A collection of namespaces is distributed across different machines.
• Mounting a foreign namespace in a distributed system (DS) requires certain information
like
o The name of an access protocol for communication.
o The name of the server hosting the foreign namespace.
o The name of the mounting point within the DS
• Each of these names needs to be resolved.
o To the implementation of the protocol.
o To an address where the server can be reached.
o to a node identifier in the foreign name space.
• These three names can be listed together as a URL.
Example

• Sun's Network File System (NFS) is an example of a distributed file system.

• NFS utilizes a protocol that enables clients to access files stored on remote NFS file
servers.
• An NFS URL follows the format nfs://flits.cs.vu.nl/home/steen.
• nfs represents the protocol used for communication.
 • flits.cs.vu.nl is the server’s name, which is resolved using DNS.
• /home/steen is resolved by the server and refers to a specific file or directory.
• The /remote subdirectory includes mount points for foreign name spaces on the client
machine.
• The directory node /remote/vu stores the NFS URL nfs://flits.cs.vu.nl/home/steen.
• When resolving the name /remote/vu/mbox, the process starts at the client's root
directory and progresses until reaching node /remote/vu.
• Node /remote/vu returns the NFS URL nfs://flits.cs.vu.nl/home/steen.
• The client machine contacts flits.cs.vu.nl using the NFS protocol.
• Finally, the file mbox is read from the directory /home/steen.
• Distributed systems that support remote file system mounting also provide the ability to
execute commands.
• Example command: cd /remote/vu
• When executing this command, the user doesn't need to be concerned with the
underlying details of the actual access.
• The name space on the local machine and the name space on the remote machine
appear to form a unified or single name space.
2. Add a new root node and make the existing root nodes its children
• This method is used in GNS (Global Name Service by DEC) to merge different name
spaces.
• The problem with this method is that existing names need to be changed.
• For example, the absolute path name /home/steen would now become a relative path
name, corresponding to the absolute path name /vu/home/steen.
• The system needs to translate or expand the path name /home/steen to
/vu/home/steen without users being aware of the change.
• To accomplish this, a mapping table is stored with entries such as n0 -> vu when a new
root node is added.
• However, merging a large number of namespaces can result in performance issues.

The implementation of a namespace

• A namespace is the core component of a naming service.
• A naming service allows users and processes to add, remove, and look up names.
• Name servers are responsible for implementing the naming service.
• In a distributed system on a single LAN, a single server might be sufficient. However, for
a large-scale distributed system, the implementation of a name space is distributed
across multiple name servers.

Name space distribution

• It is necessary in large-scale distributed systems and is often organized hierarchically.
• A name service can be partitioned into logical layers.
 • Three layers that can be distinguished in a name service are outlined by Cheriton and
Mann.
Global Layer
• Consists of the highest-level nodes in the name space hierarchy, including the root node
and its immediate children.
• These nodes are known for their stability, meaning that their directory tables are rarely
modified.
• Represents organizations, groups of organizations, or other entities where names are
stored in the name space.
Administrational Layer
• Comprises groups of entities belonging to the same organization or administrative unit,
such as departments within an organization.
• This layer is relatively stable, with infrequent changes to its nodes.
Managerial Layer
• Consists of nodes that can undergo regular changes.
• Nodes in this layer represent hosts within a local area network (LAN), shared files like
libraries or binaries, and similar resources.
• Both system administrators and end users can manage these nodes, leading to more
dynamic changes compared to the global and administrational layers.
• The namespace is divided into nonoverlapping parts called zones in DNS.
• Each zone is implemented by a separate name server.
• Server requirements at different layers:
o Performance (responsiveness to lookups), availability (failure rate), etc.
o High availability is critical for the global layer as name resolution cannot proceed
beyond a failing server. It is also important at the administrational layer for
clients within the same organization.
o Performance is crucial in the lowest layer due to the ability to cache and reuse
lookup results, given the relative stability of higher layers.
o Client-side caching can enhance performance and is particularly useful in the
global and administrational layers where names change infrequently.
o Replication and inconsistency problems: Replication and caching introduce
implementation challenges as they may lead to potential inconsistency issues.

Implementation of Name Resolution

Name Resolution is the process of finding the address when the name is given.
Assumption that name servers are not replicated and client-side caches are not allowed.
Local name resolver: Each client has a local name resolver responsible for carrying out the name
resolution process.
Example: An example path name is given as
root: < nl, vu, cs, ftp, pub, globe, index. txt > or

𝑓𝑡𝑝:// 𝑓𝑡𝑝. 𝑐𝑠. 𝑣𝑢. 𝑛𝑙/𝑝𝑢𝑏/𝑔𝑙𝑜𝑏𝑒/𝑖𝑛𝑑𝑒𝑥. 𝑡𝑥𝑡 in URL notation.

The two ways of implementing name resolution
A. Iterative Name Resolution
• The name resolver passes the complete name to the root name server.
• The root server resolves the name as much as possible and returns the result to the
client. It can at least resolve the first level and provides the name of the first-level name
server to the client.
• The client contacts the first level name server and proceeds to call the following name
servers until it finds the address of the entity being resolved.
B. Recursive Name Resolution
• The name resolver provides the complete name to the root name server.
• The root server attempts to resolve the name. If it cannot resolve it, it requests the first
level name server to resolve it and returns the address.
• The first level name server performs the same process recursively, contacting
subsequent name servers until the address of the entity is obtained.
Advantages and Drawbacks
• Iterative name resolution is less demanding on individual name servers in terms of
performance compared to recursive resolution, making it suitable for name servers in
the global layer.
• Recursive resolution allows for more effective caching as each name server learns the
addresses of lower-level name servers over time. This enables efficient handling of
lookup operations.
Server for Should Looks Up Passes to Receives and Returns to
Node Resolve child caches requester
cs <ftp> #<ftp> --- --- #<ftp>
vu <cs,ftp> #<cs> <ftp> #<ftp> #<cs>
#<cs,ftp>
nl <vu,cs,ftp> #<vu> <cs,ftp> #<cs> #<vu>
#<cs,ftp> #<vu,cs>
#<vu,cs,ftp>
 root <nl,vu,cs,ftp> #<nl> <vu,cs,ftp> #<vu> #<nl>
#<vu,cs> #<nl,vu>
#<vu,cs,ftp> #<nl,vu,cs>
#<nl,vu,cs,ftp>

Communication costs may be reduced in recursive name resolution.

Summary
Method Advantage(s)
Recursive Less Communication cost, Caching is more
effective
Iterative Less Performance demand on name servers
Example 1 - The Domain Name System (DNS)

• Internet DNS is one of the largest distributed naming services.

• DNS is primarily used for looking up host addresses and mail servers.
• DNS follows a hierarchical structure with an inverted tree, where the root is at the top.
• The DNS tree can have a maximum of 128 levels.

Chapter Five
Clock Synchronization

Introduction
• Apart from communication, processes cooperate and synchronize through various
mechanisms.
• Naming plays a role in facilitating cooperation by allowing processes to share resources
or entities.
• Synchronization is concerned with ensuring that processes do not simultaneously access
a shared resource and that events occur in a defined order, such as when two processes
exchange messages.

What is Synchronization?
• Synchronization refers to the process of coordinating or aligning two or more items to
work together or have the same state.
 • An example of synchronization is adjusting two watches to display the same time,
ensuring they are in sync.
• In the context of computers, synchronization involves transferring data between two or
more devices to ensure they have the same information or state.
• It is common to synchronize data between computers or devices to maintain consistency
when running programs or sharing information.

1. Clock Synchronization
• In centralized systems, time can be reliably determined through a system call.
• For example, if process A retrieves the time at time t1 and obtains tA, and process B
retrieves the time at time t2 (where t1 < t2) and obtains tB, it is guaranteed that tA will
always be less than tB.
• Achieving agreement on time in distributed systems is challenging due to factors like
network latency and clock drift.
• For instance, consider the "make" program on a UNIX machine, which only compiles
source files if their last update time is later than that of the corresponding object file.

Physical Clocks
• It is not possible to synchronize all clocks in a distributed system.
• Clock skew occurs as the crystals in different computers run at different frequencies,
causing clocks to drift out of sync over time.
Measurement of Time
• Historically, time was measured astronomically based on the Earth's rotation around the
Sun.
• One solar second is equivalent to 1/86400th of a solar day (24 * 3600 = 86400).
• It was discovered that the Earth's rotation period is not constant, as factors like tidal
friction and atmospheric drag affect its speed.
• Astronomical timekeeping was replaced by counting transitions of the cesium 133 atom,
leading to International Atomic Time (TAI).
• TAI lags behind a solar day by 3 milliseconds due to the increasing length of the day.
• UTC was created to address this issue, introducing leap seconds when the discrepancy
between TAI and solar time reaches 800 milliseconds.
• UTC replaced GMT as the standard time reference.
• UTC is broadcasted in some countries via shortwave radio and satellites, but users must
consider propagation delay when compensating for precise time synchronization.

Clock Synchronization Algorithms

• Clock synchronization algorithms aim to address the synchronization of time among
machines.
• In the situation where one machine has a receiver of UTC time, algorithms are designed
to synchronize all other machines to it.
 • In the scenario where no machine has a receiver and each machine keeps track of its
own time, algorithms are developed to synchronize them.
• Many algorithms have been proposed to handle these situations and other related
scenarios of clock synchronization.
• A model is used as a basis for all clock synchronization algorithms.
• Each machine in the system has a timer that generates ticks H times per second or
causes an interrupt.
• The interrupt handler adds 1 to the software clock, resulting in a value C representing
the current time.
• In an ideal scenario, if the UTC time is t, the value of the clock on machine p should be
Cp(t), ideally equal to t (Cp(t) = t) or with a derivative dC/dt = 1.
• However, in practice, there are errors and deviations from ideal behavior. The clock may
tick faster or slower than expected.
• The maximum drift rate, denoted as p, represents the allowed range of clock skew: 1 - p
≤ dC/dt ≤ 1 + p.
• The maximum drift rate is set by the manufacturer and determines the extent to which a
clock's skew is allowed to fluctuate.
• Clocks can be categorized as
o slow (ticks slower than expected) or dC/dt<1
o perfect (ticks exactly as expected) or dC/dt = 1
o fast (ticks faster than expected) or dC/dt>1
• If two clocks are drifting in opposite directions, after a time ∆t since they were
synchronized, they may differ by as much as 2ρ∆t.
• To ensure that no two clocks differ by more than δ, clocks must be synchronized at least
every δ/2ρ seconds.
• The question arises: How is clock synchronization achieved?
Cristian's Algorithm
• Cristian's Algorithm is suitable when one machine has a UTC receiver, which is referred
to as the time server.
• In this algorithm, each machine sends a message to the time server, requesting the
current time, but no more frequently than every δ/2ρ seconds.
• - The first approximation is for the client to set its clock to CUTC (Coordinated Universal
Time).
• There are problems associated with this approach.
• One problem is the message propagation time.
• The solution is to estimate the message propagation time as (T1-T0)/2 and add it to CUTC.
• If we have knowledge of the time it takes for the time server to handle the interrupt, we
can improve the estimation. Let the interrupt handling time be I, then the new estimate
will be (T1-T0-I)/2.
• It is essential to ensure that time never runs backward.
 • The solution is to introduce changes gradually. For example, if a timer is set to generate
100 interrupts per second, and 10 milliseconds must be added to the time, it can be
done by gradually adjusting it to 9 milliseconds (to slow it down) or 11 milliseconds (to
advance it gradually).
Berkley’s Algorithm
• In Cristian's algorithm, the time server is passive and only responds to requests from
other machines.
• In Berkley UNIX, a time daemon actively asks each machine for its time periodically.
• The time daemon calculates the average time and sends messages to all machines to
adjust their clocks accordingly.
• The Berkley Algorithm is suitable when no machine has a UTC receiver.
• The time daemon's time needs to be set manually periodically in this algorithm.
- There are various other clock synchronization algorithms apart from Cristian's and Berkley's
algorithms.
- Averaging algorithms, like the Network Time Protocol (NTP) used in the Internet, are
decentralized and involve multiple external time sources for achieving high accuracy.

2. Logical Clocks
• Logical clocks are used in applications where the internal consistency of clocks is more
important than being synchronized with real time.
• The concept of logical clocks focuses on internal consistency rather than real-time
accuracy.

Lamport Timestamps
• It is a logical clock algorithm proposed by Lamport.
• Lamport introduced the "happens before" relation, denoted as a -> b, which signifies
that event a occurs before event b.
• The "happens before" relation holds true when events a and b occur in the same process
and a precedes b, or when a message is sent by one process and received by another
process.
• The "happens before" relation is transitive, meaning if A -> B, and B -> C, then A -> C.
• If two events, X and Y, occur in different processes that do not exchange messages, then
both X -> Y and Y -> X are not true. These events are considered concurrent, and their
order cannot be determined.
• Each event can be assigned a time value C(a) that all processes agree upon. If A -> B,
then C(a) < C(b).
• Lamport proposed an algorithm for assigning times to processes.
• The algorithm considers three processes running on different machines, each with its
own clock.
 • The solution is based on the happens before relation.
• Each message carries the sending time, and if the receiver's clock shows a value prior to
the time the message was sent, the receiver fast forwards its clock to be one more than
the sending time.
Additional requirements
• Between two events, the clock must tick at least once. If a process sends or receives two
messages in succession, its clock must advance by one tick.
• No two events must occur at exactly the same time. If this happens, the number of the
process is attached to differentiate them. For example, events happening in processes 1
and 2 at time 40 would be represented as 40.1 and 40.2.
• Assigning time to events in a distributed system is subject to the following conditions:
1. If a -> b in the same process, then C(a) < C(b).
2. If a represents the sending of a message and b represents the receiving of that message,
then C(a) < C(b).
3. For all distinct events a and b, C(a) ≠ C(b).
• Example: Totally-Ordered Multicasting
• Consider a bank database replicated across multiple cities for performance reasons.
Queries are forwarded to the nearest copy.
• Let's assume a customer in city A with $1000 in her account wants to add $100 to her
account (update 1) while a bank employee in city B initiates an update of increasing all
accounts by 1% interest (update 2).
• Both updates need to be carried out at all copies of the database.
• Due to communication delays, if the updates are performed in a different order at
different locations, the database will become inconsistent (e.g., city A = $1111, city B =
$1110).
• Situations like these require Totally-Ordered Multicast, where all messages are delivered
in the same order to each receiver.
• Lamport timestamps can be used to implement totally-ordered multicasts.
• Each message is timestamped.
• During multicasting, a message is also sent to the sender.
• Messages from the same sender are received in the order they are sent, assuming no
message is lost. All messages are put in a local queue ordered by timestamp.
• Each receiver multicasts an acknowledgement.
• Eventually, all processes will have the same copy of the local queue.
• A process can deliver a queued message to the application it is running only when that
message is at the top of the queue and has been acknowledged by each other process.
Vector Timestamps
Vector timestamps enable capturing both the total ordering and causality of events in
distributed systems.
With Lamport timestamps a → b does not necessarily mean a happens before b; only that all
processes agree; but they ensure total ordering
Unlike Lamport timestamps, which only ensure total ordering agreed upon by all processes,
vector timestamps provide information about the causal relationships between events.

Mutual Exclusion
• In distributed systems, mutual exclusion is used to ensure that only one process can
access shared data or resources at a time.
• In single-processor systems, mutual exclusion is achieved using constructs like
semaphores and monitors.
• In distributed systems, different algorithms are used to implement mutual exclusion and
protect critical regions.
• Three commonly used algorithms for achieving mutual exclusion in distributed systems
are centralized, distributed, and token ring.
Centralized Algorithm
• The centralized algorithm involves appointing a coordinator responsible for granting
permissions to access critical regions.
• Three messages are required: request, grant, release
a) Process 1 requests permission from the coordinator to enter a critical region and
receives the grant.
b) Process 2 requests permission to enter the same critical region but does not receive an
immediate response. It is blocked and queued by the coordinator.
c) When Process 1 exits the critical region, it notifies the coordinator, who then responds
to Process 2, granting it permission to enter the critical region.
• The algorithm
o guarantees mutual exclusion.
o It ensures fairness by following a first-come, first-served approach.
o There is no starvation in this algorithm.
o Implementation is easy, requiring only three messages: request, grant, release.
• Shortcoming: A failure of the coordinator can crash the system, especially if processes
block after sending a request. It also becomes a performance bottleneck.
A Distributed Algorithm
• It assumes a total ordering of events in the system, such as using Lamport timestamps.
• When a process wants to enter a critical region, it sends a message to everyone
containing the critical region's name, its process number, and the current time to all
processes, including itself.
• Message sending is assumed to be reliable, and every message is acknowledged.
• When a process receives a request message:
 1. If the receiver is not in a critical region and does not want to enter it, it sends back an OK
message to the sender.
2. If the receiver is already in the critical region, it queues the request without replying.
3. If the receiver wants to enter the critical region but has not yet done so, it compares the
timestamp of the incoming message with its own. The lowest timestamp wins. If the
incoming message has a lower timestamp, it sends an OK message; otherwise, it queues
the incoming message and doesn’t do anything.
• When the sender receives replies from all processes, it can enter the critical region.
• When the sender finishes, it sends an OK message to all processes in its queue.
• It is not possible for two processes to enter the critical region at the same time if they
initiate a message at the same time.
• Mutual exclusion is guaranteed.
• The total number of messages required to enter a critical region increases to 2(n-1),
where n is the number of processes.
• There is no single point of failure, but there are n points of failure.
• The algorithm introduces n bottlenecks.
• It is slower, more complicated, more expensive, and less robust than the previous
algorithm, but it demonstrates the possibility of a distributed algorithm.
A Token Ring Algorithm
• It assumes a bus network (e.g., Ethernet) where no physical ordering of processes is
required, but a logical ring is constructed by software.

4. Election Algorithms
• There are situations where one process must act as a coordinator, initiator, or perform a
special task.
• Assume that
o Each process has a unique number.
o Every process knows the process number of every other process, but not their
current state (running or down).
• Election algorithms are used to locate the process with the highest process number.
• Two algorithms commonly used for this purpose are the Bully algorithm and the Ring
algorithm.

The Bully Algorithm (the biggest person wins)

• When a process (P4) detects that the coordinator is unresponsive, it initiates an election.
1. P4 sends an ELECTION message to all processes with higher numbers (P5, P6, P7).
2. If a process receives an ELECTION message from a lower-numbered process, it sends an
OK message and starts its own election.
3. If no response is received, P4 wins the election and becomes the coordinator.
4. If a higher-numbered process responds, it takes over as the new coordinator.
• The last process to win the election will send a message to all processes declaring itself
as the coordinator.
• If a previously down process comes back online, it will initiate an election.
CHAPTER THREE

PROCESSES
INTRODUCTION
THREADS AND THEIR IMPLEMENTATION
THREADS IN NON-DISTRIBUTED SYSTEMS
Why do we need threads?
Thread Implementation
THREADS IN DISTRIBUTED SYSTEMS
Multithreaded Clients
Multithreaded Servers
A. Single-Threaded Process
B. Threads
C. Finite-State Machine
Summary
ANATOMY OF CLIENTS
A. USER INTERFACES
B. CLIENT-SIDE SOFTWARE FOR DISTRIBUTION TRANSPARENCY
3.3 SERVERS AND DESIGN ISSUES
GENERAL DESIGN ISSUES
A. How to Organize Servers?
Iterative Server
Concurrent Server
B. Where do clients contact a server?
The client can know the endpoint using two approaches.
C. Whether and how a server can be interrupted?
D. Whether or not the server is stateless
SERVER CLUSTERS
DISTRIBUTED SERVERS
CODE MIGRATION
REASONS FOR MIGRATING CODE
MODES FOR CODE MIGRATION
WEAK MOBILITY
STRONG MOBILITY

CHAPTER FOUR

NAMING
INTRODUCTION
1. NAMING ENTITIES
NAMES, IDENTIFIERS, AND ADDRESSES
ACCESS POINT
ADDRESS
IDENTIFIER
2. NAME SPACES AND NAME RESOLUTION
RESOLUTION
LINKING AND MOUNTING
1. Mounting
2. Add a new root node and make the existing root nodes its children
THE IMPLEMENTATION OF A NAMESPACE
NAME SPACE DISTRIBUTION
Global Layer
Administrational Layer
Managerial Layer
IMPLEMENTATION OF NAME RESOLUTION
A. Iterative Name Resolution
B. Recursive Name Resolution
Advantages and Drawbacks
Summary

CHAPTER FIVE

CLOCK SYNCHRONIZATION
INTRODUCTION
WHAT IS SYNCHRONIZATION?
1. CLOCK SYNCHRONIZATION
PHYSICAL CLOCKS
Measurement of Time
CLOCK SYNCHRONIZATION ALGORITHMS
Cristian's Algorithm
Berkley’s Algorithm
2. LOGICAL CLOCKS
LAMPORT TIMESTAMPS
Additional requirements
Vector Timestamps
MUTUAL EXCLUSION
Centralized Algorithm
A Distributed Algorithm
A Token Ring Algorithm
4. ELECTION ALGORITHMS
THE BULLY ALGORITHM (THE BIGGEST PERSON WINS)