"A Planet Named Shayol" is a story by Cordwainer Smith (penname of Paul Linebarger) set in his Instrumentality universe. It was first published in Galaxy Science Fiction magazine in October 1961.
In the story, a man convicted of crimes against the Empire is sent for punishment on the planet Shayol — a name derived from Sheol, the Hebrew afterlife.
Mercer has been convicted of a crime that has no name. He is condemned to the planet Shayol, from where they broadcast the screams of the damned on the occasion of the Emperor's birthday. He is conducted to a satellite orbiting the planet, where he expects his punishment to start, but is treated like a patient in a hospital.
After medical procedures to prepare his body for survival on Shayol, he is sent down to the surface and received by B'dikkat, a bovine-derived underperson who is the caretaker of the prisoners there. Underpeople are human in appearance but derived from animals, and are treated as property. Depending on their ancestry, they may be bigger or smaller than a true human. B'dikkat is much larger. He checks Mercer to see that he is ready and sends him outside the reception building. B'dikkat himself never leaves without a huge, heavy protective suit.
Soon after stepping outside, Mercer is stung by what appears to be a flash of light. Then he collapses in excruciating pain. This seems to last forever, but when he recovers, he finds himself face to face with his fellow prisoners. There are people with extra limbs, noses, eyes, organs, and in one case a string of human torsos attached to them.
Shayol, it is revealed, is inhabited by tiny symbiotic creatures called dromozoans that try to help people. They put food in their stomachs, remove waste from their kidneys, and cause new parts to grow, even if they are not needed. The attentions of the dromozoa are what cause the pain suffered by the inmates. On the satellite, Mercer had been offered the chance to have his mind, his eyes, or both destroyed. He elected not to have anything done. He is not alone in this, but there are many mindless bodies which spend their entire time buried in the sand.
The prisoners are given super-condamine (the "ultimate drug") by B'dikkat to alleviate the immense pain of their punishment. He gives doses whenever he comes out to harvest the body parts they are growing. These parts are then used in medicine across the Empire.
The first man to set foot on Shayol, Go-Captain Alvarez, has been on Shayol so long that the dromozoa have greatly increased his size — all that is seen of him is an enormous foot, six stories high. Mercer develops a relationship with another prisoner, the Lady Da, who was sent there as part of a royal power struggle. He also briefly meets Commander Suzdal, sentenced to Shayol after the events of "The Crime and the Glory of Commander Suzdal".
Decades pass, but nothing changes, so that the inmates lose all sense of time. One day, B'dikkat drags Mercer and Lady Da into the building. They find that children have been sent to Shayol, and their brains have been removed. B'dikkat is horrified and refuses to send them outside. Lady Da knows how to contact the Lords of the Instrumentality, and soon these guardians of humanity arrive on Shayol. They are shocked by what they find. The children are the heirs to the throne — apparently the Imperium has become so bureaucratic and corrupt that it condemned them to prevent them committing treason when they grew up.
The Instrumentality decides to void the agreement by which it allowed the Empire to exist and maintain Shayol. All the prisoners with functioning minds refuse to live without super-condamine, but eventually they agree to be sent to another planet, where there are no dromozoa, and the drug will be replaced by an electronic "cap" that causes a similar effect. The mindless ones are decapitated, leaving their bodies to be handled by the dromozoa while their heads are destroyed. Lady Da claims Mercer as her consort.