• Post Reply Bookmark Topic Watch Topic
  • New Topic

Lamport Clock | Having Difficulties in Logic | Trying to implement in Object Oriented Way  RSS feed

 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to implement Lamport Logical Clock as part of one of my assignments. I need to write just the logic. As of now, I am not expected to write the algorithm in a distributed fashion. My objective is to have a better design and implement it in an object-oriented fashion.

The problem is like this:

There can be three type of events (Send, Receive and Internal). Each event is associated with a process.

Rules:
LC = Lamport Clock Value
1. If a is the first event and is internal or send event, then LC(a) = 1.
2. If a is the first event and is a receive event, then LC(a) = k + 1 where k is the LC-value of the send event corresponding to a (that has occurred at a process other than P.
3. If a is not the first event and is an internal or send event, then  LC(a) = k + 1 where k is the LC-value of the event just before a at process P.
4. If a is not the first event and is a receive event, let b be the send event corresponding to a (that has occurred at a process other than P) and k be the clock value of the event just before a at process P. Then LC(a) = max{ k, LC(b) } + 1

Assumption:
1.) Each receives event name will start with r.
2.) Each sends event name will start with s
3.) Internal event name can be anything but won't start with s and r.
4.) The initial value of each event is 0. I am setting it up in the constructor.

Example:
P0: a  s1  r3  b
P0: c  r2  s3  
P0: r1  d  s2  b

Result:
P0: 1  2  8  9
P0: 1  6  7  
P0: 3  4  5  6

How it's working:
It will start from a (the first event can be anything but a receive event). Then it will sequentially move until it finds a receive event without its sender. So in this example, as soon as it will reach to r3 (r3 is a receiver without a sender), it will go back and find a sender prior to it (in this case s1). Then it will jump to the receiver of s1 (in this case receiver of s1 is r1) and start its sequential execution from r1. Once it finishes the process 3 events, it will come back to process 2 and start from the beginning.

Since I was trying to solve this in an object-oriented way. I have designed my code in following way:

Process: I have a Process class (a pojo) and a process service.
Event: I have an Event superclass (a pojo). Event class gets extended by SendEvent, ReceiveEvent, InternalEvent. They all have an overridden computeLamport method. Then I have a EventService class.

Here are some snippets of my code:

Testing:
Created 10 events and three processes as in the above example:



Code

LamportLogicalClass Compute Lamport - I think the probelm is in this logic.



InternalEvent.Java Calculate Clock.



SendEvent.Java Calculate Clock.



ReceiveEvent.Java Calculate Clock.



Notes:

1.) I can post my whole code, but it would be too much.
2.) The reason I am trying to implement it in this way is that, later if I want to use vector clock instead of lamport. I can reuse everything. And later if I want to replace my Process to work in actual distributed system. I can do it with minimal changes.

Thanks in advance and sorry for long post.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I see some very weird stuff going on:

It appears that every object creates its own instance of EventService, they can still retrieve events that were presumably added to different services. This implies that EventService has global state. Don't do this. If objects need access to shared common state, pass it to them in the constructor. In this case though, I question the need for such a service in the first place.

Event seems to be mutable. That makes no sense. An event is something that happened. You can't change something that's happened after it's happened. The value that you seem to be setting in the event doesn't belong to the event, it belongs to a Process.

You are using Event's constructor to trigger their processing. BAD IDEA. Constructors should only be used to initialize objects, and nothing more. Right now you're leaking references to objects with inconsistent state.

Events have a reference to the process that handle them. This is not useful. Events should be created, then passed to the process that handles them without modifying the event.

Why do your calculateClock() methods operate on a passed event rather than the current event?

Here's how I would design the event model:

Now, you can easily implement your clock like this:

Recreate your example scenario like this:
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I see some very weird stuff going on:

It appears that every object creates its own instance of EventService, they can still retrieve events that were presumably added to different services. This implies that EventService has global state. Don't do this. If objects need access to shared common state, pass it to them in the constructor. In this case though, I question the need for such a service in the first place.


I was thinking to have services for everything, such as service for processes, service for events etc. Just to learn. So services should be instantiated only once?

Stephan van Hulst wrote:
Event seems to be mutable. That makes no sense. An event is something that happened. You can't change something that's happened after it's happened. The value that you seem to be setting in the event doesn't belong to the event, it belongs to a Process.


Yeah, my understanding was every event will have a process associated with it but it should be every process have an event associated with it.

Stephan van Hulst wrote:
You are using Event's constructor to trigger their processing. BAD IDEA. Constructors should only be used to initialize objects, and nothing more. Right now you're leaking references to objects with inconsistent state.

Yeah, but in the event constructor I am just initializing the values and adding them to the list. Didn't understand this.

Stephan van Hulst wrote:
Why do your calculateClock() methods operate on a passed event rather than the current event?

Yeah, it should be on this. I just changed it to this.
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Here's how I would design the event model:
Recreate your example scenario like this:


But my inputs should be in the folowing sequence:


P0: a  s1  r3  b
P0: c  r2  s3  
P0: r1  d  s2  b


But in Main.java we are creating send and receive events sequentially. I mean as per Main.java, after s1, it would be r1. Computationally I need to go to r1 after s1 but the input would be like above.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:So services should be instantiated only once

It depends, but yes, usually services are instantiated as few times as possible.

Yeah, my understanding was every event will have a process associated with it but it should be every process have an event associated with it.

Whatever the direction of association, events shouldn't be mutable.

Yeah, but in the event constructor I am just initializing the values and adding them to the list. Didn't understand this.

In your main method, you are only instantiating events. How does the event service have access to them?

But in Main.java we are creating send and receive events sequentially. I mean as per Main.java, after s1, it would be r1. Computationally I need to go to r1 after s1 but the input would be like above.

If you need to accept receive events before their associated send events are fired, there are a few ways to do this, depending on whether you want your processes to process events in parallel or sequentially. If events must be processed sequentially, your code has to reorder events so dependent events are processed after their dependencies. If processes can operate concurrently, you have to synchronize them so that processes that depend on an event from another process wait until that event is resolved. You need to use locks and conditions for this.
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Yeah, but in the event constructor I am just initializing the values and adding them to the list. Didn't understand this.

In your main method, you are only instantiating events. How does the event service have access to them?


I have a static list in my Event class and in the Event constructor, I am adding each event to that list.



But in Main.java we are creating send and receive events sequentially. I mean as per Main.java, after s1, it would be r1. Computationally I need to go to r1 after s1 but the input would be like above.

If you need to accept receive events before their associated send events are fired, there are a few ways to do this, depending on whether you want your processes to process events in parallel or sequentially. If events must be processed sequentially, your code has to reorder events so dependent events are processed after their dependencies. If processes can operate concurrently, you have to synchronize them so that processes that depend on an event from another process wait until that event is resolved. You need to use locks and conditions for this.


As of now, I need to process them sequentially. But they must be process specific. I mean send and receive event would be, process independent but internal event would be process dependent.  For example, if a receive event (r1) happens, it will find its send event (s1) and the clock value of s1, irrespective of the process. But if an internal event (a) happens it just need to find the clock value of its previous event in that process only.

By ordering them you mean like following:

Let say, I have following events:


P0: a  s1  r3  b
P1: c  r2  s3  
P2: r1  d  s2  b


1.) I will first sort/reorder all of them like following:

Event - Process:
a-P0, s1-P0, r1-P2, d-P2, s2-P2, e-P2, c-P1, r2-P1,  s3-P1, r3-P0, b-P0

2.) Calculate and Assign Lamport Value

Event - Process - Lamport value:
a-P0-1, s1-P0-2, r1-P2-3, d-P2-4, s2-P2-5, e-P2-6, c-P1-1(Because its the first internal event), r2-P1-6,  s3-P1-7, r3-P0-8, b-P0-9.

3.) Again change them to the input order and return back.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:I have a static list in my Event class and in the Event constructor, I am adding each event to that list.

Stephan van Hulst wrote:This implies that EventService has global state. Don't do this.

Stephan van Hulst wrote:You are using Event's constructor to trigger their processing. BAD IDEA. Constructors should only be used to initialize objects, and nothing more. Right now you're leaking references to objects with inconsistent state.

Punit Jain wrote:Yeah, but in the event constructor I am just initializing the values and adding them to the list. Didn't understand this.

Okay, it seems the processing isn't triggered, but your program is still using globally accessible mutable data. You must only use the static modifier on fields if they are constant, i.e. the fields are final and the data type is immutable.

As of now, I need to process them sequentially. But they must be process specific. I mean send and receive event would be, process independent but internal event would be process dependent.

Okay here's how I would solve this problem:
Give each Process an event queue that you add events to as soon as the application generates them. Let a Process handle as many events until it reaches an event that it cannot handle yet, or until it has no events left. Then move to the next Process and do the same. Repeat this until all processes report they cannot continue. At that point, you're either done or in a deadlock. The advantage of this approach is that it can easily be parallelized at a later stage.
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Okay here's how I would solve this problem:
Give each Process an event queue that you add events to as soon as the application generates them.


You mean in the Process class itself?



And then adding it from the EventHandlerList.fire() method:



Stephan van Hulst wrote:
Let a Process handle as many events until it reaches an event that it cannot handle yet, or until it has no events left. Then move to the next Process and do the same. Repeat this until all processes report they cannot continue.


This should be done in the handlers? Should I write separate classes for each handler and call them in the Main.main()?
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
After adding the queue in the above way (in the process class), when I am trying to get the events of the processes. I am getting the following output and which is what my requirements are:


[a, s1, r3, b]
[c, r2, s3, ]
[r1, d, s2, b]


I just printed them simply at the last in my main method.



I removed the name.isEmpty() validation as I can have an event with an empty name and while calculating Lamport, I should simply ignore that or assign some value like -1 or so...

Now I am stuck with handlers.

I tried to do it in following way:



See the getSendEventHandlerList(). Also, at line 7, I can override hasNext() and put all my validation, such as are you a receiver node, without a sender? than stop. etc...

Did you mean like this? 
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Correction: I can't create events sequentially. I mean even if there is no send event, there can be a corresponding receive event and the send event can be created later.

Following is valid use case:



How about this:

I will have 2 maps. One for send events and another for receive events. As soon as a send event is created it will be added to send map also with its initial clock value as 0. Same for receive event. Now when I will calculate clock values for receive events, it will check in the send map if there is a corresponding send event with clock value not equals to 0. If there is, it will grab that and calculate the value based on that. If not it will skip and move to next process.

Questions:

- What would be terminate condition for loop?
- Where should I have these maps? If I have them in the ReceiveEvent and SendEvent. I will have to have them static.
 

 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe you can first explain what it is that generates the events, and how is it decided which process gets to handle the event?
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry to make it confusing. So, I can generate/create a receive event before it's corresponding send event but I can't fire it. Input in the following sequence is valid:

Process 1: [a, s1, r3, b]
Process 2: [c, r2, s3, ]
Process 3: [r1, d, s2, b]


However, in your design, I can't have a receive event before it's corresponding send event because of the following validation, so I removed the validation for now.



Stephan van Hulst wrote:Maybe you can first explain what it is that generates the events, and how is it decided which process gets to handle the event?


Well as of now, the user will be giving the inputs, the process name and the event to fire on that process. Just like the following in the code you designed:



This means it will fire an internal event a on process p0. This will first create an internal event and then will fire it on the process p0.




Before firing the event but after creation, I will need to check the clock values stuff and event would be fired based on clock values.

Basically, the problem is, as soon as there is a receive (i.e. r1) event. It should check whether there is a corresponding send event or not (i.e. s1).

If there is the corresponding send event -
               Then take the clock value of that send event and add 1 to it and assign it to that receive event.
If there is no corresponding send event:-
               Put this receive event on hold and move on and later, once the corresponding send event comes, then take the Lamport value of its sender and assign (it's sender + 1) to the receive event and fire it.

For now, I can assume there is a fixed number of events, let say 25 in each process. Or a user can keep creating.

I was thinking of the following:

I will maintain a table for send events with their clock values. The clock value for send events would be their previous event + 1. However, if the previous event for that send event is a receive event (and that receive event doesn't have it's clock value because it's corresponding send event is yet to happen), then I can assign some arbitrary value to that send event. Later, once that receive even happens, I will go to the table and update the send event clock value again.

This will keep going until all the events have happened. Now I am totally lost, how I will put this situation in the loop.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!