Миграция данных: различия между версиями

Задачу миграции данных можно рассматривать как обобщение задач мгновенного обмена сообщениями и широковещательной передачи. Последние играют важную роль в разработке протоколов коммуникаций в сетях различных типов и были многократно исследованы (см., например, [6, 7] и ссылки в этих работах). Задача мгновенного обмена сообщениями выглядит следующим образом. Пусть имеется n человек, и у каждого человека имеется элемент сообщения («слух»), которым он или она желает поделиться со всеми остальными. Коммуникация обычно выполняется поэтапно, и на каждом этапе любой человек может связываться не более чем с одним другим человеком. Некоторые модели коммуникаций допускают полный обмен всеми слухами, известными каждому человеку, на одном этапе. Возможно наличие графа коммуникаций, ребка которого обозначают, между какими парами людей допускается непосредственная коммуникация на каждом этапе. В задаче широковещательной передачи одному человеку необходимо передать слух каждому другому человеку. Задача миграции данных обобщает эти две задачи тремя способами: (1) каждый слух необходимо передать только некоторому подмножеству людей; (2) одному человеку могут быть известны несколько слухов; (3) один и тот же слух изначально может быть известен нескольким людям.