In the recent years, message-passing paradigm has emerged as a canonical algorithmic solution to solve networkwide problems by means of minimal local information exchange, across variety of disciplines. The primary purpose of this work is to understand tradeoffs offered between network performance and protocol overhead by a class of message-passing algorithms – belief propagation and its variants. Through an extensive simulation study, for prototypical network topological models, we find that such class can lead to wireless network scheduling algorithms under which each node exchanges exactly one message per time-slot and achieve reasonably high performance. This algorithm utilizes the “continuity” of network state to achieve high performance in presence of minimal information exchange.