Arbitration circuitry for arbitrating between a plurality W of requests R for access to a shared resource. Included are state bits storage storing I state bits Q and generating 2I output bits comprising the true and compliment values of each stored state bit and routing circuitry for generating a set of mask signals M from the output bits. Grant circuitry receives the set of mask signals and the plurality of requests, and grants access to the shared resource to an asserted request having regard to the priority ordering encoded by the set of mask signals. State bit update circuitry is responsive to a trigger condition to perform an update causing a change in the priority ordering encoded by the set of mask signals. The routing circuitry provides a pattern of connections such that each mask signal in the set is directly connected to one of said output bits.