가십 프로토콜

Gossip protocol

가십프로토콜이나 전염병프로토콜은 전염병이 퍼지는 방식에 근거한 컴퓨터 P2P 통신의 절차나 과정이다.[1] 일부 분산형 시스템은 데이터가 그룹의 모든 구성원에게 전파되도록 하기 위해 피어투피어 가십을 사용한다. 일부 애드호크 네트워크는 중앙 레지스트리가 없으며 공통 데이터를 전파하는 유일한 방법은 각 회원에게 의존하여 이웃에게 전달하는 것이다.

가십 커뮤니케이션

가십 소통의 개념은 직장인들이 소문을 퍼뜨리는 비유를 통해 알 수 있다. 매시간 회사원들이 냉각수 냉각기 주위에 모여든다고 가정해보자. 각 직원은 다른 직원과 짝을 지어 무작위로 뽑힌 뒤 최근의 험담을 나눈다. 데이브는 하루의 시작과 동시에 새로운 루머를 시작한다. 그는 밥에게 찰리가 콧수염을 염색한다고 믿는다고 말했다. 다음 회의에서 밥은 앨리스에게 말하고 데이브는 이브에게 그 생각을 반복한다. 각각의 물냉방 랑데부 후에, 그 소문을 들은 사람들의 수는 대략 두 배로 증가한다(같은 사람에게 두 번 험담을 하는 것은 설명하지 않지만, 아마도 데이브는 그 이야기를 프랭크에게 말하려 할 것이다, 단지 프랭크가 앨리스에게서 이미 들었다는 것을 알게 되었다). 컴퓨터 시스템은 일반적으로 이러한 종류의 프로토콜을 임의의 "피어 선택"의 형태로 구현한다: 주어진 빈도로, 각 기계는 임의로 다른 기계를 선택하고 어떤 소문도 공유한다.

다양한 변형 및 스타일

각 사용-시나리오가 조직의 특정 요구에 맞게 맞춤 제작될 가능성이 높기 때문에 아마도 수백 가지의 특정 가십 같은 프로토콜이 있을 것이다.

예를 들어, 가십 프로토콜은 다음과 같은 아이디어 중 일부를 채택할 수 있다.

  • 프로토콜의 핵심에는 주기적인 쌍방향의 프로세스 간 상호작용이 포함된다.
  • 이러한 상호작용 동안 교환되는 정보는 한정된 크기의 정보다.
  • 에이전트가 상호 작용할 때, 적어도 한 에이전트의 상태가 다른 에이전트의 상태를 반영하도록 변경된다.
  • 신뢰할 수 있는 통신은 가정하지 않는다.
  • 상호작용의 빈도는 프로토콜 비용이 무시할 수 있도록 일반적인 메시지 지연에 비해 낮다.
  • 피어 선택에는 어떤 형태의 임의성이 있다. 피어는 전체 노드 집합 또는 작은 인접 노드 집합에서 선택할 수 있다.
  • 복제 때문에 전달된 정보의 암묵적인 중복성이 존재한다.

가십 프로토콜 유형

가십 프로토콜의 두 가지 일반적인 스타일을 구별하는 것이 유용하다.[2]

  • 전파 프로토콜(또는 루머를 퍼뜨리는 프로토콜) 이들은 가십을 사용하여 정보를 퍼뜨린다. 기본적으로 네트워크 내의 에이전트 플러딩에 의해 작동하지만, 경계된 최악의 부하를 발생시키는 방식으로 작동한다.
    1. 이벤트 전파 프로토콜은 가십을 사용하여 멀티캐스트를 수행한다. 그들은 사건을 보고하지만, 가십은 주기적으로 일어나고 사건은 실제로 가십을 유발하지 않는다. 여기서 한 가지 우려 사항은 사건이 발생한 시점부터 사건이 전달될 때까지 잠재적으로 높은 지연 시간이다.
    2. 백그라운드 데이터 배포 프로토콜은 참여 노드와 관련된 정보에 대해 지속적으로 가십을 한다. 일반적으로, 전파 지연은 문제가 되는 정보가 천천히 변경되거나 약간 오래된 데이터에 대해 행동하는 것에 대한 큰 처벌이 없기 때문에 문제가 되지 않는다.
  • Aggregate를 계산하는 프로토콜. 이들은 네트워크의 노드에서 정보를 샘플링하고 시스템 전체 값에 도달하기 위해 값을 결합하여 네트워크 전체 Aggregate를 계산한다. 즉, 일부 측정 노드에서 가장 큰 값은 만드는 값, 가장 작은 값 등이다. 핵심 요건은 고정된 크기의 쌍방향 정보 교환에 의해 집계를 계산할 수 있어야 한다는 것이다. 이러한 정보 교환 로그는 일반적으로 시스템 크기의 여러 라운드에 걸친 정보 교환 로그 후에 종료되며, 그 때까지 전체 정보 흐름 패턴이 확립될 것이다. 집계의 부작용으로서 가십을 이용하여 다른 종류의 문제를 해결하는 것이 가능하다. 예를 들어, 가십 오버레이에 있는 노드를 집적 방식의 정보 교환을 이용하여 로그타임에 노드 ID(또는 일부 다른 속성)별로 정렬된 목록으로 배열할 수 있는 가십 프로토콜이 있다. 마찬가지로 나무 구조와 일치하도록 치우친 패턴으로 가십을 함으로써 "sum"이나 "count"와 같은 집계를 계산하는 가십 알고리즘도 있다.

"gossip"이라는 용어의 초기 사용을 앞지르는 많은 프로토콜은 이 다소 포괄적인 정의에 속한다. 예를 들어 인터넷 라우팅 프로토콜은 가십과 같은 정보 교환을 사용하는 경우가 많다. 가십 기질은 표준 라우팅 네트워크: 기존의 포인트 투 포인트 메시지에 대한 노드 "가십"을 구현하기 위해 사용될 수 있으며, 가십 층을 통해 트래픽을 효과적으로 밀어낸다. 대역폭 허용, 이는 가십 시스템이 잠재적으로 어떤 고전적인 프로토콜을 지원하거나 어떤 고전적인 분산 서비스를 구현할 수 있음을 의미한다. 그러나 그러한 광범위하게 포괄적으로 해석하는 것은 거의 의도된 바가 없다. 보다 전형적으로 가십 프로토콜은 특히 규칙적이고 주기적이며 상대적으로 게으르며 대칭적이며 분산적인 방식으로 실행되는 프로토콜이다. 노드 사이의 높은 대칭성이 특히 특징이다. 따라서 가십 기질 위에 2상 커밋 프로토콜을 실행할 수 있지만, 그렇게 하는 것은 정의의 표현은 아니더라도 정신과 상충될 것이다.

집적적으로 일관되는 용어는 기하급수적으로 빠른 정보 확산을 달성하는 프로토콜을 기술하는 데 가끔 사용된다. 이를 위해 프로토콜은 시간 로그 내에서 정보의 영향을 받는 모든 노드에 새로운 정보를 시스템 크기로 전파해야 한다("믹싱 시간"은 시스템 크기에서 로그여야 한다).

예

일부 검색 패턴과 가장 밀접하게 일치하는 개체를 알 수 없는 크기의 네트워크 내에서 컴퓨터가 서로 연결되어 있고 각 컴퓨터가 가십 프로토콜을 구현하는 작은 에이전트 프로그램을 실행하는 위치를 찾으려고 한다고 가정합시다.

  • 검색을 시작하기 위해 사용자는 로컬 에이전트에게 검색 문자열에 대한 가십을 시작하도록 요청할 수 있다. (에이전트가 알려진 피어 목록에서 시작하거나 공유 저장소에서 이 정보를 검색하는 것으로 가정하고 있음)
  • 주기적으로, 어느 정도(초당 10회라고 하자, 단순성을 위해), 각 에이전트는 무작위로 몇몇 다른 에이전트를 고르고, 그것으로 뒷말을 한다. A에게 알려진 검색 문자열은 이제 B에게도 알려질 것이며, 그 반대의 경우도 마찬가지일 것이다. 가십의 다음 "라운드"에서 A와 B는 아마도 C와 D와 같은 임의의 또래들을 추가로 고를 것이다. 이러한 순환 배전 현상은 일부 메시지가 손실되거나 선택된 피어 중 일부가 검색 문자열에 대해 동일하거나 이미 알고 있더라도 프로토콜을 매우 견고하게 만든다.
  • 검색 문자열을 처음 수신할 때 각 에이전트는 로컬 시스템에서 일치하는 문서를 검사한다.
  • 요원들은 또한 지금까지 최고의 시합에 대해 험담을 한다. 따라서 A가 B와 가십을 하면 상호 작용 후 A는 B에게 알려진 최고의 경기를 알게 되고, 그 반대의 경우도 알게 된다. 최상의 일치사항은 네트워크를 통해 "확대"된다.

메시지가 커질 수 있는 경우(예: 많은 검색이 동시에 활성화된 경우) 크기 제한을 도입해야 한다. 또한 검색은 네트워크에서 "고령화"되어야 한다.

따라서 네트워크 크기(에이전트 수)의 로그 시간 내에 모든 새 검색 문자열이 모든 에이전트에 도달하게 된다. 동일한 대략적인 길이의 추가 지연 시간 내에 모든 에이전트는 가장 적합한 매치를 찾을 수 있는 위치를 알게 될 것이다. 특히 수색을 시작한 요원이 가장 잘 맞는 짝을 찾아냈을 것이다.

예를 들어, 2만 5천대의 기계가 있는 네트워크에서, 우리는 검색 문자열을 퍼뜨리기 위해 15개, 그리고 가장 잘 어울리는 것을 발견하기 위해 15개 등 약 30여 차례의 가십을 거친 후에 최고의 매치를 발견할 수 있다. 가십 교환은 과도한 부하 없이 10분의 1초마다 한 번씩 발생할 수 있기 때문에 이러한 형태의 네트워크 검색은 빅데이터 센터를 약 3초 만에 검색할 수 있다.

이 시나리오에서 검색은 예를 들어 10초 후에 네트워크에서 자동으로 만료될 수 있다. 그때쯤이면 이니시에이터는 답을 알고 그 검색에 대해 더 이상 험담할 필요가 없다.

가십 프로토콜은 또한 분산된 데이터베이스 일관성을 달성하고 유지하기 위해 또는 알 수 없는 크기의 네트워크의 노드 수를 계산하고 뉴스를 강력하게 전파하며, 어떤 구조화 정책에 따라 노드를 구성하고, 소위 오버레이 네트워크를 구축하며, 집계를 계산하며,네트워크의 노드 검색, 리더 선출 등

전염병 알고리즘

가십 프로토콜은 생물학적 집단에서 바이러스 감염이 확산되는 방식과 유사한 방식으로 정보를 전파하는 데 사용될 수 있다. 실제로 전염병의 수학은 가십 소통의 수학을 모형화하는 데 종종 사용된다. 전염병 알고리즘이라는 용어는 이러한 종류의 가십 기반 정보 전파를 사용하는 소프트웨어 시스템을 설명할 때 가끔 사용된다.

참고 항목

  • 가십 프로토콜은 네트워킹 프로토콜의 많은 클래스 중 하나의 클래스일 뿐이다. 가상 동기화, 분산 상태 시스템, Paxos 알고리즘, 데이터베이스 트랜잭션을 참조하십시오. 각 클래스는 세부사항과 성능 속성은 다르지만 사용자에게 제공되는 보증 수준에서는 유사하게 수십 또는 수백 개의 프로토콜을 포함한다.
  • 일부 가십 프로토콜은 무작위 동료 선택 메커니즘을 보다 결정론적인 계획으로 대체한다. 예를 들어 NeighourCast 알고리즘에서는 무작위 노드와 대화하는 대신 인접 노드와의 대화만으로 정보가 전파된다. 유사한 아이디어를 사용하는 알고리즘이 많이 있다. 그러한 프로토콜을 설계할 때 핵심 요구사항은 이웃이 확장기 그래프를 추적하는 것이다.
  • 라우팅
  • 트리블러, 가십 프로토콜을 사용하는 비트토렌트 피어 투 피어 클라이언트.

참조

  1. ^ Demers, Alan; Greene, Dan; Hauser, Carl; Irish, Wes; Larson, John (1987). "Epidemic algorithms for replicated database maintenance". Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. pp. 1–12. doi:10.1145/41840.41841. ISBN 978-0-89791-239-6. OCLC 8876960204. S2CID 1889203.
  2. ^ Jelasity, Márk (2011-01-01). "Gossip" (PDF). In Serugendo, Giovanna Di Marzo; Gleizes, Marie-Pierre; Karageorgos, Anthony (eds.). Self-organising Software. Natural Computing Series. Springer Berlin Heidelberg. pp. 139–162. doi:10.1007/978-3-642-17348-6_7. ISBN 9783642173479. S2CID 214970849.

추가 읽기

  • Allavena, André; Demers, Alan; Hopcroft, John E. (2005). "Correctness of a gossip based membership protocol". Proceedings of the twenty-fourth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '05. p. 292. doi:10.1145/1073814.1073871. ISBN 978-1-58113-994-5. OCLC 8876665695. S2CID 9378092.
  • Birman, Kenneth P.; Hayden, Mark; Ozkasap, Oznur; Xiao, Zhen; Budiu, Mihai; Minsky, Yaron (May 1999). "Bimodal multicast". ACM Transactions on Computer Systems. 17 (2): 41–88. doi:10.1145/312203.312207. S2CID 207744063.
  • Eugster, P. Th.; Guerraoui, R.; Handurukande, S. B.; Kouznetsov, P.; Kermarrec, A.-M. (November 2003). "Lightweight probabilistic broadcast" (PDF). ACM Transactions on Computer Systems. 21 (4): 341–374. doi:10.1145/945506.945507. S2CID 6875620.
  • Gupta, Indranil; Birman, Ken; Linga, Prakash; Demers, Al; Van Renesse, Robbert (2003). "Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead". Peer-to-Peer Systems II. Lecture Notes in Computer Science. Vol. 2735. pp. 160–169. doi:10.1007/978-3-540-45172-3_15. ISBN 978-3-540-40724-9.
  • 분산형 시스템용 P2P기술의 체계적 설계 Indranil Gupta, Global Data Management, eds: R. Baldoni, G. Cortese, F. Davide, A. 멜피냐노, 2006년
  • Leitao, Joao; Pereira, Jose; Rodrigues, Luis (2007). "HyPar View: A Membership Protocol for Reliable Gossip-Based Broadcast". 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07). pp. 419–429. doi:10.1109/DSN.2007.56. hdl:1822/38895. ISBN 978-0-7695-2855-7. S2CID 9060122.
  • Gupta, I.; Kermarrec, A.-M.; Ganesh, A.J. (July 2006). "Efficient and adaptive epidemic-style protocols for reliable and scalable multicast". IEEE Transactions on Parallel and Distributed Systems. 17 (7): 593–605. doi:10.1109/TPDS.2006.85. S2CID 1148979.
  • Jelasity, Márk; Montresor, Alberto; Babaoglu, Ozalp (August 2009). "T-Man: Gossip-based fast overlay topology construction" (PDF). Computer Networks. 53 (13): 2321–2339. doi:10.1016/j.comnet.2009.03.013.
  • Leitao, Joao; Pereira, Jose; Rodrigues, Luis (2007). "Epidemic Broadcast Trees". 2007 26th IEEE International Symposium on Reliable Distributed Systems (SRDS 2007). pp. 301–310. doi:10.1109/SRDS.2007.27. hdl:1822/38894. ISBN 978-0-7695-2995-0. S2CID 7210467.
  • Jelasity, Márk; Montresor, Alberto; Babaoglu, Ozalp (August 2005). "Gossip-based aggregation in large dynamic networks" (PDF). ACM Transactions on Computer Systems. 23 (3): 219–252. doi:10.1145/1082469.1082470. S2CID 2608879.
  • 대형 오버레이 네트워크의 슬라이싱 주문. 마르크 젤라시티와 앤 마리 케르마르렉. IEEE P2P, 2006.
  • 근접 인식 수퍼피어 오버레이 토폴로지. 지안 파올로 제시, 알베르토 몽트레소르, 오잘프 바바오글루. IEEE 네트워크 및 서비스 관리에 관한 거래, 4(2):74–83, 2007년 9월.
  • X-BOT: 비정형 오버레이의 복원력 최적화를 위한 프로토콜. 주앙 레이탕, 주앙 마르크스, 호세 페레이라, 루이스 로드리게스. Proc. 제28회 신뢰할 수 있는 분산 시스템에 대한 IEEE 국제 심포지엄(SRDS'09)
  • 공간 가십 및 자원 위치 프로토콜. 데이비드 켐페, 존 클라인버그, 앨런 데머스 ACM 저널 (JACM) 51: 6 (2004년 11월)
  • 가십 기반 집계 정보 계산. 데이비드 켐페, 알린 도브라, 요하네스 게크 Proc. 제44회 컴퓨터 과학의 기초에 관한 IEEE 연례 심포지엄(FOCES). 2003.
  • 대규모 및 동적 분산 시스템에서 그룹 크기 추정을 위한 능동 및 수동 기법 디오니시오스 코스툴라스, 디미트리오스 프살툴리스, 인드라닐 굽타, 켄 비르만, 알 데머스. Escvier Journal of Systems and Software, 2007.
  • 하나 구축, 하나를 무료로 제공: 여러 P2P 오버레이 네트워크의 공존 활용 발라수브라마네얌 마니마란, 마린 베르티에, 앤 마리 케르마르렉. Proc. ICDCS, 2007년 6월
  • 오버레이 네트워크에서 피어 카운트 및 샘플링: 무작위 보행 방법 로랑 마슐리에, 에르완 르 메러, 앤 마리 케르마르렉, 아얄바디 가네쉬. Proc. 제25회 ACM PODC. 2006년 덴버.
  • 주문형 코드. 알베르토 몽트레소르, 마르크 젤라시티, 오잘프 바바오글루. Proc. 2005년 8월 독일 콘스탄츠에서 제5차 P2P(Peer-to-Peer Computing) 회의.
  • Nielsen, Michael A. (2005). "Introduction to expander graphs" (PDF). S2CID 3045708. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  • 지름이 낮은 P2P 네트워크 구축. G. 판두랑간, P. 라그하반, 일라이 업팔. 2001년 제42회 컴퓨터 과학 기초 심포지엄의 진행에서.
  • Van Renesse, Robbert; Birman, Kenneth P.; Vogels, Werner (May 2003). "Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining". ACM Transactions on Computer Systems. 21 (2): 164–206. doi:10.1145/762483.762485. S2CID 6204358.
  • Voulgaris, S.; Kermarrec, A.-M.; Massoulie, L.; Van Steen, M. (2004). "Exploiting semantic proximity in peer-to-peer content searching". Proceedings. 10th IEEE International Workshop on Future Trends of Distributed Computing Systems, 2004. FTDCS 2004. pp. 238–243. doi:10.1109/FTDCS.2004.1316622. hdl:1871/12832. ISBN 0-7695-2118-5. S2CID 9464168.
  • Gupta, Ruchir; Singh, Yatindra Nath (2015). "Reputation Aggregation in Peer-to-Peer Network Using Differential Gossip Algorithm". IEEE Transactions on Knowledge and Data Engineering. 27 (10): 2812–2823. arXiv:1210.4301. doi:10.1109/TKDE.2015.2427793. S2CID 650473.
  • Bailey, Norman T. J. (1957). The Mathematical Theory of Epidemics. Hafner. ISBN 978-0-85264-113-2.