Gossiping in a graph is the process of distributing every vertex`s unique information to every other vertex. This thesis deals with the problem of gossiping in rectangular grids under a condition that each communicating vertex can give one packet to only one adjacent vertex and receive one packet from that. For m × n rectangular grids, previous gossiping algorithm takes μ + $\frac{1}{4}mn$ + 2) rounds[5], and known lower bound is μ + 1) [3]. A difficulty of gossiping in m × n rectangular grids is due to the absence of a Hamiltonian cycle where mn is odd. Though they have not a Hamiltonian cycle, they work like a Hamiltonian cycle in our gossiping algorithm. Our gossiping algorithm takes (mn + 9) rounds in m × n grids where mn is odd.
가쉬핑이란 그래프에서 각각의 점들이 각기 다른 정보들을 다른 모든점들에게 전파하는 것이다. 단어의 의미 그대로, 각 점들이 가진 정보를 다른 점들이 모두 알 수 있도록 소문내는 것이라고 생각할 수 있다.
이 논문에서는 그리드(직사각형 격자 구조의 그래프)에서 각각의 점들이 매번 인접한 하나의 점과 하나의 패킷을 서로 주고 받을 수 있는 조건하에 가쉬핑을 빠르게 하는 알고리즘을 제시한다.
m × n 그리드에서 가쉬핑을 하는 기존의 알고리즘은 (mn + $\frac{1}{4} mn$ + 2) 라운드가 걸려서[5] 이 문제의 알려진 하한(lower bound)인 (mn + 1)과는 [3] 다소 거리가 있었다. 이는 mn이 홀수인 그리드에는 일반적으로 가쉬핑 문제를 잘 해결할 수 있게 하는 헤밀토니안(Hamiltonian) 사이클이 없기 때문이다. 하지만 우리는 mn이 홀수인 그리드가 헤밀토니안 사이클이 없더라도, 헤밀토니안 사이클이 가쉬핑에서 동작하는 것처럼 그리드가 동작하도록 하였다. 이로써 우리는 그리드에서 가쉬핑을 (mn + 9) 라운드 만에 끝낼 수 있는 알고리즘을 제시하였다.
