Byzantine Generals Problem

What is Byzantine Generals Problem?

๋ถ„์‚ฐ์‹œ์Šคํ…œ๊ณผ ๋ธ”๋ก์ฒด์ธ

๊ณผ๊ฑฐ์—๋Š” ํ•œ๊ฐœ์˜ ์ปดํ“จํ„ฐ๋กœ ๋ชจ๋“  ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ์—ˆ์ง€๋งŒ ์‹œ๊ฐ„์ด ์ง€๋‚˜๋ฉด์„œ ํ•˜๋‚˜์˜ ๋จธ์‹ ์˜ ์ปดํ“จํŒ… ์ž์› ์ด์ƒ์„ ํ•„์š”๋กœ ํ•˜๋Š” ์ž‘์—…์ด ๋“ฑ์žฅํ–ˆ๋‹ค. ๋ถ„์‚ฐ ์‹œ์Šคํ…œ์€ ์ด๋Ÿฐ ์ž‘์—…์„ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ์—ฌ๋Ÿฌ ์ปดํ“จํ„ฐ๊ฐ€ ๊ฐ™์ด ๋™์ž‘ํ•˜๋Š” ์‹œ์Šคํ…œ์ด๋‹ค. ๋น…ํ…Œํฌ ๊ธฐ์—…๋“ค์˜ ๋ฐ์ดํ„ฐ ์„ผํ„ฐ๋Š” ์—„์ฒญ๋‚œ ์ˆ˜์˜ ์„œ๋ฒ„๋“ค์ด ์„œ๋กœ ํ˜‘๋ ฅํ•˜์—ฌ ์ผ์„ ์ฒ˜๋ฆฌํ•œ๋‹ค.

๋ธ”๋ก์ฒด์ธ์€ ๋ถ„์‚ฐ์‹œ์Šคํ…œ๊ณผ ์œ ์‚ฌํ•˜๋‹ค. ๋‚˜์ค‘์— ๋‹ค์‹œ ์„ค๋ช…ํ•˜๊ฒ ์ง€๋งŒ, ๋ธ”๋ก์ฒด์ธ์€ ๊ธฐ๋ณธ์ ์œผ๋กœ ํƒˆ์ค‘์•™ํ™” ์‹œ์Šคํ…œ(decentralized system)์ด๋‹ค. ๋ธ”๋ก์ฒด์ธ ๋„คํŠธ์›Œํฌ์— ์†ํ•œ ๋…ธ๋“œ๋“ค์ด ์„œ๋กœ ๊ฒฐ๊ณผ๋ฅผ ๋ณด๊ณ  ํ•ฉ์˜ํ•˜๋Š” ๋ธ”๋ก์ฒด์ธ ์‹œ์Šคํ…œ์€ ๊ธฐ์กด์˜ ๋ถ„์‚ฐ ์‹œ์Šคํ…œ ๋ถ„์•ผ์—์„œ์˜ ์—ฐ๊ตฌ๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋ฐœ์ „ํ–ˆ๋‹ค.

๋ ˆ์Šฌ๋ฆฌ ๋žจํฌํŠธ์™€ ๋น„์ž”ํ‹ฐ์›€ ์žฅ๊ตฐ ๋ฌธ์ œ

๋ ˆ์Šฌ๋ฆฌ ๋žจํฌํŠธ๋Š” ๋ถ„์‚ฐ ์‹œ์Šคํ…œ์˜ ์•„๋ฒ„์ง€๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” ์ปดํ“จํ„ฐ ๊ณตํ•™์ž์ด๋‹ค. ๋žจํฌํŠธ๋Š” ๋ถ„์‚ฐ ์‹œ์Šคํ…œ์— ๋Œ€ํ•œ ์ „๋ฐ˜์ ์ธ ์—ฐ๊ตฌ๋ฅผ ์ง„ํ–‰ํ–ˆ๋‹ค. ๋ถ„์‚ฐ ์‹œ๊ณ„, ํŒฉ์†Œ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ „์ž์„œ๋ช… ๋“ฑ์˜ ๋…ผ๋ฌธ์„ ๋ฐœํ‘œํ–ˆ๋‹ค. ๊ทธ ์™ธ์—๋„ 2013๋…„์— ํŠœ๋ง์ƒ์„ ์ˆ˜์ƒํ–ˆ๊ณ , LaTeX(๋ ˆ์ดํ…)์„ ๋งŒ๋“  ์—…์ ์ด ์žˆ๋‹ค.

๊ทธ ์ค‘ ํ•œ ๋…ผ๋ฌธ(http://people.cs.uchicago.edu/~shanlu/teaching/33100_wi15/papers/byz.pdf)์€ ๋น„์ž”ํ‹ฐ์›€ ์žฅ๊ตฐ ๋ฌธ์ œ์— ๋Œ€ํ•˜์—ฌ ๋‹ค๋ฃฌ๋‹ค.

Byzantine Generals Problem by Lamport

๋น„์ž”ํ‹ฐ์›€ ์žฅ๊ตฐ ๋ฌธ์ œ์˜ ๊ฐœ์š”

๋น„์ž”ํ‹ฐ์›€์˜ ๋ถ€๋Œ€๋Š” ์—ฌ๋Ÿฌ ๋ถ„๋Œ€๋กœ ๋‚˜๋‰˜์–ด ์ ๊ตฐ์„ ๋‘˜๋Ÿฌ ์‹ธ๊ณ  ์žˆ๋‹ค. ๊ฐ ๋ถ„๋Œ€๋Š” ๊ฐ ๋ถ„๋Œ€์˜ ์žฅ๊ตฐ์ด ์ง€ํœ˜ํ•œ๋‹ค. ์žฅ๊ตฐ์€ ์ „๋ น์„ ํ†ตํ•ด์„œ ๋‹ค๋ฅธ ๋ถ„๋Œ€์˜ ์žฅ๊ตฐ๊ณผ ์†Œํ†ตํ•  ์ˆ˜ ์žˆ๋‹ค. ์ ๊ตฐ์˜ ๋™ํƒœ๋ฅผ ์‚ดํŽด๋ณด๊ณ  ์žฅ๊ตฐ์€ ์„œ๋กœ ํ†ต์‹ ํ•ด์„œ ๊ณต๊ฒฉํ• ์ง€ ๋ง์ง€ ํ•˜๋‚˜์˜ ํ•ฉ์˜์ ์— ๋„๋‹ฌํ•ด์•ผ ํ•œ๋‹ค. ํ•˜์ง€๋งŒ ์žฅ๊ตฐ ์ค‘ ๋ช‡๋ช…์€ ์ด๋“ค์ด ํ•ฉ์˜์— ๋„๋‹ฌํ•˜์ง€ ๋ชปํ•˜๋„๋ก ํ•˜๋Š” ๋ฐฐ์‹ ์ž์ด๋‹ค.

๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ์—๋Š” ๋‘๊ฐ€์ง€ ๊ทœ์น™์ด ์žˆ๋‹ค. ์•„๋ž˜ ๋‘ ๊ทœ์น™์„ ๋งŒ์กฑํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐพ์•„์•ผํ•œ๋‹ค.

  1. ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ์žฅ๊ตฐ์€ ๊ฐ™์€ ํ–‰๋™์„ ์ทจํ•ด์•ผํ•œ๋‹ค. ์ฆ‰, ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ์žฅ๊ตฐ์€ ๋‹ค๊ฐ™์ด ๊ณต๊ฒฉํ•˜๊ฑฐ๋‚˜ ๋‹ค๊ฐ™์ด ํ›„ํ‡ดํ•œ๋‹ค. ๋ฐฐ์‹ ์ž๋“ค์€ ๋งˆ์Œ๋Œ€๋กœ ํ–‰๋™ํ•ด๋„ ์ƒ๊ด€์—†๋‹ค.

  2. ์ ์€ ์ˆ˜์˜ ๋ฐฐ์‹ ์ž๋“ค์ด ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ์žฅ๊ตฐ๋“ค์ด ์ž˜๋ชป๋œ ๊ฒฐ์ •์„ ํ•˜๊ฒŒ ํ•˜๋ฉด ์•ˆ ๋œ๋‹ค.

๋…ผ๋ฌธ์— ์˜ํ•˜๋ฉด ์ด ์กฐ๊ฑด์€ ๊ฒฐ๊ตญ ์•„๋ž˜์˜ ์กฐ๊ฑด์œผ๋กœ ๋ฐ”๊ฟ” ๋งํ•  ์ˆ˜ ์žˆ๋‹ค. (๋…ผ๋ฌธ ์ฐธ๊ณ )

  1. v(i)๋ฅผ ์ž์‹ ์ด ์•Œ๊ณ ์žˆ๋Š” i๋ฒˆ์งธ ์žฅ๊ตฐ์˜ ๊ฒฐ์ •์ด๋ผ๊ณ  ํ•œ๋‹ค๋ฉด, ๋ชจ๋“  ์žฅ๊ตฐ์€ ์„œ๋กœ ๊ฐ™์€ v(i)๋ฅผ ๊ฐ€์ ธ์•ผํ•œ๋‹ค.

  2. ๋งŒ์•ฝ i๋ฒˆ์งธ ์žฅ๊ตฐ์ด ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ์žฅ๊ตฐ์ด๋ผ๋ฉด, ๊ทธ๊ฐ€ ๋ณด๋‚ธ ๋ฉ”์„ธ์ง€์™€ v(i)๋Š” ์ผ์น˜ํ•ด์•ผ ํ•œ๋‹ค.

์—ฌ๊ธฐ์„œ i๋ฒˆ์งธ ์žฅ๊ตฐ์„ ์‚ฌ๋ น๊ด€(commander)๋ผ๊ณ  ๋ถ€๋ฅด๋ฉด ๊ฒฐ๊ตญ ๋น„์ž”ํ‹ฐ์›€ ์žฅ๊ตฐ ๋ฌธ์ œ๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด ์ •๋ฆฌ๋œ๋‹ค.

๋น„์ž”ํ‹ฐ์›€ ์žฅ๊ตฐ ๋ฌธ์ œ

์‚ฌ๋ น๊ด€์€ ๊ทธ์˜ ๋ถ€ํ•˜ n-1๋ช…์—๊ฒŒ ๋ช…๋ น์„ ์ „๋‹ฌํ•˜๋Š”๋ฐ, ์•„๋ž˜๋ฅผ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค. ์–ด๋–ป๊ฒŒ ๋ฉ”์„ธ์ง€๋ฅผ ์ฃผ๊ณ  ๋ฐ›์•„์•ผํ• ๊นŒ?

  1. ๋ชจ๋“  ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ๋ถ€ํ•˜๋Š” ๊ฐ™์€ ๋ช…๋ น์„ ์ˆ˜ํ–‰ํ•˜๊ณ ,

  2. ์‚ฌ๋ น๊ด€์ด ์ถฉ์„ฑ์Šค๋Ÿฝ๋‹ค๋ฉด, ๋ชจ๋“  ์ถฉ์„ฑ์Šค๋Ÿฌ์šด ๋ถ€ํ•˜๋Š” ๊ทธ ๋ช…๋ น์— ๋”ฐ๋ฅธ๋‹ค.

์ฐฉํ•œ ๊ณฐ๋“ค์€ ๊ฐ™์€ ๊ฒฐ์ •์„ ๋‚ด๋ ค์•ผํ•œ๋‹ค. http://www.distributedsystemscourse.com/

๋ ˜ํฌํŠธ์˜ ํ•ด๋ฒ•

๋ ˜ํฌํŠธ๋Š” ๋…ผ๋ฌธ์—์„œ ๊ตฌ๋‘ ๋ฉ”์„ธ์ง€(Oral Message), ์„œ๋ช…๋œ ๋ฉ”์„ธ์ง€(Signed Message)์˜ ๊ฒฝ์šฐ์— ๋Œ€ํ•œ ํ•ด๋ฒ•์„ ์ œ์‹œํ•œ๋‹ค. ์ž์„ธํ•œ ๋‚ด์šฉ์€ ๋…ผ๋ฌธ์—์„œ ์‚ดํŽด๋ณด์ž.

๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ์™€ ๋ธ”๋ก์ฒด์ธ์€ ๋ฌด์Šจ ์ƒ๊ด€?

๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ์—์„œ ์‚ฌ๋ น๊ด€์˜ ๋ช…๋ น์„ ์ธํ’‹(Input), ๋ถ€ํ•˜๋ฅผ ํ”„๋กœ์„ธ์„œ(processors), ๋ฐฐ์‹ ์ž๋ฅผ ์˜ค์ž‘๋™ํ•˜๋Š” ํ”„๋กœ์„ธ๋กœ ๋ฐ”๊ฟ”๋ณด๋ฉด ๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ๋Š” ์˜ฌ๋ฐ”๋ฅธ ์ธํ’‹์„ ๋ฐ›์€ ํ”„๋กœ์„ธ์„œ๋Š” ์˜ค์ž‘๋™ํ•˜๋Š” ํ”„๋กœ์„ธ๊ฐ€ ์žˆ๋”๋ผ๋„ ํ•ญ์ƒ ์˜ฌ๋ฐ”๋ฅธ ์•„์›ƒํ’‹์„ ๋„์ถœํ•ด์•ผ ํ•จ์„ ๋‹ค๋ฃจ๊ณ  ์žˆ์Œ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

๋” ๋‚˜์•„๊ฐ€์„œ ๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ์—์„œ ์‚ฌ๋ น๊ด€์˜ ๋ช…๋ น์„ ๊ฑฐ๋ž˜(transaction), ๋ถ€ํ•˜๋ฅผ ๋ธ”๋ก์ฒด์ธ ๋„คํŠธ์›Œํฌ์— ์ฐธ์—ฌํ•œ ๋…ธ๋“œ(Node) ํ˜น์€ ์ปดํ“จํ„ฐ, ๋ฐฐ์‹ ์ž๋ฅผ ๊ณต๊ฒฉ์ž(Hacker) ๋ณด๋ฉด ๋น„์ž”ํ‹ฐ์›€ ๋ฌธ์ œ๋Š” ๋ธ”๋ก์ฒด์ธ์—์„œ ๊ณต๊ฒฉ์ž๊ฐ€ ์†Œ์ˆ˜ ์กด์žฌํ•˜๋”๋ผ๋„ ๋…ธ๋“œ๊ฐ€ ๋‹จ ํ•˜๋‚˜์˜ ํ•ฉ์˜๋ฅผ ๋„์ถœํ•˜๋Š” ๊ฒƒ์— ๋Œ€ํ•œ ๋ฌธ์ œ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

๋ธ”๋ก์ฒด์ธ์€ ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ํ•˜๋‚˜์˜ ํ•ด๋ฒ•์ด๋‹ค.

๋ธ”๋ก์ฒด์ธ๋งŒ์ด ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋‹ค. ํ™˜๊ฒฝ์— ๋”ฐ๋ผ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๋ณ€์ˆ˜๊ฐ€ ์กด์žฌํ•˜๊ณ  (์ฐธ์—ฌํ•˜๋Š” ๋…ธ๋“œ๋“ค์ด ์–ผ๋งˆ๋‚˜ ๋งŽ์€ ์ง€, ๋„คํŠธ์›Œํฌ๊ฐ€ ๋Š๊ฒจ๋„ ๋ณต๊ตฌ๋˜์–ด์•ผ ํ•˜๋Š”์ง€ ๋“ฑ...) ์ด์— ๋”ฐ๋ผ์„œ ํ•ฉ์˜๋ฅผ ๋„์ถœํ•˜๋Š” ๋ฐฉ๋ฒ• ๋˜ํ•œ ๋‹ฌ๋ผ์ง„๋‹ค.

์ฐธ๊ณ : http://www.distributedsystemscourse.com/

Last update: 04/07/2021

Last updated

Was this helpful?