Pseudo Time? WTF?

[ShaunR]

I am constantly amazed that some ideas were prescient in hindsight but rejected in their time for more mainstream alternatives. The sands of time covering their bones for an archeologist to piece together later. Luckily, the internet is an excavator

 

I was watching a video called "Is it really "Complex"? Or did we just make it "Complicated" because I've felt for a number of years that the whole idea about using frameworks is really a dead horse flogging exercise because we can't innovate out of a rut. Anyway. During the video there is a throwaway comment that semaphores had a superior alternative called Pseudo Time. Wait. What? Non deadlocking semaphores? Well. Perhaps, perhaps not. The only reference I could find was a paper written in 1978 called Naming and Synchronization in a Decentralized Computer System by David P. Reed.

 

In there he talks about an alternative (NAMOS) to mutual exclusion A.K.A. critical sections around shared resources, rather than semaphores specifically,  but the real gold is his definition of the reliable and self recovering synchronisation of unreliable shared resources. In a nutshell, he's talking about synchronising across cloud servers and blockchain forks and any other distributed computational system you care to design - in 1978! This is a bit more than non-deadlocking  semaphores, I think.

 

So why am I posting. Well. a) Has anyone ever heard of this or any superseding research (links would be great) and b) Has anyone got any LabVIEW examples?

Edited July 11, 2015 by ShaunR

[chris754]

This is very interesting. I will be investigating further as it has relevance to a project I am working on.

[infinitenothing]

"critical sections around shared resources" sounds a little like how non-reentrant VIs are used to arbitrate functional globals

 

If I recall correctly, there's also some deadlock proofing in the DVRs where if you try and nest DVRs in a bad way you get an error.

 

Just remember, you can't have it all

 

https://en.wikipedia.org/wiki/CAP_theorem

Edited July 13, 2015 by infinitenothing

[MarkCG]

Thanks for sharing this! Now you got me on an Alan Kay video watching roll. His way of thinking abotu things really resonates with me

[ShaunR]

This is very interesting. I will be investigating further as it has relevance to a project I am working on.

 

I think it applies to all projects that have asynchronous processes which is why I'm interested.

 

"critical sections around shared resources" sounds a little like how non-reentrant VIs are used to arbitrate functional globals

 

If I recall correctly, there's also some deadlock proofing in the DVRs where if you try and nest DVRs in a bad way you get an error.

 

Just remember, you can't have it all

 

https://en.wikipedia.org/wiki/CAP_theorem

 

I don't know how all that works internally. From the initial cursory reading (which may change as I re-read another 20 times ) )  he is generally talking about a journaling system for messages (I think) and using this pseudo time mechanism to resolve contention by what seems to be a slot-scheduling method.

 

Thanks for sharing this! Now you got me on an Alan Kay video watching roll. His way of thinking abotu things really resonates with me

 

Indeed. He has given me the prism and terminology to [succinctly] describe why I am so unhappy with all the frameworks and architectures I see being produced in LabVIEW. However, I'm hoping that this paper, or one of its later incarnations, results in an elegant solution to remote messaging that I have been unhappy about for quite some time.

[ShaunR]

 

Just remember, you can't have it all

 

https://en.wikipedia.org/wiki/CAP_theorem

 

I just reread what you said here and it seems there is a paper written 30 years ago by David P. Reed that debunks that theory if you consider consistency to be able see data at the same pseudo time rather than absolute time. Still getting my head around it though.

Edited July 16, 2015 by ShaunR

[shoneill]

I just reread what you said here and it seems there is a paper written 30 years ago by David P. Reed that debunks that theory if you consider consistency to be able see data at the same pseudo time rather than absolute time. Still getting my head around it though.

 

This is the problem though.  I admit to having a much less than full grasp of the topic but it seems to me that this consideration is a purely theoretical machination.  In the real-world, users and agents interact with a distributed system in absolute time, not pseudo-time.  Translation between pesudo-time and absolute time is not free (or trivial) and will automatically run into the issues outlined in the CAP theorem.  So by simply formulating the problem in pseudo-time versus absolute time nothing has changed because you can't shift the interaction with he outside world to pseudo-time and the CAP theorem still holds.

[ShaunR]

This is the problem though.  I admit to having a much less than full grasp of the topic but it seems to me that this consideration is a purely theoretical machination.  In the real-world, users and agents interact with a distributed system in absolute time, not pseudo-time.  Translation between pesudo-time and absolute time is not free (or trivial) and will automatically run into the issues outlined in the CAP theorem.  So by simply formulating the problem in pseudo-time versus absolute time nothing has changed because you can't shift the interaction with he outside world to pseudo-time and the CAP theorem still holds.

 

Maybe the blind leading the blind at this point but are you saying that you accept that with this approach availability and partition tolerance are satisfied? 

 

Assuming the affirmative the issue then is consistency (as defined as "atomic consistency" -  a property of a single request/response operation sequence) which is not itself absolutely time constrained and a constraint that data must be seen at the same time. Whos time? EST? GMT? System Time?. How about clock ticks? Is that excluded from being time? So what is the reasoning for a "Translation between pesudo-time and absolute"? In LabVIEW we have "execute when all inputs have been satisfied" (dataflow). Does that violate the first rule?

Edited July 16, 2015 by ShaunR

[shoneill]

"execute when all inputs have been satisfied" is synchronous.  If we do this then we lose availability in the presence of partitioning (inputs never arrive).

 

I can't comment on the overall idea because I find the idea rather theoretical.  You can't simply define a different time scale because not all of the actors are operating on this time scale.  I think the invention of "pseudo-time" sounds terribly like a purely theoretical construct as does the rebuttal of David P. Reed by assuming that everything is in "pseudo-time" (it isn't).

 

I like the description HERE.

 

Based on this, if we define a "pseudo-time" we can look in the logs and see that to Time X, the caller in Chapter 3 DID give his details and that they WERE in the system.  Unfortunately, the caller in Chapter 3 does not conform to "pseudo-time", he's calling in absolute time and expects an answer in absolute time so the answer he got still frustrates him.  Defining any given arbitrary time scale does not solve any of these customer's problems because he is not bound by this scale.

[ShaunR]

 

I can't comment on the overall idea because I find the idea rather theoretical. 

 

I get rather tired of this type of cop-out. It is basically saying "I won't engage your arguments because I don't want to - I will talk about this!". So I will throw back to you that CAP is not a central idea to pseudo-time or the paper so please stay on topic.

Edited July 16, 2015 by ShaunR

[shoneill]

The following is my opinion based on my experience and having read some of the documents linked to earlier in the thread.  I am not an expert but I fear no expert opinion.  I also am not deferent to people who claim to know more than me because knowing more is not always the same as knowing better.  If this leads people to think I'm talking about things I know nothing about then so be it.

 

Regarding my "cop-out".  I dislike having discussions on purely theoretical ideas because it allows people to make silly statements like "Just assume X is true".  I dislike that kind of discussion if it is apparent that such assumptions are essentially "deus ex machina" assumptions.  I believe the essence of "pseudo-time" is such a thing, a sleight of hand (which the author amusingly uses as an example in his NOMAS document.  It pretends to solve problems it has simply shifted to a different location.  I may be wrong but that's my take on it at the moment.

 

Regarding the focus on CAP,  you brought the ability to simultaneously satisfy C and A and P into the equation not me when you stated that a paper by David P. Reed debunked the idea that you can't have C and A and P in the same system "if you consider consistency to be able see data at the same pseudo time rather than absolute time".  I find this argument to be highly suspicious for the  same reasons I think the whole idea of "pseudo-time" is suspicious.  In a distributed system, pseudo-time suffers from the exact same propagation and synchronisation problems as other data.  Even the formulation of "seeing data universally in pseudo-time" simply side-steps the entire issue.  In a centralized system it may have merit, but not in a distributed system as I can see it.

 

My opinion on the idea of pseudo-time is that it's an interesting mental exercise but solves nothing in the real-world where response times are important where results obtained by interfacing with the system cannot be revised afterwards. "Oops, I shouldn't actually have put my hand in the blender, turns out it WAS switched on"!  For data which stays completely WITHIN the bounds of the system, it might be fine (i.e. journalling) but as soon as you mix in real-world interfaces (where incorrectly reported values cannot be corrected post-fact) some of the the benefits (and consistency) are lost.

 

Reading some of the NAMOS paper you linked to reveals a host of inconsistencies.  In one place, pseudo-time defined the order of execution so that incorrect operations can be detected, in other places he talks of tolerating out-of-order pseudo-times where the real time determines the correct order.  I fail to see how both can be used without completely destroying the whole concept.  Even the creation of the pseudo-time itself is pre-destined to be a central, shared, exclusively accessed resource in order to ensure that each message can be guaranteed to have a unique identifier i.e. a global counter.  This might work on a single machine, but once you cross physical boundaries (TCP) this approach has problems.  This is also acknowledged at the very end of the document "- that it can't handle a high degree of contention among the transactions acting on a particular object.  We have suggested above a strategy that mixes together NAMOS and some sort of centralized transaction scheduling discipline."

 

By linking all of this to exclusivity (Page 63) "To say that no other program can interfere with the queue during the execution of the program means that the pseudo-temporal environment must provide a means to reserve a range of pseudo-times for exclusive use of the program, so that no other executing program can access the queue object in that range of pseudo-times" is essentially calling for a lock.  It's not a global lock, it's a lock on a particular Time T (or range T1 to T2).

 

So taking the ever-increasing "pseudo-time" identifier, a centralized numbering system and the ability to refer to any current or older version of data it sounds a lot like Subversion. For data which changes very infrequently, this might be a workable approach but for "lively" systems, the memory requirement for an approach like this would be prohibitive.  Not to mention the work required in how to handle conflicting updates.  Dynamic deadlocks also open up a whole new group of problems.  Also, the lock mentioned on Page 63 become locks on specific version numbers in Subversion (which leads us right back to deadlocks).

 

I'm not saying the idea is without merit, but I don't see the revolution.  The concepts exist and are in widespread use today.  Not for messaging in the Actor framework for example, but it's not completely new either.  The combination of such a mechanism in a distributed messaging system would be interesting if it weren't for the fore-mentioned issues.....

 

So yes, it is a journalling messaging system but problems still arise in ensuring integrity of the pseudo-time entity itself given the nature of distributed systems.  The same problem which is observed in ensuring consistent data across machine boundaries exists also for ensuring the consistency of pseudo-time (latency, partitioning etc.).  A system which aims to solve such problems cannot rely on itself being somehow magically impervious to the very same problems it is trying to solve.

And as usual, it I am wrong I'll happily take any newly-gained information on board.  As always.

[ShaunR]

The following is my opinion based on my experience and having read some of the documents linked to earlier in the thread.  I am not an expert but I fear no expert opinion.  I also am not deferent to people who claim to know more than me because knowing more is not always the same as knowing better.  If this leads people to think I'm talking about things I know nothing about then so be it.

 

Regarding my "cop-out".  I dislike having discussions on purely theoretical ideas because it allows people to make silly statements like "Just assume X is true".  I dislike that kind of discussion if it is apparent that such assumptions are essentially "deus ex machina" assumptions.  I believe the essence of "pseudo-time" is such a thing, a sleight of hand (which the author amusingly uses as an example in his NOMAS document.  It pretends to solve problems it has simply shifted to a different location.  I may be wrong but that's my take on it at the moment.

 

Regarding the focus on CAP,  you brought the ability to simultaneously satisfy C and A and P into the equation not me when you stated that a paper by David P. Reed debunked the idea that you can't have C and A and P in the same system "if you consider consistency to be able see data at the same pseudo time rather than absolute time".  I find this argument to be highly suspicious for the  same reasons I think the whole idea of "pseudo-time" is suspicious.  In a distributed system, pseudo-time suffers from the exact same propagation and synchronisation problems as other data.  Even the formulation of "seeing data universally in pseudo-time" simply side-steps the entire issue.  In a centralized system it may have merit, but not in a distributed system as I can see it.

 

My opinion on the idea of pseudo-time is that it's an interesting mental exercise but solves nothing in the real-world where response times are important where results obtained by interfacing with the system cannot be revised afterwards. "Oops, I shouldn't actually have put my hand in the blender, turns out it WAS switched on"!  For data which stays completely WITHIN the bounds of the system, it might be fine (i.e. journalling) but as soon as you mix in real-world interfaces (where incorrectly reported values cannot be corrected post-fact) some of the the benefits (and consistency) are lost.

 

Reading some of the NAMOS paper you linked to reveals a host of inconsistencies.  In one place, pseudo-time defined the order of execution so that incorrect operations can be detected, in other places he talks of tolerating out-of-order pseudo-times where the real time determines the correct order.  I fail to see how both can be used without completely destroying the whole concept.  Even the creation of the pseudo-time itself is pre-destined to be a central, shared, exclusively accessed resource in order to ensure that each message can be guaranteed to have a unique identifier i.e. a global counter.  This might work on a single machine, but once you cross physical boundaries (TCP) this approach has problems.  This is also acknowledged at the very end of the document "- that it can't handle a high degree of contention among the transactions acting on a particular object.  We have suggested above a strategy that mixes together NAMOS and some sort of centralized transaction scheduling discipline."

 

By linking all of this to exclusivity (Page 63) "To say that no other program can interfere with the queue during the execution of the program means that the pseudo-temporal environment must provide a means to reserve a range of pseudo-times for exclusive use of the program, so that no other executing program can access the queue object in that range of pseudo-times" is essentially calling for a lock.  It's not a global lock, it's a lock on a particular Time T (or range T1 to T2).

 

So taking the ever-increasing "pseudo-time" identifier, a centralized numbering system and the ability to refer to any current or older version of data it sounds a lot like Subversion. For data which changes very infrequently, this might be a workable approach but for "lively" systems, the memory requirement for an approach like this would be prohibitive.  Not to mention the work required in how to handle conflicting updates.  Dynamic deadlocks also open up a whole new group of problems.  Also, the lock mentioned on Page 63 become locks on specific version numbers in Subversion (which leads us right back to deadlocks).

 

I'm not saying the idea is without merit, but I don't see the revolution.  The concepts exist and are in widespread use today.  Not for messaging in the Actor framework for example, but it's not completely new either.  The combination of such a mechanism in a distributed messaging system would be interesting if it weren't for the fore-mentioned issues.....

 

So yes, it is a journalling messaging system but problems still arise in ensuring integrity of the pseudo-time entity itself given the nature of distributed systems.  The same problem which is observed in ensuring consistent data across machine boundaries exists also for ensuring the consistency of pseudo-time (latency, partitioning etc.).  A system which aims to solve such problems cannot rely on itself being somehow magically impervious to the very same problems it is trying to solve.

And as usual, it I am wrong I'll happily take any newly-gained information on board.  As always.

Leaving aside your beliefs and the strange disclaimer....

 

It's not new because it is over 30 years old but I have never heard anyone talking of Pseudo Time  until Alan Kay mentioned it and I have a feeling, neither have you.

 

I'm surprised you didn't point to page 72 to challenge my assertion about consistency  where he states

 

The problem is obvious.Pseudo Time must be correlated to real time.

 

You are reading it now, .

 

I need to read it at least twice more and then I will have a full understanding and will address your points but rather than think of Pseudo Time as a kind of subversion-like database for values, I think it would be better to think of it more as a mechanism within a subversion-like database that has similarities to a hard, real-time system - atomic execution slots where batches of operations can be executed under a single label. As I said before

 

what seems to be a slot-scheduling method.

He is still a professor at MIT, so I might email him and ask about his thoughts about it after 30 years and if there are implementation examples. I have a feeling it was the basis for the TeaTime synchronization architecture in Croquet.

 

This messaging protocol supports a coordinated distributed two-phase commit that is used to control the progression of computations at participating user sites. In this way messages may be dynamically redirected to large numbers of users while maintaining the appropriate deadline-based scheduling. Thus, TeaTime is designed to allow for a great deal of adaptability and resilience and works on a heterogeneous set of resources. It is a framework of abstraction that works over a range of implementations and that can be evolved and tuned over time, both within an application and across applications.

Edited July 17, 2015 by ShaunR

[shoneill]

I'm surprised you didn't point to page 72 to challenge my assertion about consistency

...

You are reading it now, .

 

Yes I read it.  I didn't refer to it (again) because I have already addressed this as a central problem in my first post.

 

Either way, while he lists off some possible solutions to the problem, the absence of an actual fixed implementation for this problem leaves way too much room for wriggling to make the idea fit whatever you want it to.  Hence my deus ex reference.  Take the problems you are experiencing, put them in a new box and call it a solution.  Just don't open the box!

 

If Project Open Cobalt is indeed based on the ideas of NAMOS then I too would be interested in hearing about the details of actually implementing the ideas, where problems arose and where changes were required in order to achieve their goals.  But then we'd be having a very different discussion.  The idea of embedding the time scale "pseudo-time" in the peer-to-peer communications (as per Project Open Cobalt) is but one of a number of possible real-world to pseudo-time options the author mentions in his 1978 paper.  If they have chosen a specific implementation then the reasons for this over others may enlighten me.  It's a world of difference to me if pseudo-time was the actual basis for TeaTime or simply whether it served as an inspiration for the implementation of a similar idea.

 

Leaving aside your beliefs and the strange disclaimer....

 

It's not new because it is over 30 years old but I have never heard anyone talking of Pseudo Time  until Alan Kay mentioned it and I have a feeling, neither have you.

 

There are lots of new things I learn all the time, most of these things are in themselves really old.  I imagine that's true for all of us.  I'm very open in admitting the limits of my current experience and (alleged) knowledge.  In the limits of this discussion, I fail to see what relevance the 30 years or my past exposure (or non-exposure) to pseudo-time has to do with the correctness of the idea or indeed my observed problems with it.  It seems to be invoking the authority fallacy, something I have very purposefully and deliberately referred to in my "strange disclaimer".  You could almost think I saw that one coming.... .

[ShaunR]

Y

There are lots of new things I learn all the time, most of these things are in themselves really old.  I imagine that's true for all of us.  I'm very open in admitting the limits of my current experience and (alleged) knowledge.  In the limits of this discussion, I fail to see what relevance the 30 years or my past exposure (or non-exposure) to pseudo-time has to do with the correctness of the idea or indeed my observed problems with it.  It seems to be invoking the authority fallacy, something I have very purposefully and deliberately referred to in my "strange disclaimer".  You could almost think I saw that one coming.... .

 

Except I already stated that "From the initial cursory reading (which may change as I re-read another 20 times)" and "Still getting my head around it though" so it wasn't an authoritative stance-you just chose to jump on a specific tangential comment that you thought you might score points on You can bet it has been refined and re-imagined. I even said I was looking for the superseding research in the original post. I also asked for any examples so you know there are none, so far.

 

If they have chosen a specific implementation then the reasons for this over others may enlighten me.  It's a world of difference to me if pseudo-time was the actual basis for TeaTime or simply whether it served as an inspiration for the implementation of a similar idea.

 

It is clear that you require to be spoon-fed solutions with concrete implementations. Drive by the fill-up station of knowledge and stick the nozzle in your ear. It is the programmers equivalent  of the "pictures or it's not true" that is in some online cultures. I will let you know if and when I have such a solution, an example of it working, a published paper for you to annotate and a licence for you to use it. In the mean-time you will just have to watch to me brainstorm as to possible uses and applications as I piece together the timeline after a serendipitous stumbling over of an ancient text that was written a long time ago by one of the founders of TCP and UDP.

Edited July 17, 2015 by ShaunR

[shoneill]

Any particular reason why you're getting so annoyed about this particular topic?  I have no stake to claim here nor any territory to defend.  But it is becoming clear that instead of trying to understand my issues with the topic at hand you're trying to reduce me to either someone who is capable of having this discussion with you or not.  Well (back to my strange disclaimer) I care not what you think of my credentials.

 

By the way, I never attached the authority (of the authority fallacy) to yourself, it's clear you're not the expert on the topic (and that's not meant in an inflammatory way), but rather to the author of the NOMAS document.  I do not blindly accept what he has written there just because he's done some good things.  That would be a incorrect and I would be surprised if you did either.  I have a look at it and identify good and bad points.  If what I think are bad points can be shown to be otherwise, I have learned and I can adjust my thinking accordingly.  But at the moment I'm getting precious little feedback as to why you have such an issue with my stance as opposed to having a problem with me even daring to take a stance.  I have given points where I think the proposed work is weak.  My gripe with the topic stands.  If you agree, fine, if you disagree, tell me why.

 

This is all completely irrelevant to the discussion at hand.  If you want to continue to insult ME instead of discussing the merits or non-merits of my responses to your question then so be it.  Fire away.

[ShaunR]

I managed to track down a later paper from 1983 called Implementing Atomic Actions on Decentralized Data where David P. Reed extends his original paper to talk about using Pseudo Time specifically for distributed atomic actions. That is, an action and a failure of that action is atomic across multiple remote sites.