Ushbu tadqiqot Lightning Network kabi to‘lov kanallari tarmoqlarida muayyan kanal kelajakda qanday amallar kelishini oldindan bilmagan holda, kelayotgan tranzaksiya takliflarini qabul qilish yoki rad etish orqali qabul qilingan jami tranzaksiyalar sonini qanday oshirishi mumkinligini o‘rganadi. Tadqiqotchilar muammoni tranzaksiya yo‘nalishiga ko‘ra musbat yoki manfiy kattalikka ega elementlar ketma-ket keladigan yangi onlayn xalta (online knapsack) masalasi sifatida modellashtirganlar va Exp deb nomlangan deterministik qabul algoritmini ishlab chiqqanlar. Exp algoritmi tranzaksiya hajmlari muayyan yuqori chegara ichida qolganda O(log B) raqobatbardoshlik nisbatiga (competitive ratio) ega ekani hamda har qanday randomizatsiyalangan (tasodifiylashtirilgan) algoritm ham umumiy holda Ω(log m) quyi chegarasidan qochib qutula olmasligi matematik jihatdan isbotlangan.

Modelda B kanal holatining mutlaq chegarasini; m esa qabul qilinishi mumkin bo‘lgan eng katta tranzaksiya hajmini ifodalaydi. Exp kanal balansini markazga qarab tortuvchi qarama-qarshi yo‘nalishdagi amallarni to‘liq qabul qiladi, mavjud nomutanosiblik yo‘nalishidagi amallarga esa borgan sari qat’iyroq eksponensial chegara qo‘llaydi. Shu tariqa kichik va muvozanatlashtiruvchi amallarga joy ajratilgan holda, kanalning bir tomonidagi likvidlikni tugatib qo‘yish xavfi bo‘lgan yirik tranzaksiyalar saralab rad etiladi.

Haqiqiy Lightning Network topologiyasida sintetik tranzaksiyalar bilan o‘tkazilgan simulyatsiyalarda Exp tasodifiy va muvozanatli kundalik tranzaksiyalar oqimida keng qo‘llaniladigan Greedy (ochko‘z) usuli bilan deyarli bir xil miqdordagi amallarni qabul qildi. Tranzaksiyalar asosan bir yo‘nalishda bitta sotuvchiga oqqan va kanallar soni cheklangan ssenariylarda esa Exp ancha yuqori qabul ko‘rsatkichini ta’minladi. Shu bilan birga, tadqiqot butun tarmoq uchun umumiy marshrut va likvidlik optimallashuvini emas, har bir kanalning mahalliy qabul qarorini tahlil qiladi; shuningdek, real tranzaksiyalar tarixi o‘rniga haqiqiy tarmoq topologiyasida yaratilgan sintetik tranzaksiyalar oqimidan foydalanilgan.

Tadqiqotning asosiy savoli nima?

To‘lov kanallari tarmoqlari har bir kriptovalyuta o‘tkazmasi uchun blokcheynda yangi yozuv va tasdiq kutish o‘rniga, oldindan mablag‘ kiritilgan kanallar orqali zanjirdan tashqarida (off-chain) tezkor hisob-kitob qilish imkonini beradi. Lightning Network va Raiden Network ushbu yondashuvning mashhur namunalaridir.

Ikki foydalanuvchi to‘lov kanalini ochganda, umumiy mablag‘ning bir qismi kanalning bir tomonida, qolgani ikkinchi tomonida joylashadi. Bir yo‘nalishda to‘lov amalga oshirilgani sari likvidlik qarama-qarshi tomonga siljiydi. Agar kanalning bir tomonida yetarli balans qolmasa, ayni shu yo‘nalishdagi yangi tranzaksiyalar kanalning umumiy sig‘imi yetarli bo‘lsa ham o‘tkazilmaydi.

Shu sababli kanalning barcha sig‘adigan amallarni surishtirmay qabul qilishi har doim ham eng yaxshi strategiya hisoblanmaydi. Bugun qabul qilingan bitta yirik tranzaksiya kanal balansini chekkaga surib qo‘yib, kelajakda keladigan juda ko‘p sonli kichik amallarning rad etilishiga sabab bo‘lishi mumkin. Biroq onlayn sharoitda algoritm kelajakda qanday amallar kelishini oldindan ko‘ra olmaydi. Qaror har bir amal kelib tushgan paytda va qaytarib bo‘lmaydigan tarzda qabul qilinishi lozim.

Tadqiqotning asosiy savoli quyidagicha: To‘lov kanali kelajakdagi tranzaksiya takliflarini bilmagan holda, kanal balansini ruxsat etilgan oraliqda saqlab, eng noqulay sharoitlarda ham o‘zi qabul qiladigan jami tranzaksiyalar sonini qanday qilib maksimal darajaga yetkazishi mumkin?

Tadqiqot nima uchun muhim?

To‘lov kanallari tarmoqlarida muvaffaqiyatsiz tranzaksiyalarning asosiy sabablaridan biri marshrutdagi kanallardan kamida bittasida kerakli yo‘nalishda yetarli likvidlikning yo‘qligidir. Kanal nomutanosib bo‘lib qolganda, uni qayta ishlatish uchun teskari yo‘nalishdagi amallarni kutish, aylanma qayta muvozanatlash (rebalancing) o‘tkazish yoki blokcheynda qimmat tranzaksiya bajarish talab etilishi mumkin.

Agar tranzaksiya marshruti bir nechta kanaldan o‘tsa, yo‘ldagi barcha kanallar amalni qabul qilishi shart. Bitta kanalning rad etishi butun to‘lovning barbod bo‘lishini anglatadi. Shu bois mahalliy qabul qarorlarining oqilona berilishi butun tarmoqning o‘tkazuvchanlik quvvatiga bevosita ta’sir ko‘rsatadi.

Oldingi tadqiqotlarning bir qismi barcha tranzaksiyalar oldindan ma’lum bo‘lgan oflayn optimallashtirish masalalarini, boshqa qismi esa muayyan ma’lumotlar to‘plamlarida sinalgan evristik usullarni o‘rgangan. Ushbu tadqiqot esa tranzaksiyalar ixtiyoriy tartibda keladigan va kelajak mutlaqo noma’lum bo‘lgan eng qat’iy onlayn modelni tahlil qiladi.

To‘lov kanali xalta (knapsack) masalasiga qanday aylantirildi?

Tadqiqotchilar har bir tranzaksiya taklifini ishorali element sifatida ifodalaydilar:

\[ \sigma_1,\sigma_2,\ldots \]

Bu yerda \(\sigma_i\) — kelib tushgan \(i\)-tranzaksiya taklifining yo‘naltirilgan hajmidir. Musbat va manfiy ishoralar amalning kanaldagi ikki mumkin bo‘lgan yo‘nalishdan qaysi biri bo‘yicha ketayotganini ko‘rsatadi. Ishora “yaxshi” yoki “yomon” amalni emas, shunchaki likvidlik qaysi tomonga siljiyotganini bildiradi.

Har bir amalning mutlaq kattaligi quyidagi oraliqda qabul qilinadi:

\[ 1 \leq |\sigma_i| \leq m \]

• 1: Masshtablangan eng kichik tranzaksiya hajmi.
• m: Kanalning qabul siyosatida ruxsat berilgan eng katta tranzaksiya hajmi.
• Bitcoin kontekstida eng kichik masshtab satoshi bo‘lishi mumkin.

Eng kichik hajmning 1 deb olinishi umumiylikni cheklamaydi. Agar real minimal hajm boshqacha bo‘lsa, barcha miqdorlar, kanal sig‘imi va qabul egri chizig‘i ayni koeffitsiyent bilan masshtablanishi mumkin.

Kanalning joriy holati \(s\) bilan belgilanadi:

\[ s \in [-B,B] \]

\(B\) — kanal holatining musbat yoki manfiy yo‘nalishdagi mutlaq chegarasi. Boshlang‘ich holat aks holda aytilmagan bo‘lsa:

\[ s_0=0 \]

deb olinadi. Bu kanalning ikki tomonidagi boshlang‘ich likvidlik teng taqsimlanganini anglatadi. Agar boshlang‘ich mablag‘lar teng bo‘lmasa, \(s_0\) noldan farqli tanlanishi mumkin.

Agar algoritm \(\sigma_i\) tranzaksiyasini qabul qilsa, holat yangilanadi:

\[ s \leftarrow s+\sigma_i \]

Agar tranzaksiya rad etilsa, \(s\) o‘zgarmaydi. Har bir qarordan so‘ng:

\[ -B \leq s \leq B \]

sharti saqlanishi majburiydir.

Model nimani maksimallashtiradi?

Asosiy maqsad qabul qilingan tranzaksiyalarning umumiy pul qiymatini yoki komissiya daromadini emas, balki qabul qilingan tranzaksiyalar sonini oshirishdir. Modelda qabul qilingan har bir amal bir birlik foyda keltiradi.

• 1 satoshilik amal ham bitta qabul deb sanaladi.
• Juda katta hajmdagi amal ham bitta qabul deb sanaladi.

Shu sababli tadqiqot maksimal pul o‘tkazish yoki maksimal komissiya yig‘ish muammosidan farq qiladi. Tadqiqotchilar hajm o‘rniga kanalning o‘tkazuvchanlik sonini (throughput) nishonga olganlar.

Onlayn algoritmning muvaffaqiyati qanday o‘lchanadi?

Tranzaksiyalar ketma-ketligi \(\sigma\) uchun:

• \(Alg(\sigma)\) — onlayn algoritm qabul qilgan tranzaksiyalar soni.
• \(Opt(\sigma)\) — butun ketma-ketlikni oldindan biladigan eng yaxshi oflayn yechim qabul qilishi mumkin bo‘lgan tranzaksiyalar soni.

Deterministik algoritm barcha tranzaksiya ketma-ketliklari uchun quyidagi tengsizlik bajarilsa, \(c\)-raqobatbardosh (c-competitive) hisoblanadi:

\[ c\cdot Alg(\sigma)\geq Opt(\sigma)-\beta \]

• \(c\) — o‘lchovsiz raqobatbardoshlik nisbati.
• \(\beta\) — \(B\) yoki \(m\) kabi model parametrlariga bog‘liq bo‘lishi mumkin bo‘lgan qo‘shimcha o‘zgarmas son.
• \(\beta\) ketma-ketlikning uzunligi yoki mazmuniga bog‘liq bo‘la olmaydi.

\(c\) qanchalik kichik bo‘lsa, onlayn algoritmning eng yomon holatdagi kafolati shunchalik kuchli bo‘ladi. Tasodifiylashtirilgan algoritmlarda \(Alg(\sigma)\) o‘rniga algoritmning tasodifiy tanlovlari bo‘yicha kutilayotgan yutuq olinadi.

Greedy (ochko‘z) yondashuvi nima uchun yetarli emas?

Greedy algoritmi kanal chegarasini buzmaydigan har qanday amalni darhol qabul qiladi. Bu yondashuv qisqa muddatda tabiiy ko‘rinadi; ammo kelajakka joy qoldirmagani sababli maxsus tuzilgan noqulay amallar ketma-ketligida juda past natija beradi.

1-rasmda \(B=10\) uchun quyidagi amallar ketma-ketligi ko‘rsatilgan:

\[ +3,\;-2,\;-5,\;+14,\;+1,\;+1,\;+1,\;+1 \]

Greedy holati bosqichma-bosqich quyidagicha kechadi:

1. +3 qabul qilinadi: holat 0 dan 3 ga chiqadi.
2. -2 qabul qilinadi: holat 1 ga tushadi.
3. -5 qabul qilinadi: holat -4 ga tushadi.
4. +14 qabul qilinadi: holat eng chekka chegara +10 ga yetadi.
5. Ortidan kelgan to‘rtta +1 amali holat +10 dan oshib ketishi sababli rad etiladi.

Greedy jami to‘rtta amalni qabul qiladi. Oflayn optimal yechim esa +14 ni rad etib, dastlabki uchta amal bilan oxirgi to‘rtta kichik amalni qabul qiladi va jami yettita tranzaksiyani o‘tkazadi. Bu misol kanal chegarasiga sig‘adigan yirik amalning qabul qilinishi kelgusidagi ko‘plab kichik amallarni to‘sib qo‘yishini ko‘rsatadi.

Greedy uchun matematik quyi chegara

Tadqiqotchilar Greedy raqobatbardoshlik nisbati quyidagicha ekanini isbotlaydilar:

\[ \Omega(m) \]

Isbotda:

\[ d=\left\lceil\frac{B}{m}\right\rceil \]

va:

\[ m'=\frac{B}{d} \]

aniqlanadi. \(m'\) — 1 va \(m\) orasida tanlanadigan va asimptotik jihatdan \(m\) kattaligidagi tranzaksiya qiymatidir.

Noqulay ketma-ketlik quyidagi navbatlashuvchi fazalardan tuziladi:

• Avval kam sonli yirik musbat amallar, so‘ngra juda ko‘p sonli kichik musbat amallar.
• Keyin kam sonli yirik manfiy amallar, so‘ngra juda ko‘p sonli kichik manfiy amallar.
• Ishoralar keyingi fazalarda navbat bilan almashtiriladi.

Greedy har bir fazaning boshidagi yirik amallarni qabul qilib chegarani to‘ldiradi. Oflayn yechim esa yirik amallarni rad etib, ancha ko‘p sonli kichik amallarni o‘tkazadi.

PDF dagi matematik yozuv nomuvofiqligi: Isbot matnida Greedy bilan oflayn yechim nisbati Greedy(σ)=(B/d)·Off(σ) shaklida yozilgan. Ammo fazalardagi qabul sonlari va teoremaning maqsadi bo‘lgan Ω(m) quyi chegarasi hisobga olinsa, munosabat teskari ko‘rinadi. 0-fazada Greedy d ta, oflayn yechim esa B ta amal qabul qilgani sababli to‘g‘ri ifoda Off(σ)=(B/d)·Greedy(σ) bo‘lishi kerak. Bu umumiy natijani o‘zgartirmaydigan algebraik yozuv xatosidir.

Exp algoritmining asosiy g‘oyasi nima?

Taklif etilgan deterministik algoritm Exp deb ataladi. U nomini eksponensial qabul egri chizig‘idan olgan.

Dastlab yordamchi masshtab belgilanadi:

\[ b=\frac{B}{\ln B} \]

Algoritmning isbotlangan kafolati quyidagi texnik shartlarga tayanadi:

\[ B\geq 4{,}1 \]

va:

\[ m\leq b=\frac{B}{\ln B} \]

Ya’ni eng katta tranzaksiya hajmi kanal sig‘imi chegarasidan ma’lum darajada kichik bo‘lishi talab etiladi.

Qabul qilish chegarasi quyidagi funksiyadir:

\[ f(s)=b\cdot \exp\left(-\frac{|s|}{b}\right) \]

• \(s\) — kanalning joriy holati.
• \(|s|\) — kanalning muvozanatli markazdan qanchalik uzoqlashgani.
• \(b\) — qabul egri chizig‘ining masshtabi.
• \(f(s)\) — mavjud nomutanosiblik yo‘nalishida qabul qilinishi mumkin bo‘lgan eng katta tranzaksiya hajmi.

Exp kelgan \(\sigma_i\) tranzaksiyasini quyidagi ikki shartdan biri bajarilsa qabul qiladi:

1. Tranzaksiya bilan joriy holatning ishorasi har xil bo‘lsa; ya’ni amal kanalni markazga qarab muvozanatlashtirsa.
2. Tranzaksiya mavjud nomutanosiblik bilan bir xil yo‘nalishda bo‘lsa va:

\[ |\sigma_i|\leq f(s) \]

shartini qanoatlantirsa.

Exp qarorini qanday tushunish kerak?

Kanal muvozanatda bo‘lganda \(|s|\) kichik bo‘ladi va \(f(s)\) yuqori bo‘ladi. Algoritm har ikki yo‘nalishdagi nisbatan katta amallarni qabul qila oladi. Kanal bir tomonga qarab to‘lib borgan sari, o‘sha yo‘nalishda keladigan yirik amallar xavfliroq bo‘lib boradi va qabul chegarasi eksponensial tarzda pasayadi.

Agar kanal musbat tomonga to‘lib borayotgan bo‘lsa:

• Musbat amallar likvidlikni yana o‘sha tomonga surgani sababli faqat juda kichik bo‘lsagina qabul qilinadi.
• Manfiy amallar esa kanalni markazga qaytargani uchun doimo qabul qilinadi.

Bu tuzilma sig‘imni darhol to‘ldirib qo‘ymasdan, kelajakdagi kichik amallar uchun likvidlik zaxirasini saqlab qoladi.

2-rasmdagi qabul egri chizig‘i nimani bildiradi?

2-rasm \(B=100\) uchun \(f(s)\) egri chizig‘ini ko‘rsatadi. Gorizontal o‘q kanal holatini, vertikal o‘q tranzaksiyaning mutlaq hajmini ifodalaydi.

Ushbu misolda:

\[ b=\frac{100}{\ln 100}\approx 21{,}7 \]

bo‘lgani sababli, kanal to‘liq muvozanatda bo‘lganda ayni yo‘nalishda qabul qilinishi mumkin bo‘lgan eng katta amal taxminan 21,7 birlikdir:

\[ f(0)=b\approx 21{,}7 \]

\(|s|\) ortgani sari egri chiziq tez pasayadi. Egri chiziq musbat va manfiy tomonda simmetrikdir; chunki qaysi tomon to‘lgani emas, kanalning markazdan qanchalik og‘gani muhim.

Agar grafikdagi nuqta egri chiziq ostida qolsa, amal joriy holat bilan bir xil ishorada bo‘lsa ham qabul qilinadi. Agar ishoralar qarama-qarshi bo‘lsa, egri chiziqqa qaramasdan qabul qilinadi.

Algoritm nima uchun kanal chegaralarini buzmaydi?

Tadqiqotning ikkinchi teoremasi \(B\geq 4{,}1\) bo‘lganda Exp holatni doimo \([-B,B]\) oralig‘ida saqlashini isbotlaydi.

Agar \(s\geq 0\) bo‘lsa va qabul qilingan amal manfiy bo‘lsa, u kanalni markazga yoki narigi tomonga suradi. Amal hajmi ko‘pi bilan \(m\leq b\leq B\) bo‘lgani uchun yangi holat quyi chegaradan oshmaydi:

\[ s+\sigma_i\geq s-m\geq -B \]

Agar amal musbat bo‘lsa, Exp faqat amal hajmi qabul chizig‘idan kichik bo‘lsagina ruxsat beradi:

\[ \sigma_i\leq f(s) \]

Mualliflar bir xil yo‘nalishdagi eng kichik amal bo‘lgan 1 qabul qilinishi mumkin bo‘lgan eng oxirgi holat nuqtasini quyidagicha belgilaydilar:

\[ \hat{s}=b\ln b \]

Chunki:

\[ f(\hat{s})=1 \]

bo‘ladi. Bundan yuqori holatda hech qanday musbat amal qabul qilinmaydi.

Exp algoritmining raqobatbardoshlik nisbati qanday isbotlangan?

Yuqori chegara isbotida potensial funksiya usuli qo‘llanilgan. Exp ning \(i\)-amaldan keyingi holati \(s_i\), barcha kelajakni biluvchi optimal yechim holati esa \(s_i^*\) bilan belgilanadi.

Optimal yechim holatiga va Exp qaysi chegaraga yaqinligiga qarab:

\[ d_i= \begin{cases} 2B-s_i^*, & s_i\geq 0\\ 2B+s_i^*, & s_i<0 \end{cases} \]

aniqlanadi.

Potensial funksiya:

\[ \Phi(i)=\frac{d_i}{f(s_i)} \]

sifatida tanlanadi. Agar Exp chegaradan uzoq va qulay holatda bo‘lsa, \(f(s_i)\) katta, potensial esa kichik bo‘ladi. Exp chegaraga yaqinlashganda qabul chegarasi kichrayadi va potensial ko‘tariladi.

Har bir tranzaksiya uchun quyidagi tengsizlik isbotlanadi:

\[ Opt(i)+\Phi(i)-\Phi(i-1)\leq \left(1+(5e-3)\ln B\right)\cdot Exp(i) \]

Barcha amallar bo‘yicha yig‘indilar hisoblanganda oraliq potensial hadlar qisqarib ketadi:

\[ \left(1+(5e-3)\ln B\right)\cdot Exp(\sigma) \geq Opt(\sigma)-O(B\log B) \]

Natijada Exp ning raqobatbardoshlik nisbati quyidagicha topiladi:

\[ O(\log B) \]

Bu natija eng yomon holatda optimal yechim bilan Exp o‘rtasidagi farq sig‘im logarifmi darajasidagi ko‘paytuvchi bilan cheklanishini bildiradi.

Tasodifiylashtirilgan (randomized) algoritmlar uchun quyi chegara

Tadqiqotchilar hech qanday randomizatsiyalangan onlayn algoritm muayyan logarifmik chegaradan yaxshiroq bo‘la olmasligini ham isbotlaganlar.

Quyi chegara uchun:

\[ q=\left\lfloor\log_2(m/2)\right\rfloor \]

va:

\[ h=\left\lceil\frac{2B}{2^q}\right\rceil \]

aniqlanadi. Kiruvchi oqim musbat va manfiy fazalarning navbat bilan kelishi orqali tasodifiy jarayondan hosil qilinadi. Bitta fazada avval kamroq yirik amallar, so‘ngra ko‘proq mayda amallar keladi.

Faza davomiyligi \(z\) quyidagi ehtimollik taqsimotidan olinadi:

\[ \Pr[z=i]=\frac{2^{-i}}{1-2^{-q}}, \qquad i\in\{1,\ldots,q\} \]

Oflayn optimal yechim faza qayerda tugashini bilgani uchun eng oxirgi va eng kichik amallar guruhiga e’tibor qarata oladi. Onlayn algoritm esa faza davom etish-etmasligini bilmagani sababli o‘z sig‘imini erta kelgan yirik amallar bilan kelgusida kelishi mumkin bo‘lgan kichik amallar o‘rtasida taqsimlashga majbur.

Yao minimaks tamoyilidan foydalanib, har qanday tasodifiylashtirilgan algoritm uchun raqobatbardoshlik nisbatining quyi chegarasi olinadi:

\[ \Omega(\log m) \]

Natija nima uchun asimptotik optimal hisoblanadi?

Exp ning yuqori chegarasi \(O(\log B)\), umumiy quyi chegara esa \(\Omega(\log m)\) ko‘rinishidadir. Algoritm ruxsat bergan eng katta hajm:

\[ m=b=\frac{B}{\ln B} \]

deb tanlanganda:

\[ \log m=\log\left(\frac{B}{\ln B}\right) =\Theta(\log B) \]

bo‘ladi. Shu tariqa quyi va yuqori chegaralar ayni asimptotik darajada ustma-ust tushadi.

Simulyatsiyalar qanday o‘tkazildi?

To‘rtta siyosat o‘zaro qiyoslangan:

Simulyatsiyalar Python NetworkX kutubxonasida o‘tkazilgan va barcha kanallar dastlab \(s=0\) holatiga qo‘yilgan.

Bitta kanal va tarmoq topologiyasi tajribalari

Yakka kanal tajribasida amallar yo‘nalishi va mutlaq hajmlari tasodifiy hosil qilingan (1 000, 10 000 va 100 000 ta amal). 3-rasm Exp va Greedy tasodifiy oqimda deyarli bir xil miqdordagi tranzaksiyalarni qabul qilganini ko‘rsatadi.

Tarmoq tajribalarida 2023-yil 23-sentyabrdagi Lightning Network Gossip ma’lumotlar to‘plamidan foydalanilgan (tozalashdan so‘ng 6 673 ta kanal qolgan). Tasodifiy manba va maqsadlar o‘rtasidagi oqimda ham (4-rasm) Exp va Greedy bir-biriga juda yaqin natija bergan.

Sotuvchi (Merchant) ssenariysi

Sotuvchi ssenariysida tasodifiy tugunlardan chiquvchi to‘lovlar yagona qabul qiluvchi tugunga (sotuvchiga) yo‘naltiriladi. Bu oqim tabiatan bir tomonlamadir va kanalning teskari amallar bilan o‘z-o‘zidan muvozanatlashish ehtimoli past.

5-rasm 30 000 ta sotuvchi amali uchun qabul sonlarini maqsadli tugunning darajasiga (bog‘langan kanallar soniga) qarab taqqoslaydi:

• Tugun darajasi 3 bo‘lganda Exp ning qabul ko‘rsatkichi Greedy dan sezilarli darajada yuqori bo‘lgan.
• Daraja 8 bo‘lganda Exp o‘z ustunligini saqlagan, biroq farq qisqargan.
• Daraja 331 bo‘lganda ikki usul natijalari deyarli tenglashgan.

Past daraja sotuvchiga boruvchi kanallar soni kamligini va umumiy sig‘im cheklanganligini bildiradi. Bunday holatda Greedy yirik amallarni erta qabul qilib, kanallarni tezda to‘ldirib qo‘yadi. Exp esa kichik amallar uchun joy saqlab, ko‘proq tranzaksiyalar o‘tishini ta’minlaydi.

PDF dagi uslubiy nomuvofiqlik: Qisqacha tahlil qismida amallarning 85 foizi eng kichik qat’iy hajmda, 15 foizi esa o‘zgaruvchan hajmda ekani aytilgan. Batafsil metodologiya qismida esa kichik amallar 15 foiz, yirik amallar 85 foiz ekani yozilgan. Matnda bu ikki nisbat bir-biriga teskari berilgan.

Tadqiqotning kuchli tomonlari

• To‘lov kanallarida qabul muammosi musbat va manfiy elementli onlayn xalta modeli sifatida aniq ifodalangani;
• Greedy algoritmining eng yomon holatdagi natijasi uchun matematik quyi chegara (\(\Omega(m)\)) isbotlangani;
• Exp algoritmi kanal holatini doimo ruxsat etilgan oraliqda saqlashi isbotlangani;
• Algoritm uchun aniq \(O(\log B)\) yuqori chegarasi berilgani;
• Tasodifiylashtirilgan algoritmlar uchun ham \(\Omega(\log m)\) quyi chegarasi topilgani;
• Yagona kanal, real Lightning topologiyasi va bir tomonlama sotuvchi oqimlari orqali natijalar tasdiqlangani.

Tadqiqotning cheklovlari

• Matematik model faqat bitta kanalning mahalliy qarorini optimallashtiradi; butun tarmoq bo‘yicha global optimallik isbotlanmagan;
• Faqat amallar soni maksimallashtirilgan; komissiya tushumi yoki pul qiymati maqsad funksiyasida hisobga olinmagan;
• Kafolat \(m\leq B/\ln B\) shartiga bog‘liq;
• Lightning topologiyasi real bo‘lsa-da, tranzaksiyalar oqimi sintetik taqsimotlardan olingan;
• Tarmoq xaritasi 2023-yil sentyabriga tegishli;
• Kanalni faol qayta muvozanatlash (rebalancing) jarayonlari modelga kiritilmagan.

Tadqiqotning metodologiyasi va natijalari

Manba va metodologiya eslatmasi

To‘liq asl nomi: Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items

Mualliflar: Marcin Bienkowski (Wrocław universiteti); Julien Dallot, Dominik Danelski, Maciej Pacut, Stefan Schmid (Berlin Texnika universiteti / Weizenbaum instituti).

DOI: 10.48550/arXiv.2604.08205 (arXiv preprint DOI).

Nashr yili: 2026.

Platforma: arXiv (cs.DS, cs.NI).

Taqriz holati: Taqrizdan o‘tmagan konferensiya preprinti.

Rasmiy havola:https://arxiv.org/abs/2604.08205

Kod ombori:https://git.tu-berlin.de/etua/negative-knapsack-network

Ushbu Verianla maqolasi yuklangan PDF matni, teoremalari, isbotlari va tajriba natijalari asosida tayyorlangan. PDF dagi uslubiy nomuvofiqliklar (sotuvchi ssenariysidagi 85%/15% nisbati chalkashligi va Greedy isbotidagi yozuv xatosi) o‘zgartirilmasdan qayd etilgan.