Problem

Above shows a section of traffic route around the narrow bridge AB on a river. Two red cars(R1,R2) and two blue cars(B1,B2) move along the designated routes that involve indefinite number of trips across the bridge. The bridge is so narrow that at any time, multiple cars cannot pass in opposite directions.
a, Using the Message-passing model, design a decentralized protocol so that at most one car is on the bridge at any time and no car is idefinitely preventd from crossing the bridge. Treat each car to be a process and assume that their clocks ar not synchronized.
b,Modify the protocol so that multiple cars can be on the bridge as long as they are moving in the same direction, but no car is indefinitely prevented from crossing the bridge.
Design a graphical user interface to display the movement of the cars, so that the observer can visualize the cars, control their movements, and verify the protocol.
Solution

This program runs in two different platforms. One part is car control logic. They are written by C++ and each car is a independent process. These processes are a group that needs to communicate with each other to enter critical section in order. In this project, the critical section is the narrow bridge. This group is decentriliaze system that no other central server to make a decision to order car processes. So these group members use Lamport Algorithm, a famous therom to solve concurrency problem in distributed system, to determine which one access bridge first which is later. This car control logic is located in server folder and they are Linux OS based. To abserver the whole process, a client grapic is needed to show cars' movement.I used Android Java to receive messages from all cars and draw
Here is my program video link:
http://youtu.be/_XIKJeisfIs How to run

There are two folder in submission: Server and Car

Compile and run Server

• Step 1:Deploy server folder in ubuntu OS server.
  
• Step 2:In Server folder, input this command line to compile:
  $ make
  Two executebal files are created: launch and discar
  
• Step 3: Then run program：
  $ . /launch 192.168,173.16 ,where IP is the client address to draw graphic.

Run client

Client runs in Android emulator. So Android studio and Java needs to be installed.

• Step 1: install java environment;
  
• Step2: install Android studio;
  http://developer.android.com/sdk/index.html
  
• Step3:install Android SDK;
  http://developer.android.com/sdk/installing/index.html
  
• Step 4: import Car folder into Android studio;
  
• Step5: run program;
  

Implementation

There are two major modules in this system: Discar and UI. The Discar is the core system that controls car logic movement and they are running in different mechines. Each car has four states. Their state transition is showed in following figure

Sequence Diagram