1

Suppose two machines are running the same code, but you want to offset the timing of the code being run so that there's no possibility of their not running simultaneously, and by simultaneously I mean not running within 5 seconds of each other.

One could generate a random number of seconds prior to the start of the running code, but that may generate the same number.

Is there an algorithm to independently guarantee different random numbers?

A.G.
  • 2,089
  • 3
  • 30
  • 52
  • 1
    Just use a different seed for each machine. – David L Jun 09 '15 at 21:29
  • 4
    [That's the problem with randomness. You can never be sure](http://dilbert.com/strip/2001-10-25) – Steve Jun 09 '15 at 21:30
  • But then you'd have to keep track of which machine used which seed? – A.G. Jun 09 '15 at 21:33
  • What random generator were you going to us? The default c# Random .Net class? That seed value only takes a .Net Int value, which is smaller than a GUID. A GUID is 16 bytes, and will very likely be unique if two separate machines that are not VMs hosted on the same host machine generate them. – StarPilot Jun 09 '15 at 21:38
  • What's the purpose? Why can't two programs start within 5 seconds of each other? – D Stanley Jun 09 '15 at 21:39
  • @StarPilot You could use `Guid.NewGuid().GetHashCode()` to generate a "random" `int`. – D Stanley Jun 09 '15 at 21:39
  • But that would increase the likelihood that two different GUIDs hash to the same int, doesn't it? Might be worth finding a small library that allows for a larger seed value, to lower the chances of the two machines generate a GUID that hash to the same value. – StarPilot Jun 09 '15 at 21:41
  • 2
    If two independent random processes aren't allowed to produce the same value, then it isn't random. That said, and I don't know much about it, have you considered researching cryptographic random number generators? – Anthony Pegram Jun 09 '15 at 21:43
  • Just like the above comments, there is *no guarantee*, you can reduce the probability of generating a duplicate. You can use Guid to add randomness to your custom random generator (see http://stackoverflow.com/questions/14074238/guid-uniqueness-on-different-machine) – Ruskin Jun 09 '15 at 21:54
  • 2
    You still haven't answered _why_ they need to be 5 seconds apart. I'm wondering if you don;t have a deeper problem to solve. – D Stanley Jun 09 '15 at 22:01
  • @StarPilot Yes, the likelihood of collision drops from one in 2^128 to one in 2^32. given what the indented purpose is I'd say that's "random" enough... – D Stanley Jun 09 '15 at 22:02

5 Answers5

4

In order to guarantee that the apps don't run at the same time, you need some sort of communication between the two. This could be as simple as someone setting a configuration value to run at a specific time (or delay by a set amount of seconds if you can guarantee they will start at the same time). Or it might require calling into a database (or similar) to determine when it is going to start.

Kyle W
  • 3,702
  • 20
  • 32
  • Yeah I was afraid someone might say that. I was hoping there might be a way to grab some unique value on a machine and use that to generate. – A.G. Jun 09 '15 at 21:35
  • @user1013388 You certainly can, but _what would you do with it_? How can you expect that to guarantee that two programs won't start within 5 seconds of each other? – D Stanley Jun 09 '15 at 21:41
  • Well, that's the question isn't it. :) – A.G. Jun 09 '15 at 21:44
  • I'm wondering if you've thought of the next step - suppose you have two "random" numbers - how are you going to use those to ensure that two programs start 5 seconds apart? You mentioned delaying by N seconds, but what if one gets 5 and one gets 9? How many seconds would you delay at a maximum? 2 billion seconds would be a long time to wait for a program to start... – D Stanley Jun 09 '15 at 22:00
  • @user1013388 There's simply no way to have them start up at different times when there is absolutely no communication between the two (directly or indirectly). If you can describe your use-case, then we might be able to suggest other solutions, but even taking the MAC address and generating something will give you collisions sometimes. – Kyle W Jun 10 '15 at 13:19
1

It sounds like you're looking for a scheduler. You'd want a third service (the scheduler) which maintains when applications are supposed to/allowed to start. I would avoid having the applications talk directly to each other, as this will become a nightmare as your requirements become more complex (a third computer gets added, another program has to follow similar scheduling rules, etc.).

Have the programs send something unique (the MAC address of the machine, a GUID that only gets generated once and stored in a config file, etc.) to the scheduling service, and have it respond with how many seconds (if any) that program has to wait to begin its main execution loop. Or better yet, give the scheduler permissions on both machines to run the program at specified times.

You can't do this in pure isolation though - let's say that you have one program uniquely decide to wait 5 seconds, and the other wait 7 seconds - but what happens when the counter for program 2 is started 2 seconds before program 1? A scheduler can take care of that for you.

Dan Field
  • 20,885
  • 5
  • 55
  • 71
0

As pointed in comments/other answer true random can't really provide any guarantees of falling into particular ranges when running in parallel independently.

Assuming your goal is to not run multiple processes at the same time you can force each machine to pick different time slot to run the process.

If you can get consensus between this machines on current time and "index" of machine than you can run your program at selected slots with possible random offset withing time slot.

I.e. use time service to synchronize time (default behavior for most of OS for machines connected to pretty much any network) and pre-assign sequential IDs to machines (and have info on total count). Than let machine with ID to run in time slot like (assuming count < 60, otherwise adjust start time based on count; provide enough time to avoid overlaps when small time drift happens between time synchronization interval)

(start of an hour + (ID*minutes) + random_offset (0,30 seconds))

This way no communications between machines is needed.

Alexei Levenkov
  • 98,904
  • 14
  • 127
  • 179
0

Have both app read a local config file, wait the number of seconds specified and then start running.

Put 0 in one, 6+ in the other. They'll not start within 5 seconds of each other. (Adjust the 6+ as necessary to cater for variations in machine loads, speeds etc.)

David Arno
  • 42,717
  • 16
  • 86
  • 131
  • What happens when the "wait loop" starts 6 seconds before the other one that gets to start immediately? – Dan Field Jun 09 '15 at 22:21
0

Not really an algorithm but you could create two arrays of numbers that are completely different and then grab a number from the array (randomly) before the app starts.

What is the penalty for them running at the same time?

The reason I ask is that even if you offset the starting time one could start before the other one is finished. If the data they are processing grows then this gets more likely as time goes on and the 5s rule becomes obsolete.

If they use the same resources then it would be best to use those resources somehow to tell you. E.g. Set a flag in the database, or check if there is enough memory available to run.

Touch Cat Digital Inc.
  • 143
  • 1
  • 10