Gemara

19b - Mishnah: They would occupy the Kohen Gadol (to keep him awake) until the time for Shechitah.

20b: On a normal day, Terumas ha'Deshen is done at Kros ha'Gever. On Yom Kipur, it is done at midnight, lest the Kohen Gadol get weak.

22a - Mishnah: ...This is the first lottery (for Terumas ha'Deshen).

25a - Mishnah: The second lottery determines who is Shochet, who does Zerikah, who is Medashen the inner Mizbe'ach, who is Medashen the Menorah, and who brings the limbs of the Tamid (partially) up the ramp:

26a - Mishnah: The third lottery determines who offers Ketores. The fourth determines who brings limbs from the ramp to the (top of the) Mizbe'ach.

32b - Beraisa: All Avodos of Yom Kipur are Kesherim only if the Kohen Gadol did them.

Rishonim

Tosfos Yeshanim (20b mi'Shum) and Ba'al ha'Ma'or (1a DH v'Havi): The Kohen Gadol must do all the Avodah on Yom Kipur. The lotteries were not conducted on Yom Kipur, contrary to the Piyutim for Musaf of Yom Kipur.

Rebuttal (Milchamos Hash-m): All Piyutim say that the four lotteries were conducted on Yom Kipur. These were written by Ge'onim, Chachamim of the Yeshivos, and R. Eliezer ha'Kalir. (Vayikra Rabah 30:1 says that the Tana R. Elazar b'Rebbi Shimon wrote Piyutim. Tosfos (Chagigah 13a DH v'Raglei) says that he is R. Eliezer ha'Kalir.) It is unreasonable to say that the Mishnayos of (the second Perek of) Yoma teach about the lotteries, even though there are no lotteries on Yom Kipur (if so, they should have been taught in Tamid! However, if there are lotteries on Yom Kipur, it is reasonable to teach in Yoma the normal procedure of the lotteries, even if some aspects do not apply on Yom Kipur.) Terumas ha'Deshen and Dishun of the Mizbe'ach and Menorah are not Avodos of the day, rather of the previous night, therefore Hedyotos may do them (and did do them, lest the Kohen Gadol get too weary).

Question: On Yom Kipur, Terumas ha'Deshen is done earlier, lest the Kohen Gadol get weak. If a Hedyot does it, what difference does it make to the Kohen Gadol?

Answer #1 (Tosfos 20b DH mi'Shum): Terumas ha'Deshen is done earlier to enable the Kohen to start his Avodah promptly, to give him time to rest between Avodos (or so he can begin before he gets weak from fasting).

Note: The Tamid was slaughtered about the same time on Yom Kipur as on other days (Yoma 29a, Tamid 30a), when Terumas ha'Deshen was done at Kros ha'Gever! Even though we want to be confident that the Kohen Gadol will be able to start promptly, it is not clear why Terumas ha'Deshen must be done so much earlier.

Answer #2 (Riva, in Tosfos, ibid.): The text says lest the Kohen (Hedyot) get weak (from the fast).

Rebuttal (continued): The first time the Kohen Gadol is mentioned in Avodas ha'Yom is after dawn, when he was Tovel and slaughtered the Tamid. This is after Terumas ha'Deshen and arranging the Ma'arachah! Also, if the Kohen Gadol did these, he would have to Tovel, put on the Bigdei Zahav and Mekadesh (wash his hands and feet) at midnight. But after dawn he was Tovel (Mishnah 28a), and then they brought the Bigdei Zahav (31b) before slaughtering the Tamid! All agree that that he is Tovel five times and is Mekadesh 10 times (32a). Tevilah and Kidush before Terumas ha'Deshen are not among them!

Defense (Tosfos Yeshanim, ibid. and Ritva 12b DH Hachi Garsinan): The Gemara does not count when he is Tovel and is Mekadesh at night. It counts only those for Avodas ha'Yom. The only Avodah Abaye found for a Hedyot on Yom Kipur was flipping limbs on the Mizbe'ach (12a)!

Question: It says that they would occupy the Kohen Gadol until the time for slaughter. This implies that he did not do Avodah beforehand!

Answer (Tosfos Yeshanim, ibid.): No. Rather, after the time for slaughter they did not need to occupy him, for he was busy with Avodah.

Rebuttal (continued): The Piyutim mention only Dishun of the Mizbe'ach and Menorah in the second lottery, for the other Avodos are of the day and require the Kohen Gadol.

Question: On 33a it says that placing two logs on the Ma'arachah precedes Dishun Mizbe'ach ha'Penimi. Regarding both it says "Ba'Boker ba'Boker"!

Answer: "Ba'Boker ba'Boker" is not written regarding Dishun. It is written regarding Haktarah, and Dishun must precede Haktarah. Really, Dishun could be done at night; since it is only a Machshir and does not take long. Chachamim left it for after Avodos. Surely a Hedyot may do it. It has no source in the Torah; it appears that it is mid'Rabanan. If the Kohen Gadol did Dishun, he would have to change his Begadim afterwards, for one should not mix a cup in the same garments used to cook!

Question: The third lottery is new Kohanim for the Ketores. The Kohen Gadol offered the Ketores!

Answer #1: Indeed, the Kohen Gadol offered the extra Ketores for Yom Kipur by himself, and he burned the normally daily Ketores. The lottery picked a Kohen to help for the daily Ketores, by taking coals from the Mizbe'ach in the Machtah.

Question: The fourth lottery is to bring limbs from the ramp onto the Mizbe'ach. This is Avodas ha'Yom, so the Kohen Gadol must do it!

Answer #1 (Milchamos Hash-m): If limbs of the Tamid of Erev Yom Kipur were left, a Hedyot would put them on the Ma'arachah. This is like R. Meir, who permits Haktarah of limbs of Chol on Yom Kipur. Alternatively, this is done when Erev Yom Kipur was Shabbos.

Mishneh l'Melech (Temidim u'Musafim 1:7, b'Sof, DH v'Da): The Ramban did not need to say that this is like R. Meir. Chachamim also permit Haktarah of limbs of Chol on Yom Kipur. They argue only about whether or not they were brought on a separate Ma'arachah. Perhaps only R. Meir considers burning leftover limbs important enough to have a lottery just for it (just like they are burned on a separate Ma'arachah), but Chachamim would say that there is no lottery for it.

Rebuttal (Tosfos Yom Tov 2:2 DH Arba): R. Yishmael permits Haktarah of limbs of Shabbos on Yom Kipur, but the Halachah follows R. Akiva, who forbids!

Answer #2 (Tosfos Yom Tov, ibid.): The fourth lottery is to hand limbs to the Kohen Gadol to throw onto the Mizbe'ach. This is done whenever the Kohen Gadol offers on the Mizbe'ach, to honor him (Tamid 7:3).

Rambam (Hilchos Avodas Yom Kipur 1:2): The Avodah of all 15 animals offered on Yom Kipur is Kosher only through the Kohen Gadol. Also the Ketores, Menorah and (if it is Shabbos) Musaf of Shabbos must be through the Kohen Gadol.

Tosfos (32b DH Im): "Chukah" requires the Kohen Gadol to do the Avodah. This applies only to the special Avodos of Yom Kipur. Mid'Rabanan, he also does the Tamid.

Question (Mayim Chayim, brought in Frankel Rambam, Likutim Avodas Yom Kipur 1:2): Perhaps a tradition from Sinai requires the Kohen Gadol to do Avodos not special to Yom Kipur!

Ritva (ibid., citing Ramban): If the Kohen Gadol is weak, Hedyotos may do normal daily Avodos. This is why the lotteries were taught in Yoma.

Rambam (ibid. 2:5): On other days the Kohen who merited Machtah scooped coals from the Mizbe'ach in a silver Machtah and poured them into a gold Machtah. On Yom Kipur, the Kohen Gadol scooped coals using a gold Machtah and entered the Heichal with it.

Rambam (ibid. 4:1): On Yom Kipur Terumas ha'Deshen, arranging the Ma'arachah and Dishun of the Mizbe'ach are done like usual, through lottery.

Tosfos Yom Tov (ibid.): The Rambam holds that there were lotteries only for Terumas ha'Deshen and Dishun of the inner Mizbe'ach.

Rosh (Hilchos Seder Avodas Yom Kipur, Sof DH Shiv'as): Riva allows Terumas ha'Deshen through a Hedyot, since it is not Avodas ha'Yom. R. Elchanan says that the Kohen Gadol must do it; he was Mekadesh his hands and feet beforehand.