Document:

<PAGE>
                                                                   Exhibit 4.31

                  AMENDED AND RESTATED STOCKHOLDERS' AGREEMENT

               This Amended and Restated Stockholders' Agreement (this
"Agreement") is entered into as of August 10, 2000, by and among McLeodUSA
Incorporated, a Delaware corporation (the "Company"), Kwok Li, a resident of
Texas ("Li"), and Linsang Partners, LLC, a Delaware limited liability company
("Linsang" and together with Li, the "Stockholders").

               WHEREAS, in accordance with the terms and conditions of the
Amended and Restated Agreement and Plan of Merger, dated as of February 11, 2000
(the "Merger Agreement"), among the Company, Southside Acquisition Corporation,
a Delaware corporation and wholly owned subsidiary of the Company ("Southside"),
Splitrock Services, Inc., a Delaware corporation ("Splitrock"), Splitrock
Holdings, Inc., a Delaware corporation and wholly owned subsidiary of Splitrock
("Holdco"), and Splitrock Merger Sub, Inc., a Delaware corporation and wholly
owned subsidiary of Holdco, Southside merged with and into Holdco (the "Merger")
effective on March 30, 2000;

               WHEREAS, Li is Chairman and Manager of Linsang and owns a
majority of the membership interest in Linsang;

               WHEREAS, in accordance with the terms and conditions of the
Merger Agreement and as a condition to the obligation of each of the Company and
Southside to close the transactions contemplated thereby, the Stockholders
entered into a Stockholders' Agreement, dated as of March 30, 2000 (the
"Stockholders' Agreement"), with the Company;

               WHEREAS, the Company effected a three-for-one stock split of its
Class A Common Stock (as defined below) in the form of a stock dividend paid on
April 24, 2000 to stockholders of record on April 4, 2000, and all share amounts
referred to in this Agreement have been adjusted to reflect such stock split;
and

               WHEREAS, the Company and the Stockholders desire to amend and
restate the Stockholders' Agreement in its entirety with the terms and
conditions hereinafter set forth;

               NOW, THEREFORE, for and in consideration of the foregoing and of
the mutual covenants and agreements contained herein, the parties hereto hereby
agree to amend and restate the Stockholders' Agreement as follows:

1.      DEFINITIONS

               For purposes of this Agreement, the following terms have the
meanings indicated:

<PAGE>
               (a)    "Affiliate" and "Associate" shall have the respective
                      meanings ascribed to such terms in Rule 12b-2 under the
                      Securities Exchange Act of 1934, as amended (the "Exchange
                      Act").

               (b)    A person shall be deemed the "beneficial owner" of and
                      shall be deemed to "beneficially own" any securities:

                      (i)    which such person or any of such person's
                             Affiliates or Associates, directly or indirectly,
                             has the right to acquire (whether such right is
                             exercisable immediately or only after the passage
                             of time) pursuant to any agreement, arrangement or
                             understanding (whether or not in writing), or upon
                             the exercise of conversion rights, exchange rights,
                             other rights, warrants or options, or otherwise;

                      (ii)   which such person or any of such person's
                             Affiliates or Associates, directly or indirectly,
                             has the right to vote or dispose of or has
                             "beneficial ownership" of (as determined pursuant
                             to Rule 13d-3 under the Exchange Act), including
                             pursuant to any agreement, arrangement or
                             understanding, whether or not in writing; or

                      (iii)  which are beneficially owned, directly or
                             indirectly, by any other person (or any Affiliate
                             or Associate thereof) with which such person or any
                             of such person's Affiliates or Associates has any
                             agreement, arrangement or understanding (whether or
                             not in writing), for the purpose of acquiring,
                             holding, voting or disposing of any voting
                             securities of the Company.

               (c)    "Class A Common Stock" shall mean the Class A common
                      stock, par value $.01 per share, of the Company.

               (d)    "Covered Securities" shall mean (i) 7,315,647 shares of
                      Class A Common Stock owned beneficially and of record by
                      Li as a result of the Merger (excluding any shares
                      described in clause (ii) below), (ii) 22,829,639 shares
                      of Class A Common Stock owned beneficially and of record
                      by Linsang as a result of the Merger (including 100,583
                      shares of Class A Common Stock owned beneficially and of
                      record by Linsang as a result of the exercise of certain
                      warrants by Linsang on June 20, 2000), and (iii)
                      Securities issued or issuable with respect to the
                      Securities referred to in clauses (i) and (ii) above by
                      way of a stock dividend or stock split or in connection
                      with a combination of shares, recapitalization, merger,
                      consolidation or other reorganization.

                                       2
<PAGE>
               (e)    "Expiration Date" shall mean December 31, 2002.

               (f)    "Securities" shall mean any equity securities of the
                      Company or any other securities convertible into or
                      exercisable for such equity securities.

2.      TRANSFERS OF COVERED SECURITIES

        2.1    RESTRICTIONS ON TRANSFERS

               Except as otherwise provided in this Section 2, the Stockholders
hereby agree that until the Expiration Date, the Stockholders will not offer,
sell, contract to sell, grant any option to purchase, or otherwise dispose of,
directly or indirectly, ("Transfer"), any Covered Securities without submitting
a written request to, and receiving the prior written consent of, the Board of
Directors of the Company.

        2.2    INITIAL TRANSFER PERIOD

               For the period commencing as of the date of this Agreement and
ending December 31, 2000 (such period, the "Initial Transfer Period"), the
Stockholders may Transfer at any time and from time to time during such Initial
Transfer Period up to an aggregate number of shares of Class A Common Stock
which are Covered Securities equal to the Initial Transfer Amount, provided any
such Transfer is effected in accordance with all applicable laws (including
without limitation applicable federal and state securities laws). For purposes
of this Section 2.2, the Initial Transfer Amount shall be equal to the aggregate
number of shares of Class A Common Stock which are Covered Securities, which may
be Transferred from time to time during the Initial Transfer Period by the
Stockholders directly or through their Affiliates and Associates and which
result in aggregate gross proceeds of $105 million. The Stockholders shall
deliver to the Company a written report not later than September 11, 2000 for
the period commencing August 10, 2000 and ending August 31, 2000, and a written
report not later than October 10, 2000, November 10, 2000, December 11, 2000 and
January 10, 2001 for each of the months of September, October, November and
December 2000. Each such written report shall set forth the date and number of
shares of Class A Common Stock Transferred and the gross proceeds resulting
therefrom during each such month or portion thereof, as the case may be. In no
event shall any portion of the Initial Transfer Amount that is not utilized by
the Stockholders during the Initial Transfer Period be carried forward or
otherwise Transferred at any time during the period commencing January 1, 2001
and ending December 31, 2002. The allocation between Li and Linsang of the
Initial Transfer Amount shall be determined by Li as the Representative pursuant
to Section 4.9.

                                       3
<PAGE>
        2.3    SUBSEQUENT TRANSFER PERIODS

               (a) Subject to Section 2.3(b), during each of the calendar years
ending December 31, 2001 and December 31, 2002 (each such year, a "Subsequent
Transfer Period" and together, the "Subsequent Transfer Periods"), the
Stockholders may Transfer at any time and from time to time during each such
Subsequent Transfer Period up to an aggregate number of shares of Class A Common
Stock which are Covered Securities equal to the Subsequent Transfer Amount,
provided any such Transfer is effected in accordance with all applicable laws
(including without limitation applicable federal and state securities laws). For
purposes of this Section 2.3, the Subsequent Transfer Amount shall be equal to
4,183,440 shares of Class A Common Stock, subject to adjustment pursuant to
Section 4.1. The Stockholders shall deliver to the Company a written report not
later than the tenth day of the first month following each calendar quarter
during the Subsequent Transfer Periods commencing with a report due on or before
April 10, 2001 for the quarter ending March 31, 2001 and ending with a report
due on or before January 10, 2003 for the quarter ending December 31, 2002. Each
such written report shall set forth the date and number of shares of Class A
Common Stock Transferred by the Stockholders during each such quarter. In no
event shall any portion of the Subsequent Transfer Amount that is not utilized
by the Stockholders during the Subsequent Transfer Period commencing January 1,
2001 and ending December 31, 2001 be carried forward or otherwise Transferred at
any time during the Subsequent Transfer Period commencing January 1, 2002 and
ending December 31, 2002. The allocation between Li and Linsang of the
Subsequent Transfer Amount shall be determined by Li as the Representative
pursuant to Section 4.9.

               (b) Notwithstanding Section 2.3(a), the Stockholders shall not
Transfer any Covered Securities during any thirty (30) day period immediately
following written notice from the Company requesting the Stockholders not to
Transfer any Covered Securities during such thirty (30) day period if (i) the
Stockholders Transfer more than 200,000 shares of Class A Common Stock, subject
to adjustment pursuant to Section 4.1, on any single day during the Subsequent
Transfer Periods, and (ii) the Company determines that any such Transfer has
adversely affected the trading price of the Company's Securities on The Nasdaq
Stock Market's National Market System (or any comparable system).

        2.4    LI PLEDGE

               At any time following the date hereof, Li may pledge to a
nationally recognized financial institution (the "Pledgee") up to the aggregate
number of Covered Securities required by such Pledgee in order to secure
financing for the purchase of a Gulfstream IV or other similarly priced
aircraft; PROVIDED, HOWEVER, (i) such pledge complies with all applicable laws
(including without limitation applicable federal and state securities laws) and
(ii) the Pledgee takes such shares

                                       4
<PAGE>

subject to the restrictions on Transfer of this Agreement and agrees to be
bound by the terms hereof (as this Agreement may be amended or amended and
restated from time to time) and to become a party hereto with respect to the
Covered Securities being pledged pursuant to this Section 2.4.

3.  REPRESENTATIONS AND WARRANTIES

        3.1    REPRESENTATIONS AND WARRANTIES OF LINSANG

               Linsang hereby represents and warrants, as of the date of this
Agreement, to the Company as follows:

               3.1.1  AUTHORIZATION

               Linsang has taken all action necessary for it to enter into this
Agreement and to consummate the transactions contemplated hereby.

               3.1.2  BINDING OBLIGATION

               This Agreement constitutes a valid and binding obligation of
Linsang, enforceable in accordance with its terms, except to the extent that
such enforceability may be limited by bankruptcy, insolvency, and similar laws
affecting the rights and remedies of creditors generally, and by general
principles of equity and public policy; and each document and instrument to be
executed by Linsang pursuant hereto, when executed and delivered in accordance
with the provisions hereof, shall be a valid and binding obligation of Linsang,
enforceable in accordance with its terms (with the aforesaid exceptions).

        3.2    REPRESENTATIONS AND WARRANTIES OF LI

               Li hereby represents and warrants, as of the date of this
Agreement, to the Company as follows:

               3.2.1  POWER AND AUTHORITY

               Li has the legal capacity and all other power and authority
necessary to enter into this Agreement and to consummate the transactions
contemplated hereby.

               3.2.2  BINDING OBLIGATION

               This Agreement constitutes a valid and binding obligation of
Li, enforceable in accordance with its terms, except to the extent that such
enforceability may be limited by bankruptcy, insolvency, and similar laws
affecting the rights and remedies of creditors generally, and by general
principles of equity and public policy; and each document and instrument to
be executed by Li pursuant

                                       5
<PAGE>

hereto, when executed and delivered in accordance with the provisions hereof,
shall be a valid and binding obligation of Li, enforceable in accordance with
its terms (with the aforesaid exceptions).

        3.3    REPRESENTATIONS AND WARRANTIES OF THE COMPANY

               The Company hereby represents and warrants, as of the date of
this Agreement, to each of Li and Linsang as follows:

               3.3.1  AUTHORIZATION

               The Company has taken all corporate action necessary for it to
enter into this Agreement and to consummate the transactions contemplated
hereby.

               3.3.2  BINDING OBLIGATION

               This Agreement constitutes a valid and binding obligation of the
Company, enforceable in accordance with its terms, except to the extent that
such enforceability may be limited by bankruptcy, insolvency, and similar laws
affecting the rights and remedies of creditors generally, and by general
principles of equity and public policy; and each document and instrument to be
executed by the Company pursuant hereto, when executed and delivered in
accordance with the provisions hereof, shall be a valid and binding obligation
of the Company, enforceable in accordance with its terms (with the aforesaid
exceptions).

4.  MISCELLANEOUS

        4.1    EFFECT OF CHANGES IN CAPITALIZATION

               Each of the references to a number of shares of the Company's
capital stock referred to in this Agreement shall be appropriately and
proportionally adjusted for any recapitalization, reclassification, stock
split-up, combination of shares, exchange of shares, stock dividend or other
distribution payable in capital stock, or other increase or decrease in such
shares effected without receipt of consideration by the Company, occurring after
the date of this Agreement.

        4.2    ADDITIONAL ACTIONS AND DOCUMENTS

               Each of the parties hereto hereby agrees to take or cause to be
taken such further actions, to execute, deliver and file or cause to be
executed, delivered and filed such further documents and instruments, and to
obtain such consents, as may be necessary or as may be reasonably requested in
order to fully effectuate the purposes, terms and conditions of this Agreement.

                                       6
<PAGE>
        4.3    ENTIRE AGREEMENT; AMENDMENT

               This Agreement, together with the amended and restated letter
agreement by and among the parties hereto dated as of the date hereof,
constitute the entire agreement among the parties hereto with respect to the
specific matters contemplated herein and therein and supersede all prior oral or
written agreements, commitments or understandings with respect to the matters
provided herein and therein. No amendment, modification or discharge of this
Agreement shall be valid or binding unless set forth in writing and duly
executed by the Company and the Stockholders.

        4.4    LIMITATION ON BENEFIT

               It is the explicit intention of the parties hereto that no person
or entity other than the parties hereto is or shall be entitled to bring any
action to enforce any provision of this Agreement against any of the parties
hereto, and the covenants, undertakings and agreements set forth in this
Agreement shall be solely for the benefit of, and shall be enforceable only by,
the parties hereto or their respective successors, heirs, executors,
administrators, legal representatives and permitted assigns.

        4.5    BINDING EFFECT; SPECIFIC PERFORMANCE

               This Agreement shall be binding upon and shall inure to the
benefit of the parties hereto and their respective successors, heirs, executors,
administrators, legal representatives and permitted assigns. No party shall
assign this Agreement without the written consent of the other parties hereto;
and such consent shall not be unreasonably withheld. The parties hereto agree
that irreparable damage would occur in the event any provision of this Agreement
was not performed in accordance with the terms hereof and that the parties shall
be entitled to specific performance of the terms hereof, in addition to any
other remedy at law or in equity.

        4.6    GOVERNING LAW

               This Agreement, the rights and obligations of the parties hereto,
and any claims or disputes relating thereto, shall be governed by and construed
in accordance with the laws of Delaware (excluding the choice of law rules
thereof).

        4.7    NOTICES

               All notices, demands, requests, or other communications which may
be or are required to be given, served, or sent by any party to any other party
pursuant to this Agreement shall be in writing and shall be hand-delivered or
mailed by first-class, registered or certified mail, return receipt requested,
postage prepaid, or transmitted by telegram, telecopy, facsimile transmission or
telex, addressed as follows:

                                       7
<PAGE>
               (i)    If to the Company:

                      McLeodUSA Incorporated
                      McLeodUSA Technology Park
                      6400 C Street SW, P.O. Box 3177
                      Cedar Rapids, IA  52406-3177
                      Attention:  Randall Rings, Esq.
                      Facsimile:  (319) 790-7901

               (ii) If to either of the Stockholders:

                      Linsang Partners, LLC
                      8401 Colesville Road, Suite 500
                      Silver Spring, MD  20910
                      Attention:  Kwok Li
                      Facsimile:  (301) 563-8414

                      with a copy to:

                      Shea & Gardner
                      1800 Massachusetts Avenue, N.W.
                      Washington, D.C.  20036
                      Attention:  Martin J. Flynn, Esq.
                      Facsimile:  (202) 828-2195

                      and

                      Fried, Frank, Harris, Shriver & Jacobson
                      1001 Pennsylvania Avenue, N.W.
                      Washington, D.C.  20004
                      Attention:  Richard A. Steinwurtzel, Esq.
                      Facsimile:  (202) 639-7003

               Each party may designate by notice in writing a new address to
which any notice, demand, request or communication may thereafter be so given,
served or sent. Each notice, demand, request or communication which shall be
hand-delivered, mailed, transmitted, telecopied or telexed in the manner
described above, or which shall be delivered to a telegraph company, shall be
deemed sufficiently given, served, sent, received or delivered for all purposes
at such time as it is delivered to the addressee (with the return receipt, the
delivery receipt, or the answerback being deemed conclusive, but not exclusive,
evidence of such delivery) or at such time as delivery is refused by the
addressee upon presentation.

                                       8
<PAGE>
        4.8    TERMINATION

               This Agreement shall terminate on the Expiration Date, such that
all rights and obligations hereunder shall cease, and this Agreement shall be of
no further force or effect.

        4.9    APPOINTMENT OF REPRESENTATIVE

               Linsang hereby appoints Li, with power of substitution, as its
exclusive agent to act on its behalf with respect to any and all actions to be
taken under or amendments or modifications to be made to this Agreement (the
"Representative"). The Representative shall take, and Linsang agrees that the
Representative shall take, any and all actions which the Representative believes
are necessary or advisable under this Agreement for and on behalf of Linsang, as
fully as if Linsang was acting on its own behalf, including, without limitation,
dealing with the Company with respect to all matters arising under this
Agreement, entering into any amendment or modification to this Agreement deemed
advisable by the Representative and taking any and all other actions specified
in or contemplated by this Agreement. The Company shall have the right to rely
upon all actions taken or not taken by the Representative pursuant to this
Agreement, all of which actions or omissions shall be legally binding upon
Linsang.

        4.10   PUBLICITY

               The Stockholders will use their reasonable best efforts to
consult with the Company prior to issuing any press release, making any filing
with any governmental entity or national securities exchange or making any other
public dissemination of information by the Stockholders within which this
Agreement or the contents hereof are referenced or described.

        4.11   EXECUTION IN COUNTERPARTS

               To facilitate execution, this Agreement may be executed in as
many counterparts as may be required; and it shall not be necessary that the
signatures of, or on behalf of, each party, or that the signatures of all
persons required to bind any party, appear on each counterpart; but it shall be
sufficient that the signature of, or on behalf of, each party, or that the
signatures of the persons required to bind any party, appear on one or more of
the counterparts. All counterparts shall collectively constitute a single
agreement. It shall not be necessary in making proof of this Agreement to
produce or account for more than a number of counterparts containing the
respective signatures of, or on behalf of, all of the parties hereto.

                        *      *       *      *      *

                                       9
<PAGE>

               IN WITNESS WHEREOF, the undersigned have duly executed and
delivered this Amended and Restated Stockholders' Agreement, or have caused this
Amended and Restated Stockholders' Agreement to be duly executed and delivered
on their behalf, as of the day and year first hereinabove set forth.

                                       McLEODUSA INCORPORATED

                                       By: /s/ Randall Rings
                                           -------------------------------------
                                           Name:  Randall Rings
                                           Title:  Vice President and Secretary

                                       STOCKHOLDERS

                                       LINSANG PARTNERS, LLC

                                       By: /s/ Kwok Li
                                           -------------------------------------
                                           Name:    Kwok Li
                                           Title:   Chairman and Manager

                                           /s/ Kwok Li
                                           -------------------------------------
                                           Kwok Li

                                       10<PAGE>

                                                                       Exh. 4.41

                          CAPROCK COMMUNICATIONS CORP.,

                                    AS ISSUER

                                       AND

              CHASE MANHATTAN TRUST COMPANY, NATIONAL ASSOCIATION,

                              AS SUCCESSOR TRUSTEE

--------------------------------------------------------------------------------

                          FIRST SUPPLEMENTAL INDENTURE

                        DATED AS OF ___________ __, 2000

                                  TO INDENTURE

                           DATED AS OF JULY 16, 1998,

--------------------------------------------------------------------------------

                                  $150,000,000

                            12% SENIOR NOTES DUE 2008

<PAGE>

        FIRST SUPPLEMENTAL INDENTURE, dated as of _________ __, 2000, by and
between CAPROCK COMMUNICATIONS CORP., a Texas corporation, (the "Issuer"),
and CHASE MANHATTAN TRUST COMPANY, NATIONAL ASSOCIATION, as successor
Trustee, (the "Trustee").

                                   WITNESSETH

        WHEREAS the Issuer has heretofore executed and delivered to the
Trustee an Indenture dated as of July 16, 1998, (the "Indenture"), providing
for the issuance of an aggregate principal amount of up to $150,000,000 of
12% Senior Notes due 2008 (the "Notes");

        WHEREAS, the Issuer has commenced a solicitation of consents (the
"Consent Solicitation") from the Holders to certain amendments to the
Indenture as set forth in the Consent Solicitation Statement of the Issuer
dated October 11, 2000, (the "Proposed Amendment");

        WHEREAS, pursuant to the Consent Solicitation, the Holders of at
least a majority in aggregate principal amount of the Notes outstanding have
consented (the "Requisite Consents") to the amendments effected by this First
Supplemental Indenture in accordance with the provisions of the Indenture;

        WHEREAS, this First Supplemental Indenture evidences the Proposed
Amendments described in the Consent Solicitation Statement;

        WHEREAS, Section 9.02 of the Indenture provides, among other things,
that with the written consent of Holders holding not less than a majority of
the aggregate principal amount of the Notes then outstanding, the Issuer may
from time to time amend or supplement the Indenture, subject to certain
exceptions specified in Section 9.02 of the Indenture;

        WHEREAS, on October 11, 2000, the Issuer mailed or otherwise
delivered a Consent Solicitation Statement to each Holder of record as of
October 6, 2000, and has obtained the Requisite Consents;

        WHEREAS, this First Supplemental Indenture has been duly authorized
by all necessary corporate action on the part of the Issuer; and

        WHEREAS, the Issuer has delivered, or caused to be delivered, to the
Trustee an Officers' Certificate and an Opinion of Counsel meeting the
requirements of Sections 1.04 and 10.09 of the Indenture and stating that all
conditions precedent (including any covenants compliance with which
constitutes a condition precedent), if any, provided for in the Indenture
relating to this First Supplemental Indenture have been satisfied.

                                       1
<PAGE>

        NOW THEREFORE, in consideration of the foregoing and for other good
and valuable consideration, receipt of which is hereby acknowledged, the
Issuer, and the Trustee mutually covenant and agree for the equal and ratable
benefit of the holders of the Notes as follows:

                                    ARTICLE I

                                   DEFINITIONS

        SECTION 1.01. DEFINITIONS. When used herein, the following terms will
have the respective meanings set forth below.

        "Covenant Amendments" means the amendments to the Indenture listed in
Article III of this First Supplemental Indenture.

        "McLeodUSA" means McLeodUSA Incorporated, a Delaware corporation.

        "McLeodUSA Merger" means any merger of the Issuer with McLeodUSA or
any wholly-owned subsidiary of McLeodUSA pursuant to, or any other
transaction contemplated by, that certain Agreement and Plan of Merger dated
as of October 2, 2000 by and among McLeodUSA, Cactus Acquisition Corp., a
Delaware corporation, and the Issuer, or any amendment thereto and any
related agreements.

        "Merger Amendments" means the amendments to the Indenture listed in
Article II of this First Supplemental Indenture.

                                   ARTICLE II

                                MERGER AMENDMENTS

        SECTION 2.01. EFFECTIVE TIME OF MERGER AMENDMENTS. The Merger
Amendments shall become effective upon execution of this First Supplemental
Indenture by the Trustee and the Issuer.

                                       2
<PAGE>

        SECTION 2.02. AMENDMENT AND RESTATEMENT OF THE DEFINITION OF "CHANGE
OF CONTROL". The definition of "Change of Control" in Section 1.01 of the
Indenture is hereby amended and restated in its entirety to read as set forth
below:

              " "Change of Control" shall be deemed to occur if, after the
Transaction occurs:

               (i) the sale, conveyance, transfer or lease of all or
        substantially all of the assets of the Issuer to any Person or "group"
        (as such term is used in Sections 13(d)(3) and 14(d)(2) of the Exchange
        Act, including any group acting for the purpose of acquiring, holding or
        disposing of securities within the meaning of Rule 13d-5(b)(1) under the
        Exchange Act), other than to one or more Permitted Holders and/or one or
        more Restricted Subsidiaries, shall have occurred,

               (ii) any Person or "group" (as such term is used in Sections
        13(d)(3) and 14(d)(2) of the Exchange Act including any group acting for
        the purpose of acquiring, holding or disposing of securities within the
        meaning of Rule 13d-5(b)(1) under the Exchange Act), other than any
        Permitted Holder (or group that includes a Permitted Holder), becomes
        the "beneficial owner" (as defined in Rule 13d-3 under the Exchange Act)
        of more than 50% of the total voting power of all classes of the Voting
        Stock of the Issuer (including any warrants, options or rights to
        acquire such Voting Stock), calculated on a fully diluted basis,

               (iii) during any period of two consecutive years, individuals
        (OTHER THAN THOSE APPOINTED BY MCLEODUSA) who at the beginning of such
        period constituted the Board of Directors of the Issuer (together with
        any directors whose election or appointment by the Board of Directors of
        the Issuer or whose nomination for election by the stockholders of the
        Issuer was approved by a vote of a majority of the directors then still
        in office who were either directors at the beginning of such period or
        whose election or nomination for election was previously so approved)
        cease for any reason to constitute a majority of the Board of Directors
        of the Issuer then in office or

               (iv) EXCEPT FOR THE MCLEODUSA MERGER, the merger, amalgamation or
        consolidation of the Issuer with or into another Person or the merger of
        another Person with or into the Issuer shall have occurred, and the
        securities of the Issuer that are outstanding immediately prior to such
        transaction and which represent 100% of the aggregate voting power of
        the Voting Stock of the Issuer are changed into or exchanged for cash,
        securities or property, unless pursuant to such transaction such
        securities are changed into or exchanged for, in addition to any other
        consideration, securities of the surviving Person that represent,
        immediately after giving effect to such transaction, at least a majority
        of the aggregate voting power of the Voting Stock of the surviving
        Person."

        SECTION 2.03. AMENDMENT AND RESTATEMENT OF THE DEFINITION OF
"PERMITTED HOLDERS". The definition of "Permitted Holders" in Section 1.01 of
the Indenture is hereby amended and restated in its entirety to read as set
forth below:

                                       3
<PAGE>

                " "Permitted Holders" means MCLEODUSA, Jere W. Thompson, Sr.,
        Jere W. Thompson, Jr., Mark Langdale, Timothy W. Rogers, Scott L.
        Roberts, Timothy M. Terrell and Ignatius W. Leonards and any
        corporation, limited liability company, partnership, joint venture or
        other entity controlled by any one or more of them."

        SECTION 2.04. AMENDMENT AND RESTATEMENT OF SECTION 8.01. Section 8.01
of the Indenture is hereby amended and restated in its entirety to read as
set forth below:

                "Section 8.01.ISSUER MAY CONSOLIDATE, ETC., ONLY ON CERTAIN
        TERMS.

                The Issuer will not consolidate with, or merge with or into or
        sell, convey, transfer, lease or otherwise dispose of all or
        substantially all of its property and assets (as an entirety or
        substantially an entirety in one transaction or a series of related
        transactions) to any Person or permit any Person to merge with or into
        the Issuer, other than in connection with THE MCLEODUSA MERGER, the
        Transaction or the Special Partnership Transactions (WHICH EVENTS ARE
        HEREBY EXPRESSLY PERMITTED), unless:

                (a) the Issuer shall be the continuing Person, or the Person (if
        other than the Issuer) formed by such consolidation or into which the
        Issuer is merged or that acquired or leased such property and assets of
        the Issuer shall be a corporation organized and validly existing under
        the laws of the United States of America or any jurisdiction thereof,
        and shall expressly assume, by a supplemental indenture, executed and
        delivered to the Trustee, all of the obligations of the Issuer on all of
        the Notes and under the Indenture;

                (b) immediately after giving effect to such transaction, no
        Default or Event of Default shall have occurred and be continuing;

                (c) immediately after giving effect to such transaction on a PRO
        FORMA basis, the Issuer, or any Person becoming the successor obligor of
        the Notes, as the case may be, could Incur at least $1.00 of
        Indebtedness under clause (i) of Section 10.11(a) hereof; PROVIDED,
        HOWEVER, that this clause (c) shall not apply to a consolidation or
        merger with or into a Wholly Owned Restricted Subsidiary with a positive
        net worth, PROVIDED that in connection with any such merger or
        consolidation, no consideration (except Capital Stock (other than
        Redeemable Stock) in the surviving Person or the Issuer (or a Person
        that owns directly or indirectly all of the Capital Stock of the
        surviving Person or the Issuer immediately following such transaction)
        or cash paid to satisfy dissenter or appraisal rights; PROVIDED that
        such rights are exercised with respect to no more than 5% of the
        outstanding Capital Stock of the Issuer or other Person) shall be issued
        or distributed to the stockholders of the Issuer; and

                (d) the Issuer delivers to the Trustee an Officers' Certificate
        (attaching the arithmetic computations to demonstrate compliance with
        clause (c) above) and an Opinion of Counsel, in each case stating that
        such consolidation, merger or transfer and such supplemental indenture
        comply with this provision and that all conditions precedent provided
        for herein relating to such transaction have been complied with;
        PROVIDED, HOWEVER, that clauses (b) and (c) above do not apply if, in
        the good faith determination of the Board of Directors of the Issuer,
        whose determination shall be evidenced by a Board

                                       4
<PAGE>

        Resolution, the principal purpose of such transaction is to change the
        state of incorporation of the Issuer; and PROVIDED FURTHER that any such
        transaction shall not have as one of its purposes the evasion of the
        foregoing limitations."

                                   ARTICLE III

                               COVENANT AMENDMENTS

        SECTION 3.01. DELETION AND ADDITION OF CERTAIN DEFINITIONS. Upon the
occurrence of (i) the execution of this First Supplemental Indenture by the
Trustee and the Issuer and (ii) the later of (a) the effective time of the
McLeodUSA Merger and (b) twenty (20) business days following commencement by
McLeodUSA of an exchange offer to acquire all of the outstanding Notes in
exchange for notes of McLeodUSA having the same interest rate, payment,
maturity and redemption terms as the Notes but otherwise having terms
substantially similar to the 8 1/8% Senior Notes due 2009 of McLeodUSA
("Covenant Amendment Effective Time"), Sections 1.01 and 1.02 of the
Indenture shall be amended by deleting the definition of each term that is
used in the Indenture only in the Articles, Sections or Subsections thereof
that are deleted pursuant to Section 3.02 hereof, and by adding the following
to Section 1.01:

                " "Covenant Amendment Effective Time" shall have the meaning set
        forth in Section 3.01 of the First Supplemental Indenture."

        SECTION 3.02. DELETION OF CERTAIN SECTIONS. Upon the occurrence of
the Covenant Amendment Effective Time, the text of each of the following
Articles, Sections or Subsections of the Indenture shall be deleted in its
entirety and replaced, in each case, by the words "Intentionally Omitted":

<TABLE>
        <S>                  <C>
        Section 7.04.        Reports by Issuer

        Article 8            Consolidation, Merger, Sale of Assets, etc.

        Section 10.04.       Corporate Existence

        Section 10.05.       Payment of Taxes and Other Claims

        Section 10.06.       Maintenance of Properties

        Section 10.07.       Insurance

        Section 10.10.       Repurchase of Notes Upon a Change of Control

        Section 10.11.       Limitation on Indebtedness

        Section 10.13.       Limitation on Restricted Payments

        Section 10.14.       Limitation on Transactions with Stockholders and
                             Affiliates

                                       5
<PAGE>

        Section 10.15.       Limitation on Asset Sales

        Section 10.16.       Limitation on Liens

        Section 10.18.       Limitation on the Issuance and Sale of Capital
                             Stock of Restricted Subsidiaries

        Section 10.19.       Limitation on Dividend and Other Payment
                             Restrictions Affecting Restricted Subsidiaries

        Section 10.20.       Limitation on Sale-Leaseback Transactions

        Section 10.22.       Commission Reports and Reports to Holders

        Section 10.23.       Limitation on Issuances of Guarantees by
                             Restricted Subsidiaries
</TABLE>

        SECTION 3.03. Amendment of Section 5.01(c). Section 5.01(c) is hereby
amended and restated in its entirety to read as set forth below:

                "(c) the failure to make or consummate an Offer to Purchase in
        accordance with Section 10.21."

                                   ARTICLE IV

                                  MISCELLANEOUS

        SECTION 4.01. RATIFICATION OF INDENTURE; SUPPLEMENTAL INDENTURES PART
OF INDENTURE. Except as expressly amended hereby, the Indenture is in all
respects ratified and confirmed and all the terms, conditions and provisions
thereof shall remain in full force and effect. Upon the execution and
delivery of this First Supplemental Indenture by the Issuer and the Trustee,
this First Supplemental Indenture shall form a part of the Indenture for all
purposes, and every holder of Notes heretofore or hereafter authenticated and
delivered shall be bound hereby. Any and all references, whether within the
Indenture or in any notice, certificate or other instrument or document,
shall be deemed to include a reference to this First Supplemental Indenture
(whether or not made), unless the context shall otherwise require.

        SECTION 4.02. GOVERNING LAW; GOVERNANCE, ETC. THIS FIRST SUPPLEMENTAL
INDENTURE SHALL BE GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH, THE LAWS OF
THE STATE OF NEW YORK BUT WITHOUT GIVING EFFECT TO APPLICABLE PRINCIPLES OF
CONFLICTS OF LAW TO THE EXTENT THAT THE APPLICATION OF THE LAWS OF ANOTHER
JURISDICTION WOULD BE REQUIRED THEREBY. This First Supplemental Indenture
shall be governed and construed in accordance with the applicable terms and
provisions of the Indenture as amended hereby, which terms and provisions are
incorporated herein by reference, as if this First Supplemental Indenture
were the "Indenture" referred to therein.

                                       6
<PAGE>

        SECTION 4.03. TRUSTEE MAKES NO REPRESENTATION. The recitals contained
herein shall be taken as the statements of the Issuer and the Trustee assumes
no responsibility for their correctness. The Trustee makes no representation
as to the validity or sufficiency of this First Supplemental Indenture.

        SECTION 4.04. COUNTERPARTS. The parties may sign any number of copies
of this First Supplemental Indenture. Each signed copy shall be an original,
but all of them together represent the same agreement.

        SECTION 4.05. EFFECT OF HEADINGS. The Section headings herein are for
convenience only and shall not affect the construction thereof.

        SECTION 4.06. TERMS. Certain capitalized terms used but not defined
herein have the meanings assigned to them in the Indenture.

        SECTION 4.07. ENTIRE AGREEMENT. This First Supplemental Indenture,
together with the Indenture as amended hereby and the Notes, contains the
entire agreement of the parties, and supersedes all other representations,
warranties, agreements and understandings between the parties, oral or
otherwise, with respect to the matters contained herein and therein.

        SECTION 4.08. BENEFITS OF FIRST SUPPLEMENTAL INDENTURE. Nothing in
this First Supplemental Indenture, the Indenture, or the Notes, express or
implied, shall give to any Person, other than the parties hereto and thereto
and their successors hereunder and thereunder, and the Holders, any benefit
of any legal or equitable right, remedy or claim under the Indenture, the
First Supplemental Indenture or the Notes.

        SECTION 4.09. NOTATION ON NOTES. Pursuant to Section 9.06 of the
Indenture, new Notes reflecting the amendments to the Indenture made hereby
shall not be issued; however, corresponding changes to the Notes to reflect
the amendments made hereby shall be deemed to be made to the Notes as of the
date of this First Supplemental Indenture. The Trustee may, but shall not be
required to, place an appropriate notation as to this First Supplemental
Indenture on any Note hereafter authenticated in accordance with Section 9.06
of the Indenture.

                                       7
<PAGE>

        IN WITNESS WHEREOF, the parties hereto have caused this First
Supplemental Indenture to be duly executed as of the date first above written.

                                       CAPROCK COMMUNICATIONS CORP.

                                       By_________________________________
                                       Name:   Jere W. Thompson, Jr.
                                       Title:  Chairman of the Board and
                                               Chief Executive Officer

                                       CHASE MANHATTAN TRUST COMPANY,
                                       NATIONAL ASSOCIATION,
                                       as Trustee

                                       By_________________________________
                                       Name:
                                       Title:

                                       8

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00016-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00016-of-00352.parquet"}]]