# A Software Architecture Teacher’s Dilemmas 111This is the reviewed version
of the paper submitted to International Conference on Software Architecture
(ICSA 2021)

Arvind W Kiwelekar
Department of Computer Engineering
Dr. Babasaheb Ambedkar Technological University
Lonere-Raigad India
<EMAIL_ADDRESS>
###### Abstract

An instructor teaching a course on Software Architecture needs to be more
reflective to engage students productively in the learning activities. In this
reflective essay, the author identifies a few decisive moments referred to as
instructional dilemmas at which a teacher reflects upon choices and their
consequences so that meaningful learning happens. These situations are
referred to as dilemmas because they offer two options to instructors. Some of
these dilemmas arise from the inherent nature of Software Architecture as a
discipline, while the source of others is the background knowledge of
learners. The paper suggests a set of principles and small-teaching methods to
make teaching and learning more effective in such situations.

Keywords: Instruction Design and Sequencing, Instructional Decisions, Software
Architecture Education, Soft skills for Software Architects.

##  1 Introduction

A course on Software Architecture is increasingly becoming an integral part of
the curriculum for the graduate programs in Software Engineering and Computer
Science. Many academic institutes are preferring a dedicated course on
Software Architecture over offering it as a one of the module in a course on
Software Engineering. This is because of the emphasis of architectural issues
in software development processes[1], and lack of sufficient coverage given to
architectural problems in a course on Software Engineering.

Such a dedicated course on Software Architecture is usually offered at the
senior undergraduate level (i.e. third or final year of a four years duration
program) or at the graduate level. While offering a course on Software
Architecture, it is ensured that students enrolled for the course have
completed prerequisite courses on Software Engineering, Programming Languages,
Databases, Operating Systems and Distributed Systems.

With this prerequisite knowledge, the students enrolled in the course need to
understand software design issues such as information storage, transaction
management, process concurrency, information presentation, application
security and deployment models. Students are aware of the principles of
programming-in-small [2, 3] such as data abstraction, information hiding,
code-reuse, and to some extent design reuse through Object-Oriented design
patterns.

With the experience of programming-in-small that too in only one programming
language (e.g., C/Java) students find it difficult to grasp the high-level
systemic issues (e.g., Viewpoints, Architectural Styles, Architectural
Decisions and their consequences) dealt in a course on Software Architecture.
These difficulties stem from two sources. First, students lack experience of
working on a large-sized project. The second source is the abstract nature of
Software Architecture [4]. As a result, students become passive learners, and
they start loosing interest in the course content.

Hence, to engage students more productively during class-room interaction and
as well as through off-class assignments, become a major goal of teaching. To
attain this instructional objective, a teacher needs to make the right
instructional decisions. This paper identifies a few such decisive moments
referred to as instructional dilemmas(Section III) which offers two choices to
a teacher about sequencing of the course content. The author of the paper has
experienced these situations while teaching courses on Software Architecture
to undergraduate and graduate students during the last five years and while
conducting teacher’s training programs.

The experiences described in the paper can be useful to the first-time
teachers of Software Architecture to design their instructions in a more
meaningful way. Also, the experienced teachers delivering the course can use
these experiences to set up controlled experiments for evaluating the
effectiveness of their individual choices. Besides, the paper provides a set
of guidelines (Section II) based on modern learning theories which can be
useful to deal with similar situations in either a course on Software
Architecture or any other Software Engineering courses.

Abstractions First |  Implementation First
---|---
Unit |  Topic |  Unit |  Topic
1 |  Requirement Analysis:Architectural Design and Requirements, Allocation |  1 |  Architecture Recovery Documenting Module Dependency View in SEI framework . UML Notations for Module View
2 |  Software Structure and Architecture: Architectural Structures and Viewpoints, Architectural Styles, design patterns, architecture design decisions. |  2 |  Technological Architectures Service Oriented Architecture, 3 tier Web Application Development (LAMP vas MEAN), Mobile Application Development, Blockchain Technology, Microservices
3 |  Technological Architectures Service Oriented Architecture, 3 tier Web Application Development (LAMP vas MEAN), Mobile Application Development, Blockchain Technology, Microservices |  3 |  Requirement Analysis:Architectural Design and Requirements Allocation
4 |  Architecture Evaluation: Quality Attributes, Quality Analysis and Evaluation Techniques, Measures |  4 |  Software Structure and Architecture: Architectural Structures and Viewpoints, Architectural Styles, design patterns, architecture design decisions.
5 |  Architecture Recovery and Description Documenting Module Dependency View in SEI framework . UML Notations for Module View |  5 |  Architecture Evaluation: Quality Attributes, Quality Analysis and Evaluation Techniques, Measures
Table 1: Two Different Course Sequencing Models

##  2 Guiding Principles

The guiding principles explained below help us to deal with the instructional
dilemmas, to define learning outcomes, and to adopt appropriate teaching
methods.

  1. 1.

Increase the level of students engagement.Increased students engagement is
typically used as the indicator of measuring learning progress and
effectiveness of course delivery. Designing purposeful learning activities and
instruction sequences are the common means through which student’s
participation can be enhanced [5].

  2. 2.

Engage students in the knowledge construction process. In the conventional
view, teaching is perceived as a process of knowledge dissemination in which
students passively absorb the knowledge. In contrast to this, the
constructivist approach perceives learning as a knowledge construction process
in which students develop insight about a topic through the active
participation in learning activities. Few educators have highlighted the
importance of the constructivist approach while teaching courses on Software
Engineering [6].

  3. 3.

Engage students in Project or Problem based Learning Working collaboratively
in a team is an essential soft-skill required for engineers in general and
software architects in particular. Educators suggest designing curriculum and
courses around a project or problem-based learning activities to train
students for collaborative working [7, 8].

  4. 4.

Teach concrete things before abstract things. The abstract or vague nature of
Software Architecture is the prime reason that makes teaching Software
Architecture difficult [4]. Also, education psychologists suggest that
teaching concrete things before abstract concepts improve student’s
comprehension of the subject matter [9].

  5. 5.

Adopt of modern technologies. Modern technologies such as web-based course
delivery platforms provide timely and effective media to disseminate course
content, engage students in discussions, conduct exit quizzes and seek feed-
backs. These technologies can be effectively adopted to address challenges
faced by teachers and students.

The principles mentioned above guide an instructor to devise appropriate
interventions to overcome the following instructional dilemmas.

##  3 Instructional Dilemmas

This section describes four kinds instructional dilemmas. These are: (i)
Architecture Modelling Dilemma, (ii) Definitional Dilemma, (iii) Architecture
Design Dilemma, and (iv) Implementation Dilemma.

We use a standard template to describe each dilemma. The template includes the
following elements.

  1. 1.

Context: This element describes the background and source of the dilemma .

  2. 2.

Alternatives: This element describes the two conflicting or competing
alternatives.

  3. 3.

Decision: This element describes the selected alternatives.

  4. 4.

Guiding Principles: The rationale behind the selected option is explained. The
explanation is based on one or more guiding principles presented in the
previous section.

  5. 5.

Teaching Method: A teaching method used to deal with the instructional dilemma
is described.

  6. 6.

Learning outcomes: The expected learning outcomes that will be attained by the
application of the teaching method described in this section.

The use of a standard template to document the instructional dilemmas is
inspired by the framework used to document architectural decisions [10].

###  3.1 Architecture Modelling Dilemma

####  3.1.1 Context

Software architects usually perform architecture modelling in two different
contexts, i.e. forward engineering and reverse engineering. During forward
engineering, architects specify a software solution satisfying the given
functional requirements and quality attributes. The specified architecture
acts as a blueprint for the downstream engineering activities such as low-
level design, system implementation, and testing. These kinds of architecture
models are referred to as prescriptive architectures. During reverse
engineering, architects recover high-level descriptions from the
implementation to support system maintenance and evolution activities. These
kinds of architecture models are referred to as descriptive architectures [11,
12].

####  3.1.2 Alternatives

Whether to begin the course with the descriptive or prescriptive architecture
can be the first dilemmatic situation. The conventional life-cycle model
prescribes that the course shall start with the topic of prescriptive
architecture. This sequence of instruction will follow the path in which the
first topic would be identifying architecturally significant requirements
followed by high-level system design and architecture evaluation. This
instructional sequencing referred to as abstractions first is shown in the
first column of Table 1. The second alternative is shown in the second column
of Table 1. With this sequence, the course begins with the topic of
architecture recovery followed by documenting the extracted architecture with
the module view from the SEI framework [13]. The sequencing in the second
column is referred to as implementation first approach.

####  3.1.3 Decision

We observe that starting the course with the descriptive architectures is a
better choice.

####  3.1.4 Guiding Principles

The following guiding principles justify the choice. (i) Teach concrete
concepts before abstract concepts. (ii) Use technology-based teaching methods
to flip the classroom activities.

####  3.1.5 Teaching Method

A course typically begins with handing over the code of an open-source
software application (e.g., DSpace [14], HealthWatcher [15]) to students and
asking them to document the system with UML notations such as class diagram.
Students will struggle to cope with the size of the program when they start
documenting such a large-sized application.

The teaching method is based on project-based learning and flipped classroom
with the following steps.

  1. i

An instructor shares a video explaining Module View from SEI Documentation
framework.

  2. ii

In the classroom or laboratory session, an instructor helps students to
identify dependency relationships among programming elements manually.

  3. iii

A group of 3 to 4 students are asked to prepare a report documenting the
module view for the assigned system.

####  3.1.6 Learning Outcomes

The students will realize the necessity of higher-level abstractions to gain
control over a large-sized application. The students will be able to document
a given application in module view.

###  3.2 Definitional Dilemma

####  3.2.1 Context

This dilemma arises from the definition of Software Architecture as a concept.
Two dominant views exist concerning the definition of Software Architecture.
The first and classical view suggests that Software Architecture refers to the
fundamental structure of a software system manifested through program elements
and relationships among them[16, 17]. This definition highlights architecting
as a decomposition process. Secondly, one of the most recent approaches
defines software architecture as a set of hard decisions made during the
initial stages of development that affect quality attributes or externally
visible properties. These decisions are usually referred to as architectural
decisions and difficult to change in the later stages of development—for
example, decisions concerning the choice of technological platforms or choice
of architecture style [10]. This definition highlights that software
architecture is a decision making process.

####  3.2.2 Alternatives

These two equally dominant views of Software Architecture provides two
alternatives to teach architecture documentation, i.e. whether to teach how to
document the decomposition of a system or to teach how to document
architectural decisions. The researchers have developed frameworks to document
both,i.e. architectural decisions [18], as well as, system decomposition [13].
Resolving upon what to document? becomes a crucial instructional decision once
it is decided to emphasize descriptive modelling.

####  3.2.3 Decision

We suggest that asking students to document a decomposition of a system is a
better choice over architectural decisions.

####  3.2.4 Guiding Principle

The choice of emphasizing the decomposition view is guided by following
observations. (i) Documenting the decomposition of a system is more concrete
activity as compared to documenting architectural decisions. This observation
holds, mostly when students are engaged in the architecture recovery process.
Because recovering architecture decisions is challenging when information
necessary to extract decisions is absent in the implementation artefacts, on
the other hand, information about dependencies among program elements is
present and visible in the implementation artefacts, thus simplifying the
extraction of high-level views. (ii) Instructors can easily design projects
and form teams to support project-based learning when students have to
document decomposition of a system.

####  3.2.5 Teaching Method

A combination of the flipped classroom and project-based learning method can
be adapted to emphasize the significance of the structural aspect of software
architecture. The teaching method includes following steps.

  1. i

The instructor shares a video explaining various concerns handled in software
design in general which includes concurrency, control, handling of events,
data persistence, distribution of components, error and exception handling,
interaction, presentation, and security.

  2. ii

In a lab session, the instructor explains how language-specific mechanisms
(e.g., Java) that deal with these concerns

  3. iii

Students are asked to look for the programming elements handling these
concerns in the application software assigned to them.

  4. iv

Further, students are asked to group the programming elements handling similar
concerns and to prepare a report.

####  3.2.6 Learning Outcomes

The students will realize that there exist multiple ways to group or decompose
a software system. Further, students will realize that there exist few
concerns which can not be cleanly grouped called cross-cutting concerns (e.g.,
Error handling, persistence). The students will be able to identify design
concerns in the system implementation and document them with a given template
or a UML profile.

###  3.3 Architecture Design Dilemma

The third kind of dilemma is concerned with the process of architecture
design. The design process includes two steps. The first stage aims to
identify Architecturally Significant Requirements (ASR) [19] from software
requirement specification or a problem statement. The second step maps
architecturally significant requirements to software architecture elements.

The Pattern-Oriented Software Architecture (POSA)[20] and the Attribute-Driven
Design (ADD) [21] are two commonly used approaches in architecture-centric
software development. The POSA approach suggests using a ready-made solution
to recurrently occurring design problem, which is catalogued as a pattern
(e.g., Model-View-Controller, Pipe-and-Filter). The ADD approach is a
recursive design method which, when applied, leads to a solution specific to a
quality attribute (e.g., Modifiability, Security).

####  3.3.1 Alternatives

The ADD and POSA are two approaches available for teaching architecture
design. The ADD as compared to POSA is more systematic and a planned method.
The architecture design is a process of solving a wicked problem; hence, both
approaches lead to multiple and different solutions. Moreover, knowing
architecture styles and patterns is a prerequisite to apply ADD for solving
design problems.

####  3.3.2 Decision

We observe that teaching architecture design with POSA approach followed by a
brief explanation of ADD is a better option.

####  3.3.3 Guiding Principle

The students of engineering programs are familiar to solving problems. As
architectural styles and patterns catalogue solutions to recurrent problems,
it will be easier to devise a teaching method around the POSA approach. An
instructor can frame a set of questions for a given design problem which can
lead to an architecture-style-based solution. Thus students get engaged in the
knowledge construction process as recommended by the constructivist theory of
learning.

####  3.3.4 Teaching Method

Software architecture design is a specialized skill set of the general-purpose
skill called design thinking. Though all engineering graduates are expected to
acquire design thinking, it has been observed that teaching and learning
design skill is hard. Various specialized pedagogy centred around project-
based learning have been devised, and educators have debated their
effectiveness [22]. We suggest adopting the following teaching method aimed at
increasing students engagement.

  1. i

The instructor hands over an architecture design problem from a domain to
which students are familiar with. For example, we used problems such as
student’s academic record management, room-allotment in student’s hostel,
travel-grant approval and disbursement.

  2. ii

The instructor explains a specific architecture style such as Model-View-
Controller (MVC), Pipe-Filter, Client-Server, Service-Oriented Architecture,
Micro-Service, Publisher-Subscribers.

  3. iii

The instructor asks questions that will lead to the identification of
Architecturally Significant Requirements.

  4. iv

The instructor forms multiple teams out of the students attending the class.

  5. v

The instructor asks a team to select an architectural style and to map the
ASRs to architectural elements from the chosen style (e.g., Publisher-
Subscriber)

  6. vi

The instructor displays each groups’ mappings on the board so that a solution
is visible to everyone.

  7. vii

Multiple design mappings will be displayed on the board. At which point, the
instructor asks the students to select the ’best’ mapping and justify their
selection.

  8. viii

At this point, the instructor introduces the concept of architecture
evaluation against quality attributes to the students.

####  3.3.5 Learning Outcomes

During the course delivery an instructor will observe following outcomes:

  1. 1.

Increased participation in architecture design activity.

  2. 2.

Students will understand the wicked nature of architecture design problem.

  3. 3.

Students will be able to apply various architecture styles.

  4. 4.

Students will be able to evaluate a given solution against a set of quality
attributes.

###  3.4 Implementation Dilemma

####  3.4.1 Context

The implementation dilemma is not an instructional dilemma in the sense as
described in the previous sections which affect the sequence of instructions.
But, this dilemma helps to describe an important topic missed in the course
content i.e. architectural decisions.

A software architect needs to select a particular technology platform to
implement the designed architectural solution. For example, a client/server
web application can be realized using either the Linux-Apache-MySQL-PHP (LAMP)
stack or the MongoDB-Express.js-Angular.js-Node.js (MEAN) stack. Similarly,
the Service-Oriented-Architecture (SOA) and Micro-services are two
technologies to implement component-oriented distributed applications. These
implementation dilemmas are best examples to explain the significance of
architectural decisions and documentation framework for architectural
decisions as defined in [10].

####  3.4.2 Alternatives

Technological platforms such as (i) LAMP vs MEAN (ii) SOA vs Micro-Services
(iii) Ethereum vs HyperLedger.

####  3.4.3 Decision

To explain architectural elements in various technological platforms at
conceptual level with an emphasis on quality attributes supported by them.

####  3.4.4 Guiding Principle

To adopt latest technologies to implement an architectural solution.

####  3.4.5 Teaching Method

The prescribed teaching method is a combination of classroom lectures and
project based learning. The method includes following instructional steps.

  1. i

The instructor explains the basic building blocks in the following
technological platforms (i) LAMP and MEAN (ii) SOA and Micro-Services (iii)
Hyperledger and Ethereum

  2. ii

The instructor asks student to select an appropriate technology to implement
the architectural solution for the problem used during architecture design
activity.

  3. iii

Further, the instructor asks student to document their decision using the
framework described in [10].

####  3.4.6 Learning Outcomes

The students will develop an insight about architectural decisions and they
will be able to document their rationale.

##  4 Earlier Work and Discussion

Teachers and educators from the disciplines other than Software Architecture
have identified teaching dilemmas concerning to their domains. For example,
teachers teaching Mathematics courses experience a conflict between teaching
symbolism and logic versus procedural aspects of problem-solving [23].
Further, in Reference [24], the author identifies a set of classroom-teaching
dilemmas for Mathematics teachers and asks them to weigh their classroom time
devoted to the activity. For example, Mathematics can be learnt either through
individual practice or by solving a problem in a team.

Another example of the teaching dilemma experienced by an English teacher is
described in [25], which reports the conflict between authoritarian teacher-
centric approach versus student-centric approach while teaching grammar and
writing.

In this paper, the author identifies a set of conflicting situations
experienced while teaching a course on Software Architecture to graduate,
undergraduate students and conducting teacher’s training program. Unlike
earlier approaches described above, the author goes beyond reporting conflicts
and tensions among teaching alternatives. In this paper, the author specifies
what it is called as small teaching methods [26] by James Lang. These small
teaching methods are derived from modern learning theories and applicable to
day-to-day classroom teaching.

Here, it needs to be noted that these are the dilemmas experienced by an
instructor and not to be confused with conflicting situations encountered by
the Software Developer (e.g., particularly implementation dilemma). These
conflicting situations need to be resolved, and their choice affects
instruction design and sequence and not the quality of software.

Further, an instructor may experience other kinds of dilemmas such as breadth
versus depth of a concerning topic. Hence, it is not a comprehensive catalogue
of teaching dilemmas for a course on Software Architecture.

##  5 Conclusion and Future Scope

Teaching design skills in general and Software Architecture, in particular,
has been recognized as a difficult task by many educators. Industrial
professionals have also found that software design as a skill is difficult to
transfer from an expert mentor to a novice trainee joined in the profession
because the design and architecting skills heavily make use of experiences
accrued over the period. However, the discipline of Software Architecture has
a rich and evolving knowledge base that codify these experiences in the form
of Architectural Styles, Design Patterns, design methods, and documentation
frameworks which when properly utilized can help instructors to design a
course instruction aimed to develop software design thinking.

This paper contributes by identifying some of the challenges faced by
instructors. These challenges are referred to as instructional dilemmas.
Further, the paper contributes by suggesting small-teaching methods specific
to a challenge or an instructional dilemma. These small-teaching methods are
based on the proven principles in modern learning theories. The author has
used these methods to overcome the passivity observed among students and
participants attending the teacher’s training programs.

Instructors can use the teaching methods and instructional dilemmas described
in the paper to design and plan instruction sequence. Also, the effectiveness
of these methods needs to be evaluated in terms of attainment of course
objectives.

## References

  * [1] S. Angelov and P. de Beer, “Designing and applying an approach to software architecting in agile projects in education,” _Journal of Systems and Software_ , vol. 127, pp. 78–90, 2017.
  * [2] M. E. Fayad, M. Laitinen, and R. P. Ward, “Thinking objectively: software engineering in the small,” _Communications of the ACM_ , vol. 43, no. 3, pp. 115–118, 2000.
  * [3] F. DeRemer and H. Kron, “Programming-in-the large versus programming-in-the-small,” _ACM Sigplan Notices_ , vol. 10, no. 6, pp. 114–121, 1975.
  * [4] M. Galster and S. Angelov, “What makes teaching software architecture difficult?” in _2016 IEEE/ACM 38th International Conference on Software Engineering Companion (ICSE-C)_. IEEE, 2016, pp. 356–359.
  * [5] R. d. A. Maurício, L. Veado, R. T. Moreira, E. Figueiredo, and H. Costa, “A systematic mapping study on game-related methods for software engineering education,” _Information and software technology_ , vol. 95, pp. 201–218, 2018.
  * [6] A. Cain and M. A. Babar, “Reflections on applying constructive alignment with formative feedback for teaching introductory programming and software architecture,” in _Proceedings of the 38th International Conference on Software Engineering Companion_ , 2016, pp. 336–345.
  * [7] P. Dolog, L. L. Thomsen, and B. Thomsen, “Assessing problem-based learning in a software engineering curriculum using bloom’s taxonomy and the ieee software engineering body of knowledge,” _ACM Transactions on Computing Education (TOCE)_ , vol. 16, no. 3, pp. 1–41, 2016.
  * [8] E. L. Ouh and Y. Irawan, “Applying case-based learning for a postgraduate software architecture course,” in _Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education_ , 2019, pp. 457–463.
  * [9] R. Moreno, G. Ozogul, and M. Reisslein, “Teaching with concrete and abstract visual representations: Effects on students’ problem solving, problem representations, and learning perceptions.” _Journal of educational psychology_ , vol. 103, no. 1, p. 32, 2011.
  * [10] J. TYREE and A. AKERMAN, “Architecture decisions: Demystifying architecture: Postmodern software design,” _IEEE software_ , vol. 22, no. 2, pp. 19–27, 2005.
  * [11] R. Heldal, P. Pelliccione, U. Eliasson, J. Lantz, J. Derehag, and J. Whittle, “Descriptive vs prescriptive models in industry,” in _Proceedings of the acm/ieee 19th international conference on model driven engineering languages and systems_ , 2016, pp. 216–226.
  * [12] U. Eliasson, R. Heldal, P. Pelliccione, and J. Lantz, “Architecting in the automotive domain: Descriptive vs prescriptive architecture,” in _2015 12th Working IEEE/IFIP Conference on Software Architecture_. IEEE, 2015, pp. 115–118.
  * [13] P. Clements, D. Garlan, R. Little, R. Nord, and J. Stafford, “Documenting software architectures: views and beyond,” in _25th International Conference on Software Engineering, 2003. Proceedings._ IEEE, 2003, pp. 740–741.
  * [14] M. Smith, M. Barton, M. Bass, M. Branschofsky, G. McClellan, D. Stuve, R. Tansley, and J. H. Walker, “Dspace: An open source dynamic digital repository,” 2003.
  * [15] M. Pinto, N. Gamez, and L. Fuentes, “Towards the architectural definition of the health watcher system with ao-adl,” in _Early Aspects at ICSE: Workshops in Aspect-Oriented Requirements Engineering and Architecture Design (EARLYASPECTS’07)_. IEEE, 2007, pp. 5–5.
  * [16] D. L. Parnas, “On the criteria to be used in decomposing systems into modules,” in _Pioneers and Their Contributions to Software Engineering_. Springer, 1972, pp. 479–498.
  * [17] D. Taibi and K. Systä, “From monolithic systems to microservices: A decomposition framework based on process mining.” in _CLOSER_ , 2019, pp. 153–164.
  * [18] U. Van Heesch, P. Avgeriou, and R. Hilliard, “A documentation framework for architecture decisions,” _Journal of Systems and Software_ , vol. 85, no. 4, pp. 795–820, 2012.
  * [19] L. Chen, M. A. Babar, and B. Nuseibeh, “Characterizing architecturally significant requirements,” _IEEE software_ , vol. 30, no. 2, pp. 38–45, 2012\.
  * [20] F. Buschmann, K. Henney, and D. C. Schmidt, _Pattern-oriented software architecture, on patterns and pattern languages_. John wiley & sons, 2007, vol. 5.
  * [21] F. Bachmann and L. Bass, “Introduction to the attribute driven design method,” in _Software Engineering, International Conference on_. Citeseer, 2001, pp. 0745–0745.
  * [22] C. L. Dym, A. M. Agogino, O. Eris, D. D. Frey, and L. J. Leifer, “Engineering design thinking, teaching, and learning,” _Journal of engineering education_ , vol. 94, no. 1, pp. 103–120, 2005.
  * [23] M. Kamaruddin _et al._ , “Dilemma in teaching mathematics.” _Online Submission_ , 2012.
  * [24] M. Swan, “Designing tasks that challenge values, beliefs and practices: A model for the professional development of practicing teachers,” in _Constructing knowledge for teaching secondary mathematics_. Springer, 2011, pp. 57–71.
  * [25] P. Smagorinsky, A. A. Wilson, and C. Moore, “Teaching grammar and writing: A beginning teacher’s dilemma,” _English Education_ , vol. 43, no. 3, pp. 262–292, 2011.
  * [26] J. M. Lang, _Small teaching: Everyday lessons from the science of learning_. John Wiley & Sons, 2016.


exposure to systemic risk, arguably the only notion of approximation of
interest to industry – a conceptual point so far overlooked in the literature.
We show that this problem is FIXP-complete. Secondly, we initiate the study of
the rational fragment of FIXP by studying the conditions under which rational
solutions for cds-clearing exist. Our results here are not conclusive in that
there is a gap between our necessary and sufficient conditions, the cycles
which involve both switched on and switched off nodes being not fully
understood. 131313We regard the _simplicity_ condition we made (i.e., about
off-cycle paths between cycle nodes) as a technicality, which is less
interesting and likely somewhat easier to deal with. We conjecture that for
any network with a weakly switched cycle there exist rational values for
assets and liabilities that lead to irrational solutions (Appendix C contains
one such example); however, our arguments and scheme cannot be easily
generalised to those instances. We leave providing a full characterisation as
an open problem.

There are further research directions that are suggested by our work. It would
be interesting to study whether Corollary 1’s connection between cds-clearing,
PPAD, and $\textsf{P}_{\mathbb{R}}$ (i.e. polynomial time under the Blum-Shub-
Smale model of computation [5]) holds more generally for the entire rational
subset of problems in FIXP. Furthermore, it is interesting to pursue finding
polynomial-time _constant_ approximation algorithms of clearing recovery rate
vectors: Also from an applied point of view, achieving a good approximation
factor here (say with an additive approximation term of $1/100$) might yield
solutions that are useful in most practical circumstances and could be
considered acceptable by financial institutions. We note here that a
$1/2$-strong approximation is easy to compute (a recovery rate vector of only
$1/2$s would indeed suffice).

## References

  * [1] Euro-parliament bans ’naked’ credit default swaps. EUBusiness.  https://www.eubusiness.com/news-eu/finance-economy-cds.dij.
  * [2] Lasting effects: The global economic recovery 10 years after the crisis. IMFBlogs.  https://blogs.imf.org/2018/10/03/lasting-effects-the-global-economic-recovery-10-years-after-the-crisis/.
  * [3] Daron Acemoglu, Asuman Ozdaglar, and Alireza Tahbaz-Salehi.  Systemic risk and stability in financial networks.  American Economic Review, 105(2):564–608, 2015.
  * [4] Nils Bertschinger, Martin Hoefer, and Daniel Schmand.  Strategic payments in financial networks.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 46:1–46:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [5] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale.  Complexity and real computation.  Springer Science & Business Media, 1998.
  * [6] Rodrigo Cifuentes, Gianluigi Ferrucci, and Hyun Song Shin.  Liquidity risk and contagion.  Journal of the European Economic association, 3(2-3):556–566, 2005\.
  * [7] Larry Eisenberg and Thomas H Noe.  Systemic risk in financial systems.  Management Science, 47(2):236–249, 2001.
  * [8] Matthew Elliott, Benjamin Golub, and Matthew O Jackson.  Financial networks and contagion.  American Economic Review, 104(10):3115–53, 2014.
  * [9] Kousha Etessami and Mihalis Yannakakis.  On the complexity of nash equilibria and other fixed points.  SIAM Journal on Computing, 39(6):2531–2597, 2010.
  * [10] Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças.  On the complexity of equilibrium computation in first-price auctions.  arXiv preprint arXiv:2103.03238, 2021.
  * [11] Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, and Alexandros Hollender.  Fixp-membership via convex optimization: Games, cakes, and markets.  arXiv preprint arXiv:2111.06878, 2021.
  * [12] Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod.  Settling the complexity of leontief and PLC exchange markets under exact and approximate equilibria.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 890–901. ACM, 2017.
  * [13] Paul Glasserman and H Peyton Young.  How likely is contagion in financial networks?  Journal of Banking & Finance, 50:383–399, 2015.
  * [14] Paul W Goldberg and Alexandros Hollender.  The hairy ball problem is ppad-complete.  Journal of Computer and System Sciences, 2021.
  * [15] Sebastian Heise and Reimer Kühn.  Derivatives and credit contagion in interconnected networks.  The European Physical Journal B, 85(4):1–19, 2012.
  * [16] Brett Hemenway and Sanjeev Khanna.  Sensitivity and computational complexity in financial networks.  Algorithmic Finance, 5(3-4):95–110, 2016.
  * [17] Daning Hu, J Leon Zhao, Zhimin Hua, and Michael CS Wong.  Network-based modeling and analysis of systemic risk in banking systems.  MIS quarterly, pages 1269–1291, 2012.
  * [18] Jon Kleinberg and Eva Tardos.  Algorithm design.  Pearson Education India, 2006.
  * [19] Christos H. Papadimitriou.  Computational complexity.  Addison-Wesley, 1994.
  * [20] Christos H. Papadimitriou.  On the complexity of the parity argument and other inefficient proofs of existence.  Journal of Computer and System Sciences, 48(3):498–532, 1994.
  * [21] Pál András Papp and Roger Wattenhofer.  Default ambiguity: finding the best solution to the clearing problem.  arXiv preprint arXiv:2002.07741, 2020.
  * [22] Pál András Papp and Roger Wattenhofer.  Network-aware strategies in financial systems.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 91:1–91:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [23] Leonard CG Rogers and Luitgard AM Veraart.  Failure and rescue in an interbank network.  Management Science, 59(4):882–898, 2013.
  * [24] Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston.  Clearing payments in financial networks with credit default swaps.  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 759–759, 2016.
  * [25] Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston.  Finding clearing payments in financial networks with credit default swaps is PPAD-complete.  LIPIcs: Leibniz International Proceedings in Informatics, 67, 2017\.

##  Appendix A Weak Fixed Points versus Exact Fixed Points

######  Example 4.

$1$1$2$$3$11/2$4$1$5$$6$$4\epsilon$1 Figure 8: Financial system of Example 4

Consider the financial system depicted in Figure 8. Assume that $e_{1}=1$,
$e_{2}=0$, $e_{4}=1$, $e_{5}=0$. Also $c_{1,2}^{5}=c_{4,5}^{2}=1$,
$c_{2,3}=1/2$, $c_{5,6}=4\epsilon$, for a tiny $\epsilon>0$.

Take the point $r=(1,1,1,1,0,1)$. Obviously, $f_{1}(r)=f_{4}(r)=1$, and
$f_{2}(r)=\min\\{1,(1-r_{5})/(1/2)\\}=1$,
$f_{5}(r)=\min\\{1,(1-r_{2})(4\epsilon)\\}=0$. Since $r=f(r)$, the point
$r=(1,1,1,1,0,1)$ is an exact fixed point.

Assume $r^{\prime}=(1,1-2\epsilon,1,1,1/2+\epsilon,1)$. It holds that
$f_{2}(r^{\prime})=\min\\{1,(1-r^{\prime}_{5})/(1/2)\\}=\min\\{1,(1/2-\epsilon)/(1/2)\\}=1-2\epsilon$.
Moreover,
$f_{5}(r^{\prime})=\min\\{1,(1-r^{\prime}_{2})/4\epsilon\\}=\min\\{1,(1-1+2\epsilon)/4\epsilon\\}=1/2$.
Thus, $\|r^{\prime}-f(r^{\prime})\|_{\infty}\leq\epsilon$ which constitutes
$r^{\prime}=(1,1-2\epsilon,1,1,1/2+\epsilon,1)$ a weakly
$\epsilon$-approximate fixed point.

When comparing $r^{\prime}$ to $r$ though, we observe that the distance from
the exact fixed point is
$\|(1,1,1,1,0,1)-(1,1-2\epsilon,1,1,1/2+\epsilon,1)\|_{\infty}>1/2$, proving
the claim that weakly $\epsilon$-approximate fixed points may potentially be
very far from exact fixed points. On top of that, the information we get on
node 2 in $r^{\prime}$ is that $r^{\prime}_{2}=1-2\epsilon<1$, meaning that 2
is in default whereas actually 2 can fully pay its liabilities since
$r_{2}=1$. This indicates that a weakly $\epsilon$-approximate fixed point may
contain misleading information about whether a bank is in default or not, thus
making such approximations unreliable while motivating the study of strong
approximations.

##  Appendix B Financial System Gadgets Used in the Proof of Theorem 3

In this section we present our gadgets, in Figures 9–13. For simplicity, (some
of) our gadgets lead to degenerate instances; we deal with this in the next
subsection.

$r$$1$$r$11$2$1$3$1$5$$c$$6$$c\cdot r$1$4$1$c$ Figure 9: Gadget
$g_{\text{dup}}$: This gadget outputs two values: $r$ and $cr$, where
$c\in[0,1]$ is a rational constant. Choosing $c=1$ yields a duplication gadget
that takes the input recovery rate $r$ and outputs $r$ as the two recovery
rates of the output nodes. We may also denote this gadget by $g_{c\cdot r}$,
for $c\in[0,1]$ in case this gadget is used to multiply the input by a
constant $c$.
$r_{2}$$1$$2$11$3$$4$$5$111$r_{1}$$6$$7$$8$111$9$$10$$11$111$12$$13$$\frac{r_{1}}{r_{2}}$111
Figure 10: Division gadget $g_{/}$. Note that this gadget does not satisfy
non-degeneracy. We present it for the sake of keeping the exposition simple,
but it is not formally used in the reduction of Theorem 3, as this reduction
should result in a non-degenerate financial system. In Appendix B.1, we show
that it is possible to change the basis and avoid using this gadget
altogether. $r_{1}$$1$$2$11$3$$4$$5$111$6$$7$$8$$r_{1}\cdot r_{2}$111$r_{2}$11
Figure 11: Multiplication gadget $g_{*}$. Note that this gadget does not
satisfy non-degeneracy. We present it for the sake of keeping the exposition
simple, but it is not formally used in the reduction of Theorem 3, as this
reduction should result in a non-degenerate financial system. A more complex
version of the gadget that is non-degenerate (i.e., the “true” version of the
gadget) is given in Figure 14 in Appendix B.1.
$r_{1}$$1$$2$11$3$$5$11$r_{2}$$7$$8$111$9$$\max\\{0,r_{1}-r_{2}\\}$11 Figure
12: Positive subtraction gadget $g_{\text{pos}-}$. Generates the value
$\max\\{0,r_{1}-r_{2}\\}$ from the input recovery rates $r_{1}$ and $r_{2}$.
$13$$14$$15$11$16$$17$11$18$$19$$20$111$21$$22$11$23$$24$$25$11$26$$27$1$28$$29$$30$111$31$$32$11$\lvert
r_{1}-r_{2}\rvert$11$r_{1}$$1$$2$$3$$4$$5$$6$1111$r_{2}$$7$$8$$9$$10$$11$$12$111111111111
Figure 13: Absolute difference gadget $g_{\text{abs}}$: The recovery rate of
the output node is $\lvert r_{1}-r_{2}\rvert$, where $r_{1}$ and $r_{2}$ are
the recovery rates of the input nodes. The gadget is formed by first applying
$g_{\text{dup}}$ on both its inputs. The positive difference gadget
$g_{\text{pos}-}$ is then used on the two pairs of inputs to compute
$\max\\{r_{1}-r_{2},0\\}$ and $\max\\{r_{2}-r_{1},0\\}$, after which these two
maxima are added together using $g^{+}$, resulting in the desired output
$|r_{1}-r_{2}|$.

###  B.1 Non-degenerate Multiplication and Division Gadgets

This section describes how to adapt the hardness reduction of Theorem 3 in
such a way that the financial system is non-degenerate. This is a rather
technical detail and needs substantial work, yet it is needed for correctness
of the reduction.

First, we present a non-degenerate version of our multiplication gadget in
Figure 14. In this gadget, the input recovery rates $r_{1}$ and $r_{2}$ are
pre-processed by multiplying them both by $1/2$, using our constant
multiplication gadget $g_{cr}$. The gadget then generates the recovery rate
$(r_{1}(1+r_{2}))/4\in[0,1]$, which can be post-processed using a positive
subtraction gadget $g_{\text{pos}-}$ and a multiplication gadget $g_{*}$ to
obtain $r_{1}\cdot r_{2}$.

It is much more difficult to replace the degenerate gadget $g_{/}$. To do
this, we will essentially get rid of division gates altogether in
$C_{I}^{\prime}$, and replace each of them by a set of alternative operations
that achieve the same result. We thus make a few modifications to
$C_{I}^{\prime}$. The first modification is that we alter the sub-circuit $T$,
which was used to generate the value $t=1/2^{2^{d}}$, which was used to scale
all the signals in the circuit so that each signal is in $[0,1]$ irrespective
of the input vector. Here, $d$ is a polynomial time computable value that
satisfies that every signal in the original circuit $C_{I}$ is at most
$2^{2^{d}}$. We adapt $T$ such that the scaling factor it outputs is
$1/(2^{1+{2^{d}}})$ instead of $1/2^{2^{d}}$. This can be done by adding one
additional multiplication gate at the end of $T$. Let the output of the
modified $T$ be $t^{\prime}=t/2$. After this modification, it holds that all
signals inside the circuit are in $[0,1/2]$.

We now observe that division gates are used in a very limited way in
$C_{I}^{\prime}$ (with $T$ modified as above).

  * •

First, division is used for dividing by $c$, where $c$ is a given explicit
constant in the original circuit $C_{I}$. For such divisions, we can simply
use our constant multiplication gadget $g_{cr}$ to multiply by $1/c$, which is
equivalent to dividing by $c$.

  * •

Secondly, division is used to divide certain outputs of gates by $t^{\prime}$
(previously $t$), where $t^{\prime}=1/2^{1+2^{d}}$. This type of division
happens in two cases.

    1. 1.

At every point in the circuit where two scaled signals $t^{\prime}a$ and
$t^{\prime}b$ with $a,b\leq 2^{2^{d}}$ are multiplied with each other,
resulting in the value $t^{\prime}t^{\prime}ab$. This value is divided by
$t^{\prime}$ in order to generate the signal $t^{\prime}ab$, i.e., a scaled
version of the signal $ab$ in the original circuit.

    2. 2.

At the end of the circuit, where a scaled signal $t^{\prime}a$ is divided by
$t^{\prime}$ to produce an output signal of the original circuit, which is in
$[0,1]$.

In the first case, let $x=t^{\prime}ab$ and in the second case, let $x=a$, so
that in both cases a number $t^{\prime}x$ is divided by $t^{\prime}$ to result
in $x$, and in both cases it holds that $x\in[0,1]$. We replace the division
$t^{\prime}x/t^{\prime}$ by a sequence of $d$ gates that compute the square
root of its input, followed by a multiplication by $2$, followed by a sequence
of $d$ successive squaring multiplication gates, followed by a final
multiplication by $2$. This results in the correct value

$((t^{\prime}x)^{1/2^{d}}\cdot 2)^{2^{d}}\cdot 2=(t^{\prime
1/2^{d}}x^{1/2^{d}}\cdot 2)^{2^{d}}\cdot 2=t^{\prime}x\cdot 2^{2^{d}}\cdot
2=\frac{1}{2}x\cdot 2=x.$

It is furthermore straightforward to verify that, due to the order in which we
apply our arithmetic operations, all of the values throughout this computation
stay in the interval $[0,1]$. We note that the adapted scaling factor
$t^{\prime}=t/2$ is needed because of the multiplication by $2$ that is
executed after the successive square roots and before the successive squaring.

The resulting circuit has no division gates anymore, so we do not need a
division gadget in our reduction. Instead, now we need a square root gadget.
Fortunately, it is possible to design this gadget in a non-degenerate way,
although its construction is not very straightforward. It is presented in
Figure 17, and it combines the two subgadgets given in Figures 15 and 16 which
we provide separately for ease of understanding. The square root gadget may
evidently output an irrational recovery rate, which is caused by the cyclic
dependencies of the CDSes and debt contracts in the system.

$r_{1}/2$$1$$2$11$g_{r_{1}/2}$$3$$4$$5$111$6$1/2$7$$8$$\frac{r_{1}(1+r_{2})}{4}$111$r_{2}/2$11$g_{r_{2}/2}$
Figure 14: Non-degenerate multiplication gadget $g_{*}^{\prime}$.
$r$$1$$3$$2$11$4$$1-r$111 Figure 15: Inversion gadget $g_{\text{inv}}$,
computing $1-r$ from $r$.
$3$$2$$1$$4$111$9$$5$$6$$7$111$8$1$10$1$11$$\sqrt{c}$11$1-c$$1-c$ Figure 16:
This gadget has no input nodes. It outputs the square root of a constant
$c\in[0,1]$, where $1-c$ is provided as the external assets of two banks in
the gadget.
$r$$1$1$2$1$3$1$5$1$6$$7$11$8$1$9$1$12$$11$$10$$13$1111$18$$14$$15$$16$111$17$1$19$1$\sqrt{r}$1$4$11
Figure 17: Square root gadget $g_{\sqrt{\cdot}}$, obtained by combining the
duplication gadget $g_{\text{dup}}$, the inversion gadget $g_{\text{inv}}$,
and the gadget of Figure 16.

##  Appendix C Irrational Solutions for Weakly Switched Cycles

Consider the instance in Figure 18. This is an instance containing a weakly
switched cycle that admits irrational solutions. Firstly the instance contains
a red cycle which is $C=(1,2,3,R)$. Notice that $C$ contains one node that is
switched on (which is Node 1) and one switched off node (Node 3). Thus, by
definition, $C$ is weakly switched. Next we prove that through the
coefficients shown in the figure, the instance has a unique irrational
solution.

For Node 1, it holds that $r_{1}=\frac{1}{3-r_{R}}$. Node 2 has a recovery
equal to $r_{2}=\frac{1-r_{R}}{3-r_{R}}$. Since node 3 has $e_{3}=1$ and a
liability of at most 1, its recovery rate is equal to 1, so $r_{3}=1$. Now
node $R$ has incoming payment from node 3
$a_{R}=1-r_{2}=1-(1-r_{R})/(3-r_{R})=2/(3-r_{R})$ and a liability of $2$, so
its recovery rate is $r_{R}=1/(3-r_{R})$. To compute the recovery rate of $R$
we must therefore solve the equation $r^{2}_{R}-3r_{R}+1=0$, whose solution is
$r_{R}=\frac{3-\sqrt{5}}{2}$.

$R$$1$$2$$3$$4$221111 Figure 18: Example of an instance with a weakly (but not
strongly) switched cycle having only irrational solutions.

##  Appendix D Further Financial System Gadgets

The gadgets presented in this section illustrate that financial systems are
able to naturally capture the $\max$ and $\min$ operations. However, these
gadgets remain unused in the reduction of Theorem 3.

$r_{1}$$2$$3$$4$1$5$$6$$1$$r_{2}$$8$$9$$x$ Figure 19: This is an alternative
multiplication gadget where all contract notionals are assumed to be 1. This
multiplication gadget was provided to us by an anonymous reviewer in the first
draft of our paper. The gadget is non-degenerate, and is somewhat simpler than
our non-degenerate multiplication gadget, at the trade-off of including a
cycle in the gadget. We thank the reviewer for this contribution.
$r_{1}$$r_{2}$$g_{\text{dup}}$$g_{\text{dup}}$11$r_{1}$$r_{1}$$r_{2}$$r_{2}$1111$g_{\text{abs}}$11$g_{(1/2)r}$1$g_{(1/2)r}$$g_{(1/2)r}$11$\frac{r_{1}}{2}$$\frac{r_{2}}{2}$11$\frac{\lvert
r_{1}-r_{2}\rvert}{2}$1$g_{+}$11$\frac{\lvert
r_{1}-r_{2}\rvert+r_{2}}{2}$11$g_{+}$11$\max\\{r_{1},r_{2}\\}$1 Figure 20:
Maximum gadget $g_{\max}$, computing $\max\\{r_{1},r_{2}\\}$. This is a
compact representation where the nodes labeled with a subscripted $g$ have to
be replaced by copies of the respective gadgets, in order to obtain the full
financial system defining the gadget.
$r_{1}$$r_{2}$$g_{\text{dup}}$$g_{\text{dup}}$11$r_{1}$$r_{1}$$r_{2}$$r_{2}$1111$g_{\text{abs}}$11$g_{(1/2)r}$1$g_{(1/2)r}$$g_{(1/2)r}$11$\frac{\lvert
r_{1}-r_{2}\rvert}{2}$1$\frac{r_{1}}{2}$$\frac{r_{2}}{2}$11$g_{+}$11$\frac{r_{1}+r_{2}}{2}$1$\max\\{0,r_{1}-r_{2}\\}$11$\min\\{r_{1},r_{2}\\}$1
Figure 21: Minimum gadget $g_{\min}$, computing $\min\\{r_{1},r_{2}\\}$. This
is a compact representation where the nodes labeled with a subscripted $g$
have to be replaced by copies of the respective gadgets, in order to obtain
the full financial system defining the gadget.