- Membahas cara memberikan ID yang benar-benar tidak duplikat untuk perangkat atau objek, dengan membandingkan pendekatan acak (random) dan deterministik
- Pendekatan acak dapat membuat probabilitas tabrakan praktis menjadi 0 dengan memakai jumlah bit yang cukup besar, dengan berbagai tingkat mulai dari UUID (122 bit) hingga batas komputasi seluruh alam semesta (798 bit)
- Untuk pendekatan deterministik, artikel ini mengusulkan beberapa skema seperti penghitung terpusat, hierarki delegatif (Dewey), pohon biner (Binary), dan token (Token), lalu menganalisis karakteristik pertumbuhan panjang ID tiap metode melalui simulasi
- Juga disajikan pembuktian matematis bahwa semua skema deterministik tidak dapat menghindari pertumbuhan linear dalam kasus terburuk
- Kesimpulannya, metode yang praktis dan efisien bahkan pada skala kosmik adalah pembuatan ID acak, sedangkan pendekatan deterministik terbukti tidak efisien
Kebutuhan akan ID unik dan perumusan masalah
- Identifikasi objek adalah dasar semua sistem seperti manufaktur, logistik, komunikasi, dan keamanan, dan pada skala besar pemberian ID tanpa duplikasi menjadi tantangan utama
- Bahkan jika umat manusia meluas hingga skala galaksi, tetap dibutuhkan sistem ID tanpa duplikasi
- Masalahnya dirumuskan sebagai: “bagaimana membuat ID yang sama sekali tidak pernah bertabrakan?”
Pendekatan acak (Random)
- Metode paling sederhana adalah memilih angka secara acak
- Dapat dibuat di mana saja tanpa pengelolaan pusat atau sinkronisasi
- Probabilitas tabrakan dapat dikendalikan dengan menambah jumlah bit, hingga bisa diatur mendekati 0 secara praktis
- UUID (122 bit) diperkirakan mulai mengalami tabrakan saat menghasilkan sekitar $2^{61}$ ID
- Jika mempertimbangkan batas komputasi seluruh alam semesta (10¹²⁰ kali), dibutuhkan 798 bit
- Berdasarkan unit atom (10⁸⁰ buah) diperlukan 532 bit, sementara 1g nanobot (10⁵⁶ buah) memerlukan 372 bit
- Menjamin keacakan yang sesungguhnya sangat penting, dan disarankan menggunakan CSPRNG atau sumber bilangan acak kuantum
- Seed umum atau ID konstan (misalnya all-zero) perlu dilarang
Pendekatan deterministik (Deterministic)
- Metode penghitung terpusat menerbitkan ID secara berurutan dari satu server
- Karena ada masalah aksesibilitas, diusulkan struktur delegasi antar satelit/perangkat (Dewey)
- Skema Dewey: ID hierarkis berbentuk
A.B.C, direpresentasikan dengan pengodean Elias omega
- Bergantung pada struktur pohon, pertumbuhannya bisa logaritmik atau linear
- Skema Binary membagi ruang ID ke dalam pohon biner, dan dalam beberapa kasus lebih efisien daripada Dewey
- 2-Adic Valuation menjamin keunikan secara matematis, sebagai bentuk variasi dari Binary
- Skema Token menunjukkan pertumbuhan logaritmik pada struktur berantai, tetapi berubah menjadi linear saat lebar struktur membesar
Pembuktian bahwa pertumbuhan linear tidak dapat dihindari
- Dengan asumsi bahwa semua jalur pemberian ID harus unik, artikel ini menghitung jumlah jalur yang mungkin
- Saat jumlah node adalah n, jumlah ID yang dibutuhkan meningkat menjadi $2^{n-1}$
- Karena itu, panjang ID minimal adalah O(n), artinya pertumbuhan linear dalam kasus terburuk tak terhindarkan
- Tidak ada algoritme yang dapat mempertahankan pertumbuhan logaritmik untuk semua kasus
Simulasi model ekspansi
- Eksperimen dilakukan memakai berbagai model pertumbuhan seperti Random Recursive Tree, Preferential Attachment, dan Fitness Model
- Pada skala kecil (2.048 node), Binary unggul, sementara Dewey dan Token berbeda tergantung kondisi
- Pada model Preferential, Dewey paling efisien
- Pada model Fitness, Dewey dan Binary menunjukkan performa serupa
- Dalam eksperimen skala satu juta node pun, Dewey dan Token tetap mempertahankan pertumbuhan logaritmik
- Panjang ID dapat didekati dengan bentuk ≈ 6.55 × ln(n)
Model ekspansi skala galaksi dan alam semesta
- Penyebaran antarplanet dimodelkan sebagai gelombang (front) dengan kecepatan tetap
- Tiap planet menghasilkan sekitar 10⁹ ID sebelum menyebar ke planet berikutnya
- Dengan radius galaksi sekitar 2.121 planet, panjang ID saat ekspansi penuh menjadi sekitar 288.048 bit
- Jika ekspansi antargalaksi (sekitar 7.816 tahap) juga diperhitungkan, diperlukan sekitar 2,2 miliar bit (281MB)
- Pendekatan deterministik tidak efisien, dan pendekatan acak (di bawah 798 bit) jauh lebih efisien
Keamanan dan pertimbangan tambahan
- Untuk mencegah pemalsuan ID, dapat diterapkan sistem verifikasi berbasis tanda tangan
- Pada ID acak, kunci publik dapat digunakan sebagai ID; pada skema deterministik, induk menandatangani kunci anak
- Diperlukan pula kode koreksi kesalahan dan manajemen versi
- Untuk objek yang tidak bisa menyimpan ID (misalnya planet), pengelolaan dilakukan dengan memetakan beberapa ID
- Artikel ini juga membahas apakah ID harus tetap berlanjut saat komponen diganti, seperti pada paradoks Kapal Theseus
- Konsep terkait: Decentralized Identifiers (DID), Ancestry Labeling Schemes
Kesimpulan
- Skema deterministik menarik secara teoretis, tetapi rendah nilai praktisnya
- Pembuatan ID acak tetap realistis dan efisien bahkan pada skala kosmik
- Menjadikan probabilitas tabrakan ID “praktis 0” adalah pilihan yang paling aman dan paling praktis
3 komentar
Pastikan membaca artikel aslinya. Penjelasannya sangat menarik karena memvisualisasikannya dengan rumus dan simulasi.
Kalau dibuat berbasis waktu, itu harus dianggap sebagai sesuatu yang linear, ya..?
Sepertinya saya perlu melihat naskah aslinya. Ini cerita yang menarik.
Kalau sampai bertabrakan, berarti sialnya sudah seukuran kosmik... (?)