Today we will continue our discussion on the DES and see if we can consider each source and server to be a separate process. Clients are passed as messages between the processes. We assume a queue for transit so that the messages appear sequentially.
Now since every process maintains a single queue for event, it has to decide when to process it. If it processed it rightaway, there might be another message from another source that should have been processed earlier. So the server has to wait for the incoming messages on all its inbound channels before deciding which one to execute. It must wait. But this could lead to a deadlock because two process could be waiting on each others inbound channel.In order to advance, we must ensure that such events arrive.
One solution is to send update events called null events. They don't do anything other than to break the impass and ensure progress. But even the null events need to be time-stamped properly.
Since null events don't take any time to process,  they don't advance the clock. For each process in the cycle, the empty queue should contain the minimum time, but this is deadlock. So a null event has to be timestamped strictly larger than the one at the current process. This null event is then sent out to all processes.
The null events break the impass because they represent a guarantee that no events will arrive earlier than this event. The increment of the null message timestamp above the current time is represented by the lookahead.
Several refinements of this basic algorithm are available. Some of these are :
1) pre-compute service time. If the service time is independent of the particulars client, the length of the time required for the next service request can be calculated before the next event has arrived. and this is typically larger than the original look-aheads.
2) Request time-updates explicitly - Rather than sending null events, processes can explicitly request null events. This occurs when a queue for a particular in-neighbor becomes empty.
3) Allow deadlock - Yet another approach is to not use null messages at all. Instead a deadlock detection scheme is used.
4) Increased synchronization -  A tighter synchronization between processes can be used to ensure that no processes get too far ahead of any other. A safety window is maintained.
All of these variants behave differently and often some experimentation is involved. Generally speaking, the magnitude of the look-ahead affects performance and this is highly application specific.

In the time driven simulation approach we mentioned earlier,  how to "discretize" continuous state changes. The simulation is advanced by small increments in physical time. This time interval must be chosen carefully because if its too large, it will not detect the events of interest and if it is too small, it will make the simulation very slow.
Together with the overall amount of physical time being simulated, the time granularity adds to the computational complexity of the simulation. Hence both the factors deserve attention so that we can simulate just what we want.
In a true DES, the absolute sizes of the time intervals between events do not affect how quickly the simulation can proceed. Only the number of events matter.
In the event queue example we mentioned earlier, we use an arrival event to seed the queue. The arrrival queue contained a single event with the description as arrival c1 and timestamp 1 represented as <arrival c1, 1>. This event is now dequeued, the "current time" is updated to 1 and simulated. Simulating this event sends the first client to the server, where there is no wait. The only time taken is the time to service the client. So the client begins service immediately.
This immediately schedules a future event to be scheduled: the completion of service of c1 at this server. This event is represented as say <complete c1, 10>.
When that event occurs, a second event is generated : The arrival of the next client. Say this event is <arrival c2, 4>. Now both the events are inserted into the now empty event queue in the increasing order of time.
Thus we set up a loop for events to be processed at this queue. Note that we keep track of the timestamps only, so from our earlier discussion, this is local. When we want to capture the state across different systems we use snapshots.
Notice that the events are queued in a single queue. To alleviate the bottleneck, we could have a few more queues depending on how many the processor can handle. Typically one more queue per processor could help.
If the processor would like to keep track of the priority of the clients, then that could be maintained as separate queues for priority or another data structure.
In the parallelized case, we still honor the arrival events and mark with appropriate time stamps.
This is how DES systems do time based simulation. 

Discrete Event simulation
This is yet another interesting topic in distributed computing. Consider a network of nodes and directed links between the nodes. There are three categories of nodes. source servers and sinks.
Source generates clients that travel through this network along the links. The clients get service at the server node. Servers can provide service to at most a single client at a time. Clients are in a queue at the server. Finally, the clients disappear at the sink.
The behavior of the system over time can be defined as a series of discrete events over time.
There are four different kinds of events:
A client arrives in the system
A client arrives at a server
A client completes service
A client leaves the system
With a precise event, we can assume no two events happen at the same time.
DES is therefore characterized by a list of time-stamped events described above that occur in increasing order of time. One use for this list is that we can gather metrics  such as average queue length etc.
These systems can be simulated to gather the relevant measurements and statistics. System can then be tuned to optimize performance.
Events are generally not affected in their service by previous clients at the same server. Therefore clients are independent.
The data structure used in DES is an event queue. This queue maintains a list of scheduled future events in increasing order of time. Simulating an event from this queue could generate new events that are inserted into the event queue.
Clients are generated at the source using an initial arrival event. Now simulating this arrival event involves both the insertion of new clients and the scheduling the next arrival.
One limitation with the approach mentioned here is that we have a single event queue that can be a bottleneck. Since events have to wait for earlier events to be simulated, one way to remove this bottleneck would be to parallelize the events.
There are also other simulations such as time driven simulations. In discrete event simulation, the absolute sizes of the time intervals between events does not affect how quickly the simulation can proceed. Only the number of events matter.
For continuous systems, this is not suitable. For example, take the cueing of billiard balls or when they collide. If we discretize the state changes we cannot predict the next event. So we have to take finer time slices.
In general, the computational complexity is proportional to the amount of physical time being simulated and the granularity of the time steps.

In the previous post, we discussed synchronous network with faults. In today's post, we will continue the discussion and look at specific faults/ One specific failure is called the Byzantine fault. Here two processes must agree but their messages may get lost in transit. If there were n rounds of messages, each could have a failure so the processes may each start out with a binary value and at the end of each round, may still have opposing binary values. Consequently, there is no convergence as the rounds decrease from n to 1.  Such faults are generally more difficult to tolerate than crash faults because the outcome is to simply stop execution . There is no solution when there are three processes.
Authenticated messages alleviate this problem. Because now the processes can now that the message was signed by the sender and no one else. This message is also tamper proof and the receiver can know that this was the intended message by the sender.
Now the same can be used to address the Byzantine fault with just two rounds. The signed messages are compared and the proposed value is discarded if the same value was not proposed to all the parties.
So each process takes the following steps:
1) broadcast signed value to all other processes
2) broadcast set of received (signed) values
3) compare received values for each of the other processes
4) if they agree, include the process that sent the value, else exclude it
5) choose minimum value of the included process
As compared to the crash failure where the fault could occur in the first or second round, in this fault the faulty process continues to execute so that there may be faulty messages in both rounds. And after the second round, the processes know that whether any faulty message was sent in the first round regardless of any faulty messages in the second round.
This problem becomes more interesting when there are more than one processes that can fail. In this case, rounds don't suffice. Instead a consensus tree is constructed.  In this tree, the nodes at level i represent message chains of length i. The message at depth 3 has signed messages contained one within the other from three processes. The root has n children representing the messages received in the broadcast of the first round. Each of those nodes have N-1 children from the messages received in the second round and  each of those nodes have N-2 children from the messages received in the third round and so on.
At a given level say N-3 the messages look like (l,k,j,1), (l,k,j,2), (l,k,j,3)...(l,k,j,N). In this case, Pj relayed the same message regarding Pk which in turn relayed Pl to all the processes. So the messages all agree. The decision value of these children can then be bubbled up to the parent.
In order for this tree to calculate the same value for all processes, every message chain in the leaf nodes must include at least one non-faulty process. Thus in order to tolerate f faults, the leaf nodes must represent message chains of length f + 1. That is a consensus tree of height f+1 is required.
The consensus tree also helps in cases when the authenticated signatures are not available. In this case, the value from the children will be bubbled up to the parent only when a majority is there. This is based on the assumption that the majority will be non-faulty and so a quorum suffices and the correct value will be bubbled up.

Asynchronous consensus with process failures.
When there is one fault, it is impossible to solve the consensus problem in a distributed system that involves asynchronous model. Unfortunately, asynchronous design is common. Faults also happen such as failures of disk. And it only takes one fault to disrupt consensus.
This has been proved based on the observation that a protocol begins in a decision state value is either 0 or 1. And it continues in which either result is still possible.
In transaction systems, for commit/abort we used the two-phase locking semantics. In group membership, leader election and reliable multicast too , this problem is common Hence, some suggestions to modify the assumptions of the problem include:
1) Synchrony - If a system can provide an upper bound on the delay or recovery, then this problem can be solved.
2) Randomness - Some probabilistic algorithms can help
3) Failure Detectors - a delayed process is difficult to differentiate from a crashed process without a failure detector.
4) Approximation - Even if all the process cannot agree on the same value, some arbitrary value can suffice.
Let us look at synchronous agreement with process failures.
Every process broadcasts to all other processes its initial value and this can be done in a single round of messages. All of them can then agree on say the minimum.
If there were to be a crash before the first round completes, then they may not have all the values. So a second round of messages could be initiated with all the values from the first round so that everyone has the same set.
Notice that if there are more failures, then there must be more rounds before the agreement. In such a case, there must be an upper bound on the number of rounds otherwise this may not converge.
Also there could be authentication and encryption involved in the messages so that it is not tampered  and that it can be shared effectively. We don't focus on those at this time because we are addressing a different issue.
When we discussed the solution for synchronous systems, we may see how the assumption modifications come useful for asynchronous networks.

We will continue our discussion on garbage collection. The process has some steps that are not obvious. We will go over them in this post.
First, we look at the propagator step we added.  The propagator tests a condition for each edge. This condition marks an edge between x and y as ok if x is a root and with an edge between x and y, they are connected with y as root. That is the propagator takes each garbage and connects them to food.  It continues execution until a termination condition has been reached where the root is connected with all the vertices visited such that each edge x,y is ok.
Between two edges there is only one condition when the edge is not ok. This is when x is not a root. If x is not a root, it is manure. A manure is now easy to collect.
The fact that x is manure and is not a root is maintained as an invariant with the progress because we add edges. Notice that in the ok condition, we checked and maintained that y is root. This is a refinement from the earlier definition where we considered y is food. This let us come up with two separate connected graph where one is manure and the other is food. Everything else is unconnected and garbage.
To be able to prove that this is the case, we considered our actions and maintain the invariant that if x is manure it is not a root. Said differently, each vertex is neither manure or not a root for the marker to propagate. We show that this invariant holds throughout the progress.
Initially there is a root for food and  manure is part of garbage. This is easy to establish because the food is mutually exclusive. By definition, food is any vertex that is reachable to the root. So our initial condition holds.
Next in our actions, we look at the two that change a vertex from being or not being a root.
The first is when we add the edge between x and y  and y is food. In this case since y is food, it is not manure. Since the initial invariant holds for all vertex that is not y, adding an edge from that vertex to y, maintains the invariant.
The other action we do is when x is a root and now there exists an edge between x and y. In this case we proceed from the left. If x is not manure and we connect y, then y is not manure. if y is not manure, then y is root. This re-establishes our invariant.
Thus by maintaining our invariant and our progress, we are able to propagate. we detect the termination condition when the root is chosen and all the edges reaching to it are ok. 

In the previous post we described how the garbage collection works however we did not explain the second attempt or provide proof of correctness. We will look into that now. Remember that for our jargon a vertex is food if it can be reached from the root. If it is not a food, it is garbage. Now onto garbage collection.
The mutator and the marker program superimpose their actions. The mutator actions are not affected and it can continue to add and remove the edges. However we cannot say the same for the marker because the mutator actions can frustrate the marker. For example, marking a single vertex as food could depend on the edges added or removed. To fix this difficulty,  we may have to take another step.
We modify the mutator program from the original where it maintained that a vertex that is food is connected to the root and a vertex that is not food is garbage. In the original program, it assigned  an edge between x and y if y was food and set the edge to true. If this was not the case, it would delete the edge.
Now we add an extra step that we set y as root when y is food. Also, if x is root and adding an edge to x,y implies only y is root.  This is called the propagator step How do we know that this program is correct ? Because we now work off of a root. Two vertices will not satisfy the propagator step only when x is manure. We know the marker has terminated  when we mark the root and for all edges we have completed the propagator.
Note that we mentioned that manure vertices need not be marked. Since they were marked earlier and we will collect them in the next iteration. As an aside, some of the properties that remain true are as follows: a garbage remains a garbage, a food remains a food, a manure is a garbage. Each of the category can only be reached from themselves.
Now we discuss the proof of correctness. Here we have to prove the invariant that if x is manure then x cannot be root. For all vertex, each is neither a manure nor a root.
There are two actions that can modify the root property.
First is the action step we discussed. That is, if x is added to y and y is food, then edge exists between x and y and y is root. Since y is food, y cannot be manure. For all x that is not y, if x is not manure or x is not root and y is not manure, we maintain the invariant.
For the other action where x is root and the edge between x,y is added with y becoming root, the invariant is maintained because x is not a manure. That and y not being a manure implies y can remain a root. Thus maintaining the invariant.