- Untersucht wird, wie man Geräten oder Objekten absolut kollisionsfreie IDs zuweist, wobei zufällige (random) und deterministische Ansätze verglichen werden
- Beim zufälligen Ansatz lässt sich die Kollisionswahrscheinlichkeit mit ausreichend vielen Bits praktisch auf 0 senken; es gibt verschiedene Größenordnungen von UUID (122 Bit) bis zur gesamten Rechengrenze des Universums (798 Bit)
- Für deterministische Ansätze werden mehrere Schemata vorgeschlagen, darunter zentraler Zähler, delegierte Hierarchie (Dewey), binärer Baum (Binary) und Token, und die Wachstumseigenschaften der ID-Länge werden per Simulation analysiert
- Außerdem wird mathematisch bewiesen, dass alle deterministischen Schemata lineares Wachstum im Worst Case nicht vermeiden können
- Im Ergebnis zeigt sich: Auch bei Expansion im kosmischen Maßstab ist die praktikable und effiziente Methode die Erzeugung zufälliger IDs; deterministische Ansätze sind ineffizient
Die Notwendigkeit eindeutiger IDs und die Problemstellung
- Objektidentifikation ist die Grundlage aller Systeme in Fertigung, Logistik, Kommunikation, Sicherheit usw.; bei großer Skalierung ist die Vergabe duplikatfreier IDs eine Kernaufgabe
- Selbst wenn sich die Menschheit auf galaktische Größenordnungen ausdehnt, wird ein ID-System ohne Duplikate benötigt
- Die Fragestellung lautet: „Wie kann man IDs erzeugen, die absolut nie doppelt vorkommen?“
Zufälliger (Random-)Ansatz
- Die einfachste Methode ist die Auswahl einer zufälligen Zahl
- Sie kann überall ohne zentrale Verwaltung oder Synchronisierung erzeugt werden
- Die Kollisionswahrscheinlichkeit lässt sich durch mehr Bits steuern und auf praktisch 0 absenken
- Bei UUID (122 Bit) ist bei etwa $2^{61}$ erzeugten IDs mit Kollisionen zu rechnen
- Berücksichtigt man die gesamte Rechengrenze des Universums (10¹²⁰ Operationen), werden 798 Bit benötigt
- Auf Atomebene (10⁸⁰ Stück) sind es 532 Bit, für 1-g-Nanobots (10⁵⁶ Stück) 372 Bit
- Entscheidend ist echte Zufälligkeit; empfohlen werden CSPRNGs oder Quanten-Zufallsquellen
- Gewöhnliche Seeds oder konstante IDs (z. B. all-zero) müssen ausgeschlossen werden
Deterministischer Ansatz
- Beim zentralen Zähler vergibt ein einzelner Server IDs der Reihe nach
- Wegen Erreichbarkeitsproblemen wird eine Delegationsstruktur zwischen Satelliten und Geräten (Dewey) vorgeschlagen
- Das Dewey-Schema: hierarchische IDs in der Form
A.B.C, dargestellt mit Elias-Omega-Codierung
- Je nach Baumstruktur ergibt sich logarithmisches oder lineares Wachstum
- Das Binary-Schema teilt den ID-Raum als binären Baum auf und ist in manchen Fällen effizienter als Dewey
- 2-adische Bewertung (2-Adic Valuation) garantiert mathematische Eindeutigkeit und ist eine Variante von Binary
- Das Token-Schema zeigt in Kettenstrukturen logarithmisches Wachstum, wechselt bei größerer Breite jedoch zu linearem Wachstum
Beweis der Unvermeidbarkeit linearen Wachstums
- Unter der Voraussetzung, dass alle Wege der ID-Vergabe eindeutig sein müssen, wird die Zahl möglicher Pfade berechnet
- Bei n Knoten steigt die erforderliche Zahl der IDs auf $2^{n-1}$
- Daher gilt: Die ID-Länge muss mindestens O(n) sein, also ist lineares Wachstum im Worst Case unvermeidbar
- Kein Algorithmus kann in allen Fällen logarithmisches Wachstum beibehalten
Simulation von Skalierungsmodellen
- Es wird mit verschiedenen Wachstumsmodellen experimentiert, darunter Random Recursive Tree, Preferential Attachment und Fitness Model
- Im kleinen Maßstab (2.048 Knoten) ist Binary überlegen, Dewey und Token unterscheiden sich je nach Situation
- Im Preferential-Modell ist Dewey am effizientesten
- Im Fitness-Modell zeigen Dewey und Binary ähnliche Leistung
- Auch in Experimenten mit einer Million Knoten behalten Dewey und Token logarithmisches Wachstum
- Die ID-Länge lässt sich näherungsweise als ≈ 6.55 × ln(n) ausdrücken
Modelle für Expansion im galaktischen und kosmischen Maßstab
- Interplanetare Ausbreitung wird als Wellenfront mit konstanter Geschwindigkeit modelliert
- Jeder Planet erzeugt etwa 10⁹ IDs und breitet sich dann zum nächsten Planeten aus
- Bei einem Galaxieradius von etwa 2.121 Planeten beträgt die ID-Länge bei vollständiger Ausbreitung rund 288.048 Bit
- Berücksichtigt man auch die Ausbreitung zwischen Galaxien (etwa 7.816 Schritte), werden etwa 2,2 Milliarden Bit (281 MB) benötigt
- Deterministische Ansätze sind ineffizient; der zufällige Ansatz (unter 798 Bit) ist überwältigend effizienter
Sicherheit und weitere Überlegungen
- Um ID-Fälschung zu verhindern, kann ein signaturbasiertes Verifikationssystem eingesetzt werden
- Bei zufälligen IDs kann der öffentliche Schlüssel als ID dienen; bei deterministischen Schemata signiert der Elternknoten den Schlüssel des Kindknotens
- Fehlerkorrekturcodes und Versionsverwaltung sind erforderlich
- Objekte, die keine ID speichern können (z. B. Planeten), werden über mehrere IDs und deren Zuordnung verwaltet
- Es wird diskutiert, ob eine ID bei Austausch von Bestandteilen bestehen bleibt, ähnlich dem Schiff des Theseus
- Verwandte Konzepte: Decentralized Identifiers (DID), Ancestry Labeling Schemes
Fazit
- Deterministische Schemata sind theoretisch interessant, aber praktisch wenig brauchbar
- Die Erzeugung zufälliger IDs ist auch im kosmischen Maßstab realistisch und effizient
- Die Kollisionswahrscheinlichkeit von IDs auf „praktisch 0“ zu senken, ist die sicherste und praktikabelste Wahl
Noch keine Kommentare.