مشكلة خادم k

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
مشكلة لم تُحل في علوم الحاسوب
هل يوجدك{\displaystyle k}خوارزمية تنافسية لحلك{\displaystyle k}مشكلة الخادم في فضاء متري عشوائي؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

مشكلة الخوادم k هي مشكلة في علوم الحاسوب النظرية، وتحديدًا في فئة الخوارزميات المتصلة بالإنترنت ، وهي إحدى مشكلتين تجريديتين في الفضاءات المترية تُعدّان أساسيتين لنظرية التحليل التنافسي (والأخرى هي أنظمة المهام المترية ). في هذه المشكلة، يجب على خوارزمية متصلة بالإنترنت التحكم في حركة مجموعة من k خادمًا ، ممثلة بنقاط في فضاء متري، ومعالجة الطلبات التي تُمثّل أيضًا بنقاط في هذا الفضاء. مع وصول كل طلب، يجب على الخوارزمية تحديد الخادم الذي يجب نقله إلى النقطة المطلوبة. يهدف عمل الخوارزمية إلى تقليل المسافة الإجمالية التي تقطعها جميع الخوادم، مقارنةً بالمسافة الإجمالية التي كان من الممكن أن تقطعها الخوادم لو كان الخصم الأمثل على دراية مسبقة بتسلسل الطلبات بالكامل.

طُرحت هذه المشكلة لأول مرة من قِبل مارك ماناس، ولايل أ. ماكجيوخ، ودانيال سليتور (1988). [ 1 ] يُعدّ ما يُعرف بفرضية الخادم k ، التي طرحها ماناس وآخرون أيضًا، أبرز سؤال مفتوح يتعلق بمشكلة الخادم k . تنص هذه الفرضية على وجود خوارزمية لحل مشكلة الخادم k في أي فضاء متري، ولأي عدد k من الخوادم، بحيث تكون نسبة التنافس k تساوي k بالضبط . تمكّن ماناس وآخرون من إثبات فرضيتهم عندما k = 2، ولقيم أكثر عمومية لـ k في بعض الفضاءات المترية التي تحتوي على k + 1 نقطة بالضبط. أثبت ماريك كروباك ولورانس ل. لارمور (1991) الفرضية للمقاييس الشجرية. تُسمى الحالة الخاصة للمقاييس التي تتساوى فيها جميع المسافات بمشكلة الترحيل، لأنها تُحاكي مشكلة خوارزميات استبدال الصفحات في ذاكرة التخزين المؤقت، وكان من المعروف أيضًا وجود خوارزمية تنافسية k لها ( سليتور وتارجان 1985 ). أثبت فيات وآخرون (1990) لأول مرة وجود خوارزمية ذات نسبة تنافسية محدودة لأي قيمة ثابتة k وأي فضاء متري، وأثبت كوتسوبيا وباباديميتريو (1995) أن خوارزمية دالة الشغل (WFA) لها نسبة تنافسية تساوي 2k - 1. ومع ذلك، وعلى الرغم من جهود العديد من الباحثين الآخرين، لا يزال خفض النسبة التنافسية إلى k أو توفير حد أدنى محسّن غير متاح حتى عام 2014.السيناريو الأكثر شيوعًا هو أن خوارزمية دالة العمل تنافسية من الدرجة k . وفي هذا السياق، أظهر بارتال وكوتسوبيا في عام 2000 أن هذا صحيح في بعض الحالات الخاصة (إذا كان الفضاء المتري عبارة عن خط، أو نجمة موزونة، أو أي مقياس مكون من k + 2 نقطة).

تتضمن فرضية الخادم k أيضًا نسخةً للخوارزميات العشوائية ، والتي تسأل عما إذا كانت هناك خوارزمية عشوائية بنسبة تنافسية O(log k ) في أي فضاء متري عشوائي (يحتوي على k + 1 نقطة على الأقل ). [ 2 ] في عام 2011، تم اكتشاف خوارزمية عشوائية بحد تنافسي O(log 2 k log 3 n). [ 3 ] [ 4 ] في عام 2017، تم الإعلان عن خوارزمية عشوائية بحد تنافسي O(log 6 k)، [ 5 ] ولكن تم سحبها لاحقًا. [ 6 ] في عام 2022، تم إثبات خطأ النسخة العشوائية من الفرضية. [ 2 ] [ 7 ] [ 8 ]

مثال

لتوضيح المشكلة بشكل ملموس، تخيل إرسال فنيي دعم العملاء إلى العملاء عند مواجهتهم مشاكل في أجهزتهم. في مثالنا، يوجد فنيان، ماري ونوح، يخدمان ثلاثة عملاء في سان فرانسيسكو، كاليفورنيا؛ وواشنطن العاصمة؛ وبالتيمور، ماريلاند. باعتبارها مسألة من نوع k -server، فإن الفنيين هم الخوادم، لذا فإن k = 2، وهذه مسألة من نوع 2-server. المسافة بين واشنطن وبالتيمور 35 ميلاً (56 كم) ، بينما تبعد سان فرانسيسكو 3000 ميل (4800 كم) عن كلتيهما، وفي البداية، كان كل من ماري ونوح في سان فرانسيسكو.  

لنفترض وجود خوارزمية لتخصيص الخوادم للطلبات، بحيث تُخصص دائمًا أقرب خادم لكل طلب. ولنفترض أن العميل في واشنطن يحتاج إلى مساعدة كل صباح من أيام الأسبوع، بينما يحتاج العميل في بالتيمور إلى مساعدة كل مساء من أيام الأسبوع، وأن العميل في سان فرانسيسكو لا يحتاج إلى مساعدة أبدًا. عندئذٍ، ستخصص خوارزميتنا أحد الخوادم (ولنقل ماري) لمنطقة واشنطن، وستكون دائمًا أقرب خادم، وبالتالي ستُخصص دائمًا لجميع طلبات العملاء. وهكذا، تتكبد خوارزميتنا يوميًا تكلفة السفر بين واشنطن وبالتيمور ذهابًا وإيابًا، أي 110 كيلومترات (70 ميلًا) . بعد عام من هذا النمط من الطلبات، ستكون الخوارزمية قد تكبدت 33,000 كيلومتر (20,500 ميل) : 3,000 كيلومتر لإرسال ماري إلى الساحل الشرقي، و17,500 كيلومتر للرحلات بين واشنطن وبالتيمور. من جهة أخرى، يمكن لخصم مثالي، على دراية بجدول الطلبات المستقبلية، أن يرسل كلاً من ماري ونوح إلى واشنطن وبالتيمور على التوالي، متكبداً تكلفة سفر قدرها 9700 كيلومتر (6000 ميل) مرة واحدة، متجنباً بذلك أي تكاليف سفر مستقبلية. تبلغ نسبة التنافس لخوارزميتنا على هذه المدخلات 20500/6000 أو ما يقارب 3.4، ومن خلال تعديل معلمات هذا المثال، يمكن رفع نسبة التنافس لهذه الخوارزمية إلى أي قيمة كبيرة.   

وهكذا نرى أن تخصيص أقرب خادم دائمًا قد لا يكون الأمثل. من جهة أخرى، يبدو من غير المنطقي أن تُرسل خوارزمية لا تعرف الطلبات المستقبلية كلا فنييها بعيدًا عن سان فرانسيسكو، إذ قد يكون الطلب التالي في تلك المدينة، ما يستدعي إرسال أحدهم فورًا. لذا، يبدو من الصعب، أو حتى المستحيل، على خوارزمية ذات k خادم أن تُحقق أداءً جيدًا مقارنةً بخصمها. مع ذلك، بالنسبة لمسألة الخادمين، توجد خوارزمية لا تتجاوز مسافة تنقلها الإجمالية ضعف مسافة تنقل الخصم. وتنص فرضية k خادم على وجود حلول مماثلة لمسائل ذات عدد أكبر من الفنيين.

مشكلة خادم k غير المتصل بالإنترنت

تُعدّ مسألة الخوادم المتعددة مفيدةً أيضًا في بيئة غير متصلة بالإنترنت، أي عندما يكون تسلسل الطلبات معروفًا تمامًا. على سبيل المثال، في بعض الخوارزميات، يكون تسلسل الوصول إلى الذاكرة مستقلًا عن المدخلات (مثل ضرب المصفوفات )، وبالتالي يمكن حلّ مسألة الترحيل دون اتصال بالإنترنت. وقد ثبت أن هذه المسألة قابلة للحلّ في وقت متعدد الحدود. [ 9 ]

ملحوظات

  1. ↑ ماناس، مارك؛ ماكجيوخ، لايل؛ سليتور، دانيال (1988-01-01). "خوارزميات تنافسية للمسائل عبر الإنترنت" . وقائع الندوة السنوية العشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '88 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 322-333 . doi : 10.1145/62212.62243 . ISBN  978-0-89791-264-8. S2CID 13356897 . 
  2. 1 2 بوبيك، سيباستيان؛ كويستر، كريستيان؛ رباني، يوفال (20-23 يونيو 2023). فرضية الخادم العشوائي 𝑘 خاطئة! المؤتمر السنوي الخامس والخمسون لجمعية ACM حول نظرية الحوسبة (STOC '23). أورلاندو، فلوريدا، الولايات المتحدة الأمريكية: ACM. ص 14. arXiv : 2211.05753 . doi : 10.1145/3564246.3585132 . 
  3. ^ بانسال، نيخيل. بوشبيندر، نيف؛ مادري، الكسندر. ناعور، جوزيف (2015). "خوارزمية متعددة اللوغاريتمات التنافسية لمشكلة خادم k " (PDF) . مجلة ACM . 62 (5): أ40:1-أ40:49. أرخايف : 1110.1580 . دوى : 10.1145/2783434 . السيد 3424197 . S2CID 15668961 .  
  4. ↑ "مشكلة مفتوحة مزعجة أخرى" . 19 نوفمبر 2011.
  5. ↑ لي، جيمس ر. (2017). "Fusible HSTs and the Randomized k-Server Conjecture". arXiv : 1711.01789 [ cs.DS ].
  6. ↑ "تصحيح: HSTS القابل للدمج وتخمين الخادم k العشوائي" .
  7. ↑ غولدبيرغ، ماديسون (2023-11-20). "باحثون يدحضون اعتقادًا شائعًا حول الخوارزميات على الإنترنت" . مجلة كوانتا . تاريخ الاسترجاع: 2023-11-26 .
  8. ↑ العرض التقديمي للفيديو الخاص بالورقة البحثية "تخمين الخادم العشوائي k خاطئ!" في مؤتمر STOC 2023 متاح على يوتيوب.
  9. ↑ Chrobak et al. (1991) .

مراجع

  • فيات، أ.؛ رباني، ي.؛ رافيد، ي. (1990). " خوارزميات الخوادم التنافسية من الرتبة k ". وقائع الندوة السنوية الحادية والثلاثين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . الصفحات 454-463 .