Interconnect circuitry 2 has a plurality of data source circuits 8 connected to respective input paths 4 and a plurality of data destination circuits 10 connected to respective output paths 6. Connection cells 12 provide selective connections between input paths 4 and output paths 6. Arbitration circuitry 26 provides adaptive priority arbitration between overlapping requests received at different input paths. Priority bits 16 within a matrix of priority bit 46 for each output path 10 are used to represent the priority relationships between different input paths which compete for access to that output path 10. Update operations are applied on a per row or per column basis within the matrix to implement update schemes such as least recently granted, most recently granted, round robin, reversal, swap, selective least recently granted, selective most recently granted etc.