The scope of this document is limited to the study of placement of following services in Mach, V Distributed System, Denali, XEN and UNIX Systems
• File System
• Scheduling
• Communication
• Memory Management
System Design Problems
Unique User ID
Design a system to generate unique id for 1 billion user in distributed system
Mean and Median
You are given say 20 nodes in a distributed system and each node have 1 billion numbers. Find mean and median. You can have some other nodes for co-ordination.
Mean = (sum of all the numbers) / total numbers
Median = Mid element in sorted sequence
For example
Input = [2, 3, 4, 1]
Mean = (2+3+4+1) / 4 =2.5
For median sorted sequence is [1, 2, 3, 4]. Median is 2 or 3.
Reading List
Now Reading/Listening
Follow Vaibhav Gautam’s board Now Reading/Listening on Pinterest.
Naming in Distributed Systems
Introduction
The scope of this post is limited to the study of naming systems for following system
• Directory Service for Wide Area
• File system or Content manage system for collaborative work
Naming can be categorized into four kinds
1. Host based naming
2. Global naming
3. User/Objet centered naming
4. Attribute based naming
Context Switch
- Message Passing
- Remote Procedure Calls (RPC)
- Lightweight Remote Procedure Call
- Distributed Shared Memory – IVY
- Further reading
The scope of this post is limited to the study of context switches in various communication and synchronization primitives in distributed systems mainly focus on following:
• Message Passing
• Remote Procedure Calls (RPC)
• Light weight Procedure Calls (LRPC)
• Distributed Shared Memory (DSM)
Scale in Distributed Systems
- Introduction
- Systems designed to Scale
- Naming and Directory Services
- Security Subsystem
- Remote resources
- Replication
- Distribution
- Other topics in distributed systems
Introduction
This blog is summary of the research paper Scale in Distributed Systems.
A system is Scalable if it can handle addition of users and resources without suffering a noticeable loss of performance or increase in administrative complexity.
Systems designed to Scale
Some historic systems desgined to scale
D3.js and Octopress
This article is about how to use versatile D3.js with Octopress.
Recently I was looking for flow chart diagram or tree structure diagram, but I did not want to produce static image diagrams using Microsoft Vizio or similar softwares.
My requirement was to come up with tree structure data representation, which I could change in future unlike static pictures and can not be changed in future.
I found D3.js to be perfect for this scenario. Here, I store data in JSON file and I use D3.js to display that data according to my needs.
Array and Strings
- Array Problems
- Sum of 2 numbers
- Sum of 2 numbers greater or equal to given sum*
- Sum of 3 numbers*
- Find repeating/duplicate numbers*
- Find the number when size of array is unknown*
- Merge two sorted array
- Merge 2 non sorted array and remove duplicates
- Sort array based on count
- Find odd number of occurrence
- Find 2 numbers with odd occurence
- Searching an Element in a Rotated Sorted Array
- Largest Sum Contiguous Subarray
- Permute numbers
- String Problems
Array Problems
Sum of 2 numbers
We are given a sorted array A of length n and a value k. We want to find out if there are indices i, j such that A[i] + A[j] == k.
Give a Θ(n) way of solving this problem. Prove its running time and correctness.
Your algorithm should also output one pair of indices i, j such that A[i] + A[j] == k (if at least one pair exists; if multiple exist, you only need to output one of them).
Other variant of the same problem
When array is not sorted
We need to find pair of numbers in an array whose sum is equal to a given value.
Input [6,4,5,7,9,1,2]
Sum = 10
Then the pairs are [6,4] , [9,1]
Graph Algorithms
Graph problems
Find neighbour in array
Find all the neighbours of a given element in array
Neighbours can be defined as
- Neighbours are only vertical and horizontal elements next to given element
- Neighbours are only vertical, horizontal and diagonal elements next to given element
- Neighbours are all vertical, horizontal and diagonal elements next to given element
Scalability in Distributed Systems
This article is about Scalability in Distributed Systems and various engineering organizations approaching the problem of Scalability..
scalability
In electronics (including hardware, communication and software), scalability is the ability of a system, network, or process to handle a growing amount of work in a capable manner or its ability to be enlarged to accommodate that growth. For example, it can refer to the capability of a system to increase total throughput under an increased load when resources (typically hardware) are added. An analogous meaning is implied when the word is used in an economic context, where scalability of a company implies that the underlying business model offers the potential for economic growth within the company.