Abstract:

The gossip problem (telephone problem) is an information dissemination problem where each of n nodes of a communication network has a unique piece of information that must be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. Upon a call between the given two nodes, they exchange the whole information known to them at that moment. In this paper, we investigate the k-fault-tolerant gossip problem, which is a generalization of the gossip problem, where at most k arbitrary faults of calls are allowed. The problem is to find the minimal number of calls τ(n,k) needed to guarantee the spread of whole information. We constructed a fc-fault-tolerant gossip scheme (sequences of calls) to find the upper bounds of τ (n,k), which improves the previously known results for some particular small values of n and k.
; Проблемой gossip (проблемой телефонов) является проблема распространения информации, где каждый из n узлов сети связи имеет уникальный фрагмент информации, который должен быть передан всем остальныем узлам с помощью двусторонней связи (телефонные звонки) между парами узлов. После вызова между данными двумя узлами, они обмениваются всей информацией, известной им в данный момент. В этой статье, мы исследуем k-отказоустойчивую gossip проблему, которая является обобщением задачи gossip, где наиболее k произвольных сбойных вызовов разрешены. Проблема в том, чтобы найти минимальное количество звонков т (n, k), необходимых для обеспечения полного распространения информации. М ы построили k-отказоустойчивую gossip схему (последовательности вызовов) с целью найти верхние границы т (n, k ), которая улучшает ранее известные результаты для некоторых малых значений n и k.

Date submitted:

25.08.2014

Date accepted:

27.11.2014

Identifier:

oai:noad.sci.am:135972

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

42

URL:

Additional Information:

williamhovnanyan@gmail.com ; psuren55@yandex.ru ; povahagn@gmail.com

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI