CSE138 Lecture 2  Notes
Tags: distributedsystems
Published: 2020-04-25 04:26:57

---
title: CSE138 Lecture 2  Notes
published: true
date: 2020-04-19 06:07:41 UTC
tags: distributed-systems
canonical_url: 
---

### CSE138 Lecture 2 Notes

### What is a Distributed System ?

According to Leslie Lamport:

> A system where I can’t get my work done because some computer which I never heard of crashed.

According to Martin Kleppmann:

> A system running on several nodes and characterised by _partial failures._

#### What is Partial Failure ?

- Machine crashing
- Network failure
- Messages being dropped
- Software misbehaviour

> _Part of the computation happened while another don’t._

In the event of such failure, you don’t want the system to degrade in the case of partial failure. Your system must continue working.

#### Cloud Computing vs HPC Philosophy

HPC Philosophy:

_Choosing to take partial failure as total failure i.e. if something does fail, it will start the computation over completely from scratch. It involves the process of checkpointing (every so often it saves the progress and if the failure happens, it will rollback to the last checkpoint)._

Cloud Computing Philosophy:

_It involves working around such partial failures and expecting those kinds of failures._

#### Two Nodes Scenario

![](https://cdn-images-1.medium.com/max/1024/1*EgwnP-Wwr3id7Y4ZNtgTdg.png)<figcaption>System of two machines</figcaption>

Possible Failure Scenarios:

- Request from _Machine A_ gets lost: maybe someone removed the cable.
- Request from _Machine A_ is slow and _Machine B_ never receives it: network congestion or some sort of message queue either on _Machine A_ side or _Machine B_ side. _Machine A_ thought that it sent the request but _Machine B_ never received it.
- _Machine B_ crashed: _Machine A_ sent the message and _Machine B_ received the message and crashed.
- _Machine B_ is slow in precessing.
- Response from _Machine B_ is slow and _Machine A_ never receives it.
- Response from _Machine B_ gets lost.

Does _Machine A_ has any way to distinguish any of the three situations ? No.

> If you send a request to another machine and don’t receive a response, it is impossible to know WHY (without having global knowledge of the system).

Other possible failure scenarios:

- _Machine B_ is lying or refusing to answer.
- Cosmic Rays flipping the bits.

These kinds of scenarios are called [Byzantine Faults](https://en.wikipedia.org/wiki/Byzantine_fault).

How do real systems deal with it ?

- When a machine sends a message, it needs to have some sort of timeout which means if the message has no response, give up and assume failure.

Why it might be a mistake to assume failure due to timeout ?

![](https://cdn-images-1.medium.com/max/1024/1*rNBjv_0AY7y3LsVJmkHD0w.png)<figcaption>System of two machines</figcaption>

In this case, there is a possible that value of x is incremented twice because _Machine A_ asked _Machine B_ to increment the value of x twice because it never got _ok_ for the first message and timeout happened.

Let assume the following:

Maximum delay between _Machine A_ and _Machine B (and vice-versa)_ is  **_d_**

Maximum time processing a request is  **_r_**

How long should _Machine A_ waiting ? **_2d + r_**

It will rule out the uncertainties due to slowness but still leaves other kinds of uncertainties which we need to deal with. Further more, most of the time we don’t have this sort of guarantee of maximum delay, sometimes we make assumptions about this maximum delay.

According to Prof. Peter Alvaro:

> In distributed systems, not only do we have to deal with partial failures but we also have to deal with unbounded latency.

#### Why do we want to have a distributed system ?

- Data too big to fit on a single machine.
- You want things to be faster even though the data can fit on a single machine.

### Time and Clocks

#### What are clocks for ?

- _Mark points in time_: Eg. this item in my browser will expire on April 10, 2020 at 08:00 hours.
- _Durations or Intervals of time:_ Eg. this user spent 4 minutes and 55 seconds on our websites.

Computers have two types of clocks:

- _time-of-day clocks_: tells you what time it is. It is usually synchronised between machines using NTP (network time protocol). They are bad for measuring _durations or intervals_ because time-of-day clocks can jump backward due to daylight savings or leap seconds. They are okayish (but not good) for _marking points in time_ because clock synchronisation is only so good and we need more fine-grained resolution to prevent certain kinds of bugs. Hence we aren’t going to use them much in distributed systems.
- _monotonic clocks:_ they always go further i.e. its certain kind of timer, maybe it counts the milliseconds since the machine restarted. In python, if you use [time](https://docs.python.org/3/library/time.html) module, you can get the monotonic counter. It’s completely useless for _marking points in time_ but it’s good for measuring _duration or intervals of time._ We can use these types of clocks to implement _timeouts._

Checkout [Cloudflare Blog on Leap Second](https://blog.cloudflare.com/how-and-why-the-leap-second-affected-cloudflare-dns/). They tried implementing timeouts using time-of-day clock.

Both of these kinds of clocks are **physical clocks** but in distributed systems, we need to have a different notion of clocks which are **logical clocks.** Logical clocks don’t measure the time-of-day and elapsed time, instead they only measure the ordering of events (which events happened before another).

Suppose A happened before B.

A — — — → B

What does it tells us ?

- A _could_ have caused B.
- B _could not_ have caused A.

This notion of potential causality is very important. Why ?

- Debugging: Figuring out possible causes of bug.
- Designing systems.

#### Resources:

- [Lecture Video](https://www.youtube.com/watch?v=G0wpsacaYpE)

_Thank you Prof. Lindsey Kuper for keeping the lectures online._