2. Разпределени алгоритми
Програмирането на разпределени системитрябва да се основава на използването на правилни, гъвкави и ефективни алгоритми.
Разработването на разпределени алгоритми е процедура, доста различна по природа от процедурата, използвана при разработването на централизирани алгоритми. Разпределените и централизираните системи се различават в редица съществени аспекти. Следователно изследването и разработването на разпределени алгоритми се развива като самостоятелно поле на научни изследвания.
Разпределени алгоритми срещу централизирани алгоритми
Разпределените системи се различават от централизираните компютърни системи по три важни начина:
(1)Липса на знания за глобалното състояние.
Прицентрализираните решения, управлението на алгоритъмаможе да бъде направеновъз основа на наблюдения на състоянието на системата.
Въпреки че цялото състояние обикновено не може да бъде достъпно в една операция на машината,програмата може да изследва променливите една по еднаи да вземе решение, в което съответната информация в крайна сметка ще бъде оценена. Няма промени в данните между валидирането и решението и това гарантира целостта на решението.
Възлите в разпределена система имат достъп само до собственото си състояние, а не до глобалното състояние на цялата система. Следователно не е възможно да се вземе управленско решение въз основа на глобалното състояние.
Ето фактът, че един възел може да получи информация относно състоянието на други възли и да базира контролни решения на тази информация.
За разлика от централизираните системи, фактът, че получената информация е стара, може да причининевалидна информация, тъй като състоянието на друг възел може да се е променило между изпращането на информацията за състоянието и решението, основано на нея.
Състоянието на комуникационната подсистема (т.е. какви съобщения се предават в даден момент) никога не се наблюдава директно отвъзлите. Тази информация може да бъде изведена само индиректно чрез сравняване на информация за съобщения, изпратени и получени от възлите.
Липса на глобална времева рамка.
Събитията, които съставляват изпълнението на централизиран алгоритъм, са напълно подредени по естествен начин чрез временното им възникване.
За всяка двойка събития всяко събитие се случва по-рано или по-късно от другото.
Времево съотношение, причинено от събитията, съставляващи изпълнението на разпределения алгоритъм - общият им брой.
За някои двойки събития може да има причина да се реши, че всяко събитие се случва преди другото, но за други двойки е така, че нито едно събитие не се случва преди другото. Взаимно изключване може да бъде постигнато в централизирана система, изискваща това изключване. Ако достъпът наprocesspдоresourceзапочне по-късно от достъпа наprocessq, тогава достъпът наprocesspе започнал след края на достъпа наprocessq. Наистина, всички такива събития (начало и край на достъп до процесаpиq)са напълно подредени отрелацията на времеви приоритет.
В разпределена система тези събития не са подредени и една и съща стратегия не е достатъчна.Процесиpиqможе да започнат достъпресурс, като началото на единия не предхожда началото на другия.
Хостътможе да описва изчисления, тъй като тези изчисления се разгръщат от някакъв входнедвусмислено.
При дадена програма и входни данни може да се опише само едно изчисление. За разлика от това, изпълнението на изчисления от разпределена система обикновено е недетерминирано, поради възможни разлики в скоростта на изпълнение на компонентите на системата.
Помислете за ситуация, при коятосървърният процесможеда получава заявки от неизвестен брой потребителски процеси.
Сървърът не може да спре обработката на заявки, докато не бъдат получени всички заявки, защото не знае колко съобщения ще пристигнат. Следователно всяка заявка трябва да бъде обработена незабавно, а редът за обработка ще определи реда, в който пристигат заявките. Редът, в който клиентите изпращат своите заявки, може да е известен, но тъй като закъсненията на предаване не са известни, заявките може да пристигнат в различен ред.
Липсата на знания за глобалното състояние,липса на глобална времева рамкаинедетерминизъмправят дизайна на разпределен алгоритъм сложна процедура, тъй като тези три аспекта се намесват по няколко начина. Понятиятавремеисъстояниеса много взаимосвързани. Вцентрализирани системиконцепцията за време може да бъде дефинирана чрез разглеждане на последователността от състояния, взети от системата по време на изпълнението на алгоритъм за изчисление. Въпреки че в разпределена система може да се дефинира глобално състояние и изпълнението на алгоритъм може да се разглежда като последователност от глобални състояния, това представянее с ограничена употреба, тъй като изпълнението може да бъде описано и от други последователности на глобални състояния. Други алтернативни последователности обикновено се състоят от различни глобални състояния. Това прави твърдението „системата прие това или онова състояние по време на изпълнението на“ много съмнително. Липсата на знания за глобалното състояние може да бъде компенсирана, ако е възможно да се предвиди това глобално състояние от алгоритъма, който се изпълнява. За съжаление, това не е възможно поради присъщиянедетерминизъмпри изпълнението на разпределени системи.