중앙 집중식 알고리즘을 분산 알고리즘으로 변환하는 방법은 무엇입니까?

Question

중앙 집중식 알고리즘을 분산 알고리즘으로 변환하는 알고리즘 또는 절차가 있습니까?이론적 인 결과 또는 관련 복잡도 분석이 있습니까?

Answer 1

확실합니다. N 시스템이있는 분산 시스템이있는 경우, 항상 기계 1에서 항상 중앙 집중식 알고리즘을 실행할 수 있으며 기계 2..n 앉아서 유휴 상태를 유지할 수 있습니다.

모든 순차 알고리즘을 병렬로 볼 수 있는지 묻는 경우, 그것은 열려있는 질문이지만 대답은 NC 복잡성 클래스 . Wikipedia 국가로서,

아마도 "본질적으로 순차적으로"존재하는 약간의 문제가 있으며 병렬 처리를 사용하여 크게 달라질 수는 없습니다.

p-complete 문제는 병렬 처리에 의한 속도를 높이기 위해 일할 수없는 문제에 대한 좋은 후보자입니다.

분산 시스템에서 모든 알고리즘을 믿을 수 있는지 묻는 경우, 이는 당신이 고려중인 어떤 종류의 실패에 달려있는 미묘한 질문입니다. 합의 프로토콜 , 상태 컴퓨터 복제 및 캡 이론 .