Showing posts with label blocked. Show all posts
Showing posts with label blocked. Show all posts

Thursday, 26 November 2015

The Cap Theorem and Quantum Gravity

Apologies in advance, this post is both extremely technical in multiple fields, and woefully incomplete, and not nearly as humorous as it ought to be. Dragons be here. I'm incredibly sorry.

CAP Theorem for distributed systems


Brewer's CAP Theorem tells us that every distributed computer system must sacrifice at least one of these properties:
  • C: Consistency
  • A: Availability
  • P: Partition Tolerance.
Astonishingly, if we view the universe as a distributed system, then Quantum Field Theory appears to have (analogues of) each of the three properties from the CAP theorem. But at what cost? Paradoxes. So many paradoxes. The double slit experiment, the twin paradox, the EPR “spooky action at a distance” paradox. Many many more. What if QFT adds to the CAP theorem a fourth property we could sacrifice:
  • C: Consistency
  • A: Availability
  • P: Partition Tolerance
  • T: Time Never Flows Backwards (!!!)

One Million Boulders


Lets look at that last one, Time Never Flows Backwards. Suppose, inside a computer, we're trying to simulate one million boulders rolling down a mountain side. At every time step, we need to generate all the potential collisions between those million boulders, and then process them in the order in which the collision occurs. You're familiar with Newton's cradle? Every one of those collisions can change the magnitude, and order, of any subsequent collision. And worse, round-off error when dicing the time steps means that a collision over *here* can affect a collision over *there*.

(All the gory details can be found here.)

Starting to sound a little bit like quantum dynamics right?

So how do we solve it efficiently? By briefly reversing the arrow of time. We find all the collisions between those boulders in a given timestep, then, optimistically, we solve each boulder independently (“in parallel”) based on it's known potential collisions, as if the order of collisions didn't matter. Then we do a “Fix-Up” phase where we wind the time step backwards and correct any of the boulders where (A) the collision order was incorrect, and (B) the energy of the correction is above a certain tolerance. (In practice the tolerance is very small, this tolerance only serves to prevent certain pathological worst-cases)

Starting to sound a *lot* like quantum dynamics...

Spinfoam

So imagine the spinfoam. In my mind, I visualize it something like this:

Spinfoam sketch, incomplete


In Quantum Chromo Dynamics terms, every face you can see is “Colourless” = (Red + Green + Blue == Red + Red + AntiRed + Green + Blue). In this diagram, the past is down. It's the rigid fixed lattice and appears unchangable. The future is a soup of these faces to the top of the diagram, and the “present” is the coalescing region where the mobile soup phase-transitions into a fixed lattice. Naturally, each edge is the Planck length, equivalently Plank time.
You can even see what we'd call a 'particle', maybe an electron or a neutrino, zipping along at close to the speed of light. In the spinfoam, it appears as a disturbance in the otherwise orderly lattice.

  • <technical> In this diagram, the colours satisfy the Pauli exclusion principle. To represent bosons, simply write integer values at every vertex, and require every cycle-over-edges to sum to zero.
  • This 2D diagram with vertices, edges and faces represents {1xspace+1xtime} dimensions. If we axiomatically accept the Holographic Principle, then it might be possible to represent {3xspace+1xtime} dimensions using only vertices, edges, faces and solids.</technical>
Notice too that, at least in the bottom of the diagram (“past”), the laws of physics are symmetric, and invariant under rotations through both time and space. Despite this local invariance, the time dimension can still be identified by it's global properties. The arrow of time, entropy etc, really does exist and has physical meaning.

Mass

What would happen if we tried to simulate this spinfoam in a computer? Well, most obvious to me, is that 'time' in the simulation does not correlate with the amount of computation required to run the simulation. Indeed, the computation required to run the simulation depends primarily on the search activity to coalesce the soup, and it should be easy to find a computation model where that search activity has a cost that matches Einstein's General Theory of Relativity. i.e. the curvature of a region of space is related to the amount of mass in that region, G = m . r-2

Speed

Now lets take that simulation, and instead of running it on one single computer, we instead run it on a distributed computer system. Suddenly, the CAP theorem applies, and our simulation must sacrifice C, or A, or P.... or.... or..... or... T? What if we could sometimes run our simulation backwards just for a moment, the same as we did when "Fixing up" the simulate of those million boulders. When something doesn't fit, just for a little bit, we'd dissolve that fixed lattice of the past and turn it back into the mobile soup of the future, then reform the lattice into a consistent whole.
From inside the simulation, we'd never be able to send information back into the past (That would be a violation!), and yet we'd still get “spooky action at a distance” and all those other paradoxes.
But at what cost? Well, surprisingly, only a performance hit. Again, it should be easy to find a model of distributed computation overhead where this performance hit is in exact agreement with Einstein's *Special* Theory of Relativity. Specifically, it's the Lorentz Transform, γ = 1 / sqrt(1-v2.c-2)

Intermission

Okay, big deep breath. The plot-twist is coming up soon. Brace yourself.

String Theory (Science Fiction)


Almost everything I've written above isn't new or novel. It's just a rehash of various discarded String-Theory ideas from the 90s, but with different names and labels. From an experimentalist physicists point of view, String Theory is just not that interesting. In terms of knowing more about the universe we live in, String Theory is pretty much at a dead end. Why? Because it's not *testable*. We can't devise an experiment in the lab to determine if any one of the thousands of competing String Theories makes predictions which match our unique reality. If your theory isn't testable, if there's no way to determine if you theory approximates our universe better than the alternatives, then that's not "Science" with a capital 'S', it's more like Science Fiction with a whole lot more math.

Plot Twist


So here's the plot-twist: CAP Theorem + QFT is testable.
Here's how: Take that exact same familiar double slit experiment we all faithfully reproduced when we first found out about Quantum Mechanics.


  • Setup-1: Use one slit, fire the wave/particle, measure the diffraction. (Gaussian)
  • Setup-2: Use two slits, fire the wave/particle, measure the diffraction. (Interference pattern)

Now, if we compare Setup-1 with Setup-2, if CAP + QFT is true, then Setup-2 will suffer a tiny time-dilation associated with resolving the CAP constraints. If CAP+QFT is true, we could toggle between Setup-1 and Setup-2 and measure the tiny difference in time dilation.

How tiny? So tiny no-one has ever noticed it before.

...so tiny, it would be much much smaller than the time-dilation associated with the mass of the photon itself.

......so tiny, but, at least in theory, so measurable.

What happens if we go into the lab and measure the time dilation difference between Setup-1 and Setup-2, and that difference turns out to be non-zero?

Quantum Gravity and Friends.


So yeah, that's a testable theory of quantum gravity. It neatly explains why gravity is so weak compared with the other forces (aka the Hierarchy problem), and dramatically simplifies the particle zoo.

Furthermore, this theorem is fully consistent with the Copenhagen Interpretation, and even builds on it! By contrast, In this formulation, the many-worlds alternative, however appears to have a vanishingly strict interpretation.

Black holes? Yip.. (I'll let you puzzle that one through, it's actually quite cute :) Naked singularities? Nope.

It neatly explains the uncertainty principle. It's truly a quantum theory from the get-go. The randomness is real ("no hidden variables"), it's even required, but it's certainly not arbitrary or capricious.

All those crazy dimensions from String Theory? Oh yeah, the dimensionality is there, but they're no longer spatial in nature, they're more like properties stacked on the spinfoam.

There's even some tantalising hints on the nature of dark matter and dark energy and inflation in the early universe..

Anyways, I've probably said way too much, as always, if you have any questions, queries or opinions, please let me know in the comments section below!



Saturday, 19 October 2013

Praise the Fire Fighter, Damn the Safety Inspector

There's a sickness eating our industry.  It's a culture of Macho Programming.  In it's simplest form, it's the idea that if we just push harder, longer, stronger, then we will win.  Yet time and time again, experience shows that the way to win is by working smarter.

Side-effects

I was once working on a particular AAA title.  The game was running late.  We were in crunch, and had been for a while.  There was no end in sight.  I came across the following code:(1)

bool DetectCollision(Vector3 location, float radius){
  ...
  radius * 1.2f;
  ...
}

So that line of code makes the collisions a bit fatter.  It's what we call a 'Fudge Factor' - we don't know why a problem is occurring, so we fudge the numbers a little until it works.

But take a closer look.  The statement as written has no side-effects.  It doesn't actually modify the value of radius.  When the programmer wrote:

  radius * 1.2f;

they intended to write:

  radius *= 1.2f;

Let's review the facts:

  • It's the wrong fix to begin with (fudge factors are generally a bad idea)
  • It doesn't actually change the behaviour of the running program
  • The programmer didn't verify that their "fix" worked

And we can safely assume that the programmer didn't verify the original bug in the first place.

Compound Fail

It gets worse.  In this late stage of crunch, there were so many easily avoidable bugs coming in to the code, that the production team mandated every changelist required a second programmer to sign off.

That's right, not one, but two programmers, working together, managed to convince each other that this placebo changelist actually improved the game.  Together, they marked the bug as fixed and sent it back to QA, fully confident they had made the game better.

What other trivial mistakes did those programmers make that night?

What a colossal waste of time and resources, simply because those two programmers had inadequate sleep.  The project would have been much better off if those two programmers had just gone home at 18:00.  Or 17:00.  Or even 14:00.

[Edit: I just wanted to add, these are actually two really good programmers! I'd jump at the chance to have them on my team again.  The equation here is crunch + good programmers = too many careless mistakes.]

Praise The Fire Fighter ...

When you're deep in crunch, it's easy to see the heroic efforts, the mountains of caffeinated beverages, the change logs at 4am.  It's easy to point to the person who's working the hardest and say "We all need to be more like that guy."  Because when it's all falling apart, you need to do something.
(Hint: That something we need to do is to get more sleep.)

... Damn the Safety Inspector

And when you're at the beginning of the project, and the Safety Inspector is telling you that what you're building isn't up to code, that the schedules are unrealistic and will lead to crunch, slipped deadlines, hard-to-find bugs and adds unacceptable levels of risk to the project...  Well they're easy to dismiss "We're trying to build something here! Why are you trying to stop us?"
(Hint: The Safety Inspector is probably right.)

Macho Programming

As an industry, we should be working smarter than that. We should be rewarding measurable results and hard evidence, rather than effort and posturing.

To me, Macho Programming, is blundering onward in whichever way you possibly can, without regard to what's best for the project or the team, simply for the appearance of getting something done.

I think we can do better than that.  In the true Agile sense, as a team, we need to make the best decisions based on the best information we have, right now, and move forward in the best direction we can.

Who's with me?




(1) Some details have been changed to preserve anonymity.

Friday, 22 February 2013

The Squeeze

I've been adding a lot of content to ScooterBoy over the past week, and it's been causing some problems.

In particular, the size of the archive had grown to over 100MB.

Increasingly, I've come to realize that speed of iteration is one of the biggest factors in determining overall project success.

The large archive size was causing slow sync times with the tablet, and even longer upload times on my rural broadband connection.

Something had to be done.

Enter WebP


WebP is a relatively new graphics format (2010), published by Google, both patent-free and open-source.

It's like a super-JPEG and a super-PNG all rolled in to one. Oh, and it fully supports alpha!

Here's one I prepared earlier: (click through for full size images)

Original PNG, 540KB

WebP version, 23KB

(WebP version as lossless PNG, for comparison only)
In this particular example, that's a whopping 95.7% saving in space!!

Obviously results will vary, but I'm consistently seeing 75% - 90% save spacing over the equivalent PNG/JPG, for a reasonable reduction in quality for tablet devices.

I'm also finding that the compression artifacts are of a type that is less annoying than PNG or JPEG. (Apart from some YUV color noise at very low bitrates - hopefully google will fix this in an update)

And it was super easy to integrate into my codebase.

Want even more info? Go grab the source over at developers.google.com


And my archive size? Now down to a very manageable 22MB.


Friday, 3 August 2012

Status: Blocked

I'm blocked.

It's not writer's block. It's a different kind of blocked, one that's considerably harder to unblock.

Efficiency and Effectiveness


When measuring (or estimating) the output of a team, it's sometimes convenient to look at two different axes:

  • Efficiency - How much work/effort/resources are expended to produce a given amount of output. 
  • Effectiveness - How much output is produced in a given amount of calendar time.

Our natural instinct is to try and optimize efficiency, trying to reduce the cost.  Or alternatively, increasing output for the same amount of fixed cost.

I'm not sure this is the best strategy when it comes to video games. The market moves so fast, I think it makes more sense to push for more effectiveness - maximizing the output per unit of calender time, while staying within our cost constraints.

Diurnal Cycles


I find that at different times of the day, I'm better at certain types of tasks. Sometimes more analytical, other times more integrative. Sometimes more strategic. Some times of the day are better suited to striking new ground, and others are better for polishing and evaluating existing work.

With this in mind, I keep a number of different lists, each based around a type of work. For example, when I have all the microphones and speakers setup to do audio work, I want to get as much done as possible (efficiency), but I also want to make progress on my current goals (effectiveness).

Keeping these in balance is essential, and I allocate up to 20% of my time just in planning and co-ordination to ensure that I'm working on the right things at the right time.


Transition


But the problem I'm facing right now is a shortage of time. I'm currently in the process of moving home from one continent to another, so I'm averaging maybe 10-30 minutes per day for productive work. Compounding this, most of my equipment is in transit and won't be available until late August.

Sharpening the Tools


So what do you work on, when you can't make progress on your goal?

You sharpen your tools – get the latest versions of your software, defrag the hard drive, verify your backup procedures are working. All the things you won't have time to do later.

I know a lot of my friends out there in corporate land are currently caught between changing requirements, and now is your opportunity to do the same thing too. Sure you could sit around and play video games all day, but maybe now is the time to finally learn python? Or figure out rigging? Or fix the ergonomics on your monitor, keyboard and chair?


How do you remain effective, even when you can't be efficient?