I'm no expert but from a quick glance at
https://www.pulumi.com/docs/concepts/state/#using-a-self-man... it looks like this might work:
client A lists s3://bucket/prefix/.pulumi/locks/, sees nothing
client B lists s3://bucket/prefix/.pulumi/locks/, sees nothing
client A creates s3://bucket/prefix/.pulumi/locks/unique1.json
client A lists s3://bucket/prefix/.pulumi/locks/, only sees unique1.json, and proceeds
client B creates s3://bucket/prefix/.pulumi/locks/unique2.json
client B lists s3://bucket/prefix/.pulumi/locks/ and sees both unique1.json and unique2.json
client B assumes it lost a race, deletes s3://bucket/prefix/.pulumi/locks/unique2.json, and retries
There's another mode where both clients pessimistically retry, but fuzzing a retry delay could eventually choose a winner randomly.