СИНХРОНИЗАЦИЯ ТАКТОВЫХ ГЕНЕРАТОРОВ В АСИНХРОННОЙ РАСПРЕДЕЛЕННОЙ СИСТЕМЕ Российский патент 2013 года по МПК G06F1/12 

1. Уровень техники и соответствующая область техники

Компьютерные системы и связанная технология оказывают влияние на многие аспекты общества. Несомненно, способность компьютерной системы обрабатывать информацию преобразовала способ, которым мы живем и работаем. Компьютерные системы сегодня обычно выполняют массу задач (например, обработку текстов, планирование, учет и т.д.), которые до появления компьютерной системы выполнялись вручную. В последнее время компьютерные системы соединены друг с другом и с другими электронными устройствами, чтобы образовать проводные и беспроводные компьютерные сети, по которым компьютерные системы и другие электронные устройства могут передавать электронные данные. Соответственно, выполнение многих вычислительных задач распределяется по некоторому количеству разных компьютерных систем и/или некоторому количеству разных вычислительных сред.

Сети фактически стали настолько преуспевающими, что простая сетевая вычислительная система может взаимодействовать с любой из миллионов других вычислительных систем, развернутых по всей планете, по конгломерату сетей, часто называемых "Интернетом". Такие вычислительные системы могут включать в себя настольные, переносные или планшетные персональные компьютеры; персональные цифровые помощники (PDA); телефоны; или любой другой компьютер или устройство, допускающие взаимодействие по цифровой сети.

Чтобы взаимодействовать по сети, одна вычислительная система (называемая в этом документе "отправляющей вычислительной системой") создает или иным образом обращается к электронному сообщению и передает электронное сообщение по сети другой вычислительной системе (называемой в этом документе "принимающей вычислительной системой"). Электронное сообщение может быть прочитано пользователем, когда электронное сообщение является электронной почтой или мгновенным сообщением, или взамен может быть прочитано приложением, работающим на принимающей вычислительной системе. Электронное сообщение может создаваться приложением, работающим на отправляющей вычислительной системе, с возможным содействием пользователя.

В распределенной вычислительной среде некоторое количество разных узлов может взаимодействовать для выполнения нужных вычислительных операций. Подходящее выполнение вычислительных операций часто может зависеть от различных других узлов, имеющих некоторое общее понимание времени между собой. Многие системы используют "главный" тактовый генератор, к которому могут обращаться узлы для получения абсолютного времени, которое обычно распространяется всем узлам. Однако синхронизация тактовых генераторов с абсолютным временем требует протокола синхронизации и высокой соединяемости. Тактовая синхронизация посредством обращения к главному тактовому генератору также приводит к возможным узким местам и центральным точкам отказа. В некоторых сетях, таких как Интернет, высокая соединяемость практически невозможна, поскольку компьютерные системы часто подключаются и отключаются от сети.

Некоторые одноранговые системы используют периодические синхронизации с общим источником импульсов истинного времени, чтобы добиться псевдосинхронной работы. Таким образом, эти системы также имеют общего временного главного, который должен существовать и быть доступным в определенные моменты (например, присоединение нового участника), чтобы иметь надежную и безопасную систему.

КРАТКАЯ СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Настоящее изобретение распространяется на способы, системы и компьютерные программные продукты для синхронизации тактовых генераторов в асинхронной распределенной системе. В некоторых вариантах осуществления определяется расхождение между тем, какое время подразумевает наблюдающая компьютерная система в другой наблюдаемой компьютерной системе, и фактическим (локальным) временем в наблюдаемой компьютерной системе. Наблюдающая компьютерная система принимает участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой.

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

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

Наблюдающая компьютерная система вычисляет разность между верхней границей и нижней границей. Наблюдающая компьютерная система вычисляет максимальное расхождение между тем, какое время подразумевает наблюдающая компьютерная система в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе путем деления вычисленной разности на усредняющий коэффициент, например деления вычисленной разности пополам. Последующие обмены сообщениями могут использоваться для дополнительного уточнения нижней и верхней границ. Наблюдающая компьютерная система может вычислить диапазон времени, указывающий, когда произошло событие в наблюдаемой компьютерной системе, на основе нижней и верхней границы.

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

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

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

Дополнительные признаки и преимущества изобретения будут изложены в последующем описании и частично будут очевидны из этого описания, либо могут быть изучены при применении изобретения на практике. Признаки и преимущества изобретения могут быть реализованы и получены посредством инструментов и сочетаний, подробно указанных в прилагаемой формуле изобретения. Эти и другие признаки настоящего изобретения станут более очевидными из нижеследующего описания и прилагаемой формулы изобретения, либо могут быть изучены при применении изобретения на практике, как изложено далее.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг.1 иллюстрирует примерную асинхронную распределенную систему, которая обеспечивает синхронизацию тактовых генераторов в асинхронной распределенной системе.

Фиг.2 - блок-схема алгоритма примерного способа для определения расхождения между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе.

Фиг.3 - блок-схема алгоритма примерного способа для указания времени, в которое произошло событие в наблюдаемой компьютерной системе.

Фиг.4 - блок-схема алгоритма примерного способа для вычисления максимального расхождения между тактовыми генераторами в разных компьютерных системах в асинхронной распределенной системе, которая включает в себя множество компьютерных систем.

Фиг.5 иллюстрирует примерную архитектуру компьютера, которая обеспечивает вычисление максимального расхождения между тактовыми генераторами в разных компьютерных системах в асинхронной распределенной системе, которая включает в себя множество компьютерных систем.

ПОДРОБНОЕ ОПИСАНИЕ

Настоящее изобретение распространяется на способы, системы и компьютерные программные изделия для синхронизации тактовых генераторов в асинхронной распределенной системе. В некоторых вариантах осуществления определяется расхождение между тем, какое время подразумевает наблюдающая компьютерная система в другой наблюдаемой компьютерной системе, и фактическим (локальным) временем в наблюдаемой компьютерной системе. Наблюдающая компьютерная система принимает участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой.

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

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

Наблюдающая компьютерная система вычисляет разность между верхней границей и нижней границей. Наблюдающая компьютерная система вычисляет максимальное расхождение между тем, какое время подразумевает наблюдающая компьютерная система в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе путем деления вычисленной разности на усредняющий коэффициент, например деления вычисленной разности пополам. Последующие обмены сообщениями могут использоваться для дополнительного уточнения нижней и верхней границ. Наблюдающая компьютерная система может вычислить диапазон времени, указывающий, когда произошло событие в наблюдаемой компьютерной системе, на основе нижней и верхней границы.

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

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

Варианты осуществления настоящего изобретения могут содержать или использовать специализированный или универсальный компьютер, включающий в себя аппаратные средства компьютера, которые подробнее обсуждаются ниже. Варианты осуществления в рамках объема настоящего изобретения также включают в себя физические и другие машиночитаемые носители для переноса или хранения исполняемых компьютером команд и/или структур данных. Такие машиночитаемые носители могут быть любыми доступными носителями, к которым можно обращаться посредством универсальной или специализированной компьютерной системы. Машиночитаемые носители, которые хранят исполняемые компьютером команды, являются физическими носителями информации. Машиночитаемые носители, которые переносят исполняемые компьютером команды, являются передающими средами. Таким образом, в качестве примера, а не ограничения, варианты осуществления изобретения могут содержать по меньшей мере два отчетливо разных вида машиночитаемых носителей: физические носители информации и передающие среды.

Физические носители информации могут содержать RAM, ROM, EEPROM, компакт-диск или другой накопитель на оптических дисках, накопитель на магнитных дисках или другие магнитные запоминающие устройства, либо любой другой носитель, который может использоваться для хранения необходимого средства программного кода в виде выполняемых компьютером команд или структур данных, и к которому [носителю] можно обращаться посредством универсального или специализированного компьютера.

"Сеть" задается в качестве одного или нескольких каналов передачи данных, которые дают возможность переноса электронных данных между компьютерными системами и/или модулями и/или другими электронными устройствами. Когда информация предается или предоставляется компьютеру по сети или другому соединению связи (одному из проводного, беспроводного или сочетания проводного или беспроводного), компьютер по существу рассматривает соединение как передающую среду. Передающие среды могут включать в себя сетевые каналы и/или каналы передачи данных, которые могут использоваться для переноса нужного средства программного кода в виде исполняемых компьютером команд или структур данных и к которым можно обращаться с помощью универсального или специализированного компьютера. Сочетания вышеперечисленного также следует включить в область машиночитаемых носителей.

Дополнительно, после достижения различных компонентов компьютерной системы, средство программного кода в виде исполняемых компьютером команд или структур данных может быть автоматически перенесено из передающих сред на физические носители информации (или наоборот). Например, исполняемые компьютером команды или структуры данных, принятые по сети или каналу передачи данных, могут быть буферизованы в RAM в сетевом интерфейсном модуле (например, "NIC"), а затем в итоге переданы в RAM компьютерной системы и/или в менее энергозависимые физические носители информации в компьютерной системе. Таким образом, следует понимать, что физические носители информации могут включаться в компоненты компьютерной системы, которые также (или даже в основном) используют передающие среды.

Исполняемые компьютером команды содержат, например, команды и данные, которые заставляют универсальный компьютер, специализированный компьютер или специализированное устройство обработки выполнять определенную функцию или группу функций. Исполняемые компьютером команды могут быть, например, двоичным кодом, командами промежуточного формата, например языком ассемблера, или даже исходным кодом. Несмотря на то что предмет изобретения описан на языке, характерном для структурных признаков и/или методологических действий, необходимо понимать, что предмет изобретения, определенный в прилагаемой формуле, не обязательно ограничивается описанными выше конкретными признаками или действиями. Скорее, описанные признаки и действия раскрываются в качестве примерных форм реализации формулы изобретения.

Специалисты в данной области техники примут во внимание, что изобретение может быть применено на практике в сетевых вычислительных средах со многими типами конфигураций компьютерных систем, включая персональные компьютеры, настольные компьютеры, переносные компьютеры, процессоры сообщений, карманные устройства, многопроцессорные системы, микропроцессорную или программируемую бытовую электронику, сетевые ПК, мини-компьютеры, мэйнфреймы, мобильные телефоны, PDA, пейджеры, маршрутизаторы, коммутаторы и т.п. Изобретение также может быть применено на практике в распределенных средах, где задачи выполняют локальные и удаленные компьютерные системы, которые связаны через сеть (либо с помощью проводных каналов передачи данных, беспроводных каналов передачи данных, либо сочетания проводных и беспроводных каналов передачи данных). В распределенной среде программные модули могут размещаться как на локальных, так и на удаленных запоминающих устройствах.

В рамках этого описания и нижеследующей формулы изобретения квантованный задается как не являющийся непрерывным, то есть хранящим значение в течение некоторой длительности (например, одной секунды), а затем переходящим на новое значение.

В рамках этого описания и нижеследующей формулы изобретения уход задается в виде одного тактового генератора, не работающего с точной скоростью по сравнению с другим тактовым генератором. Таким образом, после некоторого количества времени один тактовый генератор может "разойтись" с другим тактовым генератором. Тактовые генераторы могут уходить в разных направлениях (например, либо отставая, либо уходя вперед относительно другого тактового генератора) и могут уходить с разными скоростями. Уход отдельного тактового генератора также может меняться в разные моменты в ответ на изменения окружающей среды, например изменения температуры окружающей среды, мощности батареи и т.д.

Как правило, тактовые генераторы в асинхронной системе могут соответствовать одному или нескольким ограничениям. Например, тактовые генераторы настоящего компьютера могут ограничиваться прохождением времени очень близко к одинаковой частоте (которая измерена прогрессом значений их локальных тактовых генераторов). Таким образом, (относительно небольшие и возможно незначительные) погрешности в механике тактовых генераторов могут компенсироваться в наихудшем случае. Соответственно, варианты осуществления изобретения используют алгоритм, который рассматривает такие ограничения, так что рассматриваемый наблюдатель может сотрудничать с другими наблюдателями для установления относительно строгих границ для значения тактовых генераторов других наблюдателей в данное время с точки зрения рассматриваемого наблюдателя (даже если рассматриваемый наблюдатель не может напрямую наблюдать те другие тактовые генераторы).

Соответственно, варианты осуществления изобретения могут быть реализованы для обеспечения относительно целостного (надежного) представления о текущем времени в наихудшем случае (например, при огромном расхождении) во всей асинхронной системе - без использования сущности общего внешнего генератора истинного времени. Компьютерные системы в асинхронной распределенной системе не обладают зависимостью от общего временного главного и соответственно являются практически "самостоятельными".

В некоторых вариантах осуществления рассматриваемый наблюдатель (например, узел) может наблюдать значение одного тактового генератора (его тактового генератора), и множество равноправных наблюдателей (в таком же виде нашего рассматриваемого наблюдателя) могут передавать асинхронные не мгновенные сообщения другим наблюдателям, внося неопределенную задержку посредством канала связи между наблюдателями.

Описание некоторых примеров изобретения предоставляется на основе следующих обозначений:

1. t0, t1, t2,… являются указаниями определенных событий на общей временной шкале.

2. (t1-t0) описывает точную длительность между двумя событиями (t1 и t0).

3. Если событие t0 происходит перед другим событием t1, то: t0<t1.

4. X(t0) является значением тактового генератора X, который наблюдается, когда происходит событие t0.

3. (X(t1)-X(t0)) является величиной длительности (промежутком времени) между двумя событиями (t1 и t0), которая измерена тактовым генератором X.

5. O_X задает наблюдателя тактового генератора X.

6. O_X.отправка(O_Y, {содержимое}) представляет событие, в котором O_X отправляет сообщение (например, запрос) к O с заданным содержимым.

7. O_X.прием(O_Y, {содержимое}) представляет событие, в котором O_X принимает сообщение (например, ответ) от O_Y с заданным содержимым.

Таким образом, в рамках асинхронной распределенной системы имеются следующие ограничения:

A. Значение тактового генератора увеличивается монотонно:

если t0<t1, то X(t0)<=X(t1).

B. Имеется верхняя граница у шага квантования тактового генератора, Q, так что для любого тактового генератора X:

если t0+Q<t1, то X(t0)<X(t1).

C. Имеется верхняя граница ухода тактового генератора, D, так что для любого тактового генератора X и событий t0<t1:

если t0<t1, то (1-D)*(X(t1)-X(t0))<=(t1-t0)+Q.

D. И

если t0<t1, то (t1-t0)<=((1+D)*(X(t1)-X(t0)))+Q.

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

@t0: O_X наблюдает X(t0)

@t1: O_X.отправка(O_Y, {X(t0)})

@t2: O_Y.прием(O_X, {X(t0)})

@t3: O_Y наблюдает Y(t3)

@t4: O_Y.отправка(O_X, {X(t0), Y(t3)})

@t5: O_X.прием(O_Y, {X(t0), Y(t3)})

@t6: O_X наблюдает X(t6)

Последовательность обмена сообщениями соответствует операции запроса/ответа, где O_X запрашивает у O_Y текущее значение локального тактового генератора O_Y, записывая, когда он сделал это (t0) и когда получил ответ (t6). O_X теперь знает, что Y имел значение Y(t3) в некоторый момент между временем, когда локальный X тактовый генератор имел значение X(t0) и когда локальный тактовый генератор X имел значение X(t6). Хотя сочетание сообщений может использоваться для представления глобального порядка, каждый из O_X и O_Y может работать в соответствии с их собственной независимой временной шкалой.

В случае идеальных локальных тактовых генераторов, которые не уходят, O_X может установить следующие границы на значение тактового генератора Y в любой момент t после t6:

Y(t)>=X(t)-(X(t6)-Y(t3))

Y(t)<=X(t)+(Y(t3)-X(t0))

Учитывая квантование, O_X может установить следующие границы на значение тактового генератора Y в любой момент t после t6:

Y(t)>=X(t)-(X(t6)-Y(t3)+2Q)

Y(t)<=X(t)+(Y(t3)-X(t0)+2Q)

Элемент Q представляет, что тактовые генераторы квантуются. Чтобы увидеть, что квантование добавляет элемент двух Q к каждой из границ, предположим, что наблюдение было выполнено так, что X(t0)=0, Y(t3)=1 и X(t6)=2. Это наводило бы на мысль, что тактовые генераторы были синхронизированы с неопределенностью, равной 2. Чтобы обнаружить фактическую неопределенность, можно рассмотреть граничные случаи для каждого из трех тактовых генераторов, которые могли бы привести к этому наблюдению:

X наблюдает X(t0) Y наблюдает Y(t3) X наблюдает X(t6) Максимальная отрицательная ошибка Максимальная положительная ошибка 0+Δ 1+Δ 2+Δ 1 1 0+Δ 1+Δ 3-Δ 1 2-2Δ 0+Δ 2-Δ 2+Δ 2-2Δ 2Δ 0+Δ 2-Δ 3-Δ 2-2Δ 1 1-Δ 1+Δ 2+Δ 2Δ 1 1-Δ 1+Δ 3-Δ 2Δ 2-2Δ 1-Δ 2-Δ 2+Δ 1 2Δ 1-Δ 2-Δ 3-Δ 1 1

Первые три столбца указывают время наблюдения относительно времени, когда тактовый генератор переходит на заданное значение. Например, во втором столбце "2-Δ" указывает время события, которое предшествует событию, в котором Y изменяет свое значение с 1 на 2. Четвертый столбец является разностью между столбцами 1 и 2, а пятый столбец является разностью между столбцами 2 и 3.

Получая максимальные значения из двух последних столбцов и позволяя Δ стремиться к 0, мы обнаруживаем, что максимальная неопределенность в любом направлении равна 2. Сравнивая это с наблюдаемой неопределенностью, квантование внесло возможную ошибку в 2 кванта. Это может быть обобщено для любого X(t0), Y(t3) и X(t6) путем наблюдения, что изменения в этих значениях одинаково влияют как на наблюдаемые результаты, так и на возможные граничные случаи. Таким образом, квантование вносит элемент ошибки, равный 2Q.

Учитывая квантование и уход тактового генератора, O_X может установить следующие границы на значение тактового генератора Y в любой момент t после t6:

Y(t)>=X(t)-(X(t6)-Y(t3)+2Q)-2D(X(t)-(X(t6)+X(t0))/2+2Q)

Y(t)<=X(t)+(Y(t3)-X(t0)+2Q)+2D(X(t)-(X(t6)+X(t0))/2+2Q)

Разность между этими значениями равна:

(X(t)+(Y(t3)-X(t0)+2Q)+2D(X(t)-(X(t6)+X(t0))/2+2Q))-

(X(t)-(X(t6)-Y(t3)+2Q)-2D(X(t)-(X(t6)+X(t0))/2+2Q))

=X(t)-X(t)+Y(t3)-Y(t3)+X(t6)-X(t0)+4Q+4D(X(t)-(X(t6)+X(t0))/2+2Q)

=X(t6)-X(t0)+4Q+4D(X(t)-(X(t6)+X(t0))/2+2Q)

Это подразумевает максимальную ошибку, равную:

(X(t6)-X(t0))/2+2Q+2D(X(t)-(X(t6)+X(t0))/2+2Q)

В этом выражении (X(t6)-X(t0)) равно времени, которое требуется для взаимодействия запрос-ответ от O_X к O_Y и обратно. Q зависит от того, как часто обновляются значения тактовых генераторов. Завершающий элемент 2D(X(t)-(X(t6)+X(t0))/2+2Q) указывает, как граница становится слабее со временем (то есть затухает) из-за возможного ухода тактового генератора.

Запрос последовательности обмена сообщениями может повторяться несколько раз, и O_X может выбирать самую близкую верхнюю границу из любого запроса и может выбирать самую близкую нижнюю границу из любого запроса. При выборе самая близкая верхняя граница и самая близкая нижняя граница не должны поступать из одного и того же запроса. С помощью периодического повторения запроса последовательности обмена сообщениями наблюдатель (в этом примере O_X) может минимизировать третий элемент, поскольку в любой момент T это будет последним измерением.

Фиг.1 иллюстрирует асинхронную распределенную систему 100, которая обеспечивает синхронизацию тактовых генераторов в асинхронной распределенной системе 100. Ссылаясь на фиг.1, архитектура 100 компьютера включает в себя компьютерные системы 101, 151 и другие компьютерные системы 191. Каждая из изображенных компьютерных систем и их соответствующие компоненты могут быть подключены друг к другу по каналу связи (или быть его частью), например, по локальной сети ("LAN"), глобальной сети ("WAN"), универсальной последовательной шине (USB) и даже по Интернету. Соответственно, каждый из изображенных компонентов, а также любые другие подключенные компоненты могут создавать связанные с сообщением данные и обмениваться связанными с сообщением данными (например, дейтаграммами Интернет-протокола ("IP") и других высокоуровневых протоколов, которые используют дейтаграммы IP, например Протокол управления передачей ("TCP"), протокол передачи гипертекстовых файлов ("HTTP"), простой протокол электронной почты ("SMTP") и т.д.) по сети.

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

Как изображено, компьютерная система 101 включает в себя модуль 102 управления тактовым генератором и тактовый генератор 103. Как правило, компьютерная система 101 конфигурируется для участия в последовательностях обмена запросом/ответным сообщением с другими компьютерными системами и поддержания предполагаемого времени в наблюдаемых компьютерных системах на основе данных о времени, ассоциированных с последовательностями обмена запросом/ответным сообщением.

Модуль 102 управления тактовым генератором конфигурируется для записи и хранения данных о времени (например, данных 194 о времени), ассоциированных со связью между компьютерной системой 101 и другими компьютерными системами в асинхронной распределенной системе 100. Модуль 102 управления тактовым генератором может записать время у тактового генератора 103, когда сообщения отправляются и принимаются в компьютерной системе 101. Модуль 102 управления тактовым генератором также может хранить время, принятое от наблюдаемых компьютерных систем (например, компьютерной системы 151), которое содержится в ответных сообщениях, принятых как часть последовательности обмена запросом/ответным сообщением. Из записанного и принятого времени модуль 102 управления тактовым генератором может указывать время возникновения событий в наблюдаемых компьютерных системах в заданных диапазонах.

Как изображено, компьютерная система 151 включает в себя модуль 152 управления тактовым генератором и тактовый генератор 153. Как правило, компьютерная система 151 конфигурируется для участия в последовательностях обмена запросом/ответным сообщением с другими компьютерными системами и поддержания предполагаемого времени в наблюдаемых компьютерных системах на основе данных о времени, ассоциированных с последовательностями обмена запросом/ответным сообщением.

Модуль 152 управления тактовым генератором конфигурируется для записи и хранения данных о времени, ассоциированных со связью между компьютерной системой 151 и другими компьютерными системами в асинхронной распределенной системе 100. Модуль 152 управления тактовым генератором может записать время у тактового генератора 153, когда сообщения отправляются и принимаются в компьютерной системе 151. Модуль 152 управления тактовым генератором также может хранить время, принятое от наблюдаемых компьютерных систем (например, компьютерной системы 101), которое содержится в ответных сообщениях, принятых как часть последовательности обмена запросом/ответным сообщением. Из записанного и принятого времени модуль 152 управления тактовым генератором может указывать время возникновения событий в наблюдаемых компьютерных системах в заданных диапазонах.

Варианты осуществления настоящего изобретения включают в себя компьютерные системы, наблюдающие свои тактовые генераторы и логически выводящие диапазоны значений для других тактовых генераторов. Например, компьютерная система 101 может наблюдать тактовый генератор 103 и может вывести диапазон значений для тактового генератора 153 (а также тактовых генераторов в других компьютерных системах 191). Аналогичным образом, компьютерная система 151 может наблюдать тактовый генератор 153 и может вывести диапазон значений для тактового генератора 103 (а также тактовых генераторов в других компьютерных системах 191). Другие компьютерные системы 191 также могут наблюдать собственные тактовые генераторы и выводить диапазон значений для каждого из тактовых генераторов 103 и 153.

Модули управления тактовыми генераторами также могут конфигурироваться с максимальной разностью квантования Q между тактовыми генераторами в асинхронной распределенной системе 100 (например, квантование 192) и максимальным уходом D тактового генератора за период времени в асинхронной распределенной системе 100 (например, уход 193).

Соответственно, некоторые варианты осуществления изобретения включают в себя использование обменов запросом/ответным сообщением для определения расхождения между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе. Обмен запросом/ответным сообщением может включать в себя запрос и соответствующее ответное сообщение. Например, обмен 184 сообщениями включает в себя запрос 181 и ответ 182. Из определенного расхождения наблюдающая компьютерная система может, например, вывести диапазон значений для тактового генератора в наблюдаемой компьютерной системе. Однако также могут использоваться сообщения с более слабыми корреляциями (например, чем точный запрос/ответ).

Таким образом, другие варианты осуществления изобретения используют обмены сообщениями с более слабой корреляцией между отправленными и принятыми сообщениями, чтобы определить расхождение между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе. Например, один компьютер может отправить множество запросов и получить меньшее количество или только один соответствующий ответ (например, изображенный другими обменами 185 сообщениями). Более того, ответ от одного компьютера также может представлять запрос от одного компьютера обратно к другому компьютеру. Таким образом, сообщение может представлять собой как запрос, так и ответ. Более того, часто отсутствует требование, предписывающее, когда должен вернуться ответ на принятый запрос. Таким образом, даже когда имеется сильная корреляция между парой запрос/ответ, могут отсутствовать ограничения на то, когда возвращается ответ. Например, в рамках запроса/ответа 184 могут отсутствовать временные ограничения, предписывающие, когда возвращается ответ 182 в ответ на прием запроса 181.

Фиг.2 - блок-схема алгоритма примерного способа 200 для определения расхождения между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе. Способ 200 будет описываться по отношению к компонентам и данным в асинхронной распределенной системе 100.

Способ 200 включает в себя действие по участию в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой (действие 201). Например, компьютерная система 101 может принять участие в обмене 184 сообщениями с компьютерной системой 151. С другой стороны, компьютерная система 101 может принять участие в одном или нескольких дальнейших обменах 185 сообщениями. Обмены сообщениями могут иметь более слабую связь между запросами и ответами, нежели обмен 184 сообщениями. В других вариантах осуществления компьютерная система 101 принимает участие в дальнейших обменах 185 сообщениями, но не принимает участие в обмене 184 сообщениями. Таким образом, компьютерная система 101 может принимать участие в слабосвязанных обменах сообщениями, которые не включают в себя коррелированные сообщения в любых обменах запросом/ответным сообщением.

Участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой может включать в себя действие по записи времени тактового генератора в наблюдающей компьютерной системе, когда отправляется сообщение (действие 202). Например, модуль 102 управления тактовым генератором может записать запись 171 времени в данные 194 о времени. Запись 171 времени записывает время в тактовом генераторе 103, когда компьютерная система 101 отправила запрос 181, например, в формате чч:мм:сс.мс. Таким образом, запись 181 времени указывает, что запрос 181 был отправлен, когда тактовый генератор 103 указывал время 8 часов. Иначе или в сочетании, записи времени также могут добавляться для других запросов (например, запросов, которые должны включаться в дальнейшие обмены 185 сообщениями). Участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой может включать в себя действие по отправке сообщения наблюдаемой компьютерной системе, причем сообщение включает в себя записанное время отправки (действие 203). Например, компьютерная система 101 может отправить запрос 181 в компьютерную систему 151. Запрос 181 может включать в себя информацию из записи 171 времени. Иначе или в сочетании, один или несколько других запросов (например, как часть дальнейших обменов 185 сообщениями) также могут отправляться из компьютерной системы 101 в компьютерную систему 151.

Участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой может включать в себя действие по последующему приему коррелирующих сообщений в ответ на сообщение от наблюдаемой компьютерной системы, причем коррелирующее сообщение содержит время от наблюдаемой компьютерной системы (действие 204). Например, компьютерная система 101 может принять ответ 182 от компьютерной системы 151. Ответ 182 включает в себя время 183. Время 183 указывает наблюдаемое время в тактовом генераторе 153 (например, когда отправлялся ответ 182, когда обрабатывался запрос 181, и т.д.). Иначе или в сочетании один или несколько других ответов также могут приниматься от компьютерной системы 151 (например, ответы, включенные в дальнейшие обмены 185 сообщениями). Таким образом, один или несколько ответов могут включать в себя время, указывающее наблюдаемое время в тактовом генераторе 153.

Участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой может включать в себя действие по записи принятого времени тактового генератора в наблюдающей компьютерной системе, когда принимается коррелирующее сообщение (действие 205). Например, модуль 102 управления тактовым генератором может записать запись 172 времени в данные 194 о времени. Запись 172 времени записывает время в тактовом генераторе 103, когда компьютерная система 101 приняла ответ 182. Таким образом, запись 172 времени указывает, что ответ 182 был принят, когда тактовый генератор 103 указывал время 8 часов и 64 мс. Иначе или в сочетании модуль 102 управления тактовым генератором также может записать записи времени (в данные 194 о времени), указывающие, когда принимались другие ответы, включенные в дальнейшие обмены 185 сообщениями.

Участие в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой может включать в себя действие по записи времени от наблюдаемой компьютерной системы (действие 206). Например, модуль 102 управления тактовым генератором может записать запись 173 времени в данные 194 о времени. Запись 173 времени записывает время, которое компьютерная система 151 наблюдала в тактовом генераторе 153 (например, принимая запрос 181, во время обработки запроса 181, и т.д.). Запись 173 времени указывает, что время тактового генератора 153 наблюдалось в 8 часов и 43 мс во время последовательности 184 обмена запросом/ответом. Иначе или в сочетании модуль 102 управления тактовым генератором также может записать записи времени (в данные 194 о времени) для времени, содержащегося в других ответах, включенных в дальнейшие обмены 185 сообщениями.

Способ 200 включает в себя действие по вычислению нижней границы для времени в наблюдаемой компьютерной системе относительно времени у наблюдающей компьютерной системы на основе разности между временем, записанным для отправки сообщения, и временем от наблюдаемой компьютерной системы, включенным в коррелирующее сообщение (действие 207). Например, модуль 102 управления тактовым генератором может вычислить нижнюю границу 161 для времени тактового генератора 103 относительно тактового генератора 153. Модуль 102 управления тактовым генератором может реализовать ранее описанные формулы для вычисления нижней границы 161 в тактовом генераторе 153. Таким образом, в момент, когда принимается ответ 182 и наблюдается тактовый генератор 103 для считывания 8:00:00,064, нижняя граница 161 может вычисляться в виде:

Тактовый генератор 153>=

8:00:00,064

-(8:00:00,064-8:00:00,043+15 мс)

-2(0,0007)(8:00:00,064-(8:00:00,064+8:00:00,000)/2+15 мс)

Тактовый генератор 153>=8:00:00,064-(21 мс+15 мс)-0,0014(32 мс+15 мс)

Тактовый генератор 153>=8:00:00,064-36 мс-0,07 мс

Тактовый генератор 153>=8:00:00,027

Иначе или в сочетании модуль 102 управления тактовым генератором также может вычислить нижнюю границу 161 из записей времени, имеющих отношение к другому запросу и другим ответам в дальнейших обменах 185 сообщениями.

Способ 200 включает в себя действие по вычислению верхней границы для времени в наблюдаемой компьютерной системе относительно времени в наблюдающей компьютерной системе на основе разности между временем, записанным для приема коррелирующего сообщения, и временем от наблюдаемой компьютерной системы, включенным в коррелирующее сообщение (действие 208). Например, модуль 102 управления тактовым генератором может вычислить верхнюю границу 162 для времени тактового генератора 103 относительно тактового генератора 153. Модуль 102 управления тактовым генератором может реализовать ранее описанные формулы для вычисления верхней границы 161 в тактовом генераторе 153. Таким образом, в момент, когда принимается ответ 182 и наблюдается тактовый генератор 103 для считывания 8:00:00,064, верхняя граница 162 может вычисляться в виде:

Тактовый генератор 153<=

8:00:00,064

+(8:00:00,043-8:00:00,000+15 мс)

+2(0,0007)(8:00:00,064-(8:00:00,064+8:00:00,000)/2+15 мс)

Тактовый генератор 153<=8:00:00,064+(43 мс+15 мс)+0,0014(32 мс+15 мс)

Тактовый генератор 153<=8:00:00,064+58 мс+0,07 мс

Тактовый генератор 153<=8:00:00,123

Иначе или в сочетании модуль 102 управления тактовым генератором также может вычислить верхнюю границу 162 из записей времени, имеющих отношение к другому запросу и другим ответам в дальнейших обменах 185 сообщениями.

Способ 200 включает в себя действие по вычислению разности между верхней границей и нижней границей (действие 209). Например, модуль 102 управления тактовым генератором может вычислить разность между верхней границей 162 и нижней границей 161. В момент, когда принимается ответ 182, и с учетом квантования 192 разность верхней границы 162 и нижней границы 161 приблизительно равна 123 мс-27 мс, или 96 мс.

Способ 200 включает в себя действие по вычислению максимального расхождения между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе путем деления вычисленной разности на усредняющий коэффициент (действие 210). Например, модуль 102 управления тактовым генератором может разделить 96 мс на 2, чтобы вычислить 48 мс. Середина смещения между тактовым генератором 103 и 153 равна ((8:00:00,027+8:00:00,123)/2)-8:00:00,064, что указывает, что тактовый генератор 153 приблизительно на 12 мс опережает тактовый генератор 103.

Как описывалось ранее, иначе или в сочетании с обменами 184 сообщениями компьютерная система 101 может принимать участие в дальнейших обменах 185 сообщениями с компьютерной системой 151. Таким образом, нижние и/или верхние границы для выведенного диапазона времени могут уточняться на основе этих дальнейших обменов сообщениями. Таким образом, нижняя граница 161 может уточняться, когда любое последующее время отправки - наблюдаемое время меньше, чем превышающее -43 мс. Например, если время отправки равно 8:01:27,53, а наблюдаемое время равно 8:01:27,69, то нижняя граница 161 может уточняться до -(16 мс+20 мс+составляющая ухода тактового генератора). Аналогичным образом может уточняться верхняя граница 162, когда любое последующее время приема - наблюдаемое время меньше, чем не превышающее -21 мс. Например, если время приема равно 8:03:52,07, а наблюдаемое время равно 8:03:51,92, то верхняя граница 162 может уточняться до -(15 мс +20 мс + составляющая ухода тактового генератора).

Нижняя граница и верхняя граница могут указывать некоторое количество времени, на которое тактовый генератор наблюдающей компьютерной системы отстает от наблюдаемого тактового генератора. Например, нижняя граница может быть равна -47 мс, а верхняя граница может быть равна -12 мс. Это сочетание нижней и верхней границы указывает, что тактовый генератор компьютерной системы отстает от наблюдаемого тактового генератора по меньшей мере на 12 мс и отстает от наблюдаемого тактового генератора не более чем на 47 мс.

Аналогичным образом, нижняя граница и верхняя граница могут указывать некоторое количество времени, на которое тактовый генератор наблюдающей компьютерной системы опережает наблюдаемый тактовый генератор. Например, нижняя граница может быть равна 17 мс, а верхняя граница может быть равна 82 мс. Это сочетание нижней и верхней границы указывает, что тактовый генератор компьютерной системы опережает наблюдаемый тактовый генератор по меньшей мере на 17 мс и опережает наблюдаемый тактовый генератор не более чем на 82 мс.

В некоторых вариантах осуществления модуль управления тактовым генератором конфигурируется для запуска обмена запросом/ответным сообщением или других обменов сообщениями, по меньшей мере с предопределенными интервалами, например, каждую минуту, каждые две минуты и т.д. Обмены сообщениями могут совмещаться с другими сообщениями (например, от приложения), обмениваемыми между компьютерными системами в асинхронной распределенной системе. Запрос/ответ или другие обмены сообщениями для тактовой синхронизации также могут начинаться в соответствии с другими политиками, например, переход через границу ухода.

После выведения времени в наблюдаемой компьютерной системе наблюдающая компьютерная система может использовать выведенное время, чтобы вычислить временные границы от того, когда событие произошло или возможно происходит (или будет происходить) в наблюдаемой компьютерной системе.

Соответственно, варианты осуществления изобретения обеспечивают общее понимание или надежное представление о течении времени между двумя компьютерными системами. Например, из максимального расхождения или диапазона времени наблюдающая компьютерная система может составить надежное представление о течении времени в наблюдаемой компьютерной системе. Из надежного представления наблюдающая компьютерная система может предположить (в пределах вычисленных границ), когда прошлое событие произошло в наблюдаемой компьютерной системе. Например, компьютерная система 101 может предположить, когда событие 196 произошло в компьютерной системе 151. Также из надежного представления две компьютерных системы могут прийти к соглашению о том, когда событие должно произойти в будущем. В результате одна компьютерная система может предположить (в пределах вычисленных границ), когда в другой компьютерной системе произойдет событие.

Фиг.3 - блок-схема алгоритма примерного способа для указания времени, в которое произошло событие в наблюдаемой компьютерной системе.

Способ 300 включает в себя действие по участию в одном или нескольких обменах сообщениями с наблюдаемой компьютерной системой (действие 301). Каждый обмен сообщениями включает в себя действие по записи времени у тактового генератора в наблюдающей компьютерной системе, когда отправляется запрос (действие 302). Каждый обмен сообщениями включает в себя действие по отправке одного или нескольких запросов наблюдаемой компьютерной системе, причем каждый запрос включает в себя соответствующее записанное время отправки (действие 303). Каждый обмен сообщениями включает в себя действие по последующему приему одного или нескольких ответных сообщений в ответ запросы от наблюдаемой компьютерной системы, причем ответные сообщения содержат время от наблюдаемой компьютерной системы (действие 304). Каждый обмен сообщениями включает в себя действие по записи времени у тактового генератора в наблюдающей компьютерной системе, когда принимается ответное сообщение (действие 305).

Например, компьютерная система 101 может принять участие в обмене 184 сообщениями и дальнейших обменах 185 сообщениями. Каждый обмен сообщениями может включать в себя: отправку одного или нескольких запросов (например, 181), запись времени, когда отправлялся каждый запрос (например, 171), прием одного или нескольких ответов (например, 182), запись времени, когда принимался каждый ответ (например, 172), и запись времени (например, 183), содержащегося в ответе от наблюдаемых компьютерных систем (например, 173).

Способ 300 включает в себя действие по вычислению временных границ для наблюдаемой компьютерной системы относительно времени наблюдающей компьютерной системы на основе одного или нескольких обменов сообщениями, причем временные границы сконфигурированы для применения ко времени в наблюдающей компьютерной системе, чтобы предположить заданный диапазон времени в наблюдаемой компьютерной системе после одного или нескольких обменов сообщениями (действие 306). Временные границы включают в себя нижнюю временную границу, представляющую нижнюю часть вычисленных временных границ, и верхнюю временную границу, представляющую верхнюю часть вычисленных временных границ. Например, компьютерная система 101 может вычислить и уточнить нижнюю границу 161 и верхнюю границу 162.

Способ 300 включает в себя действие наблюдающей компьютерной системы по приему указания, выбранного из: a) указания возникновения прошлого события в наблюдаемой компьютерной системе и b) указания того, когда событие должно произойти в наблюдаемых компьютерных системах после одного или нескольких обменов сообщениями (действие 307). Например, компьютерная система 101 может обнаружить событие 196. При приеме события 196 модуль управления тактовым генератором может записать в данные 194 о времени запись 174 времени. Запись 194 времени указывает, что событие 196 было обнаружено в 8:00:28,016. С другой стороны, компьютерная система 101 может принять указание о том, когда должно произойти событие в компьютерной системе 151 и записать запись времени для того, когда должно произойти событие.

Способ 300 включает в себя действие наблюдающей компьютерной системы по вычислению диапазона времени для наблюдаемой компьютерной системы, причем диапазон времени указывает a) когда произошло прошлое событие или b) когда событие должно произойти в наблюдаемой компьютерной системе, причем диапазон времени вычисляется на основе времени в наблюдающей компьютерной системе, когда принималось указание, и на основе нижней границы и верхней границы вычисленной временной границы (действие 308). Например, из записи 174 времени модуль 102 управления тактовым генератором может вычислить диапазон времени, указывающий, когда произошло событие 196 в компьютерной системе 151. По существу новая нижняя граница может вычисляться в виде:

Тактовый генератор 153>=

8:00:00,064

-(8:00:00,064-8:00:00,043+15 мс)

-2(0,0007)(8:00:28,016-(8:00:00,064+8:00:00,000)/2+15 мс)

Тактовый генератор 153>=8:00:00,064-(21 мс + 15 мс)-0,0014(28,016 мс-32 мс+15 мс)

Тактовый генератор 153>=8:00:00,064-36 мс-39,2 мс

Тактовый генератор 153>=7:59:59,089

И новая верхняя граница может вычисляться в виде:

Тактовый генератор 153<=

8:00:00,064

+(8:00:00,043-8:00:00,000+15 мс)

+2(0,0007)(8:00:28,016-(8:00:00,064+8:00:00,000)/2+15 мс)

Тактовый генератор 153<=8:00:00,064 +(43 мс+ 15 мс)+0,0014(32 мс+15 мс)

Тактовый генератор 153<=8:00:00,064+58 мс + 39,2 мс

Тактовый генератор 153<=8:00:00,161

Таким образом, в момент, когда обнаруживается событие 196, и с учетом квантования 192 разность верхней границы 162 и нижней границы 161 приблизительно равна 161 мс-(-11 мс), или 172 мс. Модуль 102 управления тактовым генератором может разделить 172 мс на 2, чтобы вычислить 86 мс в качестве максимального расхождения. Это новое расхождение может использоваться для вычисления времени 186, выведенного времени (в пределах максимального расхождения), в которое событие 196 произошло в компьютерной системе 151. Середина смещения между тактовым генератором 103 и 153 равна:

((8:00:27,970+8:00:28,102)/2)-8:00:28,016

8:00:28,066-8:00:28,016=50 мс, что указывает, что тактовый генератор 153 на 50 мс опережает тактовый генератор 103.

С другой стороны, нижняя и верхняя границы могут вычисляться для того, когда должно произойти событие.

Способ 300 включает в себя действие по отправке сообщения о событии, включающего указание и вычисленный диапазон времени, одной или нескольким другим компьютерным системам (действие 309). Например, компьютерная система 100 может отправить сообщение 197 о событии, включающее событие 196 (или указание того, когда событие 196 должно произойти) и время 186, другим компьютерным системам 191. Компьютерные системы, которые принимают сообщение 197 о событии, могут принять решение, имеющее отношение к состоянию компьютерной системы 151, на основе сообщения 197 о событии. Например, компьютерная система может принять указание от компьютерной системы 151, что компьютерная система 151 была в сети в 8:00:15,13. Компьютерная система впоследствии может принять сообщение 197 о событии, указывающее, что компьютерная система 151 вышла из сети. Поскольку 8:00:28,016±86 мс - это позже 8:00:15,13, компьютерная система может скорректировать свое состояние для компьютерной системы 151.

Может быть так, что максимальное расхождение вызывает наложение на ранее принятое время, приводя к потенциальному конфликту в отношении того, какое событие произошло раньше. Например, если время 184 было 8:00:15,47±90,22 мс, то расхождение вызывает некоторую вероятность, что событие 196 фактически произошло до 8:00:15,13. В таких случаях компьютерная система, которая принимает сообщение о событии, может обратиться к предопределенным правилам (например, соглашениям об уровне обслуживания) для разрешения конфликтов.

Со временем компьютерная система может вычислить среднее время для выполнения обменов запросом/ответом (или другими сообщениями). Используя этот средний и предопределенный интервал, компьютерная система может оценить границу ошибки в наихудшем случае для разностей времени. Например, ссылаясь на фиг.1, если среднее время для выполнения обмена запросом/ответным сообщением равно 40 мс, а предопределенный интервал равен 30 секундам, то граница ошибки в наихудшем случае может вычисляться равной ±[(40 мс/2)+20 мс+2*((0,5 мин/24)*60 мин)*(60 с)]=81,5 мс.

Может быть так, что (по меньшей мере предполагаемые) значения для квантового ограничения тактового генератора, ограничения скорости ухода и ограничения максимального кругового пути известны системе, например, из средних значений или даже из аппаратных требований. Уравнение максимальной ошибки может использоваться для вычисления максимального расхождения (между компьютерными системами в асинхронной распределенной системе) в том, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и каким время в наблюдаемой компьютерной системе фактически является.

Фиг.5 иллюстрирует примерную архитектуру 500 компьютера, которая обеспечивает вычисление максимального расхождения между тактовыми генераторами в разных компьютерных системах в асинхронной распределенной системе, которая включает в себя множество компьютерных систем. Фиг.4 - блок-схема алгоритма примерного способа 400 для вычисления максимального расхождения между тактовыми генераторами в разных компьютерных системах в асинхронной распределенной системе, которая включает в себя множество компьютерных систем. Способ 400 будет описываться по отношению к компонентам и данным в архитектуре 500 компьютера.

Способ 400 включает в себя действие по обращению к квантовому ограничению тактового генератора, причем квантовое ограничение тактового генератора указывает максимальную разность между квантованиями тактовых генераторов среди компьютерных систем в асинхронной распределенной системе (действие 401). Например, компьютерная система 501 может обращаться к квантовому ограничению 511 тактового генератора, например аппаратному требованию, что Q=15 мс.

Способ 400 включает в себя действие по обращению к ограничению скорости ухода, причем ограничение скорости ухода указывает максимальный уход тактового генератора в заданном периоде времени для каждой компьютерной системы в асинхронной распределенной системе (действие 402). Наблюдатель может узнать или быть сконфигурирован для ухода в наихудшем случае у заданного наблюдаемого. С другой стороны, наблюдатель может быть сконфигурирован для предположения ухода в наихудшем случае для любого наблюдаемого. Например, компьютерная система 501 может обращаться к ограничению 512 скорости ухода тактового генератора, например D<1 минуты ухода в день. Таким образом, ограничение 512 скорости ухода тактового генератора может применяться к определенному наблюдаемому или к любому наблюдаемому.

Способ 400 включает в себя действие по обращению к ограничению максимального кругового пути, причем ограничение максимального кругового пути указывает максимальное количество времени для совершения обмена запросом/ответным сообщением между любыми двумя компьютерными системами в асинхронной распределенной системе (действие 403). Например, компьютерная система 501 может обращаться к ограничению 513 максимального кругового пути. Ограничение 513 кругового пути может выводиться, например, из компьютерной системы 101, запрашивающей компьютерную систему 151 раз в минуту, и времени кругового пути, составляющего менее 50 мс.

Способ 400 включает в себя действие по вычислению максимального расхождения между тактовыми генераторами в разных компьютерных системах в асинхронной системе на основе квантового ограничения тактового генератора, ограничения скорости ухода и ограничения максимального кругового пути. Например, компьютерная система 501 может вычислить максимальное расхождение 514 тактового генератора на основе квантового ограничения 511 тактового генератора, ограничения 512 скорости ухода тактового генератора и ограничения 513 кругового пути.

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

((время приема - время отправки)/2)+Q+(2D*(T-AVG (время отправки, время приема)+Q))

или в случае заранее установленных или заданных значений:

(R/2)+Q+(2*D* заранее установленный интервал обмена запросом/ответным сообщением)

Таким образом, в соответствии с ограничениями, описанными по отношению к способу 400, максимальное расхождение облегчает наблюдающей компьютерной системе понимание времени в наблюдаемой компьютерной системе в любой момент в пределах (50 мс/2)+15 мс+(2*(1 мин/24*60 мин)*(60 с)), что составляет 25 мс + 15 мс + 83 мс=123 мс. Более того, непосредственно после запроса последовательности обмена сообщениями влияние составляющей ограничения скорости ухода тактового генератора D на максимальную ошибку приближается к нулю. То есть (2*(~0/24*60 мин)*(60 с))=0. Таким образом, непосредственно после запроса последовательности обмена сообщениями наблюдающая компьютерная система может узнать время в наблюдаемых компьютерных системах приблизительно с 25 мс + 15 мс + 0 мс=40 мс.

Таким образом, варианты осуществления изобретения облегчают создание заслуживающего доверия и практичного эталона общего времени (истинного времени) среди множества одноранговых узлов (наблюдателей), например участников в общей асинхронной (распределенной) системе. Класс псевдосинхронной системы может создаваться путем отслеживания и накопления отклонений релятивистского времени в наихудшем случае среди пар узлов (наблюдателей) без обращения к общему главному. Причинные прямые и косвенные связи могут быть образованы на основе упорядоченного взаимодействия между парами узлов. По существу, взаимодействующие узлы могут в принципе гарантировать нижнюю границу для истинного времени, которое будет наблюдать один узел, учитывая наблюдение на другом узле. Соответственно, варианты осуществления изобретения могут применяться для обеспечения целостного (весьма надежного) представления о текущем времени в наихудшем случае (то есть при огромном расхождении) во всей такой асинхронной системе - без использования сущности общего внешнего генератора истинного времени.

Настоящее изобретение может быть реализовано в других конкретных видах без отклонения от его сущности или неотъемлемых характеристик. Описанные варианты осуществления должны рассматриваться во всех отношениях только как пояснительные, а не ограничительные. Следовательно, объем изобретения указывается прилагаемой формулой изобретения, а не предшествующим описанием. Все изменения, которые подпадают под смысл и диапазон эквивалентности формулы изобретения, должны включаться в ее объем.

Изобретение относится к способам и системам для синхронизации тактовых генераторов в асинхронной распределенной системе. Техническим результатом является повышение надежности и достоверности при определении практичного эталона общего времени (истинного времени) среди множества одноранговых узлов в общей асинхронной (распределенной) системе без использования сущности общего внешнего генератора истинного времени. В способах класс псевдосинхронной системы создается путем отслеживания и накопления отклонений релятивистского времени в наихудшем случае среди пар узлов (наблюдателей) без обращения к общему главному. По существу, взаимодействующие узлы могут в принципе гарантировать нижнюю границу для истинного времени, которое будет наблюдать один узел, учитывая наблюдение на другом узле. 3 н. и 12 з.п. ф-лы, 5 ил.

1. В наблюдающей компьютерной системе (101) в асинхронной распределенной системе (100), включающей множество компьютерных систем (101, 151, 191), причем наблюдающая компьютерная система (101) включает в себя процессор и системную память, асинхронная распределенная система (100) имеет квантовое ограничение тактового генератора (192) и ограничение скорости ухода (193), причем квантовое ограничение тактового генератора (192) указывает максимальную разность между квантованиями тактовых генераторов среди компьютерных систем (101, 151, 191) в асинхронной распределенной системе (100), ограничение скорости ухода (193) указывает максимальный уход тактового генератора за указанный период времени для каждой компьютерной системы в асинхронной распределенной системе (100),
способ для определения расхождения между тем, какое время наблюдающая компьютерная система (100) подразумевает в наблюдаемой компьютерной системе (151), и фактическим временем в наблюдаемой компьютерной системе (151), содержащий этапы, на которых:
принимают участие в одном или нескольких обменах сообщениями (184, 185) с наблюдаемой компьютерной системой (151), причем обмены сообщениями включают в себя этапы, на которых:
записывают время отправки (171) у тактового генератора (103) в наблюдающей компьютерной системе (101), когда отправляется сообщение (181);
отправляют сообщение (181) наблюдаемой компьютерной системе (151), причем сообщение (181) включает в себя записанное время отправки (171);
принимают впоследствии коррелирующее сообщение (182) в ответ на сообщение (181) от наблюдаемой компьютерной системы (151), причем коррелирующее сообщение (182) содержит время (183) от наблюдаемой компьютерной системы (151);
записывают принятое время (172) тактового генератора (103) в наблюдающей компьютерной системе (101), когда принимается коррелирующее сообщение (182); и
записывают время (173) от наблюдаемой компьютерной системы (151);
вычисляют нижнюю границу (161) для времени в наблюдаемой компьютерной системе относительно времени наблюдающей компьютерной системы на основе разности между временем (181), записанным для отправки сообщения, и временем (183) от наблюдаемой компьютерной системы, включенным в коррелирующее сообщение, квантового ограничения тактового генератора (192) и ограничения ухода тактового генератора (193);
вычисляют верхнюю границу (162) для времени в наблюдаемой компьютерной системе относительно времени наблюдающей компьютерной системы на основе разности между временем (182), записанным для приема коррелирующего сообщения, и временем (183) от наблюдаемой компьютерной системы, включенным в коррелирующее сообщение, квантового ограничения тактового генератора (192) и ограничения ухода тактового генератора (193);
вычисляют разность между верхней границей (162) и нижней границей (161); и
вычисляют с помощью процессора максимальное расхождение между тем, какое время наблюдающая компьютерная система подразумевает в наблюдаемой компьютерной системе, и фактическим временем в наблюдаемой компьютерной системе, путем деления вычисленной разности на усредняющий коэффициент.

2. Способ по п.1, дополнительно содержащий этап, на котором в наблюдающей компьютерной системе используют вычисленное максимальное расхождение, чтобы составить надежное представление о течении времени в наблюдаемой компьютерной системе.

3. Способ по п.1, дополнительно содержащий этап, на котором наблюдающая компьютерная система и наблюдаемая компьютерная система договариваются о том, когда происходит событие.

4. Способ по п.3, в котором этап, на котором наблюдающая компьютерная система и наблюдаемая компьютерная система договариваются о том, когда происходит событие, содержит этап, на котором в наблюдающей компьютерной системе обнаруживают возникновение прошлого события в наблюдаемой компьютерной системе.

5. Способ по п.3, в котором этап, на котором наблюдающая компьютерная система и наблюдаемая компьютерная система договариваются о том, когда происходит событие, содержит этап, на котором наблюдающая компьютерная система и наблюдаемая компьютерная система договариваются о том, когда событие произойдет в будущем.

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

7. В наблюдающей компьютерной системе (101), причем наблюдающая компьютерная система включает в себя процессор и системную память,
способ для указания времени, когда произошло событие в наблюдаемой компьютерной системе (151), содержащий этапы, на которых:
принимают участие в одном или нескольких обменах сообщениями (184, 185) с наблюдаемой компьютерной системой (151), причем каждый обмен сообщениями включает в себя этапы, на которых:
записывают время (171) у тактового генератора (103) в наблюдающей компьютерной системе (101), когда отправляется запрос (181);
отправляют один или несколько запросов (181) наблюдаемой компьютерной системе (151), причем каждый запрос включает в себя соответствующее записанное время отправки;
принимают впоследствии одно или несколько ответных сообщений (182) в ответ на один или несколько запросов (181) от наблюдаемой компьютерной системы (151), причем каждое ответное сообщение содержит время (183) от наблюдаемой компьютерной системы; и
записывают время (172) у тактового генератора (103) в наблюдающей компьютерной системе (101), когда принимается ответное сообщение (182);
вычисляют временные границы (161, 162) для наблюдаемой компьютерной системы (151) относительно времени наблюдающей компьютерной системы (101) на основе одного или нескольких обменов сообщениями (184, 185), причем временные границы (161, 162) сконфигурированы для применения ко времени в наблюдающей компьютерной системе (101), чтобы предположить заданный диапазон времени в наблюдаемой компьютерной системе (151) после одного или нескольких обменов сообщениями (184, 185), причем временные границы включают:
нижнюю временную границу (161), представляющую нижнюю часть вычисленных временных границ; и
верхнюю временную границу (162), представляющую верхнюю часть вычисленных временных границ;
принимают с помощью процессора указание, выбранное из: а) указания возникновения прошлого события в наблюдаемой компьютерной системе (151) и b) указания того, когда событие должно произойти в наблюдаемой компьютерной системе (151) после одного или нескольких обменов сообщениями (184, 185);
вычисляют с помощью процессора диапазон времени для наблюдаемой компьютерной системы (151), причем диапазон времени указывает а) когда произошло событие или b) когда событие должно произойти в наблюдаемой компьютерной системе (151), причем диапазон времени вычисляется на основе времени в наблюдающей компьютерной системе (101), когда принималось указание, и на основе нижней границы (161) и верхней границы (162) вычисленной временной границы; и
отправляют сообщение о событии (197), включающее указание и вычисленный диапазон времени (186), одной или нескольким другим компьютерным системам (191).

8. Способ по п.7, в котором этап, на котором вычисляют временные границы для наблюдаемой компьютерной системы относительно времени в наблюдающей компьютерной системе на основе одного или нескольких сообщений, содержит этап, на котором устанавливают нижнюю границу в значение, по меньшей мере частично основанное на наименьшей разности между временем, записанным для отправки запроса, и временем от наблюдаемой компьютерной системы, включенным в соответствующее ответное сообщение в любом одном или нескольких обменах сообщениями.

9. Способ по п.8, в котором этап, на котором устанавливают нижнюю границу в значение, содержит этап, на котором устанавливают нижнюю границу в значение, по меньшей мере, частично основанное на указании разности между квантованием тактового генератора в наблюдающей компьютерной системе и квантованием тактового генератора в наблюдаемой компьютерной системе.

10. Способ по п.8, в котором этап, на котором устанавливают нижнюю границу в значение, содержит этап, на котором устанавливают нижнюю границу в значение, по меньшей мере частично основанное на уходе тактового генератора в наблюдающей компьютерной системе и уходе тактового генератора в наблюдаемой компьютерной системе.

11. Способ по п.7, в котором этап, на котором вычисляют временные границы для наблюдаемой компьютерной системы относительно времени в наблюдающей компьютерной системе на основе одного или нескольких запросов/ответных сообщений, содержит этап, на котором устанавливают верхнюю границу в значение, по меньшей мере частично основанное на наименьшей разности между временем, записанным для приема ответного сообщения, и временем от наблюдаемой компьютерной системы, включенным в ответное сообщение в любом одном или нескольких обменах запросом/ответным сообщением.

12. Способ по п.11, в котором этап, на котором устанавливают верхнюю границу в значение, содержит этап, на котором устанавливают верхнюю границу в значение, по меньшей мере частично основанное на указании разности между квантованием тактового генератора в наблюдающей компьютерной системе и квантованием тактового генератора в наблюдаемой компьютерной системе.

13. Способ по п.11, в котором этап, на котором устанавливают верхнюю границу в значение, содержит этап, на котором устанавливают верхнюю границу в значение, по меньшей мере частично основанное на уходе тактового генератора в наблюдающей компьютерной системе и уходе тактового генератора в наблюдаемой компьютерной системе.

14. Способ по п.7, в котором асинхронная распределенная система является одноранговой системой.

15. В компьютерной системе (501), включающей процессор и системную память,
способ для вычисления максимального расхождения (514) между тактовыми генераторами в разных компьютерных системах в асинхронной распределенной системе, которая включает в себя множество компьютерных систем, содержащий этапы, на которых:
обращаются к квантовому ограничению тактового генератора (511), причем квантовое ограничение тактового генератора указывает максимальную разность между квантованиями тактовых генераторов среди компьютерных систем в асинхронной распределенной системе;
обращаются к ограничению скорости ухода (512), причем ограничение скорости ухода указывает максимальный уход тактового генератора в заданном периоде времени для каждой компьютерной системы в асинхронной распределенной системе;
обращаются к ограничению максимального кругового пути (513), причем ограничение максимального кругового пути указывает максимальное количество времени для совершения обмена запросом/ответным сообщением между любыми двумя компьютерными системами в асинхронной распределенной системе; и
вычисляют с помощью процессора максимальное расхождение (514) между тактовыми генераторами в разных компьютерных системах в асинхронной системе на основе квантового ограничения тактового генератора, ограничения скорости ухода и ограничения максимального кругового пути.