| dbo:abstract
|
- Der Ringalgorithmus ist ein Auswahlalgorithmus, mit dem in einem verteilten System ein Prozess mit einer besonderen Aufgabe ermittelt wird. Diese Aufgabe kann zum Beispiel ein Koordinator sein. (de)
- In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" (or coordinator) of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader. The network nodes communicate among themselves in order to decide which of them will get into the "leader" state. For that, they need some method in order to break the symmetry among them. For example, if each node has unique and comparable identities, then the nodes can compare their identities, and decide that the node with the highest identity is the leader. The definition of this problem is often attributed to LeLann, who formalized it as a method to create a new token in a token ring network in which the token has been lost. Leader election algorithms are designed to be economical in terms of total bytes transmitted, and time. The algorithm suggested by Gallager, Humblet, and Spira for general undirected graphs has had a strong impact on the design of distributed algorithms in general, and won the Dijkstra Prize for an influential paper in distributed computing. Many other algorithms have been suggested for different kinds of network graphs, such as undirected rings, unidirectional rings, complete graphs, grids, directed Euler graphs, and others. A general method that decouples the issue of the graph family from the design of the leader election algorithm was suggested by Korach, Kutten, and Moran. (en)
- 分散コンピューティングにおいて、リーダー選出は複数のコンピュータ(ノード)に分散されたタスクの取りまとめ役として、一つのプロセスを指定する過程である。タスクが開始する前、全てのネットワークノードは、どのノードが「リーダー」、つまりタスクの取りまとめ役であるかは知らない。しかし、リーダー選出アルゴリズムが実行された後、ネットワーク中の全ノードは特定のノードをタスクリーダーとして認識する。 ネットワークノードは相互に通信を行い、いずれかが「リーダー」状態になるか決定する。そのために、ノード間の対称性を崩すための手法が必要となる。例えば、各ノードが固有のID番号があるのであれば、ノード間にてID番号の比較を行い、最も高いID番号を持っているノードがリーダーであると決定することが出来る。 この問題の定義はLeLannに帰せられることが多く、これをトークンリングネットワークにおいて、トークンが失われた際に新しいトークンを作成する手法として実現した。 リーダー選出アルゴリズムは全送信バイト数と時間という観点で経済的であるよう、設計されている。Gallager、Humblet、Spiraによって提案された一般無向グラフのためのアルゴリズム は分散アルゴリズムのデザイン一般に強いインパクトを与え、分散コンピューティングにおける影響が大きい論文としてダイクストラ賞を受賞した。 無向リング、単一方向リング、完全グラフ、グリッド、有向オイラーグラフなどの他の種類のネットワークグラフについて多くのアルゴリズムが提案された。グラフの種類とリーダー選出アルゴリズムを切り離す一般的な手法が Korach、Kutten、Moranにより提案された。 (ja)
- 분산 컴퓨팅에서 리더 선출(leader election)이란 단일 프로세서를 여러 컴퓨터(노드)에 분산된 작업들의 주최자로 지정하는 작업이다. 작업이 시작하기 전, 모든 네트워크 노드들은 누가 작업의 "리더"로 동작할지 서로 알지 못하거나 현재 리더(분산 컴퓨팅)와 통신할 수 없다. 리더 선출 알고리즘 실행 후에는, 네트워크 상의 모든 노드들은 특별한 고유 노드를 작업 리더로 인식한다. 네트워크 노드들은 그들 중 누가 "리더" 상태가 될지 결정하기 위해 그들끼리 통신한다. 이를 위해, 그들은 그들간의 균형을 깨트리기 위한 방법이 필요하다. 예를 들어, 각 노드가 비교 가능한 고유 식별자를 가질 경우, 노드들은 그들의 식별자를 비교 가능하며, 가장 뛰어난 식별자를 가진 노드를 리더로 결정할 수 있다. 이 문제의 정의는 토큰이 손실된 링 네트워크에서 새로운 토큰을 만드는 방법을 정의한 LeLann으로부터 기인된다. 리더 선택 알고리즘은 총 전송 바이트, 시간 측면에서 경제적으로 설계된다. Gallager, Humblet 스파이라에 의해 제안된 무방향성 그래프를 위한 알고리즘은 분산 알고리즘의 설계에 큰 영향을 미쳤으며, 분산컴퓨팅 분야에서 영향력 있는 논문으로서 데이크스트라 상을 수상하기도 하였다. 다른 많은 알고리즘들이 다른 종류의 네트워크 그래프를 위해 제안되었다. (비방향성 링, 단방향성 링, 완전 그래프, 그리드, 방향성 오일러 그래프 등) 리더십 선거 알고리즘의 설계와 그래프 패밀리의 문제를 분리하는 일반적인 방법은 Korach, Kutten 및 Moran에 의해 제안되었다. (ko)
- L'algoritmo di elezione viene eseguito nei sistemi distribuiti per stabilire il coordinatore a cui i processi fanno riferimento per un servizio. Se il coordinatore si guasta, l'intero sistema si blocca. Per risolvere il problema, occorre eseguire un algoritmo di elezione in cui i processi ancora attivi eleggono un nuovo coordinatore. Gli algoritmi di elezione più famosi sono:
* Algoritmo dello spaccone di Garcia - Molina, 1982
* di Le Lann, 1977
* , 1979
* , 1982 (it)
- Eleição de líder é um problema da área de sistemas distribuídos que busca selecionar de forma consensual um processo num conjunto de processos tendo como objetivo selecionar um líder para uma determinada tarefa. A eleição torna-se necessária quando o sistema distribuído está sendo iniciado pela primeira vez ou o líder anterior não consegue se comunicar com os demais processos pela ocorrência de alguma falha. Há vários algoritmos que realizam a eleição do líder, cada um específico a alguma situação. (pt)
- Алгоритм выбора лидера — это процесс в системе распределённых вычислений, который назначает один процесс организатором некоторой задачи, распределённой на несколько компьютеров (узлов). До начала выполнения задачи все узлы сети либо не осведомлены, какой узел будет вести себя как «лидер» (или координатор) задачи, либо не в состоянии общаться с текущим координатором. После того, как алгоритм выбора лидера отработает, каждый узел сети знает об определённом единственном узле, выступающем в качестве лидера. Узлы сети общаются друг с другом с целью решить, который из них возьмёт на себя роль «лидера». Для этого им нужен некоторый метод, чтобы разрушить симметрию узлов. Например, если каждый узел имеет уникальные и отличительные черты, которые можно сравнить, то узлы могут сравнивать эти черты и решать, какой узел с лучшей характеристикой является лидером. Постановку задачи часто приписывается ЛеЛанну, который формализовал её как метод создания нового маркера в потерявшей маркер сети Token ring. Алгоритмы выбора лидера разрабатываются экономичными в терминах передачи общего числа байтов и времени. Алгоритм, предложенный Галлагером, Хамблетом и Спира для общих неориентированных графов, имеет сильное влияние на разработку распределённых алгоритмов вообще и выиграл премию Дейкстры как авторитетная статья в области распределённых вычислений. Было предложено много разных алгоритмов для различных топологий сетей — графов, таких как неориентированные кольца, ненаправленных колец, полных графов, решёток, ориентированных эйлеровых графов и других. Основной метод, который отвязывает проблему семейства графов от разработки алгоритма выбора лидера, был предложен Корачем, Куттеном и Мораном. (ru)
- У розподілених обчисленнях, вибір лідера є процесом позначення одного процесу як організатора деякого завдання, розподіленого між декількома комп'ютерами (вузлами). Перш ніж розпочати завдання, всі вузли мережі або не знають, який вузол буде виконувати роль «лідера» (або координатора) завдання, або ці вузли не можуть спілкуватися з поточним координатором. Проте після запуску алгоритму вибору лідера кожен вузол у мережі визначає один особливий, унікальний вузол і сприймає його як лідера завдання. Вузли мережі спілкуються між собою, щоб вирішити, який з них отримає статус «лідеру». Для цього вони використовують певний метод (алгоритм), щоб розірвати симетрію серед них (назначити одному з них особливий статус). Наприклад, якщо кожен вузол має унікальні та порівнянні ідентичності, то вузли можуть порівнювати свої ідентичності і вирішувати, що вузол з найвищою ідентичністю є лідером. Формулювання цієї проблеми часто приписується ЛеЛану (англ. LeLann), який сформулював її як метод створення нового маркера в мережі маркерів кільця, в якому маркер був втрачений. Алгоритми виборів лідерів розроблені так, щоб бути максимально ефективними з точки зору загальної кількості переданих байтів і часу прийняття рішення. Алгоритм, запропонований Галлагером, Хумблетом і Спірою для загальних неорієнтованих графів, справив сильний вплив на розробку розподілених алгоритмів загалом, і отримав премію Дейкстри за значний внесок в розподілені обчислення. Багато інших алгоритмів були запропоновані для різних типів мережевих графів, таких як неорієнтовані кільця, односпрямовані кільця, повні графи, сітки, напрямлені графи Ейлера та інші. Загальний метод, який відокремлює проблему з сімейства графів від проектування алгоритму виборів лідера, був запропонований Корахом, і . (uk)
|
| rdfs:comment
|
- Der Ringalgorithmus ist ein Auswahlalgorithmus, mit dem in einem verteilten System ein Prozess mit einer besonderen Aufgabe ermittelt wird. Diese Aufgabe kann zum Beispiel ein Koordinator sein. (de)
- L'algoritmo di elezione viene eseguito nei sistemi distribuiti per stabilire il coordinatore a cui i processi fanno riferimento per un servizio. Se il coordinatore si guasta, l'intero sistema si blocca. Per risolvere il problema, occorre eseguire un algoritmo di elezione in cui i processi ancora attivi eleggono un nuovo coordinatore. Gli algoritmi di elezione più famosi sono:
* Algoritmo dello spaccone di Garcia - Molina, 1982
* di Le Lann, 1977
* , 1979
* , 1982 (it)
- Eleição de líder é um problema da área de sistemas distribuídos que busca selecionar de forma consensual um processo num conjunto de processos tendo como objetivo selecionar um líder para uma determinada tarefa. A eleição torna-se necessária quando o sistema distribuído está sendo iniciado pela primeira vez ou o líder anterior não consegue se comunicar com os demais processos pela ocorrência de alguma falha. Há vários algoritmos que realizam a eleição do líder, cada um específico a alguma situação. (pt)
- In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" (or coordinator) of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader. (en)
- 분산 컴퓨팅에서 리더 선출(leader election)이란 단일 프로세서를 여러 컴퓨터(노드)에 분산된 작업들의 주최자로 지정하는 작업이다. 작업이 시작하기 전, 모든 네트워크 노드들은 누가 작업의 "리더"로 동작할지 서로 알지 못하거나 현재 리더(분산 컴퓨팅)와 통신할 수 없다. 리더 선출 알고리즘 실행 후에는, 네트워크 상의 모든 노드들은 특별한 고유 노드를 작업 리더로 인식한다. 네트워크 노드들은 그들 중 누가 "리더" 상태가 될지 결정하기 위해 그들끼리 통신한다. 이를 위해, 그들은 그들간의 균형을 깨트리기 위한 방법이 필요하다. 예를 들어, 각 노드가 비교 가능한 고유 식별자를 가질 경우, 노드들은 그들의 식별자를 비교 가능하며, 가장 뛰어난 식별자를 가진 노드를 리더로 결정할 수 있다. 이 문제의 정의는 토큰이 손실된 링 네트워크에서 새로운 토큰을 만드는 방법을 정의한 LeLann으로부터 기인된다. (ko)
- 分散コンピューティングにおいて、リーダー選出は複数のコンピュータ(ノード)に分散されたタスクの取りまとめ役として、一つのプロセスを指定する過程である。タスクが開始する前、全てのネットワークノードは、どのノードが「リーダー」、つまりタスクの取りまとめ役であるかは知らない。しかし、リーダー選出アルゴリズムが実行された後、ネットワーク中の全ノードは特定のノードをタスクリーダーとして認識する。 ネットワークノードは相互に通信を行い、いずれかが「リーダー」状態になるか決定する。そのために、ノード間の対称性を崩すための手法が必要となる。例えば、各ノードが固有のID番号があるのであれば、ノード間にてID番号の比較を行い、最も高いID番号を持っているノードがリーダーであると決定することが出来る。 この問題の定義はLeLannに帰せられることが多く、これをトークンリングネットワークにおいて、トークンが失われた際に新しいトークンを作成する手法として実現した。 リーダー選出アルゴリズムは全送信バイト数と時間という観点で経済的であるよう、設計されている。Gallager、Humblet、Spiraによって提案された一般無向グラフのためのアルゴリズム は分散アルゴリズムのデザイン一般に強いインパクトを与え、分散コンピューティングにおける影響が大きい論文としてダイクストラ賞を受賞した。 (ja)
- Алгоритм выбора лидера — это процесс в системе распределённых вычислений, который назначает один процесс организатором некоторой задачи, распределённой на несколько компьютеров (узлов). До начала выполнения задачи все узлы сети либо не осведомлены, какой узел будет вести себя как «лидер» (или координатор) задачи, либо не в состоянии общаться с текущим координатором. После того, как алгоритм выбора лидера отработает, каждый узел сети знает об определённом единственном узле, выступающем в качестве лидера. (ru)
- У розподілених обчисленнях, вибір лідера є процесом позначення одного процесу як організатора деякого завдання, розподіленого між декількома комп'ютерами (вузлами). Перш ніж розпочати завдання, всі вузли мережі або не знають, який вузол буде виконувати роль «лідера» (або координатора) завдання, або ці вузли не можуть спілкуватися з поточним координатором. Проте після запуску алгоритму вибору лідера кожен вузол у мережі визначає один особливий, унікальний вузол і сприймає його як лідера завдання. (uk)
|
