Virtualization software that includes a VDRB (virtual distributed router/bridge) module for performing L3 routing and/or bridging operations is provided. At least some of the VDRBs are configured as VDBs (virtual distributed bridge) for performing bridging operations between different network segments in a distributed manner. The bridging tasks of a network are partitioned among several VDBs of the network based on MAC addresses. MAC addresses of VMs or other types of network nodes belonging to an overlay logical network are partitioned into several shards, each shard of MAC addresses assigned to a VDB in the network. Each VDB assigned a shard of MAC addresses performs bridging when it receives a packet bearing a MAC address belonging to its assigned shard. A VDB does not perform bridging on packets that do not have MAC address that falls within the VDB's shard of MAC addresses.