# Milestone A

## When do we have to synchronize? (How large must the padding be at least? How long is a cycle?)

### Minimum padding

The minimum padding is the padding necessary to account for the worst-case scenario. The minimum padding is infection radius + 1 because we want to make sure that an infectious person can infect the simulated persons in the patch after one tick. An example of the worst case scenario would be a person that is directly outside the padding of size infection radius(in the uncertainty area), walks one cell towards the patch (and thus is not modeled in the padding) and infects a person in the patch after one tick. A padding of size infection radius + 1 allows us to simulate one tick without synchronization (which is the bare minimum).

### Cycle length

A cycle is the number of ticks before a patch needs to synchronize. A cycle has a minimum size such that it accounts for the worst case scenario, although in extreme cases, it is possible that a patch doesn't need to synchronize for a whole simulation e.g. surrounded by corners/obstacle of size infection radius. The minimum cycle size is
MIN(padding - infection radius, incubation time) tick(s). The preceding section make clear why the first part is true, but what about incubation time? Well the worst case scenario would be that a person in the padding becomes infected by a person in the uncertainty zone and infects a person in the patch. An example of a worst case scenario with incubation time 3 would be:

| tick | person in padding | person in patch |
| ---- | ----------------- | --------------- |
| 0 | healthy | healty |
| 1 | infected (0) | healty |
| 2 | infected (1) | healty |
| 3 | infected (2) | healty |
| 4 | infectious(0) | infected(0) |

We want to make sure that we model tick 4 so we must synchronize after tick 3 = incubation time.
Taking the minimum of both these marker also insures that a person infected from someone in the uncertainty area (and thus not modeled) cannot walk into the patch.
Because each patch is responsible for its own person, the information would be lost, and the model would be false.

## Our approach

Our approach is to divide the work up into the afformentioned patches according to the scenario specifics and pass each piece of work on to a separate thread. Each of those threads will simulate its workload (aka a patch and the padding surrounding that patch) sequentially, much like the reference implementation does for the entire simulation area.

This will give us a sizeable performance increase as the overhead for communication should be relatively small if we only synchronize when it is necessary and keep the synchronized data to a minimum.

After the simulation is completed, each worker thread will report its results back to the central managment thread that started all the workers for assembly into the final result that contains all the data for the simulation.

There are a few restrictions to keep in mind that arise from our paralellization effort, as worker threads need to synchronize sometimes (e.g. at the end of a cycle) to update their padding from the simulation of another worker thread(s) that owns the neighbouring patch(es). Particular attention needs to be payed to the facts that
* Sometimes a worker thread will need data from another worker thread that is behind in it's computation => The requesting thread needs to recognize this and wait
* Sometimes a worker thread will need data from another worker thread that is already farther along in the simulation => The requested data needs to be historic

### Patch

We implement a patch as a separate class that is a monitor:

public class Patch (){
	private final List<TraceEntry> trace = new LinkedList<>();
	private final Map<String, List<Statistics>> statistics = new HashMap<>();
	
	synchronised trace getTrace(int tick);
	
	synchronised void addTrace(TraceEntry trace);
	
	synchronised Map<String, List<Statistics>> getStatistics(int tick);
    
        synchronised void addStatistics(Statistics statistics);
    }

### Rocket

The Rocket class has in its field, besides the same instance variables as the Slug class, a list containing all of the patches. This is where the threads are going to share their work. This list has its order given by the class PatchesIterator. This shared list allow threads to syncronise their patch with their neighbors every cycle.

public class Rocket implements Simulation {
    private final Scenario scenario;

    private final List<Person> population = new LinkedList<>();

    private final List<TraceEntry> trace = new LinkedList<>();
    private final Map<String, List<Statistics>> statistics = new HashMap<>();
    
    private final List<Patch> patches = new LinkedList(); // The new property
    
    ...
    }

Each thread is assigned a patch on initialization and is tasked with creating and synchronising padding and simulating ticks for its designated patch. After each tick, the thread writes the simulation to it's patch. When a cycle is over, after writing the simulated tick, the thread synchronises ist padding by reading the corresponding index (the same value as the tick) in the list of the neighboring patches. If the index is empty because another thread has not yet catched up to it, the thread must wait.

When a Thread is finished with its simulation, it adds the information to the instance variable `trace` and `statistic` that will be part of the output. To do this, it uses synchronised (implicitly locked) setter and getters.