В качестве разновидности запроса случайного блока по случайному смещению, можно запрашивать не сам блок, а его хэш. Что-то типа: "Эй, чувак, дай md5 блока длиной 512 по смещению 23121 файла такого-то", и узел отвечает.
Если у тебя самого нет этого куска, можно второй узел попросить сделать то же самое и сравнить. Если сходится, то успокоиться на время, если разошлось, то либо третий узел запрашивать, либо по своим кускам начинать гонять первые два узла, пока один не "спалится".
