Disserting about colliding GUIDs and the Big Bang Theory

Disserting about colliding GUIDs and the Big Bang Theory...

Can you generate two identical GUIDs? Would the world end if two GUIDs collide? How long does it take to generate a duplicate GUID and would we be still here when the result is found?

# Getting nerdy…

This is going to be a bit technical, or nerdy I should admit.

<enter mode="nerd">

We had a “confrontation” in my team whether two same GUIDs may ever exist. A GUID is a 128-bit long number, represented as a 32-character string, used for identifying resources in a unique way, potentially across the entire globe!

The initial specification of the GUID format used the network card MAC address of the computer where the application is running for generating a truly unique GUID (MAC addresses are unique). This peculiarity was causing some privacy concerns, as a GUID could be tracked to the computer that generated it, thus allowing to locate the person who created it. There is a positive side of this story, though, as this privacy hole allowed to track the creator of the Melissa virus.

The version currently used for generating GUIDs replaces the MAC address with a pseudo-random number. Cryptanalysis of the GUID generator algorithm shows that, since the sequence of GUIDs is pseudo-random, given full knowledge of the internal state, it is possible to predict previous and subsequent values.

Because GUIDs generated from random numbers contain 6 fixed bits and 122 random bits, the total number of unique such GUIDs is 2 to the 122nd power, or 5.3 followed by 36 zeros. Assuming a modern CPU is able to generate a new GUID every nanosecond (a nanosecond is one billionth of a second), that is a billion GUIDs every second, it would still take 3.8E17 (that’s 3.8 followed by 17 zeros) times the age of the Universe to have the 100% assurance to generate a duplicate GUID. This is according to the principle of the “Birthday Paradox”, for which you need at least n + 1 elements in order to obtain a duplicate, with n being the max value of distinct elements that can be obtained. Suppose you execute this program on a billion (yup!) computers, it would take 168,600,000,000 years to complete the search for a duplicate GUID, statistically (obviously, if you’re luckier, you can find it earlier!).

Assuming Moore’s law holds, it would be a lot quicker not to run this program, wait several hundred years and run it on a computer that is billions of times faster. In fact, any program that takes longer to run than it takes CPU speeds to double (about 18 months) will complete sooner if you wait until the CPU speeds have increased and buy a new CPU before running it.

Personally, I think the Big Bang was caused when two GUIDs collided.

</enter>

A privacy hole allowed to track the creator of the Melissa virus.

# Finding GUID

If you really have the time and resources for trying the search for a duplicate GUID yourself, here it is a sample C# code that may help.

class Program

{

static void Main(string[] args)

{

GuidSearch search = new GuidSearch();

Stopwatch watch = Stopwatch.StartNew();

Guid duplicate = Guid.Empty;

try

{

duplicate = search.FindDuplicate();

}

catch (OutOfMemoryException)

{

Console.WriteLine("Sorry, the Universe has ended...");

}

finally

{

watch.Stop();

Console.WriteLine(\$"Duplicate GUID {duplicate} found after {watch.Elapsed.Days} days, {watch.Elapsed.Hours} hours, {watch.Elapsed.Minutes} minutes and {watch.Elapsed.Seconds} seconds!");

}

}

}

The Main program.

The implementation of the FindDuplicate method in the GuidSearch class runs on a single thread. I bet some optimization can be obtained using a parallel loop, but I wouldn't wait for it to complete...

public class GuidSearch

{

public Guid FindDuplicate()

{

var aLotOfGuids = new List<Guid>();

Guid newGuid = Guid.Empty;

bool found = false;

while (!found)

{

newGuid = Guid.NewGuid();

found = aLotOfGuids.Contains(newGuid);

if (!found)

{

aLotOfGuids.Add(newGuid);

}

};

return newGuid;

}

}

The GuidSearch class.

Comments

#### New comment

Source Code

Project Name: GuidSearch

Related Content
A flexible Default Value for your DateTime properties
When creating an MVC application with Entity Framework, it is possible to set default values for most properties in a model using the DefaultValue attribute. However, no much flexibility is offered for a DateTime property. This article presents a custom validation attribute for DateTime types that accepts different formats for defining the default value of the property.
Adding a Secured Geo-located Audit Trail
How I built a social sharing component for my own web site and added a secured geo-located audit trail. Step by step, let’s analyse technologies and source code for developing this component.
Adding Social Sharing to a Web Site
How I built a social sharing component for my own web site and added a secured geo-located audit trail. Step by step, let’s analyse technologies and source code for developing this component.
Best practices for mobile form design in SharePoint
Build effective SharePoint forms with Nintex that are accessible anywhere, at any time, and on any device. You built the workflows, you built the forms, now make them mobile.
Bring your “A” game to ESPC16
With just over 3 weeks to go to Europe's largest gathering of SharePoint & Office 365 professionals, take a look at these tips that will help you get the most out of ESPC16…
Building an MVC application for SharePoint
Learn how to write code to perform basic operations with the SharePoint 2013 .NET Framework client-side object model (CSOM), and build an ASP.NET MVC application that retrieves information from a SharePoint server.
CIO vs CTO
What are the synergies and differences of the roles of a Chief Information Officer and a Chief Technology Officer? An open conversation about two roles with one mission…
Coded UI test automation of MVC applications with Visual Studio
Whether you are a software developer, tester, administrator or analyst, this article can help you master different types of UI testing of an MVC application, by using Visual Studio for creating coded UI test suites that can be automated for continuous execution.
Converting GIS spatial coordinates
Different formats and standards exist for describing geographical coordinates in GIS systems and applications. This article explains how to convert between the most used formats, presenting a working library written in C#.
Creating mobile accessible forms in SharePoint
With the release of the Nintex Mobile apps, SharePoint users can now optimise their experience across popular mobile devices and platforms.
Define your Performance Testing strategy with Visual Studio
Performance Testing is an essential part of software testing, with the specific goal of determining how a system performs in terms of responsiveness and stability under a particular workload. In this series of posts we’ll define and execute a good strategy for testing performance of an application using Visual Studio.
GIS Location Services in Dynamics CRM
A design paper about implementing GIS-based services for a local Council in Dynamics CRM, structuring address data, and delivering location services in the form of WebAPI endpoints via an Enterprise Service Bus.
Group or Team?
All teams are groups but not all groups are teams. What defines a group and what a team? When do we need one over the other one?
How to Give Constructive Feedback
Learning to give and receive constructive feedback is an essential part of learning, growing, improving and achieving our goals.
Mirroring an iPad on your laptop
Have you ever wanted to see your iPhone or iPad on a larger screen? Play games, watch movies, demo apps or present to your computer from your iPhone or iPad. Reflector mirrors iOS devices on big screens wirelessly using iOS built-in AirPlay mirroring.
Mobilize your SharePoint workflows
Build workflow applications in SharePoint that can be accessed on mobile devices using the Nintex solution for business process mobilization.
Natural String Sorting
Have you ever desired to have in your code a way to order a sequence of strings in the same way as Windows does for files whose name contains a mix of letters and numbers? Natural string sorting is not natively supported in .NET but can be easily implemented by specialising a string comparer and adding a few extensions to the enumerable string collection.
Sales Effectiveness in Dynamics CRM with Azure IoT and Machine Learning - Part 1
How can an organisation optimise its sales channels and product targeting by building a 365-degree view of its customers in Dynamics CRM? The answer, and topic of this article, is with the help of Azure IoT and Machine Learning services!
Scaling Applications with Azure Redis and Machine Learning - Part 1
This article presents design best practices and code examples for implementing the Azure Redis Cache and tuning the performance of ASP.NET MVC applications, optimising cache hit ratio and reducing “miss rate” with smart algorithms processed by Machine Learning.
Software Development Management in 11 steps
What it takes to be a great Software Development Manager? I have been building software for the last 15 years and have collected a few stories and experiences to share. Some I have used as questions when interviewing candidates. In 11 points, this is my story to date.
SOLID SharePoint apps with MVC
Practical code examples of ASP.NET MVC applications that connect to a SharePoint Server and comply with the SOLID principles.
The art of outsourcing projects
Outsourcing may look financially attractive, but working with companies in far-off lands introduces challenges that, if not considered properly, can drive any project to failure. Let’s explore some common pitfalls when working with offshore partners and a common-sense approach to work around them.
The value of hashtags
Customers expect a modern approach to advertising. Digital advertising can leverage evolving technology to provide just-in-time, just-at-the-right-place promotions.
We don't need no Yoda's syntax
There is an urban myth in the programmers’ community that the so called “Yoda’s syntax” performs better when checking an object for nullity. Let's demystify it...