-1
$\begingroup$

I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has.

I've been thinking about also computations that might require external factors - for example being able to hash tomorrow's newspaper is a type of computation that takes the same amount of time.

However I'm looking for something that can run on computers with certainty (tomorrow's newspaper might not come out at all).

Any thoughts?

EDIT what I'm looking for is not something that runs in exactly the same amount of time. For example, a computation that counts to 10 would be ok, as it would roughly take 10 seconds on every computer. What I need is a way to arrive at a certain result only after having waited 10 seconds. Imagine that I have a password protected key, and the only way to see the password was to wait 10 seconds.

$\endgroup$
7
  • $\begingroup$ "Algorithms" are not something that can be computed. $\endgroup$ Commented Jul 25, 2015 at 12:50
  • $\begingroup$ sorry you're right. changed "algorithms" to "computation". $\endgroup$ Commented Jul 25, 2015 at 13:07
  • 2
    $\begingroup$ Hashing tomorrow's newspaper doesn't take the same amount of time on any computer. Sure, any computer has to wait until tomorrow to receive the data but that just means that a fast computer might take, say, 24 hours and one millisecond, compared to a slow computer taking 24 hours and 300 milliseconds. $\endgroup$ Commented Jul 25, 2015 at 13:08
  • $\begingroup$ Right indeed. I was also thinking of using things such as planets position at specific intervals. But I guess that suffers from the same slow/fast computer problem for measuring it. $\endgroup$ Commented Jul 25, 2015 at 13:12
  • $\begingroup$ I've edited to show my use case. I doesn't have to be exactly 10 seconds. $\endgroup$ Commented Jul 25, 2015 at 13:16

2 Answers 2

1
$\begingroup$

I suspect you might be interested in timed-release cryptography, where some secret is released to the world only after a specific point in time, and having a faster computer doesn't help you learn the secret any quicker.

If you search on timed-release cryptography, time-lock cryptography, and time capsule cryptography on Cryptography.SE, you'll find a bunch of information on the topic. For instance:

I suspect it might also be possible to achieve what you want by using the Bitcoin block-chain, transactions with a user script, and some cleverness.

$\endgroup$
1
  • $\begingroup$ Ha. Using the blockchain would slow down the processing to the point that the speed of the computer would be much less important. $\endgroup$
    – SDsolar
    Commented Mar 23, 2017 at 7:54
0
$\begingroup$

I am not certain of what you are after, so I am giving you below pointers to various related areas of research that may answer your quesry. To be true, they fit your examples more closely than the tags you have chosen. But then, I do not see how your examples and your tags can fit together. So I am waiting for your reaction (after all, it is related to reactive programming) to understand better, and possibly suggest changing the tags.

It seems that what you are after is event driven programming. There is a wikipedia page on event driven programming and another one on event-driven architecture. The flow of execution is controled by events, which may be external events. All you expect from the computer is to be fast enough so as to be ready for the next event. So this type of programming is alsi linked to real-time programming, when events external to the computer are taken into consideration.

It is unclear whether you are concerned with external events, since you give the newspaper example, and then say that it might be a bad example, because you cannot be sure of external events. But these techniques can use all kinds of events, including internal interrupts, mouse clicks, clock driven signals, etc.

It is also linked to reactive systems, synchronous programming languages and dataflow programming.

There has been considerable research on this topic, and a large number of programming languages and formalisms were developed. Among others, you may look for programming languages such as Esterel, Lustre, or Signal.

I guess these references should give you enough starting point, if my answer meets what you are looking for.

$\endgroup$
7
  • $\begingroup$ I don't think that this is what they are after, since it "needs to run with certainty" from which I make out it can not depend on an external event. $\endgroup$ Commented Jul 25, 2015 at 13:46
  • $\begingroup$ The question is ambiguous on that. Why use this example at all, if it is always wrong? Besides, the kind of programming I am considering my be used with internal event. And the fact that an event may fail to occur can be dismissed as possible for all events, including that the sun will rise tomorrow. We just work on assumptions, possibly with fallbacks in case of failure. $\endgroup$
    – babou
    Commented Jul 25, 2015 at 14:04
  • $\begingroup$ Right, what I'm looking for is more of a "proof-of-work" system. But rather than requiring the proof of a certain amount of work (which varies based on how much computing power one has), it is based on time: prove to me you waited 10 seconds (or whatever) to run this computation. $\endgroup$ Commented Jul 25, 2015 at 14:06
  • $\begingroup$ @LucaMatteis Sorry. I just learned what is a "proof-of-work" system. The idea is to enforce waiting and have a way to check it. This requires a third party issuing certificates containing event specific data. The third party could be within the computer if it can sit there protected agaisnt tampering (special chip?). It could work with a clock and an encryption system so that its certificates cannot be forged, such assymetric cryptography, using a private key internally with a public key available to you. There should be a way of checking that the public key is an official one. $\endgroup$
    – babou
    Commented Jul 25, 2015 at 18:36
  • $\begingroup$ @LucaMatteis So my guess is that cryptographic techniques might help you., as I tried to sketch briefly. But I have no pointer to existing work of the kind, other than the work on DRM and other Technical Measures of Protection. Possibly, a non-harmful variant used for such certification only could be developed. I am not sure, and I feel rather queasy about the whole idea. Of course, an alternative would be to use an external service that delivers such certifications upon request. $\endgroup$
    – babou
    Commented Jul 25, 2015 at 18:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.