Providing presence tracking of nodes of a logical network in a distributed computing system. Each node in a logical network tracks the presence of all other nodes on the network. This presence information is used by the protocol to optimize bandwidth utilization of the shared physical media, by not attempting to communicate with a device that does not appear to be or is unlikely to be present. In one embodiment, the presence tracking is applied to a power line carrier (PLC) physical media because of PLC's low-bandwidth characteristics, low baud rate characteristics and the widespread usage of plugged-in devices, the presence of which on the network is generally more transient by nature.