Till KTH:s startsida Till KTH:s startsida

Loggy - a logical time logger

Keeping track of order of events.

In this homework assignment you are expected to 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 is slightly more tricky than one might first think.

At the corresponding reporting seminar you are required to present and demonstrate results of your homework, discuss your findings and problems (if any) you have faced, pros and cons of your solution, and your suggestions on how it can be improved.

Lärare Johan Montelius skapade sidan 8 juli 2012

Johan Montelius redigerade 7 september 2012

Keeping track of order of events.

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 is slightly more tricky than one might first think.


* loggy.pdf

En användare har tagit bort sin kommentar
kommenterade 29 september 2013

Question about 4 Lamport Time: Here we're suposed to look for messages that arrives in the wrong order. But from my understanding there's nothing new we can use here to determine whether a message arrived in the wrong order. Am I correct or did I miss something?

I mean, in the first test I determined that a message was logged in the wrong order if there was a message m such that m was received before it was sent.

The only new thing I can really test by introducing timestamps is to see if messages from a process p is not incremented...

For instance:
{p, 1, message}
{p, 3, message}  
{p, 2, message}  //wrong order

But this can never happen since the worker and logger runs on the same machine... What am I missing?

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 30 september 2013

I would say you are not missing anything. Since you are still printing the messages just the way they arrive to the logger, now you can see that sometimes the logical order is incorrect (you might get a message with a higher logical timestamp before one lower (for example a received before a sent). This is what you will try to solve in the next section.

You can also get messages from the same process in a wrong order if the jitter is big enough. Just imagine process 1 sending a message with timestamp 1 and with a delay of 2s. 500 ms after sending the first one it sends another message with timestamp 2 with a delay of 500 ms. The message from process 1 with timestamp 2 will be received before the message with timestamp 1 from the same process.

Anmäl missbruk
kommenterade 30 september 2013

About the last answer, the second part, in a real environment or if the delay was simulated in a more realistic way that could happen. In our case, since we simulate the jitter by just putting the process to sleep, it is impossible to get a wrong order from the same process as you pointed out, because it won't send the next message until it wakes up. Sorry for the confusion.

Anmäl missbruk
Johan Montelius redigerade 28 september 2015

Keeping track of order of events.

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 is slightly more tricky than one might first think.


* Loggy: a logical time logger