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