Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 5

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

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

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

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

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

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

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

Для глобальных сетей необходимо разрабатывать безопасные алгоритмы,1.1. Что такое распределенная система?19способные обеспечить защиту от враждебных пользователей, подключенных к сети в других узлах.Глобальные сети коротко обсуждаются в § 1.1.3, а § 1.1.4 посвящен локальным сетям.1.1.3. Глобальные сетиИсторический очерк. Первые достижения в создании глобальных компьютерных сетей были получены в рамках проекта, который выполнялся Агенством перспективных мсследовательских проектов (Advanced Research ProjectsAgency) министерства обороны Соединенных Штатов Америки. В 1969 г. былазапущена сеть ARPANET, которая в то время соединяла четыре узла. Затемк этой сети были подключены еще несколько сот узлов, и на основе подобнойтехнологии были созданы и другие сети (MILNET, CYPRESS). В сети ARPANETимеются специальные узлы (их называют обработчиками интерфейсов сообщений), единственное предназначение которых — обработка потоков сообщений.Как только система UNIX 2) получила широкое распространение, возниклапотребность в обмене информацией между различными машинами, на которыхустановлена операционная система UNIX.

Для этого была написана программаuucp program (UNIX-to-UNIX CoPy). Эта программа позволила обмениватьсяфайлами по телефонным линиям связи, и вскоре образовалась сеть пользователей системы UNIX (UUCP сеть). Еще одна крупная сеть под названием BITNETбыла создана в восьмидесятых годах, ввиду того что сеть ARPANET принадлежала министерству безопасности, и лишь немногие пользователи могли подключаться к ней.В наши дни все эти сети взаимосвязаны между собой: существуют узлы,которые входят в состав сразу двух сетей (такие узлы называются шлюзами),и благодаря этому узлы из разных сетей могут обмениваться информацией.

После того как были введены стандартные протоколы и унифицированное адресноепространство, все сети превратились в единую виртуальную сеть, которая известна всем под названием Internet. Она отличается от «монолитной» сети тем, чтоу нее много владельцев и нет единого административного органа, но при этом ееорганизационная неоднородность скрыта от пользователей. Электронный адресавтора этой книги (gerard@cs.uu.nl) не дает никакой информации о той сети,к которой подключен его факультет.Устройство и алгоритмические проблемы.

Глобальные сети всегда устроены на основе принципа двухточечного соединения. Это означает, что механизмсоединения между парой узлов является индивидуальным для каждой такой пары.Соединение может осуществляться по телефонной линии, по оптоволоконномукабелю, при помощи космического спутника и т. д. Структуру взаимосвязи сетис двухточечным соединением удобно представлять при помощи рисунка, в котором каждый узел изображается кружком или квадратиком, а линии, проведенныемежду этими фигурами, соответствуют линиям связи между узлами (см. рис. 1.1).2) UNIX— это торговая марка лабораторий Белла компании AT&T — Прим.

автора.20Гл. 1. Введение: распределенные системыu u uAZZBAAuZZ BZuA BBu AAuPP A PuPAu УзелЛиния связиРис. 1.1. Пример сети с двухточечным соединениемЕсли воспользоваться более формальной терминологией, то структуру сети можно представить в виде графа, ребра которого соответствуют линиям связи сети.Общие сведения о терминологии теории графов можно найти в гл. Б.Глобальные сети предназначены, в первую очередь, для обмена информацией посредством электронной почты, досок объявлений, удаленных файлов,распределенных баз данных, и т.

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

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

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

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