Синхронизация тактовых генераторов в асинхронной распределенной системе

Синхронизация тактовых генераторов в асинхронной распределенной системе

Иллюстрации

Показать все

Реферат

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 сообщениями). Более того, ответ от одного компьютера также может представлять запрос от одного компьютера обратно к другому компьютеру. Таким образом, сообщение может представлять собой как запрос, так и ответ. Более того, часто отсутствует требование, предписывающее, когда должен вернуться ответ на принятый запрос. Таким образом, даже когда имеется сильная корреляция между парой запрос/ответ, могут отсутствовать ограничения на то, ког