Brooks–Iyengar algorithm
بروکس-آئینگر الگورتھم یا فیوز سی پی اے الگورتھم یا بروکس-آئینگر ہائبرڈ الگورتھم ایک تقسیم شدہ الگورتھم ہے جو تقسیم شدہ سینسر نیٹ ورک کے ذریعہ لی گئی وقفے کی پیمائش کی درستگی اور درستگی دونوں کو بہتر بناتا ہے، یہاں تک کہ ناقص سینسر کی موجودگی میں بھی۔ سینسر نیٹ ورک ہر دوسرے نوڈ کے ساتھ ہر نوڈ پر ناپی گئی قیمت اور درستگی کی قیمت کا تبادلہ کرکے ایسا کرتا ہے، اور جمع کردہ تمام اقدار سے پورے نیٹ ورک کے لیے درستگی کی حد اور ناپی گئی قیمت کا حساب لگاتا ہے۔ یہاں تک کہ اگر کچھ سینسرز کا کچھ ڈیٹا ناقص ہے، تو بھی سینسر نیٹ ورک خراب نہیں ہوگا۔ الگورتھم غلطی برداشت کرنے والا اور تقسیم شدہ ہے۔ اسے سینسر فیوژن طریقہ کے طور پر بھی استعمال کیا جا سکتا ہے۔ اس الگورتھم کی درستگی اور درستگی 2016 میں ثابت ہوئی ہے۔ پس منظر شور کے اعداد و شمار کی موجودگی میں تقسیم شدہ کنٹرول کے لیے بروکس-آئینگر ہائبرڈ الگورتھم سینسر فیوژن کے ساتھ بازنطینی معاہدے کو جوڑتا ہے۔ یہ سینسر فیوژن اور بازنطینی فالٹ رواداری کے درمیان فرق کو ختم کرتا ہے۔ اس بنیادی الگورتھم نے پہلی بار ان مختلف شعبوں کو متحد کیا۔ بنیادی طور پر، یہ مہانے اور شنائڈر کے فاسٹ کنورجنس الگورتھم (ایف سی اے) کے ساتھ تقریبا معاہدے کے لیے ڈولیو کے الگورتھم کو یکجا کرتا ہے۔ الگورتھم این پروسیسنگ عناصر (پی ای) کو فرض کرتا ہے، جن میں سے ٹی ناقص ہیں اور بدنیتی سے برتاؤ کر سکتے ہیں۔ یہ ان پٹ کے طور پر یا تو حقیقی اقدار کو موروثی غلطی یا شور کے ساتھ لیتا ہے (جو نامعلوم ہو سکتا ہے)، یا حقیقی قدر کو غیر یقینی صورتحال کے ساتھ، یا وقفہ کے طور پر لیتا ہے۔ الگورتھم کا آؤٹ پٹ واضح طور پر مخصوص درستگی کے ساتھ ایک حقیقی قدر ہے۔ الگورتھم او (این ایل او این) میں چلتا ہے جہاں این پی ای کی تعداد ہے۔ کروسیڈر کے کنورجنس الگورتھم (سی سی اے) کے مطابق اس الگورتھم میں ترمیم کرنا ممکن ہے، تاہم، بینڈوتھ کی ضرورت میں بھی اضافہ ہوگا۔ الگورتھم میں تقسیم شدہ کنٹرول، سافٹ ویئر کی وشوسنییتا، اعلی کارکردگی والے کمپیوٹنگ وغیرہ میں ایپلی کیشنز ہیں۔ الگورتھم بروکس-آئینگر الگورتھم کو تقسیم شدہ سینسر نیٹ ورک کے ہر پروسیسنگ عنصر (پی ای) میں انجام دیا جاتا ہے۔ ہر پی ای نیٹ ورک میں موجود دیگر تمام پی ای کے ساتھ اپنے ماپا ہوا وقفہ بدلتا ہے۔ "فیوزڈ" پیمائش پائے جانے والے علاقوں کے وسط نکات کی اوسط اوسط ہے۔ بروکس-آئینگر الگورتھم کے ٹھوس اقدامات اس حصے میں دکھائے گئے ہیں۔ ہر پی ای الگورتھم کو الگ الگ انجام دیتا ہے: ان پٹ: پی ای کے کے ذریعے پی ای آئی کو بھیجی گئی پیمائش ایک بند وقفہ ہے، آؤٹ پٹ: پی ای آئی کے آؤٹ پٹ میں ایک پوائنٹ تخمینہ اور ایک وقفہ تخمینہ پی ای آئی شامل ہے جو دیگر تمام پی ای سے پیمائش وصول کرتا ہے۔ جمع شدہ پیمائشوں کے اتحاد کو آپس میں الگ الگ وقفوں میں تقسیم کریں جو پیمائش کی تعداد کی بنیاد پر جو ایک دوسرے کو کاٹتی ہے، جسے وقفہ کا وزن کہا جاتا ہے۔ کم وزن والے وقفوں کو ہٹا دیں، ناقص پی ای کی تعداد کہاں ہے اگر ایل وقفے باقی ہیں، تو باقی وقفوں کے سیٹ کو ظاہر کریں۔ ہمارے پاس ہے، جہاں وقفہ اور وقفہ سے وابستہ وزن ہے۔ ہم بھی فرض کرتے ہیں۔ پی ای آئی کے نقطہ تخمینے کا حساب لگائیں اور وقفے کا تخمینہ مثال ہے: 5 پی ای کی ایک مثال پر غور کریں، جس میں پی ای 5 () دوسرے پی ای کو غلط اقدار بھیج رہا ہے اور وہ سب اقدار کا تبادلہ کرتے ہیں۔ موصول ہونے والی اقدار اگلے جدول میں ہیں۔ ہم ان وقفوں کا وزن والے علاقے کا خاکہ (ڈبلیو آر ڈی) کھینچتے ہیں، پھر ہم الگورتھم کے مطابق پی ای 1 کا تعین کر سکتے ہیں: جو ان وقفوں پر مشتمل ہوتا ہے جہاں کم از کم 4 (= = 5−1) پیمائش ایک دوسرے کو کاٹتی ہیں۔ پی ای 1 کی پیداوار برابر ہے اور وقفے کا تخمینہ اسی طرح ہے، ہم 5 پی ای کے تمام ان پٹ اور نتائج حاصل کر سکتے ہیں: متعلقہ الگورتھم 1982 بازنطینی مسئلہ: دو جرنیلوں کے مسئلے کی توسیع کے طور پر بازنطینی عمومی مسئلہ کو بائنری مسئلہ کے طور پر دیکھا جا سکتا ہے۔ 1983 لگ بھگ اتفاق رائے: یہ طریقہ سیٹ سے کچھ اقدار کو ہٹا دیتا ہے جو اسکیلرز سے لے کر روادار ناقص ان پٹ پر مشتمل ہوتا ہے۔ 1985 عین مطابق اتفاق رائے: یہ طریقہ ان پٹ کے طور پر اسکیلر کا بھی استعمال کرتا ہے۔ 1996 بروکس-آئینگر الگورتھم: طریقہ وقفوں پر مبنی ہے۔ 2013 بازنطینی ویکٹر اتفاق رائے: یہ طریقہ ویکٹر کو ان پٹ کے طور پر استعمال کرتا ہے۔ 2013 کثیر جہتی معاہدہ: طریقہ کار ویکٹر کو ان پٹ کے طور پر بھی استعمال کرتا ہے جبکہ فاصلے کی پیمائش مختلف ہوتی ہے۔ ہم وقفہ کے آدانوں سے نمٹنے کے لیے لگ بھگ اتفاق رائے (اسکیلر پر مبنی)، بروکس-آئینگر الگورتھم (وقفہ پر مبنی) اور بازنطینی ویکٹر اتفاق رائے (ویکٹر پر مبنی) کا استعمال کر سکتے ہیں، اور مقالے نے ثابت کیا کہ بروکس-آئینگر الگورتھم یہاں بہترین ہے۔ ایپلیکیشن بروکس-آئینگر الگورتھم ایک بنیادی کام ہے اور ڈسٹری بیوٹڈ سینسنگ میں ایک اہم سنگ میل ہے، اور اسے بے کارانہ کے بہت سے منظرناموں کے لیے غلطی برداشت کرنے والے حل کے طور پر استعمال کیا جا سکتا ہے۔ اس کے علاوہ، کسی بھی نیٹ ورکنگ سسٹم کو لاگو کرنا اور اس میں شامل کرنا آسان ہے۔ 1996 میں، الگورتھم کو منیکس میں زیادہ درستگی اور درستگی فراہم کرنے کے لیے استعمال کیا گیا تھا، جس کی وجہ سے آر ٹی-لینکس کا پہلا ورژن تیار ہوا۔ 2000 میں، الگورتھم DARPA SensIT پروگرام کے تقسیم شدہ ٹریکنگ پروگرام کے لیے بھی مرکزی تھا۔ متعدد سینسرز سے صوتی، زلزلے اور حرکت کا پتہ لگانے کی ریڈنگ کو یکجا کیا جاتا ہے اور تقسیم شدہ ٹریکنگ سسٹم میں ڈالا جاتا ہے۔ اس کے علاوہ، اس کا استعمال بی بی این ٹیکنالوجیز، بی اے ای سسٹمز، پین اسٹیٹ اپلائیڈ ریسرچ لیب (اے آر ایل)، اور یو ایس سی/آئی ایس آئی کے ذریعے دائر کردہ ایپلی کیشن میں متنوع سینسر فیڈز کو یکجا کرنے کے لیے کیا گیا تھا۔ برطانیہ کے دفاعی مینوفیکچرر تھیلز گروپ نے اس کام کو اپنی گلوبل آپریشنل اینالیسس لیبارٹری میں استعمال کیا۔ اس کا اطلاق رے تھیون کے پروگراموں پر ہوتا ہے جہاں بہت سے نظاموں کو ناقابل اعتماد سینسر نیٹ ورک سے قابل اعتماد ڈیٹا نکالنے کی ضرورت ہوتی ہے، اس سے سینسر کی وشوسنییتا کو بہتر بنانے میں بڑھتی ہوئی سرمایہ کاری سے مستثنی ہے۔ نیز، اس الگورتھم کو تیار کرنے میں تحقیق کے نتیجے میں امریکی بحریہ کے ذریعہ اپنے سمندری ڈومین آگاہی سافٹ ویئر میں استعمال ہونے والے ٹولز سامنے آتے ہیں۔ تعلیم میں، بروکس-آئینگر الگورتھم کو تدریسی کلاسوں جیسے یونیورسٹی آف وسکونسن، پرڈیو، جارجیا ٹیک، کلیمسن یونیورسٹی، یونیورسٹی آف میری لینڈ وغیرہ میں بڑے پیمانے پر استعمال کیا گیا ہے۔ سینسر نیٹ ورک کے شعبے کے علاوہ، وقت سے متحرک فن تعمیر، سائبر فزیکل سسٹمز کی حفاظت، ڈیٹا فیوژن، روبوٹ کنورجنس، اعلی کارکردگی والے کمپیوٹنگ، سافٹ ویئر/ہارڈ ویئر کی وشوسنییتا، مصنوعی ذہانت کے نظام میں انسمبل لرننگ جیسے دیگر شعبے بھی بروکس-آئینگر الگورتھم سے فائدہ اٹھا سکتے ہیں۔ الگورتھم کی خصوصیات ناقص پی ای کو برداشت کیا گیا <این/3 زیادہ سے زیادہ ناقص پی ای <2 این/3 پیچیدگی = او (این لاگ این) نیٹ ورک بینڈوتھ کا آرڈر = او (این) کنورجنس = 2 ٹی/این درستگی = درستگی کے لیے ان پٹ آئیٹریٹس کے ذریعے محدود = اکثر درستگی پر درستگی = درستگی پر کوئی درستگی نہیں = نہیں یہ بھی دیکھیں تقسیم شدہ سینسر نیٹ ورک سینسر فیوژن فالٹ ٹالرنس اتفاق رائے (کمپیوٹر سائنس) چندر-توئیگ اتفاق رائے الگورتھم پیکسوس اتفاق رائے پروٹوکول رافٹ اتفاق رائے الگورتھم مارزولو کا الگورتھم انٹرسیکشن الگورتھم دو جنرلز کے مسئلہ ایوارڈز اور شناخت بروکس آئینگر الگورتھم کے موجد ڈاکٹر بروکس اور ایس ایس ڈاکٹر آئینگر کو موصول ہوا اعلی اثرات کی تحقیق اور اس کام نے امریکی حکومت کے متعدد پروگراموں اور تجارتی مصنوعات کو کس طرح متاثر کیا ہے۔ پروفیسر اسٹیو یاؤ سے ایوارڈ وصول کرتے ہوئے ڈاکٹر ایس ایس آئینگر، آئی ای ای ای ڈاکٹر ایس ایس آئینگر اپنے طالب علم ڈاکٹر بروکس کے ساتھ حوالہ جات تقسیم شدہ کمپیوٹنگ کے مسائل حساب کی غلطی رواداری تھیوری