الگوریتم مارزولو

الگوریتم Marzullo توسط مارزولو برای تز دکترا در سال ۱۹۸۴ اختراع شد، الگوریتم توافق در انتخاب منابع برای تخمین دقیق زمان از تعدادی منابع زمان شلوغ استفاده می‌شود. یک نسخه تصحیح شده از آن، به "الگوریتم اشتراک" تغییر نام داده شده‌است، بخشی از پروتکل زمانی شبکه کنونی را می‌سازد.

هدف

الگوریتم Marzullo برحسب زمان برای تولید مقدار بهینه از مجموعه‌ای برآوردها با فاصله اطمینان، جایی که مقدار واقعی ممکن است خارج از فاصله اطمینان برای بعضی منابع باشد کارامد است. در این مورد بهترین تخمین که کوچکترین فاصله ثابت با بزرگترین تعداد منابع هست، گرفته می‌شود.

اگر ما برآوردهای ۱۱ ± ۱ و ۱۰ ± ۲, ۱۲ ± ۱ را داشته باشیم سپس فاصله اینها [۱۰٬۱۲] و [۸٬۱۲], [۱۱٬۱۳]هستند که در شکل ۱۱٫۵ ± ۰٫۵ یا [۱۱٬۱۲] در همهٔ سه مقدار سازگار است.

اگر درعوض محدوده‌ها [۸٬۱۲], [۱۱٬۱۳] و [۱۴٬۱۵] پس فاصله سازگاری بین سه مقدار وجود ندارد اما [۱۱٬۱۲] با بزرگترین تعداد منابع بنام دو از آن‌ها سازگار است.

سرانجام، اگر محدوده‌ها [۸٬۹], [۸٬۱۲] و [۱۰٬۱۲] پس هر دو فاصله [۸٬۹] و [۱۰٬۱۲] سازگار با بزرگترین تعداد منابع هستتند.

این فرایند یک فاصله را تعیین می‌کند. اگر بهترین مقدار از فاصله، نتیجه مطلوب هست پس شیوه ساده که بخواهیم مرکز فاصله را به عنوان مقدار بگیریم، که چیز مشخص شده در الگوریتم Marzullo اصلی بود. مشگل و پیچیده‌ترین روش، تشخیص دادن این که اطلاعات سودمند از فاصله اطمینان منابع را، بیرون پرت کند و آنهم الگوی احتمالی منابع می‌تواند مقدار غیر مرکز را برگشت دهد. توجه به اینکه مقدار محاسبه شده شاید بهتر توصیف می‌کند مانند "خوش بینانه" به جای "بهینه". برای مثال ملاحظه سه فاصله [۱۰٬۱۲], [۱۱, ۱۳] و [۱۱٫۹۹٬۱۳]. الگوریتم محاسبه پایین [۱۱٫۹۹, ۱۲] یا ۱۱٫۹۹۵ ± ۰٫۰۰۵ را توصیف می‌کند که مقدار بسیار دقیقی می‌باشد. اگر ما گمان کنیم که یکی از تخمین‌ها ممکن است نادرست باشد لااقل دو تا برآورد باید درست باشد. در زیر این وضعیت، بهترین تخمین [۱۱٬۱۳] است چون این بزرگترین فاصله‌ای است که همیشه دو تخمین کوچکتر را از وسط قطع می‌کند.

متد

الگوریتم Marzullo با آماده کردن جدولی از منابع، مرتب سازی آن و سپس جستجو (کارامد) برای اشتراک فاصله شروع می‌شود. برای هر منبع محدودهٔ [c−r,c+r] تعریف شده با c ± r وجود دارد. برای هر محدوده جدول دو چندتایی از <offset,type> خواهیم داشت. یک چندتایی شروع محدوده را بیان خواهد کرد، با نوع ۱- مانند <c−r,−1> نشان داده می‌شود و دیگری پایان را با نوع ۱+ مانند <c+r,+1> بیان خواهد کرد. در توصیف الگوریتم از متغیرهای زیر استفاده شده‌است: best(بزرگترین تعداد فاصله دارای اشتراک پیدا شده)، cnt(تعداد جاری از فاصله دارای اشتراک)، beststart و bestend (شروع و پایان بهترین فاصله پیدا شده تاکنون)، i(ایندکس) و جدولی از دوچندتایی‌ها.

  1. ساخت جدول چندتایی‌ها.
  2. مرتب سازی جدول به وسیلهٔ افست. (اگر دو چندتایی با افست مشابه اما نوع معکوس موجود باشد، تعیین اینکه یک فاصله پایان است تنها مانند شروع دیگری است، پس متدی نزدیک به هدف که اول می‌آید لازم است. چنین اتفاقی می‌تواند مطرح شود یک اشتراک بدون مدت، که می‌تواند به وسیلهٔ الگوریتم با قرار دادن نوع ۱- قبل از نوع ۱+ پیدا نمود.
  3. مقداردهی اولیه best=0 cnt=۰
  4. حلقه [انجام دادن هر چندتایی جدول به ترتیب صعودی]
  5. تعداد جاری از فاصله اشتراکی[cnt=cnt-type[i
  6. اگر cnt>best پس best=cnt beststart=offset[i] bestend=offset[i+1]
  7. پایان حلقه [برگشت یک فاصله بهینه] [beststart,bestend].

راندمان

الگوریتم Marzullo در فضا و زمان کارامد می‌باشد. فضای مجانب کاربردی (O(n می‌باشد، جایی که n تعداد منابع است. در نظر به زمان لازم مجانب الگوریتم می‌تواند شامل ساختمان جدول، مرتب سازی و جستجوی آن مطرح شود. مرتب سازی می‌تواند در زمان (O(n lognانجام شود، و این برساختن و مرحله جستجو که می‌تواند در زمان خطی انجام شود تسلط دارد. بنابراین زمان کارایی الگوریتم Marzullo O(n log n(می‌باشد. یکوققتی ساخت و مرتب سازی جدول ممکن است فاصله یک منبع را جدید کند (زمانی اطلاعات جدیدی دریافت می‌شود) در زمان خطی بوده‌است. بنابراین به هنگام سازی داده‌های یک منبع و پیدا کردن بهترین فاصله می‌تواند در زمان (O(n انجام شود.

منابع
    • K. A. Marzullo. Maintaining the Time in a Distributed System: An Example of a Loosely-Coupled Distributed Service. Ph.D. dissertation, Stanford University, Department of Electrical Engineering, February 1984.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.