Фундаментальная теорема асинхронных параллельных вычислений Келлера.

Система переходов <S, F, A, > некоторой помеченной системы является сходящейся тогда и только тогда, когда помеченная система переходов обладает свойствами локальной детерминированности (детерминизм), коммутативности и устойчивости.

Локальный детерминизм

Локальная коммутативность

Локальная устойчивость

F - бинарное отношение следования

F⁺ - бинарное отношение достижимости

30. Свойства помеченной системы переходов и глобальные свойства порождающей её системы переходов Келлера.

Опр. S = {S1, .., Sn}, F S x S, A = { …}, : F -> A – функция пометки ребер.

Порождающая система всегда одна, а помеченных систем несколько.

Теорема (Рассела – Черча): Если метамодель обладает свойством сходимости, то такая система, то такая модель порождает процессы, приводящие к одному результату.

Эта теорема объясняет, зачем вообще нужно это свойство сходимости: процессы, порождаемые системой, обладающей этим св-вом, приводят к 1-му результату.

Келлер доказал теорему, в которой он свел глобальное абстрактное свойство сходимости порождающей непомеченной системы переходов к выполнению локальных свойств помеченной системы, порождённой ею: детерминированности, коммутативности, устойчивости.

Теорема: Если асинхронные процессы, порождаемые некоторой метамоделью, обладают локальными свойствами: детерминир., коммут., устойч., то такая метамодель обладает свойствами сходимости.

31. Метамодель Варшавского: определение, способы задания. Соглашения по назначению инициаторов и результантов. Представление процессов.

Назовём асинхронным пр-ссом (АП) четвёрку <S, F, I, R>, в которой:

S – непустое множество ситуаций; F S x S – отношение непосредственного следования ситуаций;

I S – множество инициаторов (состояний, активизирующих процесс), т.е. таких ситуаций из S, для которых если i F s_k, i Î I, s_k Ï I, то из s_k F s_l следует, что s_l Ï I;

R S – множество результантов (финальных состояний), т.е. таких ситуаций из S, для которых, если r F s, r Î R, то s Î R.

Каждый разработчик сам определяет (на основе семантики процесса), какие состояния будут в I и R.

//в любое состояние можем попасть, и из него можем попасть в конечное.

По поводу представления процессов… У Варшавского процесс – это весь граф: и вершины и дуги.