0% found this document useful (0 votes)

70 views

Distributed Systems in Erlang

The document describes a set of assignments for distributed systems courses that involve implementing distributed algorithms and systems using Erlang, including assignments to build a distributed prime number finder, web server, name server, routing protocol, failure detector, media streaming network, logical time logger, distributed game, total order multicast service, mutual exclusion lock, group membership service, snapshot algorithm, garbage collector, transaction systems, and distributed hash table. The assignments are meant to exemplify different aspects of distributed systems through hands-on implementation.

Uploaded by

Trung Nguyễn Thành

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

70 views

Distributed Systems in Erlang

Uploaded by

Trung Nguyễn Thành

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 5

Distributed Systems in Erlang

These are a set of assignments that I have used in several courses in Distributed
Systems. They have been used to exemplify systems, algorithms, or aspects such as
performance and fault tolerance.

The students have had a week of half-time study to complete the assignments and write
a small report on their findings. After handing in the reports each assignment is discussed
during a seminar where one can also extend the system or do experiments using more
computers.

The assignments assume a basic understanding of Erlang, but I've deliberately used a
limited set of Erlang functionality. I have not used OTP since I think that this will hide
complexity or, for many of the smaller assignments, add too much code. Nor do I use
some libraries that handle group communication or global registry. The aim is often for
the students to develop these themselves and better understand the pros and cons of
different strategies.

All assignments work in progress and are likely to change in the future. All assignments
are licensed under Creative Commons Attribution.

An Erlang primer
This is not a crash course in Erlang since there are plenty of tutorials available on the
web. I will, however, describe the tools that you need so that you can get a programming
environment up and running. I will take for granted that you know some programming
languages, have heard of functional programming, and that recursion is not a mystery to
you.

• crash.pdf

Primy: finding a large prime

Your task will be to implement a distributed system that will find large primes. The system
should have one server that is in control of the computation and a dynamic set of workers
that are assigned numbers to test for primarity.

• primy.pdf

Rudy: a small web server

Your task is to implement a small web server in Erlang. The aim of this exercise is that
you should be able to: describe the procedures for using a socket API, describe the
structure of a server process and describe the HTTP protocol. As a side effect you will
also learn how to use do some Erlang programming.
• rudy.pdf

Namy: a distributed name server

Your task will be to implement a distributed name server similar to DNS. Instead of
addresses we will store process identifiers to {\em hosts}. It will not be able to inter-
operate with regular DNS servers but it will show you the principles of caching data in a
tree structure.

• namy.pdf

Routy: a small routing protocol

Your task is to implement a link-state routing protocol in Erlang. The link-state protocol is
used in for example OSPF, the most used routing protocol for Internet routers. The aim
of this exercise is that you should be able to: describe the structure of a link-state routing
protocol, describe how a consistent view is maintained and reflect on the problems related
to network failures.

• routy.pdf

Detector:
Failure detectors are the heart of distributed systems. This small tutorial will whow you
how the failure detectors work in Erlang and their linmitations.

• detector.pdf

Casty:
In this assignment you will build a streaming media network. We will play around with
shoutcast streams and build proxies, distributors and peer-to-peer clients. You will use
the Erlang bit-syntax to implement a communication protocol over HTTP. The parser will
be implemented using higher order functions to hide the socket interface. You will learn
how to decode a mp3 audio stream and make it available for connecting media players.
Sounds fun? - Let's go!

• casty.pdf

Loggy: a logical time logger

In this exercise you will learn how to use logical time in a practical example. The task is
to implement a logging procedure that receives log events from a set of workers. The
events are tagged with the Lamport time stamp of the worker and the events must be
ordered before written to stdout. It's slightly more tricky than one might first think.
• loggy.pdf

Goldy: a distributed game

This seminar will serve two purpose; learning how to program a distributed application in
Erlang and understanding why distributed applications are not as simple to control as it
might first seam.

• goldy.pdf

Toty
The task is to implement a total order multicast service using a distributed algorithm. The
algorithm is the one used in the ISIS system and is based on requesting proposals from
all nodes in a group.

• toty.pdf

Muty
Your task is to implement a distributed mutual-exclusion lock. The lock will use a multicast
strategy and work in a asynchronous network where we do not have access to a
synchronized clock. You will do the implementation in three versions: the dead-lock
prone, the unfair and the Lamport clocked. Before you start you should have good
theoretical knowledge of the multicast algorithm and how Lamport clocks work.

• muty.pdf

Groupy: a group membership service

This is an assignment were you will implement a group membership service that provides
atomic multicast. The aim is to have several application layer processes with a
coordinated state i.e. they should all perform the same sequence of state changes. A
node that wish to perform a state change must first multicast the change to the group so
that all nodes can execute it. Since the multicast layer provides total order, all nodes will
be synchronized.

• groupy.pdf

Snapy: the search for dead marbles

In this exercise you will learn how to implement a snap-shot algorithm. We will use a very
simple scenario with a set of workers that create and share {\it marbles} with each other.
The problem is to find out which marbles are alive so that references to dead marbles can
be removed. It's in a sense a simplified garbage collection problem. The problem is
simplified by the fact that the data structures, the marbles, are atomic and that we do not
create duplicates of marbles. We could have solved the problem using a simpler solution
but why not play around with a snap-shot algorithm.

• snapy.pdf

Garby: a distributed grabage collector

In this exercise you will learn how to implement a snap-shot algorithm. As an example we
will try to detect garbage in a distributed computing. This is tricky and as you will see, a
quite expensive operation. Not taking the snap-shot in itself but how to interpret the snap-
shot and how to make the most use of the gained information.

• garby.pdf

Opty: optimistic concurrency control

In this session you will implement a transaction server using optimistic concurrency
control. You will also learn how to implement a updatable data structure in Erlang that
can be accessed by concurrent, possibly distributed, processes. Before you start you
should know how optimistic concurrency control with backwards validation works.

• opty.pdf

Timey: time based concurrency control

In this session you will implement a transaction server using time based concurrency
control. You will also learn how to implement a updatable data structure in Erlang that
can be accessed by concurrent, possibly distributed, processes. Before you start you
should know how time based concurrency control.

• timey.pdf

Paxy: the paxos protocol

This exercise will give you the opportunity to learn the Paxos algorithm for gaining
consensus in a distributed system. You should know the basic operations of the algorithm
but you do not have to know all the details, that is the purpose of this exercise.

• paxy.pdf

Chordy: a distributed hash table

In this assignment you will implement a distributed hash table following the Chord
scheme. In order to understand what you're about to do you should have a basic
understanding of Chord and preferably have read the original paper.

• chordy.pdf